西安电子科技大学操作系统考试重点作业讲解(2～4).ppt
作业讲解（24）,知识点,进程互斥和同步的控制 信号量机制 信号量是一种数据结构 信号量的值与相应资源的使用情况有关 信号量的值仅由P、V操作改变,知识点,记录型信号量 记录型结构，包括两个数据项： type semaphore=record value:integer; L:list of process; end,知识点,假设定义了一个信号量S S.value为资源信号量，其初值为某类资源的数目。 S.value=0，代表系统当中可用资源的数目。 S.value<0,其绝对值代表等待使用资源的进程个数。 S.L是一个阻塞队列，进程无法申请到资源则进入此队列。,知识点,定义对信号量的两个原子操作：wait(s) 和signal（s）,procedure wait(S) var S: semaphore; begin S.value: =S.value-1; if S.value0 then block(S.L) /进程阻塞，即进入S.L链表； end,知识点,定义对信号量的两个原子操作：wait(s) 和signal（s）,procedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); /唤醒阻塞队列首进程, 将进程从 /S.L阻塞队列中移出； end,第二章,22、试写出相应的程序来描述图2-17 所示的前趋图。 P82 22(a) 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(h); S7; end; parend end,第二章,26. 参看教材P58-59,第二章,3、设公共汽车上有一个司机和一个售票员，其活动如图3所示。为了安全起见，显然要求: (1)关车门后方能启动车辆；(2)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。,用记录型信号量解决这一问题，需要定义两个信号量： Start：表示是否允许司机启动车辆，初值为0； Open：表示是否允许售票员开车门，初值为0。,semaphore start=0; semaphore open=0;,售票员的活动: begin repeat 关车门; Signal(start); 售票; Wait(open); 开车门; until false end,司机的活动: begin repeat Wait(start); 启动车辆; 正常行车; 到站停车; Signal(open); until false end,第二章,知识点 进程调度算法 避免死锁银行家算法,进程调度算法,先来先服务FCFS 短作业优先调度算法 时间片轮转调度算法 概念 周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。 带权周转时间：周转时间/系统为它提供服务的时间,第三章,1、假定有如下作业：,请用FCFS、SJF、RR(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。,第三章,FCF和SPF的计算结果如下,第三章,时间片轮转调度算法，执行图如下：,BCA,银行家算法,用于避免死锁。 基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。 安全状态： 是指系统能按某种进程顺序，如,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称序列为安全序列。 若系统存在安全序列，则系统当前为安全状态。,银行家算法描述,设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果RequestijNeedi,j， 【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 如果RequestijAvailablej【请求小于库存】,便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。,银行家算法描述,3. 系统试探着把资源分配给进程Pi【试分配】，并修改下面数据结构中的数值： 【库存】 Available j :=Available j -Requestij; 【获取】 Allocationi,j:=Allocationi,j+Requestij; 【需求】 Needi,j:=Needi,j-Requestij 4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,第三章,2 .在银行家算法中，若出现下述资源分配情况：P115第22题,第三章,1）该状态是否安全？,安全，因为存在安全序列,第三章,2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？ 分配后系统资源情况如下：,此状态不安全，因此不能分配。,第四章,知识点 基本分页式存储管理地址映射过程 基本分段式存储管理地址映射过程 页面置换算法,基本分页式存储管理地址映射过程,第四章,1、在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下： 试借助地址变换图求出有效逻辑地址4865所对应的物理地址。,解答,基本分段式存储管理地址映射过程,段地址变换由硬件地址变换机构完成。,第四章 作业3,3、对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成物理地址。,4,Cb,+,0 137,比较,5*1024 + 137,段表,0<4,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,b,137<5K,比较,51337,4,Cb,+,1 4000,比较,段表,0<4,地址越界,段表始址寄存器,段表长度寄存器,逻辑地址,b,4000<3K,比较,4,Cb,4 230,4<4,段表始址寄存器,段表长度寄存器,逻辑地址,地址越界,比较,页面置换算法,在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。,页面置换算法分类,最佳页面算法（OPT） 先进先出页面置换算法（FIFO） 最近最久未使用页面置换算法（LRU） 轮转算法（Clock）,第四章 作业2：P143页 23题,2、某程序在内存中分配四个块，访问页的走向为4，3，2，1，4，3，5，4，3，2，1，5，按LRU、Clock、OPT算法分别计算缺页次数 假设开始时所有页均不在内存,LRU 4 3 2 1 4 3 5 4 3 2 1 5 块1 块2 块3 块4 x x x x x x x x 共缺页中断8次,LRU,Clock 4 3 2 1 4 3 5 4 3 2 1 5 块1 块2 块3 块4 x x x x x x x x x x 共缺页中断10次,Clock,OPT 4 3 2 1 4 3 5 4 3 2 1 5 块1 块2 块3 块4 x x x x x x 共缺页中断6次,OPT,第四章 作业4,4、某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3653，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制，而内存中尚未装入任何页。请给出使用LRU算法时的缺页次数。 解答：页块数为3，页号分别为0（01023），1（10242047），2（20483071），3（30714095），则引用内存单元对应的页号为：3、3、1、3、2、3、0、2、1、2、3、0、1、1。,LRU 3 3 1 3 2 3 0 2 1 2 3 0 1 1 块1 块2 块3,LRU,x x x x x x x x 共缺页中断8次,
