操作系统复习课

1、第二章第二章 进程的描述和控制进程的描述和控制semaphore mutex=20while(1)wait(mutex)；进入售票厅；进入售票厅；购票；购票；退出售票厅；退出售票厅；signal(mutex)；司机：司机： while(1)while(1) 正常行车；正常行车； 到站停车；到站停车； signal(open)signal(open)； wait(run)wait(run)； 启动开车；启动开车； 售票员：售票员：While(1)While(1) 售票；售票； wait(open)wait(open)； 开车门；开车门； 关车门；关车门； signal(run)signal(ru

2、n)； 用用2个私有信号量个私有信号量open、run分别表示分别表示和和由于初始状态是由于初始状态是汽车行车和售票汽车行车和售票员员售票，所以初值应该都为售票，所以初值应该都为0，到站后才会有司，到站后才会有司机发消息让开门机发消息让开门n例例3：桌子上有一只盘子，每次只能放一桌子上有一只盘子，每次只能放一只水果。爸爸专向盘子中放苹果，妈妈只水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，一个儿子专等吃盘专向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的子中的橘子，一个女儿专等吃盘子中的苹果。用苹果。用PV操作实现他们之间的同步机操作实现他们之间的同步机制。制。fathe

3、rfathermothermothersonsondaughterdaughtersemaphore empty=1, orange = 0, apple=0；orange是son的私有信号量，表示盘子中是否放入橘子。empty是father、mother的私有信号量，表示盘子是否为空。apple是daughter的私有信号量，表示盘子中是否放入苹果。father( )while(1) P (empty); 向盘子中放苹果；向盘子中放苹果； V (apple);Daughter( )while(1) P (apple); 从盘子中取苹果；从盘子中取苹果； V (empty);Mother( )

4、while(1) P (empty); 向向盘子中放橘子；盘子中放橘子； V (orange);son( )while(1) P (orange); 从从盘子中取橘子；盘子中取橘子； V (empty);例例4：三个进程三个进程P1、P2、P3互斥使用一互斥使用一个包含个包含N（N0）个单元的缓冲区。）个单元的缓冲区。P1每次用每次用produce( )生成一个正整数并用生成一个正整数并用put( )送入缓冲区某一空单元中；送入缓冲区某一空单元中；P2每每次用次用getodd ( ) 从该缓冲区中取出一个奇从该缓冲区中取出一个奇数并用数并用countodd ( ) 统计奇数个数；统计奇数个数；

5、P3每次用每次用geteven ( )从该缓冲区中取出一个从该缓冲区中取出一个偶数并用偶数并用counteven ( )统计偶数个数。统计偶数个数。请用信号量机制实现这三个进程的同步请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义的信号量的与互斥活动，并说明所定义的信号量的含义。要求用伪代码描述。（含义。要求用伪代码描述。（2009年考年考研题）研题）semahpore empty=N,even=0,odd=0,mutex=1;P1( ):while(1) x=produce(); wait(empty); wait(mutex); put(x); if x%2=0signal(ev

6、en);elsesignal(odd); signal(mutex); P2( ):while(1)wait(odd);wait(mutex);getodd();countodd();signal(mutex);signal(empty);P3( ):while(1)wait(even);wait(mutex);geteven();counteven();signal(mutex);signal(empty);例例5：一个供应商用汽车给某超市送货，并一个供应商用汽车给某超市送货，并把汽车上的货物用超市的三轮车运到仓库中。把汽车上的货物用超市的三轮车运到仓库中。超市的工作人员也用三轮车从仓库中取

7、货去超市的工作人员也用三轮车从仓库中取货去出售。假设共有出售。假设共有3辆三轮车，仓库中只能容辆三轮车，仓库中只能容纳纳10辆三轮车的货物，且每次从汽车上取货辆三轮车的货物，且每次从汽车上取货只能供给一辆三轮车，仓库也只能容纳一辆只能供给一辆三轮车，仓库也只能容纳一辆三轮车进入。考虑相关信号量的定义及初值，三轮车进入。考虑相关信号量的定义及初值，并写出用并写出用P、V操作实现向仓库中送货及从仓操作实现向仓库中送货及从仓库中取货的同步算法。库中取货的同步算法。 信号量定义及初始值：信号量定义及初始值：S=3(控制三轮车数量控制三轮车数量)mutex1=1（控制互斥访问汽车）（控制互斥访问汽车）

8、mutex2=1（控制互斥访问仓库）（控制互斥访问仓库） empty=10（仓库容量）（仓库容量） full=0（仓库现有库存量，供给超市）（仓库现有库存量，供给超市）从汽车到仓库进程：从汽车到仓库进程：P(empty);P(S);P(mutex1);从汽车上取货；从汽车上取货；V(mutex1);去仓库；去仓库；P(mutex2);入仓库装货；入仓库装货；V(mutex2);V(S);V(full);从仓库到超市进程：从仓库到超市进程：P(full);P(S);P(mutex2);从仓库取货；从仓库取货；V(mutex2);V(empty);去超市；去超市；V(S);例例6：a，b两点之间是

9、一段东西向的单行车道，现两点之间是一段东西向的单行车道，现要设计一个自动管理系统，管理规则如下：当要设计一个自动管理系统，管理规则如下：当ab之间有车辆在行驶时同方向的车可以同时驶入之间有车辆在行驶时同方向的车可以同时驶入ab段，但另一方向的车必须在段，但另一方向的车必须在ab段外等待；当段外等待；当ab之之间无车辆在行驶时，到达间无车辆在行驶时，到达a点点(或或b点点)的车辆可以的车辆可以进入进入ab段，但不能从段，但不能从a点和点和b点同时驶入，当某方点同时驶入，当某方向在向在ab段行驶的车辆驶出了段行驶的车辆驶出了ab段且暂无车辆进入段且暂无车辆进入ab段时，应让另一方向等待的车辆进入段

10、时，应让另一方向等待的车辆进入ab段行驶。段行驶。请用信号量为工具，对请用信号量为工具，对ab段实现正确管理以保证段实现正确管理以保证行驶安全。行驶安全。 解析：解析：读者读者写着问题的变形。我们设置写着问题的变形。我们设置3个信个信号量号量S1、S2和和Sab，分别用于从分别用于从a点进入的车互点进入的车互斥访问共享变量斥访问共享变量ab（用于记录当前（用于记录当前ab段上由段上由a点点进入的车辆的数量），从进入的车辆的数量），从b点进入的车互斥访问点进入的车互斥访问共享变量共享变量ba（用于记录当前（用于记录当前ab段上由段上由b点进入的点进入的车辆的数量）和车辆的数量）和a、b点的车辆互

11、斥进入点的车辆互斥进入ab段。段。3个信号量的初值分别为个信号量的初值分别为1、1和和1。两个共享变量两个共享变量ab和和ba的初值分别为的初值分别为0、0void Pab () while(1) wait(S1); if(ab=0) wait(Sab); ab=ab+1; signal(S1); 车辆从车辆从a点驶向点驶向b点点; wait(S1); ab=ab-1; if(ab=0) signal(Sab); signal(S1); void Pba () while(1) wait(S2); if(ba=0) wait(Sab); ba=ba+1; signal(S2); 车辆从车辆从b

12、点驶向点驶向a点点; wait(S2); ba=ba-1; if(ba=0) signal(Sab); signal(S2); 进程进程到达时间到达时间服务时间服务时间 A03B26C44D65E82例例1：假设假设一个系统有一个系统有5个进程，他们的到达时间和服个进程，他们的到达时间和服务时间如上表所示，忽略务时间如上表所示，忽略I/O以及其他的开销时间，以及其他的开销时间，若分别按若分别按先来先服务（先来先服务（FCFS）、非抢占式非抢占式及及抢占的抢占的短进程优先（短进程优先（SPF）调度算法进行调度算法进行CPU调度，请给出调度，请给出各进程的完成时间、周转时间、带权周转时间、平均各进

13、程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间。周转时间和平均带权周转时间。 第三章第三章 处理机调度与死锁处理机调度与死锁FCFSSPF非抢占非抢占SPF抢占抢占51015200A(3)进程运行示意图进程运行示意图B(6)C(4)D(5)E(2)BCDEA时间时间调度算法调度算法AA(3)BB(6)CDEE(2)C(4)D(5)ABCA(3)B(1)DC(4)EE(2)B(5)D(5)进程进程到达时间到达时间服务时间服务时间 A03B26C44D65E82进程进程ABCDE平均平均到达时间到达时间02468服务时间服务时间36452FCFS完成时间完成时间3913182

14、0周转时间周转时间37912128.6带权周转带权周转时间时间11.172.252.462.56SPF（非抢占）（非抢占）完成时间完成时间39152011周转时间周转时间37111437.6带权周转带权周转时间时间11.172.752.81.51.84SPF（抢占）（抢占）完成时间完成时间31582010周转时间周转时间31341427.2带权周转带权周转时间时间12.1612.811.59例例2：有有4个进程个进程P1，P2，P3，P4，它们进入就绪，它们进入就绪队列的先后次序为队列的先后次序为P1、P2、P3、P4，它们的优先，它们的优先数和需要的处理器时间如下表所示。假定这四个进数和需要

15、的处理器时间如下表所示。假定这四个进程执行过程中不会发生等待事件，忽略进程调度等程执行过程中不会发生等待事件，忽略进程调度等所花费的时间，从某个时刻开始进行调度，请回答所花费的时间，从某个时刻开始进行调度，请回答下列问题：下列问题：写出分别采用写出分别采用“先来先服务先来先服务” 、 “非抢占式优先数非抢占式优先数”（固定优先数，优先数大者优先级高）及（固定优先数，优先数大者优先级高）及 “时间片时间片轮转轮转”（时间片大小为（时间片大小为5）三种调度算法选中进程执）三种调度算法选中进程执行的次序、计算出各进程在就绪队列中的等待时间行的次序、计算出各进程在就绪队列中的等待时间以及平均等待时间。

16、以及平均等待时间。进进 程程处理器时间处理器时间优先数优先数P183P261P3225P444解析解析(1)先先来先服务算法选择进程的顺序依次为来先服务算法选择进程的顺序依次为P1、P2、P3、P4。 进程进程P1等待时间为等待时间为0； 进程进程P2等待时间为等待时间为8； 进程进程P3等待时间为等待时间为8+6=14； 进程进程P4等待时间为等待时间为8+6+22=36。 平均平均等待时间为（等待时间为（0+8+14+36）/4=14.5(2)非非抢占式的优先数算法选择进程的顺序依次为抢占式的优先数算法选择进程的顺序依次为P3、P4、P1、P2。进程进程P1等待时间为等待时间为4+22=2

17、6；进程进程P2等待时间为等待时间为22+4+8=34；进程进程P3等待时间为等待时间为0；进程进程P4等待时间为等待时间为22。平均等待时间为（平均等待时间为（26+34+0+22）/4=20.5(3)时间片时间片轮转进程调度顺序为轮转进程调度顺序为P1、P2、P3、P4、P1、P2、P3、P3、P3、P3。进程进程P1等待两次，时间为等待两次，时间为0+（5+5+4）=14；进程进程P2等待两次，时间为等待两次，时间为5+（5+4+3）=17；进程进程P3等待两次，时间为（等待两次，时间为（5+5）+（4+3+1）=18；进程进程P4等待等待1次，时间为次，时间为5+5+5=15。平均等待

18、时间为（平均等待时间为（14+17+18+15）/4=16存储器管理存储器管理例例1：设设某计算机的逻辑地址空间和物理地址空间某计算机的逻辑地址空间和物理地址空间均为均为64KB.按字节编址。若某进程最多需要按字节编址。若某进程最多需要6页页（Page）数据存储空间，页的大小为）数据存储空间，页的大小为1KB.操作操作系统采用固定分配局部置换策略为此进程分配系统采用固定分配局部置换策略为此进程分配4个个页框（页框（Page Fame）。）。 页号页号页根号页根号装入时刻装入时刻访问位访问位071301142301222001391601 当该进程执行到时刻当该进程执行到时刻260时，要访问逻辑

19、地址为时，要访问逻辑地址为17CAH的数据，请问答下列问题：的数据，请问答下列问题： （1）该逻辑地址对应的页号是多少？该逻辑地址对应的页号是多少？ （2）若采用先进先出（若采用先进先出（FIFO）置换算法，该逻辑地）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。址对应的物理地址是多少？要求给出计算过程。（3）若采用时钟（若采用时钟（CLOCK）置换算法，该逻辑地址）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针沿顺时针方向移动，且当前指向下一页的指针沿顺时针方向移动，且当前指向2号页框，号页框，示

20、意图如下。）示意图如下。） 3号页号页2号页号页0号页号页1号页号页9号页框号页框7号页框号页框4号页框号页框2号页框号页框(1) 逻辑逻辑地址空间为地址空间为64KB，则逻辑地址为，则逻辑地址为16位，位，因为页大小为因为页大小为1K，所以页内偏移地址为，所以页内偏移地址为10位，位，因此高因此高6位是页号。位是页号。17CAH=(0001 0111 1100 1010)2，所以逻辑地址，所以逻辑地址17CAH对应的页号为对应的页号为5。(2) 若若采用先进先出（采用先进先出（FIFO）置换算法，则被置）置换算法，则被置换的页面所在页框为换的页面所在页框为7，所以对应的物理地址，所以对应的物

21、理地址为为(0001 1111 1100 1010)2=1FCAH。(3)若采用时钟（若采用时钟（CLOCK）置换算法，则被置换）置换算法，则被置换的页面所在页框为的页面所在页框为2，所以对应的物理地址，所以对应的物理地址为为(0000 1011 1100 1010)2=0BCAH。作业作业1 1 某采用分页存储管理的系统中，物理地址占某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占位，逻辑地址中页号占6位，页大小为位，页大小为1KB，问：该系统的内存空间大小为多少？，问：该系统的内存空间大小为多少？每块的大小为多少？逻辑地址共几位，每个每块的大小为多少？逻辑地址共几位，每个作业

22、最大长度为多少？若作业最大长度为多少？若0页放在页放在3块中，块中，1页放在页放在7块中，块中，2页放在页放在9块中，逻辑地址块中，逻辑地址0420H对应的物理地址是多少？对应的物理地址是多少？ 解析解析内存内存空间大小为空间大小为1MB，每块的大小，每块的大小为为1KB，逻辑地址，逻辑地址16位，每个作业最大长位，每个作业最大长度为度为64KB，逻辑地址，逻辑地址0420H对应的物理对应的物理地址地址1C20H。作业作业2 2 已知某分页系统，主存容量为已知某分页系统，主存容量为64K，页面大，页面大小为小为1K，对一个，对一个4页大的作业，其页大的作业，其0、l、2、3页分别被分配到主存的

23、页分别被分配到主存的2、4、6、7块中。块中。 (1) 将十进制的逻辑地址将十进制的逻辑地址1023、2500、4500转换成物理地址。转换成物理地址。 (2) 以十进制的逻辑地址以十进制的逻辑地址1023为例画出地为例画出地址变换过程图。址变换过程图。 逻辑地址逻辑地址1023：10231K，得到页号为，得到页号为0，页内地，页内地址为址为1023，查页表找到对应的物理块号为，查页表找到对应的物理块号为2，故物理地址，故物理地址为为21K+1023=3071。 逻辑地址逻辑地址2500：25001K，得到页号为，得到页号为2，页内地，页内地址为址为452，查页表找到对应的物理块号为，查页表找

24、到对应的物理块号为6，故物理地址为，故物理地址为6IK+452=6596。 逻辑地址逻辑地址3500：3500IK，得到页号为，得到页号为3，页内地，页内地址为址为428，查页表找到对应的物理块号为，查页表找到对应的物理块号为7，故物理地址为，故物理地址为71K+428=7596。 逻辑地址逻辑地址4500：45001K，得到页号为，得到页号为4，页内地，页内地址为址为404，因页号不小于页表长度，故产生越界中断，因页号不小于页表长度，故产生越界中断。 (2)逻辑地址逻辑地址1023的地址变换过程如下图所示，其中的地址变换过程如下图所示，其中的页表项中没考虑每页的访问权限。的页表项中没考虑每页

25、的访问权限。第七章第七章 文件管理文件管理例例1：设设文件索引节点中有文件索引节点中有7个地址项，其中个地址项，其中4个地个地址项是直接地址索引，址项是直接地址索引，2个地址项是一级间接地址个地址项是一级间接地址索引，索引，1个地址项是二级间接地址索引，每个地址个地址项是二级间接地址索引，每个地址项大小为项大小为4B。若磁盘索引块和磁盘数据块大小均为。若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度，则可表示的单个文件最大长度是是( ) 。 A33KB B519KB C1 057KB D16 513KB解析：解析：C。考查磁盘文件的大小性质。考查磁盘文件的大小性质 因因每个

26、磁盘索引块和磁盘数据块大小均为每个磁盘索引块和磁盘数据块大小均为256B。所以所以4个直接地址索引指向的数据块大小为个直接地址索引指向的数据块大小为4256B。2个一级间接索引共包括个一级间接索引共包括2(2564)个直个直接地址索引，即其指向的数据块大小为接地址索引，即其指向的数据块大小为2(2564)256B。1个二级间接地址索引所包含的个二级间接地址索引所包含的直接地址索引数为直接地址索引数为(2564)(2564)，即其所指向，即其所指向的数据块大小为的数据块大小为(2564) (2564)256B。即。即7个地个地址项所指向的数据块总大小为址项所指向的数据块总大小为4256+2(25

27、64)256+(2564)(2564)256= 1082368B=1057KB。盘块大小：盘块大小：1KB盘块号：盘块号：4B一个索引块可存放一个索引块可存放256个盘块号个盘块号两级索引支持的最大文件长度：两级索引支持的最大文件长度：256*256*1K=64M盘块大小：盘块大小：4KB两级索引支持的最大文件长度：两级索引支持的最大文件长度：1K*1K*4K=4G2009年考研年考研下列文件物理结构中，适合下列文件物理结构中，适合随机访问且易于文件扩展的是随机访问且易于文件扩展的是( ) 。 A连续结构连续结构 B索引结构索引结构 C链式结构且磁盘块定长链式结构且磁盘块定长 D链式结构且磁盘

28、块变长链式结构且磁盘块变长 2. 索引结点索引结点1) 1) 索引结点的引入索引结点的引入 例：一个例：一个FCB为为64B，盘块大小为，盘块大小为1KB。若。若一个文件目录共有一个文件目录共有640个个FCB，则平均查，则平均查找一个文件需启动磁盘多少次？找一个文件需启动磁盘多少次？ 一个盘块可存放一个盘块可存放FCB个数：个数：1KB/64B=16 该文件目录占用盘块数：该文件目录占用盘块数：640/16=40 平均查找一个文件需启动磁盘平均查找一个文件需启动磁盘40/2=20次次目录占用目录占用N个盘块，则个盘块，则查找一个文件平均调入查找一个文件平均调入盘块盘块(N+1)/2次次由于在

29、检索目录文件的过程中，只用到由于在检索目录文件的过程中，只用到了了文件名文件名，用不到该文件的描述信息。仅当，用不到该文件的描述信息。仅当找到与指定文件名相匹配的目录项时，才需找到与指定文件名相匹配的目录项时，才需从该目录项中读出该文件的物理地址。从该目录项中读出该文件的物理地址。 因此，因此，有些系统如有些系统如UNIX，采用了把，采用了把文件名文件名与与文件文件描述信息描述信息分开的办法。即分开的办法。即把文件描述信息单把文件描述信息单独形成一个称为独形成一个称为索引结点索引结点的数据结构的数据结构，简称，简称i结点；而在文件目录中的每个目录项，则仅结点；而在文件目录中的每个目录项，则仅由由文件名文件名及指向该文件所对应的及指向该文件所对应的i结点的结点的指针指针所构成。所构成。 例例246某文件系统空间的最大容量为某文件系统空间的最大容量为4TB（1TB=240B），以磁盘块为基本分配单位。磁盘块大小），以磁盘块为基本分配单位。磁盘块大小为为1KB。文件控制块（。文件控制块（FCB）包含一个