操作系统进程、线程、调度

MOKE 2019-05-13 PM 18℃ 0条

进程

程序就是一个指令序列,在早起的计算机只支持单道程序,还没有进程的概念;而引入多道程序技术后,为了程序的并发执行,从而引入了进程、进程实体的概念。


进程与进程实体*

进程实体的在组成:

  • PCB:进程控制块,描述了进程的基本信息和运行状态,是进程存在的唯一标志;所谓的创建和撤销进程都是指对PCB的操作。
  • 程序段:程序的代码。
  • 数据段:程序运行时产生的运算数据,包括全局变量、局部变量等。

PCB包含:进程标识符(PID)、处理机状态、进程调度信息、进程控制信息。
1

进程和进程实体
进程是进程实体的运行过程,是系统进行资源分配的基本单位。
进程实体是静态的,进程是动态的。


进程的组织方式和特征

组织方式
进程的组织,即对多个 PCB 的组织,分为两种方式:

  • 链接方式:按照进程状态将 PCB 分为多个队列(就绪队列、阻塞队列...),操作系统对每个队列进行操作。
  • 索引方式:根据进程状态的不同,建立多张索引表,操作系统对每张索引表进行操作。

特征

  • 动态性:进程是程序的一次执行过程
  • 并发性:内存中有多个进程实体,个进程并发执行
  • 独立性:进程是能够独立运行,独立获得资源的基本单位
  • 异步性:在没有同步机制的情况下,各进程独立的以不可知的速度向前推进
  • 结构性:即进程的组成结构

进程状态*

进程的状态/生命周期
进程有五个状态(不包含挂起),前三个为基本状态:

  • 运行态: 占有 CPU,并正在执行
  • 就绪态: 已经具备执行条件,等待被 CPU 调度
  • 阻塞态: 因某一事件(系统调用)而等待不能执行,等待资源
  • 创建态:进程正在被创建,分配空间初始化 PCB
  • 终止态:进程正从系统中撤销,系统回收进程拥有的资源
    2

进程控制
进程控制就是要实现进程的状态转换。
进程控制通过原语实现。

原语:内核态下具有特定功能的指令序列,具有原子性

相关的原语:进程的创建、进程的终止、进程的阻塞、进程的唤醒、进程的切换。

fork() 、vfork()
fork 和 vfork 是 linux下的系统调用指令,是用来操作进程的指令。

  • fork()
    创建一个进程(调用fork的进程就是父进程,生成的是子进程)。

注:linux初始有两个进程,进程0(交换进程) ,进程1(进程0的子线程,是我们创建的其他所有进程的祖先)

  • vfork()
    fork创建的子进程的地址空间和父进程是分开的(除了共享代码段,其他都数据段复制),父子进程是两个独立的进程,拥有的优先级相同。

而 vfork 创建的子进程与父进程共用相同的地址空间,子进程对这些共享资源所做的修改,可以影响到父进程。


线程

线程概念
线程是独立调度的基本单位。
注:传统进程机制 CPU 调度的是进程,而引入线程后,进程就只作为资源分配的基本单位了。

一个进程中可以有多个线程,它们共享进程资源。

QQ 和浏览器是两个进程,浏览器进程里面有很多线程,例如 HTTP 请求线程、事件响应线程、渲染线程等等,线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时,浏览器还可以响应用户的其它事件。

与进程的区别/带来的变换:

  • 拥有资源
    线程不拥有资源,但可以访问隶属进程的资源。
  • 并发性
    原本只能进程间并发,引入线程后,各线程间也能并发,提高了并发度。
  • 系统开销
    线程是独立调度的基本单位,在同一进程中,线程的切换不会引起进程切换。

用户级线程和内核级线程
线程的实现可以分为两类:用户级线程和内核线线程。在多线程操作系统中,各个系统的实现方式并不相同,在有的系统中实现了用户级线程,有的系统中实现了内核级线程。它们的特点和区别:

  • 内核级线程是依赖于内核的,它存在于用户进程和系统进程中,它们的创建,撤消和切换都由内核实现;
  • 用户级线程仅存在于用户级中,它们的创建,撤消和切换不利用系统调用来实现,因而与内核无关,内核并不知道用户级线程的存在
  • 有了内核线程,每个用户线程被映射或绑定到一个内核线程(一对一、一对多、多对多)
  • 在只有用户级线程的系统内,CPU调度还是以进程为单位,由用户程序控制线程的轮换运行;在有内核支持线程的系统内,CPU调度则以线程为单位,由OS的线程调度程序负责线程的调度。
    3图片来自网络

线程通信和进程通信*

线程通信: 地址

进程通信

  • 消息传递: 直接通信、间接通信。
    原语:Send/Rececive

直接通信:消息直接挂到接受进程的消息缓冲队列上。
间接通信:消息要先发送到中间实体。

  • 管道: 就是在内存中开辟一个用于读写的固定大小的缓冲区。
    特点:半双工(某时段单向)、只能用于父子进程。
  • 命名管道: 是一个用于读写的文件,去除了管道只能在父子进程中使用的限制。
  • 消息队列: 提供一个独立于进程 的队列。
    相比 FIFO 的优点:

1.避免了 FIFO 的同步阻塞,进程不需要提供同步方法。
2.进程可以有选择的接受消息,而不像 FIFO 默认接受。

  • 信号量: 一个计数器,用于为多个进程提供对共享数据对象的访问(同步)。
  • 共享内存: 允许多个进程共享一个给定的存储区。因为数据不需要在进程之间复制,所以这是最快的一种 IPC。需要使用信号量。
  • 套接字: 用于不同机器间的进程通信。

处理机调度

处理机调度:从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行。

调度级别

首先介绍下进程的挂起状态
引入虚拟存储技术后,系统会将暂时不能运行的进程调到外存等待,在外存等待的进程状态被称为挂起状态(PCB依然在内存)。

三个调度级别:

  • 高级调度: 即作业调度,是外存和内存之间 的调度;按一定的原则从外存上处于后备队列的作业中挑选若干个作业,为它们分配资源建立 PCB。
  • 中级调度 即内存调度,选择一个处于挂起状态的进程重新调入内存。
  • 低级调度 即进程调度,从就绪队列中选取一个进程,将处理机分配给它。
    进程调度是操作系统中最基本的一种调度。

两种进程调度的方式:

  • 抢占式: 如果有一个更紧急的进程需要使用处理机,系统则会立即暂停正在执行的进程,将处理机分配给更紧急的进程。
  • 非抢占式: 只允许进程主动放弃处理机,处理机才会被分配给其他进程。

调度算法*

不同阶段的系统采用的调度算法是不同的。

1. 批处理系统

先来先服务: FCFS,非抢占式
按照到达的先后顺序调度,也就是等待时间越久的越优先得到服务。

优缺点:

  • 公平、算法实现简单,不会产生饥饿(某进程长期得不到服务)
  • 对长作业有利、对短作业不利

短作业优先: SJF,非抢占式
每次调度时选择当前已到达且运行时间最短的进程。

优缺点:

  • 相比先来先服务算法平均等待时间更短
  • 对短作业有利,对长作业不利,不公平会产生饥饿

最短剩余时间优先: SRTN,抢占式
短作业的一种,按照剩余时间最短的顺序进行调度。优缺点同短作业优先算法。

高响应比优先: HRRN,非抢占式
调度时计算所有在就绪队列中进程的响应比((等待时间+服务时间)/服务时间),选择响应比最高的进程分配处理机。

优缺点:结合先来先服务和短作业的优缺点的一种折中算法。

2. 交互式系统
时间片轮转
轮流让就绪队列中的队头的进程依次执行一个时间片,之后两种情况:

  • 时间片没完而进程执行完毕,则会主动放弃处理机
  • 时间片用完而进程未执行完毕,则会停止执行并将该线程送完就绪队列的队尾

时间片轮转算法的效率和时间片的大小有很大关系:

  • 如果时间片太大,使得每个进程都可以在一个时间片内完成,则会退化成先来先服务算法
  • 如果时间片太小,那么进程切换就会很频繁,系统会花大量时间来处理进程切换。

优先级调度
优先处理优先级最高的进程,分两种:

  • 非抢占式:选择当前已到达且优先级最高的进程
  • 抢占式:会检查就绪队列中有没有优先级最高的进程(包括执行中的)

为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级(动态优先级)。

多级反馈队列
是时间片轮转算法和优先级算法的结合。
结构:
设置多级就绪队列,各级队列优先级从高到底,时间片从小到大
4
流程:

  • 新进程到达时先进入第1级队列,FCFC排队并分配时间片
  • 若用完时间片进程未执行接受,则进入下一级队列队尾
  • 若处于最下级的队列则会重新放回该队列队尾
  • 只有前一级的队列为空时,才会为当前队列队头的进程分配时间片
标签: OS

非特殊说明,本博所有文章均为博主原创。

评论啦~