操作系统进程管理习题课件

进程管理习题设有一个可以装设有一个可以装A、B两种物品的仓库，其两种物品的仓库，其容量无限大，但要求仓库中容量无限大，但要求仓库中A、B两种物品两种物品的数量满足下述不等式：的数量满足下述不等式：-M A物品数量物品数量-B物品数量物品数量N 其中，其中，M和和N为正整数。试用信号量和为正整数。试用信号量和P、V操作描述操作描述A、B两种物品的入库过程。两种物品的入库过程。进程管理习题已知条件已知条件 -M A物品数量物品数量-B物品数量物品数量N可以拆分成两个不等式，即：可以拆分成两个不等式，即：A物品数量物品数量-B物品数量物品数量N B物品数量物品数量-A物品数量物品数量M 这两个不等式的含义是：仓库中这两个不等式的含义是：仓库中A物品可物品可以比以比B物品多，但不能超过物品多，但不能超过N个；个；B物品可物品可以比以比A物品多，但不能超过物品多，但不能超过M个。个。进程管理习题A物品入库：物品入库：P(a);A物品入库；物品入库；V(b);B物品入库：物品入库：P(b);B物品入库；物品入库；V(a);设两个信号量：设两个信号量：a=N；b=M如果没有如果没有B，A最多只能最多只能N个；个；如果没有如果没有A，B最多只能最多只能M个。个。进程管理习题设自行车生产线上有一支箱子，其中有设自行车生产线上有一支箱子，其中有N个位置个位置（N3），每个位置可存放一个车架或一个车轮；），每个位置可存放一个车架或一个车轮；又设有三个工人，其活动分别为：又设有三个工人，其活动分别为：工人工人1活动：活动：Do 加工一个车架；加工一个车架；车架放入箱中；车架放入箱中；while(1);工人工人2活动：活动：Do 加工一个车轮；加工一个车轮；车轮放入箱中；车轮放入箱中；while(1);工人工人3活动：活动：Do 箱中取一车架；箱中取一车架；箱中取二车轮；箱中取二车轮；组装为一台车；组装为一台车；while(1);试用信号量与试用信号量与P、V操作实现三个工人的合作操作实现三个工人的合作进程管理习题首先不考虑死锁问题，工人首先不考虑死锁问题，工人1与工人与工人3、工人、工人2与工人与工人3构成生产者与消费者关系，通过共构成生产者与消费者关系，通过共同的缓冲区相联系。从资源的角度看，箱子同的缓冲区相联系。从资源的角度看，箱子中的空位置相当于工人中的空位置相当于工人1和工人和工人2的资源，而的资源，而车架和车轮相当于工人车架和车轮相当于工人3的资源。的资源。定义定义3个信号量：个信号量：empty=N；（空位置）；（空位置）wheel=0；（车轮）；（车轮）frame=0；（车架）；（车架）进程管理习题 empty=N；wheel=0；frame=0；工人工人1：加工一个车架；加工一个车架；P(empy)；车架放入箱中；车架放入箱中；V(frame)；工人工人2：加工一个车轮；加工一个车轮；P(empy)；车轮放入箱中；车轮放入箱中；V(wheel)；工人工人3：P(frame)；箱中取一车架；箱中取一车架；P(wheel)；P(wheel)；箱中取二车轮；箱中取二车轮；V(empty)；V(empty)；V(empty)；组装为一台车；组装为一台车；进程管理习题为防止死锁，箱中车架的为防止死锁，箱中车架的数量不能超过数量不能超过N-2，车轮的，车轮的数量不能超过数量不能超过N-1，所以设，所以设置：置：s1=N-2，s2=N-1工人工人1：加工一个车架；加工一个车架；P(s1)；车架放入箱中；车架放入箱中；V(frame)；工人工人2：加工一个车轮；加工一个车轮；P(s2)；车轮放入箱中；车轮放入箱中；V(wheel)；工人工人3：P(frame)；箱中取一车架；箱中取一车架；V(s1)；P(wheel)；P(wheel)；箱中取二车轮；箱中取二车轮；V(s2)；V(s2)；组装为一台车；组装为一台车；进程管理习题为防止死锁，箱中车架的为防止死锁，箱中车架的数量不能超过数量不能超过N-2，车轮的，车轮的数量不能超过数量不能超过N-1，所以设，所以设置：置：s1=N-2，s2=N-1，empty=N工人工人1：加工一个车架；加工一个车架；P(s1)；P(empty)；车架放入箱中；车架放入箱中；V(frame)；工人工人2：加工一个车轮；加工一个车轮；P(s2)；P(empty)；车轮放入箱中；车轮放入箱中；V(wheel)；工人工人3：P(frame)；箱中取一车架；箱中取一车架；V(empty)；V(s1)；P(wheel)；P(wheel)；箱中取二车轮；箱中取二车轮；V(empty);V(empty);V(s2)；V(s2)；组装为一台车；组装为一台车；进程管理习题一座小桥（最多只能承重两个人）横跨南一座小桥（最多只能承重两个人）横跨南北两岸，北两岸，任意时刻同一方向只允许一人过任意时刻同一方向只允许一人过桥，桥，南侧桥段和北侧桥段较窄只能通过一南侧桥段和北侧桥段较窄只能通过一人，桥中央一处宽敞，允许两个人通过或人，桥中央一处宽敞，允许两个人通过或歇息。试用信号量和歇息。试用信号量和P、V操作写出南、北操作写出南、北两岸过桥的同步算法。两岸过桥的同步算法。进程管理习题load控制桥上人控制桥上人数，数，north控制北控制北段的互斥使用，段的互斥使用，south控制南段互控制南段互斥使用斥使用初始值：初始值：load=2,north=1,south=1To 南：南：P(load)；P(north)；过北桥段；过北桥段；到桥中间；到桥中间；V(north)；P(south)；过南桥段；过南桥段；到达南岸；到达南岸；V(south)；V(load)；To 北：北：P(load)；P(south)；过南桥段；过南桥段；到桥中间；到桥中间；V(south)；P(north)；过北桥段；过北桥段；到达北岸；到达北岸；V(north)；V(load)；进程管理习题有有3个进程个进程PA，PB和和PC合作解决文件打印问合作解决文件打印问题：题：PA将文件记录从磁盘读入主存的缓冲区将文件记录从磁盘读入主存的缓冲区1，每执，每执行一次读一个记录；行一次读一个记录；PB将缓冲区将缓冲区1的内容复制到缓冲区的内容复制到缓冲区2，每执行一次，每执行一次复制一个记录；复制一个记录；PC将缓冲区将缓冲区2的内容打印出来，每执行一次打印的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小；一个记录。缓冲区的大小等于一个记录大小；请用请用P，V操作来保证文件的正确打印操作来保证文件的正确打印进程管理习题设置设置4个信号量：个信号量：empty1、empty2、full1、full2empty1及及empty2分别表示缓冲区分别表示缓冲区1及缓冲区及缓冲区2是否为空，初值为是否为空，初值为1full1，full2分别表示缓冲区分别表示缓冲区1及缓冲区及缓冲区2是否是否有记录可供处理，其初值为有记录可供处理，其初值为0缓冲区缓冲区1缓冲区缓冲区2PA从磁盘读入从磁盘读入PB复制复制PC打印打印进程管理习题PA()从磁盘读一从磁盘读一 个记录；个记录；P(empty1)；将记录存入将记录存入 缓冲区缓冲区1；V(full1)；PB()P(full1)；从缓冲区从缓冲区1中中 取出记录；取出记录；V(empty1)；P(empty2)；将记录存入缓将记录存入缓 冲区冲区2；V(full2);PC()P(full2);从缓冲区从缓冲区2 取一个记录；取一个记录；V(empty2);打印记录打印记录;缓冲区缓冲区1缓冲区缓冲区2PA从磁盘读入从磁盘读入PB复制复制PC打印打印进程管理习题公共汽车上，司机和售票员的活动分别为：公共汽车上，司机和售票员的活动分别为：司机：司机：启动车辆；启动车辆；正常行驶，正常行驶，到站停车到站停车售票员：售票员：关车门；关车门；售票；售票；开车门；开车门；司机司机P1 售票员售票员P2 启动启动 关门关门 正常运行正常运行 售票售票 到站停到站停 开门开门进程管理习题设信号量设信号量S1：是否允许司机启动汽车，初值为：是否允许司机启动汽车，初值为0，S2：是否允许售票员开门，初值为：是否允许售票员开门，初值为0Driver()while(1)P(S1);启动汽车；启动汽车；正常行车；正常行车；到站停车；到站停车；V(S2);Busman()while(1)关车门关车门;V(S1)；售票；售票；P(S2)；开车门；开车门；上下乘客；上下乘客；s1=0;s2=0;main()Cobegin Driver();Busman();Coend 进程管理习题桌上有一空盘，允许存放一只水果。爸爸桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果苹果。规定当盘空时一次只能放一只水果供吃者取用，请用供吃者取用，请用P，V原语实现爸爸，儿原语实现爸爸，儿子女儿三个进程的同步。子女儿三个进程的同步。进程管理习题设三个信号量：设三个信号量：S：表示盘子是否：表示盘子是否为空，初值为为空，初值为1；So：表示盘中是：表示盘中是否有桔子，初值否有桔子，初值为为0；Sa：表示盘中是：表示盘中是否有苹果，初值否有苹果，初值为为0。s=1;sa=0;so=0;main()cobegin father();son();daughter();coend 进程管理习题father()While(1)P(s);将水果放入盘中；将水果放入盘中；if (放入的是桔子放入的是桔子)v(so)else v(sa);son()While(1)P(so);从盘中取出桔子；从盘中取出桔子；v(s);吃桔子；吃桔子；daughter()While(1)P(sa);从盘中取出苹果；从盘中取出苹果；v(s);吃苹果；吃苹果；进程管理习题图书馆有图书馆有100个座位，有一张登记表，要求：个座位，有一张登记表，要求：阅读者进入时登记，取得座位号；阅读者进入时登记，取得座位号；出来时，注销；出来时，注销；登记表同时只能由一个人使用；登记表同时只能由一个人使用；用用P、V原语描述一个读者的使用过程原语描述一个读者的使用过程进程管理习题信号量信号量SN，表示可用座位数，初值为，表示可用座位数，初值为100；信号量信号量sb,表示登记表是否正在使用，初值表示登记表是否正在使用，初值为为1；reader(int i)enter()；阅读阅读;outer()；enter()P(SN)；P(sb)；登记；登记；V(sb)；outer()P(sb);注销；注销；V(sb);V(SN);进程管理习题三个进程三个进程P1、P2、P3互斥使用一个包含互斥使用一个包含N（N0）个单元的缓冲区。）个单元的缓冲区。P1每次用每次用produce()生成一个正整数并用生成一个正整数并用put()送入缓冲区某已送入缓冲区某已空单元中；空单元中；P2每次用每次用getodd()从该缓冲区中从该缓冲区中取出一个奇数并用取出一个奇数并用countodd()统计奇数个数；统计奇数个数；P3每次用每次用geteven()从该缓冲区中取出一个从该缓冲区中取出一个偶数并用偶数并用counteven()统计偶数个数。请用统计偶数个数。请用信号量机制实现这三个进程的同步和互斥信号量机制实现这三个进程的同步和互斥活动，并说明所定义信号量的含义。要求活动，并说明所定义信号量的含义。要求用伪码描述。用伪码描述。进程管理习题互斥信号量：互斥信号量：mutex初值为初值为1；同步信号量：同步信号量：P1、P2因奇数的放与取而同因奇数的放与取而同步，设置信号量步，设置信号量odd；P1、P3因偶数的放与因偶数的放与取而同步，设置信号量取而同步，设置信号量even；P1、P2、P3因共享缓冲区而同步，设置信号量因共享缓冲区而同步，设置信号量empty。进程管理习题互斥信号量：互斥信号量：mutex，初值为，初值为1；同步信号量：同步信号量：P1、P2因奇数的放与取而同步，设置信号量因奇数的放与取而同步，设置信号量 odd，初值为，初值为0；P1、P3因偶数的放与取而同步，设因偶数的放与取而同步，设 置信号量置信号量even，初值为，初值为0；P1、P2、P3因共享缓冲因共享缓冲 区而同步，设置信号量区而同步，设置信号量empty，初值为，初值为N。P1：P(empty);P(mutex);put();V(mutex);If number%2=0 V(even)Else V(odd);P2：P(odd);P(mutex);getodd();V(mutex);V(empty);countodd();P3：P(even);P(mutex);geteven();V(mutex);V(empty);counteven();进程管理习题某银行提供一个服务窗口和某银行提供一个服务窗口和10个供个供顾客等待的座位。顾客到达银行时，顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一若有空座位，则到取号机上领取一个号。等待叫号。取号机每次仅允个号。等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述务。顾客和营业员的活动过程描述为：为：请添加必要的信号量和请添加必要的信号量和P、V（或（或wait()、signal()）操作，实现上述过程）操作，实现上述过程的的互斥与同步。要求写出完整的的的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。过程，说明信号量的含义并赋初值。Cobegin process 顾客顾客 从取号机获得一个号码从取号机获得一个号码;等待叫号等待叫号;获得服务获得服务;process 营业员营业员 while(TRUE)叫号；叫号；为顾客服务；为顾客服务；coend互斥资源：取号机（一次只允许一位顾客互斥资源：取号机（一次只允许一位顾客领号），因此，设一个互斥信号量领号），因此，设一个互斥信号量mutex；同步问题同步问题顾客需要获得空座位等待叫号，当营业员空闲顾客需要获得空座位等待叫号，当营业员空闲时，将选取一位顾客并为其服务。空座位的有、时，将选取一位顾客并为其服务。空座位的有、无影响等待顾客数量，顾客的有、无决定了营无影响等待顾客数量，顾客的有、无决定了营业员是否能开始服务，故分别设置信号量业员是否能开始服务，故分别设置信号量empty和和full来实现这一同步关系；来实现这一同步关系；顾客获得空座位后，需要等待叫号和被服务。顾客获得空座位后，需要等待叫号和被服务。这样，顾客与营业员就服务何时开始又构成了这样，顾客与营业员就服务何时开始又构成了一个同步关系，定义信号量一个同步关系，定义信号量service来完成这一来完成这一同步过程。同步过程。semaphore mutex=1;/互斥使用取号机互斥使用取号机semaphore empty=10;/空座位的数量空座位的数量semaphore full=0;/已占座位的数量已占座位的数量semaphore service=0;/等待叫号等待叫号cobegin process 顾客顾客 process 营业员营业员 P(empty);while(TRUE)P(mutex);从取号机获得一个号；从取号机获得一个号；P(full);V(mutex);V(empty);V(full);V(service);/叫号叫号 P(service);/等待叫号等待叫号 为顾客服务；为顾客服务；获得服务；获得服务；coend评分说明评分说明能正确给出互斥信号量定义、含义及初值，给1分。能正确给出3个同步信号量定义、含义及初值，给2分。营业员进程描述正确的，给2分。顾客进程描述中，互斥描述正确的，给1分；同步描述正确的，给2分；共3分。其他正确解答，参照-的标准给分。进程管理习题某博物馆最多可容纳某博物馆最多可容纳500人同时参观，有一个出入人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的口，该出入口一次仅允许一个人通过。参观者的活动描述如下：活动描述如下：cobegin 参观者进程参观者进程i：进门；进门；出门；出门；coend；请添加必要的信号量请添加必要的信号量和和P、V（或（或wait()、signal()）操作，以实）操作，以实现上述过程中的互斥现上述过程中的互斥与同步。要求写出完与同步。要求写出完整的过程，说明信号整的过程，说明信号量的含义并赋初值。量的含义并赋初值。进程管理习题定义两个信号量：定义两个信号量：empty=500；/博物馆可以容纳的最多人博物馆可以容纳的最多人数数mutex=1；/用于出入口资源的控制用于出入口资源的控制cobegin 参观者进程参观者进程i：P(empty);P(mutex);进门进门;V(mutex);参观参观;P(mutex);出门出门;V(mutex);V(empty);coend;进程管理习题 有有A、B两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，两人通过信箱进行辩论，每个人都从自己的信箱中取得对方的问题，将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设将答案和向对方提出的新问题组成一个邮件放入对方的邮箱中。假设A的信的信箱最多放箱最多放M个邮件，个邮件，B的邮箱最多放的邮箱最多放N个邮件。初始时个邮件。初始时A的信箱中有的信箱中有x个邮件个邮件（0 xM）,B的信箱中有的信箱中有y个邮件（个邮件（0yN）。辩论者每取出一个邮件，邮）。辩论者每取出一个邮件，邮件数减件数减1。A和和B两人的操作过程描述如下：两人的操作过程描述如下：当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，当信箱不为空时，辩论者才能从信箱中取邮件，否则等待。当信箱不满时，辩论者才能将新邮件放入邮箱，否则等待。请添加必要的信号量和辩论者才能将新邮件放入邮箱，否则等待。请添加必要的信号量和P、V（或（或wait、signal）操作，以实现上述过程的同步。要求写出完整的过程，）操作，以实现上述过程的同步。要求写出完整的过程，并说明信号量的含义和初值。并说明信号量的含义和初值。A while(TRUE)从从A的信箱中取出一个邮件；的信箱中取出一个邮件；回答问题并提出一个新问题；回答问题并提出一个新问题；将新邮件放入将新邮件放入B的信箱；的信箱；B while(TRUE)从从B的信箱中取出一个邮件；的信箱中取出一个邮件；回答问题并提出一个新问题；回答问题并提出一个新问题；将新邮件放入将新邮件放入A的信箱；的信箱；进程管理习题semaphore Full_A=x;/表示表示A的信箱的邮件数量的信箱的邮件数量semaphore Empty_A=M-x;/表示表示A的信箱中还可存放的邮件数量的信箱中还可存放的邮件数量(1分分)semaphore Full_B=y;/表示表示B的信箱的邮件数量的信箱的邮件数量semaphore Empty_B=N-y;/表示表示B的信箱中还可存放的邮件数量的信箱中还可存放的邮件数量(1分分)semaphore mutex_A=1;/用于用于A的信箱互斥的信箱互斥semaphore mutex_B=1;/用于用于B的信箱互斥的信箱互斥(1分分)进程管理习题A while(TRUE)P(Full_A);P(mutex_A);从从A的信箱中取出一个邮件；的信箱中取出一个邮件；V(mutex_A);V(Empty_A);回答问题并提出一个新问题；回答问题并提出一个新问题；P(Empty_B);P(mutex_B);将新邮件放入将新邮件放入B的邮箱；的邮箱；V(mutex_B);V(Full_B);B while(TRUE)P(Full_B);P(mutex_B);从从B的信箱中取出一个邮件；的信箱中取出一个邮件；V(mutex_B);V(Empty_B);回答问题并提出一个新问题；回答问题并提出一个新问题；P(Empty_A);P(mutex_A);将新邮件放入将新邮件放入A的邮箱；的邮箱；V(mutex_A);V(Full_A);进程管理习题评分说明：评分说明：每对信号量的定义及初值正确，给每对信号量的定义及初值正确，给1分，共分，共3分。分。每个互斥信号量的每个互斥信号量的P、V操作使用正确，各给操作使用正确，各给1分，共分，共2分。分。每个同步信号量的每个同步信号量的P、V操作使用正确，各给操作使用正确，各给1分，共分，共4分。分。进程管理习题某系统有某系统有R1、R2和和R3共共3种资源，在种资源，在T0时刻时刻P1、P2、P3和和P4这这4个进程对资源的个进程对资源的占用和需求情况见下页表，此时系统的可占用和需求情况见下页表，此时系统的可用资源向量为用资源向量为(2,1,2)，问题：，问题：将系统各种资源总数和此刻各进程对资将系统各种资源总数和此刻各进程对资源的需求数目用向量或矩阵表示出来；源的需求数目用向量或矩阵表示出来；如果此时如果此时P1和和P2均发出资源请求向量均发出资源请求向量Request(1,0,1)，为保证系统的安全性，为保证系统的安全性，应如何分配资源给这两个进程？说明采应如何分配资源给这两个进程？说明采用策略的原因。用策略的原因。进程管理习题MaxUsed(Allocation)R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0P2 6 1 3 4 1 1P3 3 1 4 2 1 1P4 4 2 2 0 0 2Need=3 2 26 1 33 1 44 2 21 0 04 1 12 1 10 0 22 2 22 0 21 0 34 2 0-=资源总量资源总量(2,1,2)+(1,0,0)+(4,1,1)+(2,1,1)+(0,0,2)=(9,3,6)进程管理习题MaxUsed(Allocation)Need R1 R2 R3 R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0 2 2 2 P2 6 1 3 4 1 1 2 0 2P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 0 0 2 Request1(1,0,1)Need1(2,2,2)Request1(1,0,1)Available(2,1,2)Used=2 0 14 1 12 1 10 0 2Need=1 2 12 0 21 0 30 0 2Available(1,1,1),不能满足任何进不能满足任何进程，系统进入不程，系统进入不安全状态，所以安全状态，所以不能分配给不能分配给P1进程管理习题MaxUsed(Allocation)Need R1 R2 R3 R1 R2 R3 R1 R2 R3P1 3 2 2 1 0 0 2 2 2 P2 6 1 3 4 1 1 2 0 2P3 3 1 4 2 1 1 1 0 3 P4 4 2 2 0 0 2 0 0 2 Request2(1,0,1)Need1(2,0,2)Request2(1,0,1)Available(2,1,2)Used=1 0 05 1 22 1 10 0 2Need=2 2 21 0 11 0 30 0 2Available(1,1,1),存在一个安全序存在一个安全序列：列：P2,P3,P4,P1，所以能分，所以能分配给配给P1某文件系统为一级目录结构，文件的数据某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。但可多次创建新文件。请回答如下问题。（1）在连续、链式、索引三种文件的数据块）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需在为定位文件数据块，需在FCB中设计哪些中设计哪些相关描述字段？相关描述字段？（2）为快速找到文件，对于）为快速找到文件，对于FCB，是集中存，是集中存储好，还是与对应的文件数据块连续存储储好，还是与对应的文件数据块连续存储好？要求说明理由。好？要求说明理由。（1）在磁盘中连续存放（采取连续结构），）在磁盘中连续存放（采取连续结构），磁盘寻道时间更短，文件随机访问效率磁盘寻道时间更短，文件随机访问效率 更高；（更高；（2分）分）在在FCB中加入的字段为：中加入的字段为：或者或者（1分）分）（2）将所有）将所有FCB集中存放，文件数据集中存放。（集中存放，文件数据集中存放。（2分）分）这样在随机查询文件名时，只需访问这样在随机查询文件名时，只需访问FCB对应的块，对应的块，可减少磁头移动和磁盘可减少磁头移动和磁盘I/O访问次数。（访问次数。（2分）分）