操作系统复习1.doc

进程1 把具有相同状态的PCB，用其中的链接字，链接成一个队列系统中进程队列分类：就绪队列、等待队列、运行队列。就绪队列：整个系统只有一个。等待队列：每个等待事件一个。运行队列：单机系统中整个系统一个。例：如果系统中有N个进程，那么l 运行进程最多几个，最少几个？l 就绪进程最多几个，最少几个？l 等待进程最多几个，最少几个？答案：假定系统中有k个CPU，l 运行进程最多k个，最少0个l 就绪进程最多N-k个，最少0个l 等待进程最多N个，最少0PCB中必须包含的信息有（ ）。l A、进程家族指针 B、系统打开文件表l C、程序段 D、进程状态 答案： A、D PCB是系统感知进程存在的唯一实体包含一个进程的描述信息（进程名，用户名及家族关系），控制作息(进程当前状态，进程优先级，程序开始地址，各种计时信息，通信作息)，资源信息管理（对换信息，共享信息，设备、I/O资源使用情况信息）。进程的上下文包括如下各项，除了（）l A、用户打开文件表 B、PCBl C、中断向量 D、核心栈 答案：C2 当信号量大于0时，说明“环境安全”，可继续运行；当信号量小于0时，说明“互斥等待”，只能阻塞有20个进程共享一个互斥段，每次最多允许5个进程进入互斥段，则信号量的变化范围是（ ） A 、0到5 B、-15到5 C、-19到1 D、-1到5开始时S=5(表示可用资源数），假定极限情况下20个进程同时要对临界区进行操作，则（5-20）-15。 答案B3 公有信号量：互斥时使用。 互斥信号量必定成对出现：进入临界区临界区退出临界区。同步P操作在互斥P操作前（互斥信号量永远紧邻临界区）两个V操作的顺序无关紧要。处于临界区的进程是可以中断的。4 PV原语例1 有一个充分大的池子，两个人分别向池内投球。甲投红球，乙投蓝球，一次投一个。开始时池子中有红蓝球各一个。要求池中红蓝球满足：蓝球数红球数2蓝球数。用P、V操作描述两个进程。甲 乙 while(true) while(true) P(r); P(b); 扔一个红球； 扔一个蓝球； V(b); V(r); V(r); R初值为1，b初值为0例2 假定航空公司有k个航班，票数分别为Ai,i=1,2,k。设有n个售票窗口，都可以对外售票。设置互斥信号量mutexi，i=1,2,k. 初值mutexi:= 1;process Piwhile(true)按旅客定票要求找到Aj； P(mutexi); Xi = Aj; if Xi=1 Xi:=Xi-1; Aj:=Xi; V(mutexi); 输出一张票；else V(mutexi); 输出票已售完； end;设置互斥信号量mutex，初值mutex:= 1;process Piwhile(true)按旅客定票要求找到Aj； P(mutex); Xi = Aj;Xi = Aj; if Xi=1 Xi:=Xi-1; Aj:=Xi; V(mutexi); 输出一张票；else V(mutexi); 输出票已售完； end; if Xi=1 Xi:=Xi-1; Aj:=Xi; V(mutex); 输出一张票；else V(mutex); 输出票已售完； end;例3 桌上有一只盘子，每次只能放入一只水果；爸爸专向盘子中放苹果(apple)，妈妈专向盘子中放桔子(orange)，一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果 信号量sp /* 盘子里可以放几个水果 */sg1 /* 盘子里有桔子 */sg2 /* 盘子里有苹果 */process son While(true)P(sg1);从plate中取桔子；V(sp);吃桔子；process daughter While(true)P(sg2);从plate中取苹果；V(sp);吃苹果；设初值 sp := 1; Sg1, := 0; sg2 := 0; process father While(true)削一个苹果；P(sp);把苹果放入plate；V(sg2);process mother While(true)剥一个桔子；V(sp);吃苹果；P(sp);把桔子放入plate；V(sg1);例4 理发店理有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉；一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开设置整形变量 waiting /*等候理发的顾客数*/ CHAIRS /*为顾客准备的椅子数*/ 信号量 customers顾客数, barbers空着的理发椅数，mutex customers = 0; barbers = 0; waiting = 0; mutex = 1;Procedure barber;while(TRUE) /*理完一人,还有顾客吗?*/ P(cutomers); /*若无顾客,理发师睡眠*/ P(mutex); /*进程互斥*/ waiting = waiting 1; /*等候顾客数少一个*/ V(barbers); /*理发师去为一个顾客理发*/ V(mutex); /*开放临界区*/ cut-hair( ); /*正在理发*/procedure customer P(mutex); /*进程互斥*/ if waitingCHAIRS /*看看有没有空椅子*/ waiting = waiting+1; /* 等候顾客数加1*/ V(customers); /*必要的话唤醒理发师*/ V(mutex); /*开放临界区*/ P(barbers); /*无理发师, 顾客坐着养神*/ get-haircut( ); /*理发*/ V(mutex); /*人满了,走吧!*/例5 某寺庙，有小和尚、老和尚若干庙内有一水缸，由小和尚提水入缸，供老和尚饮用。水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行。水取自同一井中，水井径窄，每次只能容纳一个水桶取水。设水桶个数为5个，试用信号灯和PV操作给出老和尚和小和尚的活动。 semaphore empty=30; / 表示缸中目前还能装多少桶水，初始时能装30桶水semaphore full=0; / 表示缸中有多少桶水，初始时缸中没有水semaphore buckets=5; / 表示有多少只空桶可用，初始时有5只桶可用semaphore mutex_well=1; / 用于实现对井的互斥操作semaphore mutex_bigjar=1; / 用于实现对缸的互斥操作 young_monk()old_monk()while()P(buckets);P(full);P(mutex_bigjar);get water;V(mutex_bigjar);drink water;V(buckets);V(empty); while(1)P(buckets);go to the well;P(mutex_well);get water;V(mutex_well);go to the temple;P(empty);V(buckets);V(empty); P(mutex_bigjar);pure the water into the big jar;V(mutex_bigjar);V(buckets);V(full); 例6 一座小桥(最多只能承重两个人)横跨南北两岸，任意时刻同一方向只允许一人过桥，南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或歇息。试用信号量和PV操作写出南、北两岸过桥的同步算法。 桥上可能没有人，也可能有一人，也可能有两人。共需要四个信号量，load1来控制桥上可向南人数，初值为1； load2来控制桥上可向北人数，初值为1； north用来控制北段桥的使用，初值为1，用于对北段桥互斥；south用来控制南段桥的使用，初值为1，用于对南段桥互斥。 semaphore load1=1,load 2 =1;semaphore north=1;semaphore south=1; tonorth()P(load2);P(south);过南段桥;到桥中间V(south);P(north);过北段桥;到达北岸V(north);V(load2); tosouth()P(load1);P(north);过北段桥;到桥中间V(south);P(north);过北段桥;到达北岸V(north);V(load2); 到桥中间;V(south);P(north);过北段桥;到达北岸V(north);V(load2); V(north);P(south);过南段桥;到达南岸V(south);V(load1); 例7 设有一个可以装A、B两种物品的仓库，其容量无限大，但要求仓库中A、B两种物品的数量满足下述不等式:-MA物品数量B物品数量N 其中M和N为正整数。 试用信号量和PV操作描述A、B两种物品的入库过程。 semaphore a=n;B物品入库：process B() while(1) P(b); B物品入库; V(a); semaphore b=m; A物品入库：process A()while(1) P(a); A物品入库; V(b); 例8 设有4个进程A、B、C、D共享一个缓冲区，进程A负责循环地从文件读一个整数并放入缓冲区，进程B从缓冲区循环读入MOD 3为0的整数并累计求和；C从缓冲区循环地读入MOD 3为1的整数并累计求和；D从缓冲区中循环地读入MOD 3为2的整数并累计求和。请用P、V操作写出能够正确执行的程序。Process PBBegin P(SB); V(Sempty);endProcess PCBegin P(SC); V(Sempty);endProcess PDBegin P(SD); V(Sempty);end所需同步信号量：Sempty :=1 、SB、SC、SD := 0Process PABegin P(Sempty); if（num MOD 3 = 0) V(SB);Writer：while (true) P(mutex); write(); V(mutex);r_cnt=0;Semaphore mutex=1;semaphore r_mutex=1Reader： while (true) P(r_mutex); r_cnt+; if(r_cnt=1) P(mutex); V(r_mutex); read(); P(r_mutex); r_cnt- -; if(r_cnt=0) V(mutex); V(r_mutex); if（num MOD 3 = 1) V(SC); else V(SD);End例9 读者写者之一般问题如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读， 则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待例 10 读者写者之写者优先1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）readcount=0; writecount=0； S=mutex=w=wmutex=1写者： while (true) P(wmutex); writecount+; if(writecount=1) P(S); V(wmutex); P(w); 写 V(w); P(wmutex); writecount-; if(writecount=0) V(S); V(wmutex); 读者： while (true) P(S); P(mutex); readcount +; if (readcount=1) P (w); V(mutex); V(S); 读 P(mutex); readcount -; if (readcount=0) V(w); V(mutex); ;Writer：while (true) P(rw_mutex); P(mutex); write(); V(mutex); V(rw_mutex);P(r_mutex); r_cnt- -; if(r_cnt=0) V(mutex); V(r_mutex);Reader： while (true) P(rw_mutex); P(r_mutex); r_cnt+; if(r_cnt=1) P(mutex); V(r_mutex); V(rw_mutex); read(); P(r_mutex); r_cnt- -; if(r_cnt=0) V(mutex); V(r_mutex);HY版5死锁例： 设系统中仅有一个资源类，其中共有3个资源实例，使用此类资源的进程共有3个，每个进程至少请求一个资源，它们所需资源最大量的总和为X，则发生死锁的必要条件是（X的取值）： （？）假设3个进程所需该类资源数分别是a,b,c个，因此有： a+b+c =X假设发生了死锁，也即当每个进程都申请了部分资源，还需最后一个资源，而此时系统中已经没有了剩余资源，即： (a-1)+(b-1)+(c-1) 3 X = a+b+c 6 因此，如果发生死锁，则必须满足的必要条件是（X 6） 例： 某系统中只有11台打印机，N个进程共享打印机，每个进程要求3台，当N取值不超过（）时，系统不会发生死锁？最坏情况下，N个进程每个都得到2台打印机，都去申请第3台，为了保证不死锁，此时打印机的剩余数目至少为1台，则： 11-2N = 1 N = 56 死锁避免之银行家算法Available: array1.mof integer; /系统可用资源 Claim: array1.n,1.mof integer; /进程最大需求 Allocation: array1.n,1.mof integer; /当前分配 Need: array1.n,1.mof integer; /尚需资源 Request: array1.n,1.mof integer; /当前请求例：在银行家算法中，若出现下述资源分配情况： Allocation Need AvailableP0 0 0 3 2 0 0 1 2 1 6 2 2P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6P3 0 3 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6问：1。该状态是否为安全状态，找出安全序列 2。如果进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它。解：1。利用银行家算法对此时刻的资源分配情况进行分析，可得此时刻的安全性分析情况： Work Need Alloc Work+AllocP0 1 6 2 2 0 0 1 2 0 0 3 2 1 6 5 4P3 1 6 5 4 0 6 5 2 0 3 3 2 1 9 8 6P4 1 9 8 6 0 6 5 6 0 0 1 4 1 9 9 10P1 1