操作系统计算题总结.docVIP

应用类型知识要点一：进程同步问题 整形信号量： 未遵循“让权等待原则” wait(S): while S=0 do no-op; S:=S-1; signal(S): S:=S+1 记录型信号量： 执行wait操作时，信号量的值加1，信号量的值小于0时阻塞； 执行signal操作时，信号量的值减1，信号量的值小于等于0时唤醒阻塞中的进程。 type semaphore=record value:integer; L:list of process; end procedure wait(S) var S:semaphore; begin S.value=S.value-1; if S.value0 then block(S.L); end procedure signal(S) var S:semaphore; begin S.value:=S.value+1; if S.value=0 then wakeup(S.L); end  生产者-消费者问题 读者-写者问题 哲学家进餐问题 理发室问题 进程同步问题求解要领 认真审题、确立信号量及关键变量 构建算法基本步骤及逻辑结构 资源信号量申请先于互斥信号量申请 wait操作与signal操作配对出现 利用信号量实现互斥 主程序 子程序 Var mutex:semaphore:=1; begin parbegin process1; process2; parend end process1 begin repeat wait(mutex); 临界区 signal(mutex); …… until false end process2 begin repeat wait(mutex); 临界区 signal(mutex) …… until false end 互斥信号量初值为1 互斥信号量wait和signal肯定出现在同一进程中，并出现在需要互斥访问数据(临界资源)前后 利用信号量描述前趋关系 Var a,b,c,d,e,f,g,h:semaphore:=0,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);S6;signal(h);end begin wait(f);wait(g);wait(f);S7;end parend end 首先应找出所有的前趋关系。然后，对每一种前趋关系，如Si-Sj，专门设置一初值为0的信号量，并在Si结束之后执行对该信号量的signal操作，而在Sj开始之前执行对该信号量的wait操作，这样便可保证程序段Si执行完后才执行程序段Sj。 生产者-消费者问题 主程序(n为常量) Var buffer:array[0,…,n-1] of item; in, out: integer:=0,0; mutex,empty,full:semaphore:=1,n,0; begin parbegin producer1;…;produceri;…;producerM; consumer1;…consumerj;…;consumerN; parend end 生产者子程序 消费者子程序 produceri Var nextp:item; begin repeat Produce an item in nextp; wait(empty);wait(mutex); buffer[in]:=nextp; in=(in+1)mod n; signal(mutex); signal(full); until false end consumerj Var nextc:item; begin repeat wait(full);wait(mutex); nextc:=buffer[out]; out:=(out+1) mod n; signal(mutex); signal(empty); Consume the item in nextc; until false end 生产者子程序(基于AND信号量) 消费者子程序(基于AND