操作系统101.pptx

1 互斥问题,（1）互斥算法正确性的条件是什么？（2）关于两个进程互斥问题，有人给出如下解法：试举反例，说明上述算法是不正确的。,var blocked:array0.1of boolean;turn:0.1;procedure P(id:integer);begin repeat blockedid:=true;while turnid do begin while blocked1-id do nothing turn:=id end;blockedid:=false;until falseend;,begin blocked0:=false;blocked1:=false;turn:=0;parbegin P(0);P(1)parend;end.,2 处理机调度,下表所示的5个进程：,采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。问 题：画出对上述5个进程调度结果的Gantt图；计算5个进程的平均周转时间、平均带权周转时间。,某寺庙，有小和尚、老和尚若干庙内有一水缸，由小和尚提水入缸，供老和尚饮用水缸可容纳 30 桶水，每次入水、取水仅为1桶，不可同时进行水取自同一井中，水井径窄，每次只能容纳一个水桶取水设水桶个数为5个试用信号灯和PV操作给出老和尚和小和尚的活动,3 信号量与P/V操作,old_monk()do P(full);P(bucket);P(mutex_bigjar);缸中取水;V(mutex_bigjar);喝水;V(bucket);V(empty);,Young_monk()do P(empty);P(bucket);走到井边;P(mutex_well);井中取水;V(mutex_well);走到寺庙;P(mutex_bigjar);水入缸中;V(mutex_bigjar);V(bucket);V(full);while(1),semaphore empty;(30)/水缸容量semaphore full;(0)/当前水量semaphore bucket;(5)/水桶数semaphore mutex_bigjar;semaphore mutex_well;,一南北流向的小河上有一座独木桥，如下图所示：,4 信号量与P/V操作,该独木桥宽度只能容纳一人，且该桥最多只能承重4人；东、西两方向过桥人只能前进、不能后退。问 题：写出用信号量和PV操作实现东、西两方向行人过桥的没有死锁、没有饿死的并发运行算法。要 求：给出定义的各信号量和变量的含义及其初值。,int west_crossing=0,east_crossing=0,west_wait=0,east_wait=0;semaphore wq,eq;/*初值均为0*/semaphore mutex;/*初值均为1，用于共享变量的互斥*/semaphore num;/*初值为4，用于限制过河人数*/semaphore w_wait,e_wait;/*初值均为1，防止对方饿死*/,西面过河者算法：P(w_wait);/*后续过桥者将在此等待*/P(mutex);if(east_crossing 0)west_wait+;if(west_wait=1)P(e_wait);/西边有等待，东边后续过桥者将等待V(mutex);P(wq);/*西边第一位过桥者在此等待*/else P(num);/*过河人数超过4人则等待*/west_crossing+;V(mutex);V(w_wait);,;P(mutex);west_crossing-;V(num);/*过桥人数减少1人*/if(west_crossing=0)if(east_wait 0)do east_wait;east_crossing+;V(eq);/*唤醒东边第一位等待者*/V(mutex);,东面过河者算法：P(e_wait);/*后续过桥者将在此等待*/P(mutex);if(west_crossing 0)east_wait+;if(east_wait=1)P(w_wait);/东边有等待，西边后续过桥者将等待 V(mutex);P(eq);/*东边第一位过桥者在此等待*/else P(num);/*过河人数超过4人则等待*/east_crossing+;V(mutex);V(e_wait);,;P(mutex);east_crossing-;V(num);/*过桥人数减少1人*/if(east_crossing=0)if(west_wait 0)do west_wait;west_crossing+;V(wq);/*唤醒西边第一位等待者*/V(mutex);,int west_crossing=0,east_crossing=0,west_wait=0,east_wait=0;semaphore wq,eq;/*初值均为0*/semaphore mutex;/*初值均为1，用于共享变量的互斥*/semaphore num;/*初值为4，用于限制过河人数*/semaphore w_wait,e_wait;/*初值均为1，防止对方饿死*/,某系统采用虚拟页式存储管理方式，页面大小为2KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程P的页表如下（“时钟”指针指向逻辑页面3的表项）：,问 题：当进程P依次对逻辑地址执行下述操作：引用 4C7H；修改 19B4H；修改 0C9AH；写出进程P的页表内容；在 的基础上，进程P对逻辑地址27A8H进行访问，该逻辑地址对应的物理地址是多少？,