操作系统计算题总结.doc

。应用类型知识要点一：进程同步问题整形信号量：未遵循“让权等待原则”wait(S): while S=0 do no-op; S:=S-1;signal(S): S:=S+1记录型信号量：执行wait操作时，信号量的值加1，信号量的值小于0时阻塞；执行signal操作时，信号量的值减1，信号量的值小于等于0时唤醒阻塞中的进程。type semaphore=record value:integer; L:list of process; endprocedure wait(S)var S:semaphore;beginS.value=S.value-1;if S.value0 then block(S.L);endprocedure signal(S)var S:semaphore;beginS.value:=S.value+1;if S.valueSj，专门设置一初值为0的信号量，并在Si结束之后执行对该信号量的signal操作，而在Sj开始之前执行对该信号量的wait操作，这样便可保证程序段Si执行完后才执行程序段Sj。生产者-消费者问题主程序(n为常量)Var buffer:array0,n-1 of item;in, out: integer:=0,0;mutex,empty,full:semaphore:=1,n,0;beginparbeginproducer1;produceri;producerM;consumer1;consumerj;consumerN;parendend生产者子程序消费者子程序produceriVar nextp:item;beginrepeatProduce an item in nextp;wait(empty);wait(mutex);bufferin:=nextp;in=(in+1)mod n;signal(mutex);signal(full);until falseendconsumerjVar nextc:item;beginrepeatwait(full);wait(mutex);nextc:=bufferout;out:=(out+1) mod n;signal(mutex);signal(empty);Consume the item in nextc;until falseend生产者子程序(基于AND信号量)消费者子程序(基于AND信号量)produceribeginrepeatProduce an item in nextp;Swait(empty, mutex);bufferin=nextp;in:=(in+1) mod n;Signal(mutex, full);until falseendconsumerjbeginrepeatSwait(full,mutex);nextc:=bufferout;out:=(out+1) mod n;Ssignal(mutex, empty);Consume the item in nextc;until falseend读者-写者问题(读者优先)主程序Var readercount:integer:=0;rcmutex,wmutex:semaphore:=1,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend读者readeribeginrepeatwait(rcmutex);if readercount=0 then wait(wmutex);readercount:=readercount+1;signal(rcmutex);Perform read operation;wait(rcmutex);readercount:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until falseend写者writerjbeginrepeatwait(wmutex);Perform write operation;signal(wmutex);until false;endreadercount:读者数rcmutex:读者进程中用于readercount变量的互斥访问wmutex:用于读者与写者、写者与写者之间的互斥访问写者与第一个读者竞争wmutex。一旦读者获得wmutex，那么直到所有读者执行结束由最后一个读者释放，而每个写者执行结束都释放，所以读者优先写者执行。读者-写者问题(写者优先)主程序Var readercount,writercount:integer:=0,0;rcmutex,wcmutex,wmutex,S:semaphore:=1,1,1,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend读者readeribeginrepeatwait(S);wait(rcmutex);if readercount=0 then wait(wmutex);readercount:=readercount+1;signal(rcmutex);signal(S);Perform read operation;wait(rcmutex);readercount:=readercount-1;if readercount=0 then signal(wmutex);signal(rcmutex);until false;end写者writerjbeginrepeatwait(wcmutex);if writercount=0 then wait(S);writercount:=writercount+1;signal(wcmutex);wait(wmutex);Perform write operation;signal(wmutex);wait(wcmutex);writercount:=writercount-1;if writercount=0 then signal(S);signal(wcmutex);until falseendrcmutex:读者进程中用于readercount变量的互斥访问wcmutex:写者进程中用于writercount变量的互斥访问wmutex: 用于读者与写者、写者与写者之间的互斥访问读者与第一个写者竞争S信号量。一旦读者获得S信号量，那么直到所有读者执行结束由最后一个写者释放，而每个读者执行结束都释放，所以写者优先读者执行。读者-写者问题(限定读者数)主程序Var RN:integer:=10;rmax,wmutex:semaphore:=RN,1;beginparbeginreader1;readeri;readerM;writer1;writerj;writerN;parendend读者readeribeginrepeat=Swait(rmax,1,1,wmutex,1,0);Swait(rmax,1,1);Swait(wmutex,1,0);Perform read operation;Ssignal(rmax,1);until false;end写者writerjbeginrepeatSwait(wmutex,1,1, rmax,RN,0);Perform write operationSignal(wmutex);until falseendRN:限定最多同时读的读者数rmax:空位置的数目，即系统还允许执行读操作的读者数，超过这个数目后读者将等待wmutex: 用于读者与写者、写者与写者之间的互斥访问读者执行Swait(wmutex,1,0)保证无写者(wmutex值保持不改变)写者执行Swait(wmutex,1,1,rmax,RN,0)保证既无写者在写又无读者在读(rmax值保持不变)哲学家进餐问题主程序Var chopstick:array0,4 of semaphore:=1,1,1,1,1;beginparbeginphilosopher0;philosopheri; philosopher4;parendend哲学家进餐问题子程序基于AND信号量机制philosopheribeginrepeatThink;Swait(chopstick(i+1) mod 5,chopsticki);Eat;Ssignal(chopstick(i+1)mod 5,chopsticki);until falseend哲学家进餐问题子程序限制哲学家同时进餐人数philosopherivar pmax:semaphore:=4;beginrepeatwait(pmax);wait(chopsticki);wait(chopstick(i+1) mod 5);Eat;signal(chopstick(i+1) mod 5);signal(chopsticki);signal(pmax);Think;until falseend理发师问题描述如下：理发店包含一间接待室和一间工作室，接待室内有n(n=1)把椅子，而工作室只有一把椅子。如果没有顾客，理发师就去睡觉，如果顾客来时所有的椅子都有人，那么顾客离去；如果理发师在忙且接待室有空闲的椅子，那么此顾客会坐在其中一把空闲的椅子上等待；如果理发师在睡觉，则顾客会唤醒他。请采用信号量机制解决该理发师问题(可采用伪代码描述)。解：要求描述理发师和顾客的行为，因为需要两类进程Barber()和Customer()分别描述理发师和顾客的行为。理发师和顾客之间是同步的关系，理发师和椅子使临界资源，所以顾客之间是互斥的关系。引入3个信号量和一个控制变量： 控制变量waiting也用于记录等候的顾客数，实际上是customers的一份拷贝。之所以使用waiting是因为无法读取信号量的当前值，初值均为0。 信号量customers用来记录等候理发的顾客数(不包括正在理发的顾客)，并用作阻塞理发师进程，初值为0。 信号量barbers用来记录正在等候顾客的理发师数（为0或1），并用作阻塞顾客进程，初值为0。 信号量mutex用于对waiting的访问进行互斥，初值为1。进入理发店的顾客必须先看等候的顾客数，如果少于椅子数（n），他坐下来等，否则他就离开。PV操作代码如下: int waiting=0; / 等候理发的顾客数(还没理发的), 0nsemaphore customers=0, barbers=0, mutex=1; barber() while(TRUE) / 理完一人,还有顾客吗? P(customers); / 若无顾客,理发师睡眠P(mutex); / 进程互斥waiting := waiting -1; / 等候顾客数少一个V(barbers); / 理发师去为一个顾客理发V(mutex); / 开放临界区 cut-hair( ); / 正在理发(非临界区操作) customer() /顾客进入理发店P(mutex); /进程互斥if (waiting n) /还有空位 waiting := waiting+1; /等候顾客数加1V(customers); /有顾客了，如果理发师在睡则唤醒V(mutex);/开放临界区P(barbers); /无理发师, 顾客坐着养神get-haircut( ); /一个顾客坐下等待理发 else V(mutex);/顾客已满，离开应用类型知识要点二：分页存储地址结构及地址变换 分页存储管理地址结构(由硬件机制决定) 31 12 11 0页 号页内地址 逻辑地址与页号及页内偏移地址之间的换算PageNo=INTAddr/PageLengthPageOffset=Addr mod PageLength举例：对于1KB页面，若给定逻辑地址2170B，则PageNo=2，PageOffset=122 地址变换任务 关键在于页号到物理块号之间的转变 地址映射某虚拟存储器的用户编程空间共32个页面，每页1K，主存为16K。假定某时刻用户页表中已调入主存的页面的虚页号和物理页号对照表如图所示，则当虚地址为十六进制0A5C时，对应的物理地址是多少？虚页号物理页号041102437解：虚拟地址(0A5C)=(10*16+5*16+12)页号=INT2652/1K=2，其物理块号为4 页内偏移=2652 mod 1K = 604物理地址为4*1K+604=(4700) =(125C) 应用类型知识要点三：分页存储与数据访问时间假定快表检索时间为20ns，内存访问时间为100ns，则若能在快表中找到CPU给出的页号，CPU存取一个数据将需要(100+20)=120ns，若不能在快表中找到CPU给出的页号，则为存取一个数据将需要(100+100+20)=220ns。进一步说，若假定快表查找命中率为80%，则其有效访问时间为120*80%+220*(1-80%)=140ns。应用类型知识要点四：页面置换算法与缺页次数 最佳置换算法OPT(向前看页面引用序列)基本思想：选择永不使用或是在最长时间内不再被访问(即据现在最长时间才会被访问)的页面淘汰出内存评价：理想化算法，具有最好性能(对于固定分配方式，本法可保证获得较低的缺页率)，但实际上却难于实现，故主要用于算法评价参照70120304230321201701777222222222222227770000004440000000000111333333331111111某进程分配获得三个物理块采用预调页策略(区别预调页策略与请求调页策略)，前3个页面预先装入第一行为页面访问(引用)序列第二、三、四行为内存页面分布情况，前三列页面预先装入缺页中断次数为6次，缺页率30%缺页率=(发生缺页次数/页面序列长度)*100% 先进先出置换算法FIFO(向回看页面分布情况)基本思想：选择最先进入内存即在内存中驻留时间最久的页面换出到外存。进程已调入内存的页面按进入先后次序链接成一个队列，并设置替换指针以指向最老页面。评价：简单直观，但不符合进程实际运行规律，性能较差，故实际应用极少。70120304230321201701777222244400000007770000333222221111100111100033333222221某进程分配获得三个物理块采用预调页策略(区别预调页策略与请求调页策略)，前3个页面预先装入第一行为页面访问(引用)序列第二、三、四行为内存页面分布情况，前三列页面预先装入缺页中断次数为12次，缺页率68%缺页率=(发生缺页次数/页面序列长度)*100% 最近最久未使用置换算法LRU(向回看页面引用序列)(硬件支持)基本思想：以“最近的过去”作为“最近的将来”的近似，选择最近一段时间最长时间未被访问的页面淘汰出内存。评价：适用于各种类型的程序，性能较好，但需要较多的硬件支持。70120304230321201701777222244400011111110000000033333300000111333222222222777某进程分配获得三个物理块采用预调页策略(区别预调页策略与请求调页策略)，前3个页面预先装入第一行为页面访问(引用)序列第二、三、四行为内存页面分布情况，前三列页面预先装入缺页中断次数为9次，缺页率45%缺页率=(发生缺页次数/页面序列长度)*100% 简单CLOCK置换算法(NRU)(硬件支持) 改进型CLOCK置换算法(硬件支持)评价：与简单CLOCK算法相比，可减少磁盘的I/O操作次数，但淘汰页的选择可能经历多次扫描(最多3轮加1次)，故实现算法自身的开销增大。 最少使用置换算法(硬件支持)基本思想：为内存各页设置一个以为寄存器用于记录对应被访问频率。选择在最近时期使用最少的页面作为淘汰页。评价：鉴于仅用一位寄存器有限各位来记录页面使用会导致访问一次与访问多次的等效性，本算法并不能真实全面地反映页面适用情况。应用类型知识要点五：文件结构与记录检索次数 索引顺序文件组织方式检索开销分组大小 两级索引顺序文件组织方式主文件分组大小低级索引表分组大小检索开销 顺序文件(定长记录顺序文件/变长记录顺序文件)1 逻辑记录的排序(与关键字次序一致与否)串结构与顺序结构2 顺序文件读写操作读写指针RWptr对应记录逻辑地址定长记录RWptr+=recordLength变长纪录RWptr+=currentRecordLength(无法实现随机存取)3 顺序文件评析适于批量存取及磁带介质交互应用场合单个记录操作低效 索引文件组织及检索机制(主要解决变长记录文件无法实现随机存取问题)记录号本身的物理含义很弱，强调真正具有物理含义的关键字索引表本身是定长记录顺序文件 索引顺序文件检索效率分析对于拥有N条记录的主数据文件，若基于顺序查找法来检索具有指定关键字的记录，不同文件组织方式下的系统检索开销比较(假设不存在查找失败的情况)1 顺序文件组织方式(N+1)/2条(顺序查找)2 索引文件组织方式(N+1)/2条(顺序查找)3 索引顺序文件组织方式+1(分组大小记录，此时检索效率最高)4 举例说明(N=10000) 基于多级索引的索引顺序文件(分组大小)建立多级索引以进一步提高检索效率举例说明(N=10)1 索引顺序文件组织方式检索开销1001条分组大小1000条记录2 两级索引顺序文件组织方式主文件分组大小100条记录低级索引表分组大小100条记录检索开销151.5条应用类型知识要点六：文件分配表占用空间关键计算盘块总数(实际操作系统按簇分配，这里按盘块分配)磁盘有多少个盘块，FAT中就有多少个表项(前提是按盘块分配)FAT表项应足以表示最大的盘块号文件分配表空间开销计算设定盘块大小为1KB对于1.2M的软盘，共有盘块1.2M/1KB=1.2K(2,2)(取4的倍数且较大的那个)故文件分配表表项取12位即1.5B所以FAT共需空间1.2K*1.5B=1.8KB对于200M的硬盘，共有盘块200M/1KB=200K(2,2)故文件分配表表项取20位即2.5B所以FAT共需空间200K*2.5B=500KB应用类型知识要点七：索引分配与文件最大长度两级/多级索引分配基本思想对于太大的文件和索引块太多时，直接用链接指针来链接索引块的方法显然是低效的，为此应引入多级索引分配方式允许文件最大长度两级索引、盘块大小1KB、盘块号占4B，则一个索引块可含1KB/4B=256个盘块号，于是两级索引最多可含256*256=64K个盘块号，允许文件最大长度为64MB混合分配方式(UNIX系统4KB、4MB、4GB、4TB)直接寻址直接地址项存放对应文件数据的盘块的盘块号盘块大小4KB、盘块号占4B，则支持长度在4KB*10=40KB以内的文件一次间接寻址addr(10)指向对应文件的一级索引块一级索引块可含4KB/4B=1K个盘块号，故支持长度在(4KB*1K=4MB)+40KB以内的文件多次间接寻址addr(11)、i.addr(12)分别指向对应文件的两级索引和三级索引块，所以支持的文件长度可达(4KB*1K*1K*1K=4TB)+(4KB*1K*1K=4GB)+4MB+40KB应用类型知识要点八文件查找与磁盘启动次数假定每次启动磁盘只装入一个目录盘块盘块大小1KB，文件目录共3200个FCB引入索引结点前FCB占64B，每盘块包含16个FCB，文件目录共需占用200个盘块，故查找一个文件平均需启动磁盘100.5次(顺序查找)引入索引结点后FCB占16B(文件名和索引结点指针分别占用14B和2B)，每盘块包含64个目录项，文件目录共需占用50个盘块，故查找一个文件平均需启动磁盘25.5+1次(顺序查找，读索引结点取地址信息只需一次，因为索引结点在外存上是连续存放的)应用类型知识要点九：银行家算法及资源分配管理产生死锁的必要条件1 互斥条件2 请求和保持条件3 不剥夺条件4 环路等待条件死锁预防(要求进程的资源分配是静态的)死锁预防的方法是使四个必要条件中的第2、3、4个条件之一不能成立，来避免发生死锁。至于条件1，因为它是设备的固有特性所决定的，不仅不能改变，还应加以保证。死锁避免允许进程动态地申请资源，但系统在进行资源分配之前，应首先就资源分配的安全性进行检查，且仅当确认此次分配不会导致系统进入不安全状态时才可分配，否则予以拒绝。死锁避免基本概念安全状态系统可按某种进程序列(称之为安全分配序列)来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程均能顺利完成。不安全状态系统无法找到一个安全分配序列的系统状态。死锁与状态安全性之间的关系1. 并非所有不安全状态都是死锁状态2. 当系统进入不安全状态后，便可能陷入死锁3. 只要保证系统处于安全状态，便可避免死锁安全状态及向不安全状态的转换资源名称资源总数可用资源量可用资源量磁带机1232进程最大需求已分配(尚需)已分配(尚需)P1105(5)5(5)P242(2)2(2)P392(7)3(6)T0时刻存在安全分配序列若在T0时刻应进程请求将所剩磁带机中的1台分配给P3，则系统进入不安全状态(如上图)银行家算法之数据结构(下标i对应进程，下标j对应资源)可用资源向量/请求向量ml Availablej=k表示系统现有k个Rj类资源l Requestj=k表示进程Pi请求k个Rj类资源最大需求矩阵/分配矩阵/需求矩阵n,ml Maxi,j=k表示进程Pi最多需要k个Rj类资源l Allocationi,j=k表示进程Pi已分配k个Rj类资源l Needi,j=k表示进程Pi尚需k个Rj类资源工作向量m/Finish布尔向量nl Workj=k表示系统”可”提供k个Rj类资源l Finishi表示进程Pi可否拥有足够资源完成运行银行家算法之主体算法1. 进程Pi发出资源请求Request2. 若非RequestNeedi，出错返回3. 若非RequestAvailable，则应使Pi等待并返回4. 系统试探性地满足Pi请求，并作以下修改： Available=Available-Request Allocationi=Allocationi+Request Needi=Needi-Request5. 系统调用安全性算法进行资源分配检查，若安全则执行分配，否则恢复试探分配前状态，并使Pi等待银行家算法之安全性子算法另Work=Available，Finish=FALSE从进程集合中查找一个满足Finishi=FALSE且NeediWork的进程。若找到，则可假定Pi能获得所需资源并顺利执行，故有：Work=Work+AllocationiFinishi=TRUE然后重复执行第2步；否则转至第3步执行如果Finish=TRUE，则表示系统处于安全状态；否则系统处于不安全状态银行家算法应用举例之一(无任何进程发出资源申请)进程MAXAllocationNeedWorkAllocation+WorkFinishABCABCABCABCABCP0753010743745755TRUEP1322200122332532TRUEP29023026007551057TRUEP3222211011532743TRUEP4433002431743745TRUE系统资源总量AvailableA,B,C=10,5,7T0时刻Available A,B,C=3,3,2安全分配序列？1. Work= Available=3,3,2可满足P1或P3，先满足P1(如果P1走不通，再看P3)2. Work=5,3,2，满足P33