西安电子科技大学 操作系统 考试重点作业讲解(2～4).ppt

作业讲解（2～4） 知识点 进程互斥和同步的控制 信号量机制 信号量是一种数据结构 信号量的值与相应资源的使用情况有关 信号量的值仅由P、V操作改变 知识点 记录型信号量 记录型结构，包括两个数据项： type semaphore=record value:integer; L:list of process; 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。 第二章 知识点 进程调度算法 避免死锁——银行家算法 进程调度算法 先来先服务FCFS 短作业优先调度算法 时间片轮转调度算法 概念 周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。 带权周转时间：周转时间/系统为它提供服务的时间 第三章 1、假定有如下作业： 第三章 第三章 时间片轮转调度算法，执行图如下： 银行家算法 用于避免死锁。 基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。 安全状态： 是指系统能按某种进程顺序，如P1,P2,…,Pn,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称P1,P2,…,Pn序列为安全序列。 若系统存在安全序列，则系统当前为安全状态。 银行家算法描述 设Requesti是进程Pi的请求向量，如果Requesti［j］=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： 如果Requesti［j］≤Need［i,j］， 【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 如果Requesti［j］≤Available［j］【请求小于库存】,便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。 银行家算法描述 3. 系统试探着把资源分配给进程Pi【试分配】，并修改下面数据结构中的数值： 【库存】 Available [j] :=Available [j] -Requesti[j]; 【获取】 Allocation[i,j]:=Allocation[i,j]+Requesti[j]; 【需求】 Need[i,j]:=Need[i,j]-Requesti[j] 4. 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 第三章 2 .在银行家算法中，若出现下述资源分配情况：P115第22题 第三章 1）该状态是否安全？ 第三章 2)若进程P2提出请求Request(1,2,2,2)后，系统能否将资源分配给它？ 分配后系统资源情况如下： 第四章 知识点 基本分页式存储管理地址映射过程 基本分段式存储管理地址映射过程 页面置换算法 第四章 1、在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业J的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下： 试借助地址变换图求出有效逻辑地址4865所对应的物理地址。 解答 基本分段式存储管理地址映射过程 段地址变换由硬件地址变换机构完成。 第四章 作业3