计算机操作系统-进程管理培训讲义(编辑修改稿)

计算机操作系统-进程管理培训讲义(编辑修改稿)内容摘要：

wait(Emutex)。 wait(Dmutex)。 若进程 A和 B按下述次序交替执行 wait process A: wait(Dmutex)。 于是 Dmutex=0 process B: wait(Emutex)。 于是 Emutex=0 process A: wait(Emutex)。 于是 Emutex=1 A process B: wait(Dmutex)。 于是 Dmutex=1 B阻塞 AND同步机制的基本思想是：将进程在整个运行过程中需要的所有资源 ， 一次性全部地分配给进程 ， 待进程使用完后再一起释放。 只要尚有一个资源未能分配给进程 ，其它所有可能为之分配的资源 ， 也不分配给他。 亦即 ， 对若干个临界资源的分配 ， 采取原子操作方式：要么全部分配到进程 ， 要么一个也不分配。 由死锁理论可知 ， 这样就可避免上述死锁情况的发生。 为此 ， 在 wait操作中 ， 增加了一个 “ AND”条件 ， 故称为 AND同步 ， 或称为同时 wait操作 ， 即 Swait(Simultaneous wait)定义如下： Swait(S1, S2, …, Sn) if Si≥1 and … and Sn≥1 then for i ∶ = 1 to n do Si ∶ = Si1。 endfor else place the process in the waiting queue associated with the first Si found with Si＜ 1, and set the program count of this process to the beginning of Swait operation endif Ssignal(S 1, S 2, …, S n) for i∶ = 1 to n do Si=Si+1。 Remove all the process waiting in the queue associated with Si into the ready queue. endfor。 4. 信号量集 Swait(S1, t1, d1, …, Sn, tn, dn) if Si≥t1 and … and Sn≥tn then for i∶ =1 to n do Si∶ =Sidi。 endfor else Place the executing process in the waiting queue of the first Si with Si＜ ti and set its program counter to the beginning of the Swait Operation. endif signal(S1, d1, …, Sn, dn) for i ∶ =1 to n do Si ∶ = Si+di。 Remove all the process waiting in the queue associated with Si into the ready queue endfor。 一般 “ 信号量集 ” (1) Swait(S, d, d)。 此时在信号量集中只有一个信号量 S， 但允许它每次申请 d个资源 ， 当现有资源数少于 d时 ， 不予分配。 (2) Swait(S, 1, 1)。 此时的信号量集已蜕化为一般的记录型信号量 (S＞ 1时 )或互斥信号量 (S=1时 )。 (3) Swait(S, 1, 0)。 这是一种很特殊且很有用的信号量操作。 当 S≥1时 ， 允许多个进程进入某特定区；当 S变为 0后 ，将阻止任何进程进入特定区。 换言之 ， 它相当于一个可控开关。 信号量的应用 1. 利用信号量实现进程互斥 Var mutex:semaphore ∶ = 1。 begin parbegin process 1: begin repeat wait(mutex)。 critical section signal(mutex)。 remainder seetion until false。 end process 2: begin repeat wait(mutex)。 critical section signal(mutex)。 remainder section until false。 end parend 利用信号量实现前趋关系 图 210 前趋图举例 S4S5S3S1S6S2 Var a,b,c,d,e,f,g。 semaphore ∶ = 0,0,0,0,0,0,0。 begin parbegin begin S1。 signal(a)。 signal(b)。 end。 begin wait(a)。 S2。 signal(c)。 signal(d)。 end。 begin wait(b)。 S3。 signal(e)。 end。 begin wait(c)。 S4。 signal(f)。 end。 begin wait(d)。 S5。 signal(g)。 end。 begin wait(e)。 wait(f)。 wait(g)。 S6。 end。 parend end 4 经典进程的同步问题 生产者 — 前面我们已经对生产者 —消费者问题 (The proceducerconsumer problem)做了一些描述 ， 但未考虑进程的互斥与同步问题 ， 因而造成了数据 Counter的不定性。 由于生产者 —消费者问题是相互合作的进程关系的一种抽象 ， 例如 ， 在输入时 ， 输入进程是生产者 ， 计算进程是消费者；而在输出时 ， 则计算进程是生产者 ， 而打印进程是消费者 ， 因此 ， 该问题有很大的代表性及实用价值。 1. 利用记录型信号量解决生产者 —消费者问题 假定在生产者和消费者之间的公用缓冲池中 ， 具有 n个缓冲区 ， 这时可利用互斥信号量 mutex实现诸进程对缓冲池的互斥使用；利用信号量 empty和 full分别表示缓冲池中空缓冲区和满缓冲区的数量。 又假定这些生产者和消费者相互等效 ， 只要缓冲池未满 ， 生产者便可将消息送入缓冲池；只要缓冲池未空 ， 消费者便可从缓冲池中取走一个消息。 对生产者 — 消费者问题可描述如下： Var mutex, empty, full:semaphore ∶ = 1,n,0。 buffer:array［ 0, …, n1］ of item。 in, out: integer ∶ = 0, 0。 begin parbegin proceducer:begin repeat … producer an item nextp。 … wait(empty)。 wait(mutex)。 buffer(in) ∶ = nextp。 in ∶ = (in+1) mod n。 signal(mutex)。 signal(full)。 until false。 end consumer:begin repeat wait(full)。 wait(mutex)。 nextc ∶ = buffer(out)。 out ∶ = (out+1) mod n。 signal(mutex)。 signal(empty)。 consumer the item in nextc。 until false。 end parend end 在生产者 —消费者问题中应注意：首先 ， 在每个程序中用于实现互斥的 wait(mutex)和 signal(mutex)必须成对地出现； 其次 ， 对资源信号量 empty和 full的 wait和 signal操作 ， 同样需要成对地出现 ， 但它们分别处于不同的程序中。 例如 ， wait(empty)在计算进程中 ， 而 signal(empty)则在打印进程中 ， 计算进程若因执行 wait(empty)而阻塞 ， 则以后将由打印进程将它唤醒；最后 ， 在每个程序中的多个 wait操作顺序不能颠倒。 应先执行对资源信号量的wait操作 ， 然后再执行对互斥信号量的 wait操作 ， 否则可能引起进程死锁。 利用 AND信号量解决生产者 — 消费者问题 ar mutex, empty, full:semaphore ∶ = 1, n, 0。 buffer:array［ 0, …, n1］ of item。 in out:integer ∶ = 0, 0。 begin parbegin producer:begin repeat … produce an item in nextp。 … Swait(empty, mutex)。 buffer(in) ∶ = nextp。 in ∶ = (in+1)mod n。 Ssignal(mutex, full)。 until false。 end consumer:begin repeat Swait(full, mutex)。 nextc ∶ = buffer(out)。 out ∶ = (out+1) mod n。 Ssignal(mutex, empty)。 consumer the item in nextc。 until false。 end parend end 哲学家进餐问题 1. 经分析可知 ， 放在桌子上的筷子是临界资源 ， 在一段时间内只允许一位哲学家使用。 为了实现对筷子的互斥使用 ，可以用一个信号量表示一只筷子 ， 由这五个信号量构成信号量数组。 Var chopstick: array［ 0, …, 4］ of semaphore。 所有信号量均被初始化为 1， 第 i位哲学家的活动可描述为： repeat wait(chopstick［ i］ )。 wait(chopstick［ (i+1) mod 5］ )。 … eat。 … signal(chopstick［ i］ )。 signal(chopstick［ (i+1) mod 5］ )。 … think。