操作系统【二】

3、进程控制

状态的切换实质上是通过修改 PCB 的信息、让 PCB 出队或者入队来实现的,但是是谁来控制这个过程呢?—— 答案就是进程控制,进程控制指的是对系统中所有进程,从创建到终止的全过程实行的管理和控制。

进程控制是进程管理中最基本的功能,一般由操作系统的内核中的原语来实现。

(1)操作系统内核

现代操作系统一般将OS划分为若干层次,再将OS的不同功能分别设置在不同的层次中。通常将一些与硬件紧密相关的模块、各种常用设备的驱动程序以及运行频率较高的模块,都安排在紧靠硬件的软件层次中,将它们常驻内存,即通常被称为OS的内核。

处理机的执行状态分为两种:

  • 系统态:又称为管态,或内核态。具有较高的特权,能执行一切指令,访问所有寄存器和存储区,传统的OS都在系统态运行。
  • 用户态:又称为目态。具有较低特权的执行状态,仅能执行规定的指令,访问指定的寄存器和存储区。

一般应用程序只能在用户态运行,不能去执行OS指令及访问OS区域,这样可以防止应用程序对OS的破坏。

原语(Primitive)操作:由若干条指令组成的,用于完成一定功能的一个过程,是原子操作:即一个操作中的所有动作,要么不做,要么全做,在执行过程中不允许被中断,原子操作在系统态下执行,常驻内存。

(2)进程的创建

  • 在OS中,允许一个进程创建另一个进程
  • 父进程,子进程,进程的层次结构
    • 在OS 中 允许一个进程创建另一个进程创建子进程的进程为父进程,由此形成进程树,树根为进程家族的祖先(UNIX)。
    • Windows中不存在任何进程层次结构的概念,所有进程都具有相同的地位,进程之间的关系不再是层次关系,而是获得句柄与否,控制与被控制的简单关系。
  • 子进程可以继承父进程所拥有的资源,进程不能拒绝其子进程的继承权
  • 撤销父进程时,必须同时撤销其所有的子进程
  • 为了标识进程之间的家族关系,在PCB中设置了家族关系表项,以标明自己的父进程及所有的子进程

(2)进程的终止

  • 正常结束
  • 异常结束(处决)
    • 越界错误:访问超出进程区域
    • 保护错:试图访问不允许访问的资源或文件
    • 非法指令:试图执行一条不存在的指令
    • 特权指令错:试图执行一条只允许OS执行的特权指令
    • 运行超时:执行时间超出了规定时间的最大值
    • 等待超时:等待时间超出了规定时间的最大值
    • 算术运算错:试图执行被禁止的运算,比如除0运算I/O故障:I/O过程错误
  • 外界干预(他杀)
    • 进程应外界的请求而终止运行。
    • 操作员或操作系统干预,例如发生死锁等
    • 父进程请求
    • 父进程终止

(3)进程的阻塞与唤醒

引起进程阻塞的事件

  • 请求系统服务
  • 启动某种操作
  • 新数据尚未到达
  • 无新工作可做

正在执行的进程发生上述情况时,无法继续执行,于是通过调用阻塞原语block( )把自己阻塞。 将PCB中的状态由“执行”改为“阻塞”,并加入到阻塞队列中;转进程调度进行重新调度,将处理机分配给另一就绪进程,并进行切换,保留被阻塞进程的处理机状态(在PCB中),再按新进程的PCB中的处理机状态设置CPU的环境。

进程的阻塞是一种主动行为

唤醒原语wakeup( )的执行:把阻塞进程从等待该事件的阻塞队列中移出,将其PCB中的现行状态改为就绪,将PCB插入到就绪队列中。

Block阻塞原语与唤醒原语wakeup作用相反,成对使用

一个处于阻塞状态的进程不能自己唤醒自己。

唤醒一个进程有两种方法:

  • 1、由系统进程唤醒
  • 2、由事件发生进程唤醒

当由系统进程唤醒等待进程时,系统进程统一控制事件的发生,并将“事件发生”这一消息通知等待进程,从而使得该进程因等待事件已发生而进入就绪队列。

等待进程由事件发生进程唤醒时,事件发生进程和被唤醒进程之间是合作关系。因此,唤醒原语既可以被系统进程调用,也可以被事件发生进程调用。

我们称调用唤醒原语的进程为唤醒进程

(4)进程的挂起与激活

当出现引起进程挂起的事件时,系统利用挂起原语suspend( )将指定进程或处于阻塞的进程挂起

  • 挂起原语的执行:检查被挂起进程的状态,若处于活动就绪,则改为静止就绪,若处于活动阻塞,则改为静止阻塞,将该进程PCB复制到内存指定区域,若挂起的进程正在执行,则重新进行进程调度。

当发生激活进程的事件时,系统利用激活原语active( )将指定进程激活。

  • 激活原语先将进程从外存调入内存,检查该进程的状态,若处于静止就绪,则改为活动就绪,若处于静止阻塞,则改为活动阻塞。
  • 若采用抢占调度策略,则新进程进入就绪队列时,检查是否要重新进行进程调度。

4、进程同步

(1)基础概念

进程同步的主要任务:使并发执行的诸进程之间能有效地共享资源和相互合作,从而使程序的执行具有可再现性。(因为各个进程以各自独立的、不可预知的速度向前推进。执行过程会发生一些例如读后写等问题所以,我们要通过进程同步来解决此类问题。)

两种形式的制约关系

  • (1)间接相互制约关系(互斥关系):源于资源共享(无意识安排的)
  • (2)直接相互制约关系(同步关系):源于进程合作(进程间的相互联系是有意识安排的)

些资源在一个时间段内只允许一个进程使用,诸如各种物理设备、变量、数据、内存缓冲区等,这些称之为临界资源

许多硬件资源或者共享变量都属于临界资源,多个进程可以共享,但是必须采用互斥方式。我们把并发进程中与共享变量有关的程序段称为临界区

如果能保证一个进程在临界区执行时,不让另一个进程进入相关的临界区执行即各进程对共享变量的访问是互斥的,那么就不会造成错误

为了实现临界资源的互斥访问,可以在逻辑上将一个进程对临界资源的访问过程分为四个部分:

1
2
3
4
5
6
do {
extry section; // 进入区
critical section; // 临界区
exit section; // 退出区
remainder section; // 剩余区
} while(true)
  • 进入区:A 进程想要访问临界资源,首先会在进入区检查是否可以进入,由于此时没有其它进程占用临界资源,所以检查通过,同时它设置了一个 Flag 标志当前自己正在访问临界资源;
  • 临界区:实际访问临界资源的那段代码
  • 退出区:负责解除之前的 Flag
  • 剩余区:其它处理

对于 B 进程,如果此时它也想要访问这个资源,同样就会在进入区做一个检查它知道了 A 进程正在访问,所以自己就不能访问了。这样就实现了资源访问的互斥。

对若干个并发进程共享某一变量的相关临界区的管理有三个要求

  • (1)一次最多一个进程能够进入临界区。当有进程在临界区执行时,其他想进入临界区执行的进程必须等待:
  • (2)不能让一个进程无限制地在临界区执行,即任何一个进入临界区的进程必须在有限的时间内退出临界区;
  • (3)不能强迫一个进程无限制地等待进入它的临界区,即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区执行。

由此产生了四个原则:

  • 空闲让进:当无进程处于临界区时,表明临界资源处于空闲状态, 应允许一个请求进入临界区的进程立即进入自己的临界区
  • 忙则等待:当已有进程进入自己的临界区时,表明该临界资源正被访问,因而其它所有试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。
  • 有限等待:对要求访问临界资源的进程,应保证该进程能在有限时间内进入自己的临界区,以免陷入“死等”状态,即不得使进程在临界区无休止地等待。
  • 让权等待:当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”。

(2)硬件同步机制

操作系统学习笔记-4:进程同步与进程互斥(一)

利用特殊的硬件指令解决临界区管理问题

①中断屏蔽方法

关中断:进程在临界区执行期间,计算机系统不响应中断,从而不会引发调度,不会发生进程调度,进而不会发生进程切换,保证了对锁的测试和关锁操作的连续性和完整性,因而有效地保证了互斥。

缺点

(1)滥用关中断权利可能造成严重后果;

(2)关中断时间过长,影响系统效率;

(3)关中断方法不适合多处理器系统。

②Test-and-Set指令

TestAndSetLock /TestAndSet 指令也叫 TSL/TS 指令。双标志方法的根本问题出在”上锁“和”检查“是非原子操作,导致某个进程可以利用这两个操作的空隙,而 TSL 指令将两个操作变成了原子操作(一气呵成,不留空隙),同时它也做到了像中断屏蔽指令那样,一旦进入临界区,执行过程就无法被中断。

虽然这是硬件操作,不过我们暂且用伪代码来进行理解:

1
2
3
4
5
6
7
8
9
10
11
bool TestAndSet (bool *lock){
bool old;
old = *lock;
*lock = true;
return old;
}
P0: P1:
while (TestAndSet(&lock)); while (TestAndSet(&lock));
critical section; critical section;
lock = false; lock = false;
remainder section; remainder section;

其中,lock 是全局变量,记录当前临界区是否”上锁“。

首先,进程 P0 想要访问临界区,那么就会来到 while 循环,在这个循环里,它一气呵成完成了”上锁“和”检查“的工作 —— 循环里执行了 TSL 函数,一方面将全局 lock 改为 true,一方面返回旧的值为 false 的 lock 给自己。所以,对自己来说,由于返回的是 false,它得以跳过循环进入临界区;而对 P1 进程来说,每次切换到它这里,它在 while 里企图”上锁“和”检查“的时候,都会由于之前全局 lock 已经被置 true 而陷入死循环。

因此,整个过程就保证了 P0 的”上锁“和”检查“是一气呵成的原子操作,同时也让 P0 执行时绝对不会被切换。在 P0 执行完之后,全局 lock 再次置 false,以此类推。

TSL 指令的方法实现简单,无需严格检查逻辑,也适用于多处理机环境,但是它仍然不满足”让权等待“的原则 —— 从伪代码可以看出,P1 在无法如愿进入临界区后仍然可能白白地占用处理机,导致”忙等“。

③Wrap 指令

Swap 指令或称 Exchange / XCHG 指令,它的逻辑其实和 TSL 指令差不多:

1
2
3
4
5
6
7
P0:                             P1:
bool old = true; bool old = true;
while (old == true) while (old == true)
Swap(&lock,&old) ; Swap(&lock,&old) ;
critical section; critical section;
lock = false; lock = false;
remainder section; remainder section;

一开始全局 lock 还是 false,P0 想要进入临界区,首先置 old 为 true,后面用 Swap 完成交换,所以得以跳出循环进入临界区;而对于 P1 进程,由于它共享全局 lock,全局 lock = 自身 old = true,所以陷入了死循环,无法进入临界区。

和 TSL 指令一样,Swap 指令也无法解决“让权等待”的问题。

(3)信号量(Semaphore)机制(锁)

Dijkstra发明的信号量机制是通过PV操作能够实现对临界区的管理要求。

在荷兰文中,通过叫passeren,释放叫vrijgeven,PV操作因此得名。

PV操作是由两个操作——P操作和V操作组成,为原语。P操作和V操作也可称为P操作原语和V操作原语,简称PV操作。

P操作Wait(S):检查信号量S是否小于等于0,若是则把调用Wait(S)的进程置成等待状态,否则将S减去1V操作

signal(S):将信号量加1

①整型信号量

信号量如果单纯是一个整数型的变量,那么就称为整型信号量,它的值记录了系统中某种资源的数量。在使用整型信号量的情况下,P 、V 操作是类似这样的:

1
2
3
4
5
6
7
8
9
10
int S = 1;
wait(int S)
{
while(S <= 0) /*do no-op*/
S = S-1
}
signal(int S)
{
S = S+1
}

同样以进程 P0,P1 为例进行说明:

1
2
3
4
P0:                    P1:
wait(S) wait(S) // 进入区
critical section critical section // 临界区
signal(S) signal(S) // 退出区

假定 P0 想要进入临界区,那么它就会在进入区申请资源:执行 P 操作,进行“检查”和“上锁”,由于 S 一开始是1(表示目前有一个资源可以使用),所以 P0 可以跳过循环,成功申请到资源。此后,S 减一变为 0,代表已经没有可用资源了 —— 这一步也相当于上锁;对于 P1,当他想要申请资源的时候,同样先来到进入区执行 P 操作,由于 S = 0,所以此时 P1 陷入了死循环;再回到 P0 ,他完成任务后会在退出区释放资源,S加一变为 1,这时候 P1 才有机会退出循环,进而申请资源。

整个过程其实和之前介绍的方法是很类似的,但是由于这次,“检查”和“上锁”两个操作被封装在一个原语里,所以这两个操作必定是一气呵成、无法被打断的,这就避免了某个进程钻空子的现象。但是同时我们也发现,在 P0 时间片用完后,P1 仍然会占用处理机进行没有意义的死循环,也就是仍然违背了“让权等待”的原则

于是在此基础上,又出现了记录型信号量

②记录型信号量

与整型信号量仅用一个单一变量记录可用资源数不同,记录型信号量的数据结构类似于一个结构体,它不仅记录了可用资源数 value,而且还提供了一个等待队列 L

记录型信号量的思想其实是,如果由于 P0 在使用临界资源而导致 P1 暂时无法使用,那么干脆就不给 P1 陷入循环的机会,直接让它自己去阻塞队列这样 P1 在被唤醒之前,永远无法占用处理机,也自然就不可能出现白白占用处理机的情况。而在 P0 释放资源后,我们才来考虑唤醒 P1。

记录型信号量的结构如下所示:

1
2
3
4
typedef  struct{
int value;
struct PCB * list ;
} Semaphore;

同时,记录型信号量的 P、V 操作也有所不同,如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
  wait(Semaphore *S)
{
S->value=S.value-1;
if (S->value<0)
block(S-> list)
}

signal(Semaphore *S)
{
S->value++;
if (S->value<=0)
wakeup (s-> list)
}
  • 这里要注意的第一个地方是,value 是可用的资源数,当它大于 0 的时候自然是存在可用资源(供大于求),当它小于 0 的时候,则说明不仅无可用资源而且有其他进程等着用(供不应求)。
  • 第二个地方是,在进入区 value 一定会减一,表示申请到了资源,或者表示存在着某个进程有想要申请资源的意愿

下面我们用例子来说明记录型信号量工作的过程,为了加深记忆,这里用四个进程来说明:

1
2
3
4
PO:            P1              P2           P3
wait(S) wait(S) wait(S) wait(S)
临界区 临界区 临界区 临界区
signal(S) signal(S) signal(S) signal(S)

假设计算机中有两台可用的打印机 A 和 B(也就是说,value = 2),有四个进程需要用到打印机资源。

一开始假定是 P0 先占有处理机,那么 P0 就会在进入区申请资源 。由于 value 一开始是 2,所以 P0 成功申请到资源 A,之后 value 数量减一变为 1,同时来到临界区开始“干活”;在 P0 的时间片完了之后,P1 占有处理机,此时同样申请到资源 B,value 由 1 变为 0,之后来到临界区“干活”。自此,两个打印机都被占用了。

在 P1 的时间片完了之后,P2 占有处理机,value 由 0 变为 -1 < 0,前面我们说过,value < 0 说明无可用资源,所以此时 P2 将自己主动送到了阻塞队列。接着来到了 P3,value 由 -1 变为 -2,P3 同样进入阻塞队列。P2,P3 都从运行态转为阻塞态。

处理机又来到 P0,P0 很快执行完了,于是在退出区执行 P 操作释放资源,将 value 加一变为 -1,之后由于通过 if 检测到阻塞队列中有进程等着用资源,所以马上唤醒了队头的 P2 ,P2 从阻塞态回到就绪态,并直接进入临界区开始自己的工作,在完成后同样来到退出区释放资源,value 由 -1 变为 0,但是在 if 中还是检测到了队列中仍然有进程等着用资源,于是马上把队头的 P3 唤醒,P3 回到就绪态,并直接进入临界区开始工作,此后,value 由 0 变为 1,此时 if 不通过,说明队列中再也没有其它进程等着了,该拿到资源的进程都拿到了。自此,P0,P2,P3 都拿到了 A 资源,而 P1 也在不久后完成工作,在退出区释放资源 B,此时 value 从 1 变回最初的 2 ,代表占用的资源已经全数归还。

PS:当然,实际情况还可能是,P2 拿到了 A 资源,P3 拿到了 B 资源,但分析过程也是大同小异的。

显然,记录型信号量与前面介绍的所有方法最大的区别就在于,不会再有进程白白占用处理机进行没有意义的循环 —— 相反地,这些进程非常“老实”地把自己送到了阻塞队列,选择在那里慢慢地等待,等待其它进程完成后将自己唤醒,这种做法“既方便了别人,也方便了自己”。这就正好与我们多次强调的”让权等待“非常契合了。

记录型信号量明显优于整型信号量,所以在提到 PV 操作的时候,一般默认指的都是记录型信号量。

  • 若用PV操作来管理进程互斥地进入临界区,则只要用一个信号量 ,该信号量的初值定为1
  • 任何一个进程,当要进入临界区时,先要调用P操作,以确定要进入临界区还是等待进入。
-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~