【操作系统】进程的调度、僵尸进程/孤儿进程/守护进程

1. 进程的状态

1.1. 基本状态

进程的基本状态:“就绪”、“执行”、“阻塞”。

  • 就绪:进程已获得除处理机以外的所需资源,等待分配处理机资源
  • 执行:进程正在占用处理机资源执行
  • 阻塞:进程等待某种条件,在条件满足之前无法执行。如发起了 I/O 系统调用,会被阻塞,等待 I/O 中断发生

1.2. 挂起

“挂起”是指将暂不执行的进程换出到外存,节省内存空间。

“挂起”和“阻塞”都是进程暂停执行的状态,但是这是两个维度的概念:

  • 阻塞表示进程正在等待一个事件的发生,阻塞状态下收到收到信号会切换为就绪状态
  • 挂起表示进程被换出到外存,挂起状态下被激活时会被载入到内存,切换为非挂起状态

综上所属,挂起状态的进程按照是否阻塞可以分为:

  • 挂起就绪状态:进程在外存中,但是只要被载入内存就可以执行
  • 挂起阻塞状态:进程在外存中并等待一个事件,即使被载入内存(激活)也无法运行
1.jpg
进程的五状态图,包含“挂起”

1.3. 睡眠

Linux 将进程的阻塞状态进一步细分为:暂停、浅睡眠、深睡眠。其中,若不需要等待资源,则切换为“暂停”;若需要等待资源,切换为“睡眠”;如果睡眠状态能被信号唤醒,则是“浅睡眠”,否则是“深睡眠”。

2.jpg
Linux 的进程状态图

2. 调度算法

2.1. 调度算法的分类

  • 按照 CPU 的分配方式:非抢占式、抢占式
  • 按照系统的分时方式:在批处理系统,交互系统或实时系统下的调度

2.2. 饥饿问题

某个进程无限等待,无法被调度。

2.3. 批处理系统的调度算法

调度算法的目标:

  • 吞吐量(每小时最大作业数):系统每小时完成的作业数,要尽可能多
  • 周转时间(每作业最小时间):一个作业从提交到完成时的统计平均时间
  • CPU 利用率(CPU 始终忙碌):由于没有交互,CPU 不会出现等待输入的情况,因此 CPU 利用率要高

2.3.1. 先来先服务(First Come First Serverd,FCFS)

  • 按照请求 CPU 的顺序使用 CPU,非抢占式
  • 优点是易于理解,便于实现,只需一个就绪队列
  • 缺点是对短作业不公平;对 I/O 密集型进程不利,长时间等待设备;响应时间不确定

2.3.2. 最短作业优先(Shortest Job First,SJF)

  • 预知作业的运行时间,选择最短时间的优先运行
  • 优点是提高平均周转时间
  • 缺点是对长作业不公平;可能导致饥饿问题

2.3.3. 最短剩余时间优先(Shortest Remaining Time Next,SRTN)

  • 最短作业优先的抢占式版本,如果新作业比正在执行的作业剩余时间短,则它优先执行
  • 缺点是对长作业不公平;可能导致饥饿问题。同“最短作业优先”

2.3.4. 最高响应比优先算法(Highest Response Ratio Next,HRRN)

  • 响应比的定义:作业等待时间/作业运行所需时间
  • 哪个进程的响应比大,哪个进程优先
  • 由响应比的定义可以知道,作业运行所需时间越小、作业等待时间越长,响应比越大
  • 优点:同时考虑了等待时间和执行时间,既优先考虑短作业,也防止长作业无限等待的饥饿

2.4. 交互系统(分时系统)的调度算法

调度算法的目标:

  • 响应时间:要快速响应交互请求
  • CPU 的运行分为若干个时间片,能够处理不同的运算请求,使每个用户都能共享主机资源

2.4.1. 时间片轮转(Round Robin,RR)

  • 将所有就绪进程排成一个队列,按照时间片轮流调度,用完实践篇的进程排到队列末尾,属于抢占式
  • 优点:没有饥饿问题
  • 问题:若时间片小,进程切换频繁,吞吐量低;若时间片长,则响应时间过长,实时性得不到保证

2.4.2. 优先级调度算法(Priority)

  • 优先级高的进程先运行,同优先级的进程轮转。当高优先级队列中没有进程后,再调度下一级队列
  • 缺点是可能导致低优先级进程饿死

引入 动态设定优先级 的思想:在优先级高的进程运行一个时间片后,降低其优先级,防止其一直占用 CPU,饿死优先级低的进程。结合这个思想,可设计出“多级反馈队列”。

2.4.3. 多级反馈队列(Multilevel Feedback Queue,MFQ)

  • 优先级高的队列先执行; 优先级越高,时间片越短 ;如果一个进程在当前队列规定的时间片内无法执行完毕,则移动到下一个队列的队尾
  • 缺点:也有可能出现饥饿问题,比如不断有新的更高优先级的进程加入

2.4.4. 彩票法

  • 向进程提供各种系统资源的彩票。调度时随机抽取彩票,拥有该彩票的进程得到资源
  • 可给重要的进程更多的彩票;协作进程可以交换彩票

2.4.5. 公平分享法

  • 每用户 分配一定比例的 CPU 时间,而不是按照进程
  • 各用户之间按照比例挑选进程

2.5. 实时系统的调度算法

调度算法的目标:满足任务的截止时间。也就是说,如果有一个任务需要执行,实时操作系统会马上执行该任务,不会有较长的延时。

2.5.1. 最早截止时间优先算法

先把截止时间早的任务给完成,否则这个任务如果在截止时间后才完成,就没有意义了。

3. 僵尸进程、孤儿进程、守护进程

3.1. 僵尸进程

当一个进程由于某种原因终止时,内核并不是立即把它从系统中清除。进程会保持在一种“已终止”的状态中,直到被它的父进程回收。当父进程回收已终止的子进程时,内核会抛弃已终止的进程,此时该进程就不存在了。

僵尸进程是指 终止但还未被回收 的进程。如果子进程退出,而父进程并没有调用 wait()waitpid() 来回收,那么就会产生僵尸进程。僵尸进程是一个已经死亡的进程,但是其进程描述符仍然保存在系统的进程表中。

危害:占用进程号,系统所能使用的进程号是有限的,可能导致不能产生新的进程;占用一定的内存。

如何避免产生僵尸进程:

  • 父进程调用 wait 或者 waitpid 等待子进程结束
  • 子进程结束时,内核会发生 SIGCHLD 信号给父进程。父进程可以注册一个信号处理函数,在该函数中调用 waitpid ,等待所有结束的子进程;也可以用 signal(SIGCLD, SIG_IGN) 忽略 SIGCHLD 信号,那么子进程结束后,内核会进行回收
  • 杀死父进程,僵尸进程就会变成孤儿进程,由 Init 进程接管并处理

《CSAPP》8.5.5 节提供了一个示例程序,在父进程中通过 SIGCHLD 信号处理程序回收所有子进程。

3.2. 孤儿进程

如果某个进程的父进程先结束了,那么它的子进程会成为孤儿进程每个进程结束的时候,系统都会扫描是否存在子进程,如果有则用 Init 进程(pid = 1)接管,并由 Init 进程调用 wait 等待其结束,完成状态收集工作。孤儿进程不会对系统造成危害。

3.3. 守护进程

守护进程(英语:daemon,英语发音:/ˈdiːmən/或英语发音:/ˈdeɪmən/)是一种 在后台执行 的电脑程序。此类程序会被以进程的形式初始化。