第二章进程及作业管理

第二章进程及作业管理内容摘要：

,count A:LD count,R1 B:INC R1 B:LD count,R1 count经 A、 B访问后，只加了 1，而不是所希望的 2。 为了防止发生这种与时间有关的错误，变量 count必须按临界资源处理。 第二章 进程及作业管理 系统的同步机构对解决临界区互斥问题应遵循下述准则： (1)当无一进程处于临界区内时，若有一进程要求进入临界区，应让其立即进入 (2)当已有进程在临界区内时，其他欲进入临界区的进程必须等待 (3)当无一进程处于临界区，而同时有多个进程要求进入临界区，且仅让其中之一进入，其他则等待 (4)任一进程进入临界区的要求应在有限时间满足 有限等 (5)处于等待进入临界区的进程应放弃占用 CPU让权等待。 第二章 进程及作业管理 同步机构 1．测试与设置 (Test and Set) 这是一种借助一条硬件指令 Test and Set(简记 TS)来实现互斥的同步机构。 许多计算机中都提供了这种指令，在 IBM 370中称 TS指令，在 Z 8000中称 TSET指令，在 Intel 8086/8088中称 XCHG指令。 TS指令的功能可用 PASCAL语言描述如下： 第二章 进程及作业管理 procedure TS(vara,b:boolean)。 var temp:boolean。 begin temp:=a。 a:=b。 b:=temp end function TS(var b:boolean):boolean。 begin TS:=b。 b:=true end v 第二章 进程及作业管理 TS指令的执行是不可分割的，利用 TS指令可以简单而有效地实现互斥。 其方法是为每个临界资源设置一个布尔变量 lock(锁 )，其初值为 falsc，当 lock值为 false表示锁打开，临界资源未被使用，进程可进入临界区；反之则表示锁关闭，进程不能进入。 于是用 TS指令实现互斥的进程的程序结构为： 第二章 进程及作业管理 var key: blooean。 begin … key:=true。 while key do TS(lock,key)。 （１ ′ CS (临界区 ) lock:=false。 … end begin … while TS (lock) do skip。 CS。 （２ ′ lock:=false。 … end 第二章 进程及作业管理 2．信号量和 P、 V操作 荷兰的著名计算机科学家 Dijkstra把互斥的关键含义抽象成信号量 (semaphore)概念，并引入在信号量上的 P、 V操作作为同步原语 (P和 V分别是荷兰文的“等待”和“发信号”两词的首字母 )。 信号量是个被保护的量，只有 P、 V操作和信号量初始化操作才能访问和改变它的值， Dijkstra把信号量 s定义为一个非负整型量。 把信号量 s上的 P操作 P(s)定义为：若 s0，则 s值减 1，否则执行进程等待，直到其他进程对 s进行 V操作。 把信号量 s上的 V操作 V(s)定义为： s值加 1，若有进程在 s上等待，则唤醒其中一个进程。 第二章 进程及作业管理 信号量和 P、 V操作原语可构成“阻塞 唤醒”同步机构：当一个进程对值为 0的信号量执行 P操作时便被阻塞以等待某个事件的出现；在另一进程检测到该事件发生时，通过执行 V操作唤醒被阻塞的进程。 在实现该同步机构时，可采取“忙等待”方式也可采取“让权等待”方式。 在忙等待方式下，被阻塞进程在不主动放弃处理机的情况下忙碌等待着其他进程来唤醒它，显然这不利于处理机的有效利用。 让权等待方式，即当执行进程必须在某信号量上等待时，就将该进程变为等待状态，并将其插入与此信号量相关的等待队列中，以让出处理机给其他就绪进程。 在单机系统中普遍采用让权等待方式。 而在多机系统中，为减少进程状态变换而引起的开销，可采取忙等待方式。 另外，在具体实现时通常要对 Dijkstra的原定义进行改进。 第二章 进程及作业管理 (1)忙等待方式的 P、 V vars: integer。 P(s) :while s≤ 0 do skip。 s:=s1 V(s) :s:=s+1。 当一进程在值不大于 0的信号量 s上执行 P操作时，将在循环语句 while上陷入忙等待，直到其他进程在该信号量 s上执行 V操作后，解除它的等待。 不难看出这种形式的 P、 V操作完全可用硬件指令来实现。 第二章 进程及作业管理 (2)让权等待方式的 P、 V操作。 采取这种方式需要对原信号量定义进一步扩充，把信号量由整型量扩充成为记录形式： type psem=semaphore semaphore=record value: integer。 qucue: pointer to WQ。 end 即信号量 s是二元组 s(v,q) , v是信号量 s的值，它是个整型量， q是指向 s等待队列 WQ的队首指针。 于是 P、 V操作可分别描述为： 第二章 进程及作业管理 procedure p ( s )。 var s: psem。 begin :=。 if 0 then block() end procedure V ( s )。 var s:psem。 begin :=+1 if ≤0 then wakeup() end 第二章 进程及作业管理 根据上述定义， P、 V操作的物理意义可这样来看待。 0表示某类资源的当前可用数。 每执行一次 P操作意味着请求分配一个单位的资源，因此描述为 :=。 ≤0表示该类资源已不能供分配，因此请求资源的进程将被阻塞在等待队列 ，此时 程数。 执行一次 V操作意味着释放一个单位资源，故描述为 .v:=+1，若 ≤0，表示在等待队列 源不能满足而被阻塞的进程，因此唤醒等待队列 一个或优先数最高的进程，允许其使用该资源。 第二章 进程及作业管理 1．临界区的互斥 利用信号量可方便地实现临界区的互斥执行。 此时信号量是公用信号量，它的初值为 1，每个进程均可对它施行 P、 V操作。 设 mutex为互斥信号量，其初值为 1，表示对应的临界资源 R未被占用。 对于每个想使用 R的进程，只需把它们的临界区 CS置于 P(mutex)和 V(mutex)之间，即可实现互斥。 下面给出这种模型的大致描述： 第二章 进程及作业管理 var mutex: psem。 procedure processl begin while true do begin … p(mutex)。 CS1。 V(mutex)。 … end end。 第二章 进程及作业管理 pr。