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

1、作业讲解（24）,知识点,进程互斥和同步的控制 信号量机制 信号量是一种数据结构 信号量的值与相应资源的使用情况有关 信号量的值仅由p、v操作改变,知识点,记录型信号量 记录型结构，包括两个数据项： type semaphore=record value:integer; l:list of process; end,知识点,假设定义了一个信号量s s.value为资源信号量，其初值为某类资源的数目。 s.value=0，代表系统当中可用资源的数目。 s.value0,其绝对值代表等待使用资源的进程个数。 s.l是一个阻塞队列，进程无法申请到资源则进入此队列。,知识点,定义对信号量的两个原子操

2、作：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,第二章

3、,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);

4、 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)到站停车后方能开车门。亦即“启动车辆”这一活动应当在“关车门”这一活动之后，“开车门”这一活动应当在“到站停车”这一活动之后。试用记录型信号量实现司机与售票员之间的同步，并说明各信号量的含义。,用记录型信号量解决这一问题，需要定义两个信号量： st

5、art：表示是否允许司机启动车辆，初值为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 短作业优先调度算法 时间片轮转

6、调度算法 概念 周转时间：指作业提交给系统开始，到作业完成为止的这段时间间隔。 带权周转时间：周转时间/系统为它提供服务的时间,第三章,1、假定有如下作业：,请用fcfs、sjf、rr(q=2）调度算法，分别计算周转时间、平均周转时间、带权周转时间、平均带权周转时间。,第三章,fcf和spf的计算结果如下,第三章,时间片轮转调度算法，执行图如下：,bca,银行家算法,用于避免死锁。 基本思想：当有进程申请资源时，只有满足此进程需要不会导致系统进入不安全状态才分配。 安全状态： 是指系统能按某种进程顺序，如,分别为这n个进程分配所需资源，直到满足每个进程的最大需求，使每个进程都能顺利完成，称序列

7、为安全序列。 若系统存在安全序列，则系统当前为安全状态。,银行家算法描述,设requesti是进程pi的请求向量，如果requestij=k，表示进程pi需要k个rj类型的资源。当pi发出资源请求后，系统按下述步骤进行检查： 如果requestijneedi,j， 【请求小于需求】,便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 如果requestijavailablej【请求小于库存】,便转向步骤(3)；否则， 表示尚无足够资源，pi须等待。,银行家算法描述,3. 系统试探着把资源分配给进程pi【试分配】，并修改下面数据结构中的数值： 【库存】 available

8、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)后，系统能

9、否将资源分配给它？ 分配后系统资源情况如下：,此状态不安全，因此不能分配。,第四章,知识点 基本分页式存储管理地址映射过程 基本分段式存储管理地址映射过程 页面置换算法,基本分页式存储管理地址映射过程,第四章,1、在采用页式存储管理的系统中，拥有的逻辑地址空间为32页，某作业j的逻辑地址空间为4页（每页2048字节），且已知该作业的页面映像（即页表）如下： 试借助地址变换图求出有效逻辑地址4865所对应的物理地址。,解答,基本分段式存储管理地址映射过程,段地址变换由硬件地址变换机构完成。,第四章 作业3,3、对于下表所示的段表，请将逻辑地址（0，137），（1，4000），（4，230）转换成

10、物理地址。,4,cb,+,0 137,比较,5*1024 + 137,段表,04,物理地址,段表始址寄存器,段表长度寄存器,逻辑地址,b,1375k,比较,51337,4,cb,+,1 4000,比较,段表,04,地址越界,段表始址寄存器,段表长度寄存器,逻辑地址,b,40003k,比较,4,cb,4 230,44,段表始址寄存器,段表长度寄存器,逻辑地址,地址越界,比较,页面置换算法,在请求分页式存储管理中，当发生缺页中断且无足够的内存空间时，需要置换已有的某些（个）页面。,页面置换算法分类,最佳页面算法（opt） 先进先出页面置换算法（fifo） 最近最久未使用页面置换算法（lru） 轮转

11、算法（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。如果上述数字均为十进制，而内存中尚未装入任何页。请给出使用l