OS操作系统总复习及最后补充试题-北航版

1、北航计算机学院 任爱华补充习题补充习题一、一、 作业的周转时间作业的周转时间二、二、 计算作业周转时间计算作业周转时间三、三、 P/VP/V操作例子操作例子四、四、 银行家算法银行家算法五、五、 存储分配与地址变换存储分配与地址变换六、六、 磁盘调度及设备管理概念磁盘调度及设备管理概念七、七、 磁盘空闲块的成祖分配算法磁盘空闲块的成祖分配算法八、八、 概念复习题概念复习题 北航计算机学院 任爱华练习题练习题l一个32位的虚拟存储系统有两级页表，其逻辑地址中，第22到31位是第一级页表，12位到21位是第二级页表，页内偏移占0到11位。一个进程的地址空间为4GB，如果从0XC0000000开始映

2、射4MB大小页表，请问第一级页表所占的4KB空间映射在什么位置，并说明理由。（注意B代表字节，一个32位地址占4字节）北航计算机学院 任爱华一、作业的周转时间一、作业的周转时间作业号作业号 作业作业提交时间提交时间所需所需CPU时间时间（分）（分）作业长度作业长度（KB） 开始开始执行时间执行时间 作业作业完成时间完成时间周转时间周转时间 (分分)T=完成完成提交提交110：002515 210：203060 310：202540 410：301520 510：351030 有有5个作业，到达的时间、所需执行时间、所需存储容量如下表所示。假定个作业，到达的时间、所需执行时间、所需存储容量如下表

3、所示。假定内存容量为内存容量为100KB，采用可变分区存储管理方法，作业在内存中不能移动采用可变分区存储管理方法，作业在内存中不能移动，并且假定内存中的，并且假定内存中的就绪就绪作业作业平分平分CPU时间时间，采用，采用先来先服务先来先服务调度策略，调度策略，试求各作业开始执行的时间、完成的时间和周转时间，并填入表中。（不试求各作业开始执行的时间、完成的时间和周转时间，并填入表中。（不计作业换进换出时间和其它的开销）计作业换进换出时间和其它的开销）10:2510:0010:2511:2010:5011:2011:1511:3011:4011:452560557565平均周转时间平均周转时间 =

4、（25+60+55+75+65）/ 5 = 56（分钟）（分钟）25510北航计算机学院 任爱华二、计算作业周转时间二、计算作业周转时间操作系统中采用多道程序设计技术以提高操作系统中采用多道程序设计技术以提高CPUCPU及各种资源的及各种资源的利用率利用率, , 试以下例比较说明试以下例比较说明. . 假定系统中有一个假定系统中有一个CPU, CPU, 一台一台I/OI/O设备设备, , 二者可同时工作二者可同时工作, , 有三有三个作业个作业X,Y,Z, X,Y,Z, 各自的程序行为是各自的程序行为是: I/OI/O CPUCPU I/OI/O CPUCPU I/OI/O ( (单位单位:

5、: ms)ms) X X 20 20 20 20 20 20 30 30 20 20 Y Y 40 40 30 30 40 40 10 10 Z Z 30 30 20 20 30 30 假若采用单道串行方式调度运行假若采用单道串行方式调度运行, , 总的周转时间是多少总的周转时间是多少? ? 假若采用多道程序设计技术调度假若采用多道程序设计技术调度, , 调度优先权调度优先权X X最高最高, , Y Y其其次次, , Z Z最低最低,当前三个作业都已就绪当前三个作业都已就绪. . 试画出调度时序图试画出调度时序图, , 给出给出各自的以及总的周转时间各自的以及总的周转时间. . 北航计算机学院

6、 任爱华二（续）二（续）各自的周转时间各自的周转时间 X= X=（20+20+20+30+2020+20+20+30+20） =110 (ms) =110 (ms) Y = Y = （20+20+20+30+2020+20+20+30+20）+ +（40+30+40+1040+30+40+10） = 230 (ms) = 230 (ms) Z = Z = （20+20+20+30+2020+20+20+30+20）+ +（40+30+40+1040+30+40+10）+ +（30+20+3030+20+30）=310(ms)=310(ms)总的周转时间总的周转时间=110+230+310=57

7、0=110+230+310=570，平均周转时间平均周转时间=570/3=190=570/3=190各自的周转时间各自的周转时间X:110(ms)X:110(ms) Y:140 (ms)Y:140 (ms)Z:210(ms)Z:210(ms)总的总的=110+140+210=460=110+140+210=460，平均，平均=460/3=460/3 153153 tXYZI/oYYXXXZ I/O I/O CPUCPU I/O I/O CPUCPU I/O ( I/O (单位单位: : ms)ms) X 20 X 20 20 20 20 20 30 30 20 20 Y Y 40 40 30

8、30 40 40 10 10 Z Z 30 30 20 20 30 30 20202020203020304010303020CPU执行时间北航计算机学院 任爱华三、三、P/VP/V操作例子操作例子（司机与售票员）（司机与售票员） 汽车司机与售票员之间必须协同工作汽车司机与售票员之间必须协同工作, , 一方面一方面, , 只有只有售票员把车门关好了售票员把车门关好了,司机才能开车司机才能开车, , 因此因此, , 售票员关售票员关好车门应通知司机开车好车门应通知司机开车; ; 另一方面另一方面, , 只有当汽车已经只有当汽车已经停下停下, , 售票员才能开门上下客售票员才能开门上下客, , 故

9、司机停车后应通知故司机停车后应通知售票员售票员. . 假定某辆公共汽车上有一名司机与两名售票假定某辆公共汽车上有一名司机与两名售票员员. . 汽车当前正在始发站停车上客汽车当前正在始发站停车上客.试设必要的信号试设必要的信号量并赋初值量并赋初值, , 用用P P、V V操作写出他们的同步算法操作写出他们的同步算法. . 北航计算机学院 任爱华三（续）三（续）设信号量为：设信号量为：doorclose=0; busstop=1; doorclose=0; busstop=1; conbeginconbeginDriver:beginDriver:beginrepeatrepeat P(doorc

10、lose);P(doorclose); 开车开车; 到站到站; 停车停车; V(busstop);V(busstop); 乘客上乘客上/ /下车；下车；foreverforever end endconductor:beginconductor:begin repeat repeat P(busstop);P(busstop); 开门开门; 乘客上乘客上/ /下车下车; 售票售票; 关门关门; V(doorclose);V(doorclose); 开车开车; forever forever end endconendconend北航计算机学院 任爱华习题：习题：一个供销商与三个喝冰水者一个供销

11、商与三个喝冰水者口渴的人必须有三样东西口渴的人必须有三样东西:水、冰和茶杯才能喝到冰水。水、冰和茶杯才能喝到冰水。有三个人，每人手中仅有一样上述东西有三个人，每人手中仅有一样上述东西第四个人是服务员第四个人是服务员该人可以无限地提供这三样东西该人可以无限地提供这三样东西没有人喝水时，服务员便没有人喝水时，服务员便随机地随机地提供其中的两样东西提供其中的两样东西放放在桌上在桌上如果这两样东西是口渴的人所需要的，则按需要收起，如果这两样东西是口渴的人所需要的，则按需要收起，便可喝一杯冰水。喝完后则通知服务员，此过程反复进行。便可喝一杯冰水。喝完后则通知服务员，此过程反复进行。写一个管程，控制口渴者

12、和服务员的活动过程。写一个管程，控制口渴者和服务员的活动过程。习题解答：习题解答：一个供销商与三个喝冰水者一个供销商与三个喝冰水者提供冰和水提供杯子和水提供杯子和冰有杯子 glass有水 water有冰 iceProcedure severWhile(true)drinkers. Serve(); Cobeginsever;drinker1;drinker2;drinker3;coendProcedure drinker1While(true)drinkers.GetIngredients(requirements water);drink();drinkers.NotifyServer();

13、 Procedure drinker2While(true)drinkers.GetIngredients(requirements ice) ; drink();drinkers.NotifyServer();Procedure drinker3While(true)drinkers.GetIngredients(requirements glass) ; drink();drinkers.NotifyServer();北航计算机学院 任爱华P/VP/V操作的应用操作的应用l某公司有两个生产部门和一个装配部门，两个生产部门分别生产甲、乙两种零件，装配部门的任务是把甲、乙两种零件组装成产品。两

14、个生产部门每生产一个零件后都要分别把它们送到装配部门的货架S1、S2上。S1存放零件甲，S2存放零件乙，S1和S2均可容纳20个零件。装配人员每次从货架上取一个甲零件和一个乙零件后组装成产品。请用P、V操作进行正确管理。北航计算机学院 任爱华算法描述算法描述Begin 信号量初值：mutex1:=1;mutex2:=1;empty1:=20;empty2:=20;full1:=0;full2:=0CobeginA部门： begin Repeat 生产一个产品A; P(empty1); P(mutex1); 将产品A放入S1; V(mutex1); V(full1); Until false E

15、ndB部门：beginRepeat 生产一个产品B; P(empty2); P(mutex2); 将产品B放入S2; V(mutex2); V(full2);Until falseEnd装配人员：beginRepeat P(full1); P(full2); P(mutex1); 从S1中取出产品A; V(mutex1); V(empty1); P(mutex2); 从S2中取出产品B; V(mutex2); V(empty2); 把A和B组装成产品Until false EndCoendEnd;北航计算机学院 任爱华另一种描述另一种描述? ?Begin A:=1; B:=1;S1:=0;S2

16、:=0; Procedure：Product A: 部门AbeginrepeatWhile (S120) begin P(A); Produce A; S1=S1+1; V(A);EndForeverendProduct B: 部门BbeginrepeatWhile (S20&S20)beginP(A);P(B); S1=S1-1 S2=S2-1 Assembly A and B;V(A);V(B); Endforever endCobegin product A; product B; Assembly;coend北航计算机学院 任爱华四、银行家算法四、银行家算法在银行家算法中，若出现下述的

17、资源分配情况：在银行家算法中，若出现下述的资源分配情况： Process Allocation Need AvailableProcess Allocation Need Available p0 1,0,2,3 7,6,6,1 p0 1,0,2,3 7,6,6,1 3,0,1,4 3,0,1,4 p1 2,1,0,1 6,6,5,7 p1 2,1,0,1 6,6,5,7 p2 1,0,4,1 3,5,1,5 p2 1,0,4,1 3,5,1,5 p3p3 0,3,2,1 3,1,2,80,3,2,1 3,1,2,8 p4 3,2,1,0 3,2,2,5 p4 3,2,1,0 3,2,2,5

18、p5 0,1,2,6 2,0,1,2 p5 0,1,2,6 2,0,1,2当前状态安全吗？当前状态安全吗？ 若进程若进程p3p3提出请求提出请求Request(Request(2,0,1,12,0,1,1) )后，系统能否将资源分配给后，系统能否将资源分配给它？为什么？它？为什么？AvailableAvailable的变化的变化p5p53,1,3,103,1,3,10p3p33,4,5,113,4,5,11p4p46,6,6,116,6,6,11p1p18,7,6,128,7,6,12p0p09,7,8,159,7,8,15p2p210,7,12,1610,7,12,16（1 1）安全！）安全

19、！ need Available need Available P3P3 1,1,1,7 1,1,1,7 1,0,0,31,0,0,3如果满足（如果满足（2 2，0 0，1 1，1 1）请求，则所有其它请求再也无法满足，造成死锁。）请求，则所有其它请求再也无法满足，造成死锁。北航计算机学院 任爱华80KB五、存储分配与地址变换五、存储分配与地址变换某一采用分段虚拟存储管理的系统某一采用分段虚拟存储管理的系统, , 假定假定: (1). (1). 系统提供有序对虚拟字节地址系统提供有序对虚拟字节地址v=(s,d), v=(s,d), 其中其中s s是被访问的虚是被访问的虚地址所在的段号地址所在的

20、段号, , d d是它在该段内的偏移量是它在该段内的偏移量. (2). (2). 段表格式如下段表格式如下: : (3). (3). 内存物理存储的当前分区状内存物理存储的当前分区状态如图态如图:OSJ1J2J3040K80K100K120K160K240K256K其中带斜线者为空闲区其中带斜线者为空闲区/ /40 40K K空区空区/ / /20 20K K空区空区/ /段号段号段长段长(字节字节)是否在内存是否在内存(y或或n)内存起址内存起址(字节字节)20KB空区空区40KB空区空区北航计算机学院 任爱华五续一五续一(4). 系统采用系统采用最佳适应最佳适应的空闲区分配算法的空闲区分配

21、算法. 现在调度进程要调度一个有下述逻辑结构的进程到现在调度进程要调度一个有下述逻辑结构的进程到内存内存请完成请完成: 1. 填写该进程相应的段填写该进程相应的段表信息表信息. 2. 图示虚拟地址图示虚拟地址v的再定的再定位过程位过程. 3. 分别求出主程序段与分别求出主程序段与数据段中字节地址数据段中字节地址4K所对应所对应的物理地址的物理地址. 4. 画出本次调度后的内画出本次调度后的内存分区状态图存分区状态图. (注注: 本题目不考虑淘汰其本题目不考虑淘汰其它进程的分段它进程的分段)0 12k1段子程序段044k0段主程序段06k2段数据段调度进程依段号从小到大的顺序为该进程调度进程依段

22、号从小到大的顺序为该进程分配内存分配内存, 并设法将当前段全部装入内存并设法将当前段全部装入内存. 续二续二段段号号段长段长(字节字节)是否在内是否在内存存(y或或n)内存起址内存起址(字节字节)044Ky1601212Ky1006Ky112 0 4K有效地有效地址址段表地址寄存器+OSJ1J2J3040K80K100K120K160K240K256K164K0段段1段、段、2段段204K/ /36 36K K空区空区/ /2 2K K空区空区36KB空区空区40KB空区空区北航计算机学院 任爱华六、磁盘调度六、磁盘调度进程号进程号磁道号磁道号移动磁道数移动磁道数713401419258232

23、05132256149294016322911419101219034181173159376373339620应用应用SSTF (最短寻道最短寻道时间时间shortest-seek-time-first)调度策略调度策略，某些进程可能永远，某些进程可能永远不能被调度到。如右不能被调度到。如右表所示的例子中，我表所示的例子中，我们假定每当进程们假定每当进程9 （要求读出磁道要求读出磁道376上上的信息）的请求得到的信息）的请求得到服务之前的某段时间服务之前的某段时间，系统又接收一个请，系统又接收一个请求流，而且这些请求求流，而且这些请求所要移动磁头的距离所要移动磁头的距离总小于达到磁道总小于达

24、到磁道376所移动的距离，因而所移动的距离，因而，进程，进程9和和3将永远得将永远得不到服务。不到服务。 试设计一种磁盘访试设计一种磁盘访问调度算法，以确保问调度算法，以确保不会发生诸如上例的不会发生诸如上例的“饥饿饥饿”现象。现象。答：无饥饿现象的磁盘调度算法有答：无饥饿现象的磁盘调度算法有FCFS、扫描算法等等。扫描算法等等。北航计算机学院 任爱华七、七、磁盘空闲块的成组分配算法磁盘空闲块的成组分配算法s-nfree：980 1201 121 96 14597 210 卷资源表卷资源表filsyss-nfree：990 1201 121 96 14597 21098 150 s-nfree

25、：1000 1201 121 96 14597 21098 15099 152 160#参看下图，现有某一进程的文件要释放三个物理块，参看下图，现有某一进程的文件要释放三个物理块，其块号为其块号为150#，152#，160#，试给出其释放过程和释，试给出其释放过程和释放后的卷资源表放后的卷资源表filsys的状况。其后，又有一个文件要的状况。其后，又有一个文件要求分配求分配4个空闲块，试给出其分配过程和分配后的个空闲块，试给出其分配过程和分配后的filsys状况：状况： s-nfree：10 1601 96 97 卷资源表卷资源表filsys北航计算机学院 任爱华七（七（续续） s-nfree

26、：100 0 120 1 121 96 145 97 210 98 150 99 152 160# s-nfree：99 0 120 1 121 96 145 97 210 98 150 s-nfree：98 0 120 1 121 96 145 97 210 卷资源表卷资源表filsys152#150#210#北航计算机学院 任爱华设备管理概念题设备管理概念题1 1、用于设备分配的数据结构有哪些？它们之间的关系是什么、用于设备分配的数据结构有哪些？它们之间的关系是什么? ?答：整个系统有一张答：整个系统有一张SDTSDT，每个设备有一张每个设备有一张DCTDCT，每个控制器有每个控制器有一张

27、一张COCTCOCT，每个通道有一张每个通道有一张CHCTCHCT。2 2、什么是什么是I/OI/O控制？它的主要任务是什么？控制？它的主要任务是什么？答：输入输出处理过程分为两个阶段，即：答：输入输出处理过程分为两个阶段，即：+ 用户用户I/OI/O请求请求分配设备分配设备启动设备进行启动设备进行I/OI/O操作操作+ 响应设备中断响应设备中断设备中断处理设备中断处理从处理从处理I/OI/O请求开始到设备中断处理结束，这一总过程称为请求开始到设备中断处理结束，这一总过程称为I/OI/O控控制。制。SDTDCTCOCTCHCT北航计算机学院 任爱华设备管理概念题续设备管理概念题续3 3、I/O

28、I/O控制可用哪几种方式实现？各有什么优缺点？控制可用哪几种方式实现？各有什么优缺点？答：答：I/OI/O控制过程可用三种方式实现：作为请求控制过程可用三种方式实现：作为请求I/OI/O操作的进程实现；作为当操作的进程实现；作为当前进程的一部分实现；由专门的系统进程（前进程的一部分实现；由专门的系统进程（I/OI/O进程）完成。进程）完成。第一种方式请求对应第一种方式请求对应I/OI/O操作的进程能很快占据处理机，但要求系统和操作的进程能很快占据处理机，但要求系统和I/OI/O操作的进程应具有良好的实时性。第二种方式不要求系统具有高的实时操作的进程应具有良好的实时性。第二种方式不要求系统具有高

29、的实时性，但性，但I/OI/O控制过程要由当前进程负责。第三种方式增加了一个额外的进控制过程要由当前进程负责。第三种方式增加了一个额外的进程开销，但用户进程不用处理程开销，但用户进程不用处理I/OI/O控制过程。控制过程。4 4、设备驱动程序是什么？为什么要有设备驱动程序？用户进、设备驱动程序是什么？为什么要有设备驱动程序？用户进程怎样使用驱动程序？程怎样使用驱动程序？答：设备驱动程序是驱动外部物理设备和相应答：设备驱动程序是驱动外部物理设备和相应DMADMA控制器或控制器或I/OI/O控制器等器件控制器等器件，使之可以直接和内存进行，使之可以直接和内存进行I/OI/O操作的子程序的集合。它们

30、负责设置相应操作的子程序的集合。它们负责设置相应设备有关寄存器的值，启动设备进行设备有关寄存器的值，启动设备进行I/OI/O操作，指定操作的类型和数据流操作，指定操作的类型和数据流向等。向等。设备驱动程序屏蔽了直接对硬件操作的细节，为编程者提供操纵设备的设备驱动程序屏蔽了直接对硬件操作的细节，为编程者提供操纵设备的便利接口。便利接口。用户进程通过调用设备驱动程序提供的接口来使用设备驱动程序。用户进程通过调用设备驱动程序提供的接口来使用设备驱动程序。linux北航计算机学院 任爱华八、八、问题参考问题参考l 操作系统的类型操作系统的类型+每种操作系统追求的目标是什么？每种操作系统追求的目标是什么

31、？+分析操作系统的几种观点强调的侧重点各是什么？分析操作系统的几种观点强调的侧重点各是什么？+分布式系统与网络系统之间的关系分布式系统与网络系统之间的关系l 什么是管态和目态？用户程序如何进入管态执行？什么是管态和目态？用户程序如何进入管态执行？l 什么是特权指令？用户程序可以执行特权指令吗？什么是特权指令？用户程序可以执行特权指令吗？l 什么是系统调用？什么是系统调用？l 什么是进程同步与互斥，什么是进程同步原语？原语的含义？什么是进程同步与互斥，什么是进程同步原语？原语的含义？l 什么是临界区和临界资源？什么是临界区和临界资源？l 什么是什么是PCB?PCB?什么是进程？什么是进程调度？什

32、么是进程？什么是进程调度？l 什么是多道程序设计？什么是死锁以及死锁产生的必要条件是什么？什么是多道程序设计？什么是死锁以及死锁产生的必要条件是什么？l P P、V V操作的定义？实际物理意义？操作的定义？实际物理意义？l 管程的特点管程的特点l 死锁定义、进程资源图的化简方法死锁定义、进程资源图的化简方法l 预防死锁、避免死锁的方法有哪些？预防死锁、避免死锁的方法有哪些？l 什么是高级调度、中级调度和低级调度？什么是高级调度、中级调度和低级调度？l 解释解释DCTDCT、FCBFCB、JCBJCBl 目录项和目录项和FCBFCB的区别是什么？的区别是什么？l 简述页式存储管理的实现原理及其地

33、址变换过程。简述页式存储管理的实现原理及其地址变换过程。l 在分区式存储管理中硬件提供那些支持？在分区式存储管理中硬件提供那些支持？北航计算机学院 任爱华问题参考（续）问题参考（续）l 在页式存储管理中，硬件提供哪些支持？在页式存储管理中，硬件提供哪些支持？l 什么是虚拟存储管理？虚拟存储器的大小受什么限制？什么是虚拟存储管理？虚拟存储器的大小受什么限制？l 那些存储管理技术可用于虚存管理？那些存储管理技术可用于虚存管理？l 什么是虚拟机？什么是虚拟机？l 什么是作业？什么是作业控制块什么是作业？什么是作业控制块l 进程的基本状态有哪些，状态之间的转换的原因是什么？进程的基本状态有哪些，状态之

34、间的转换的原因是什么？l 什么是设备管理中的主设备号和次设备号？什么是设备管理中的主设备号和次设备号？l 中断处理应包括哪些主要步骤？中断处理应包括哪些主要步骤？l 中断与陷阱的区别？中断与陷阱的区别？l 文件的定义文件的定义l 文件的逻辑结构有哪些？文件的逻辑结构有哪些？l 文件的物理组织有哪些？文件的物理组织有哪些？l 描述实现文件的系统的层次结构。描述实现文件的系统的层次结构。l 何谓文件的共享、保护和保密？何谓文件的共享、保护和保密？l 何谓实时信息处理系统和实时控制系统？何谓实时信息处理系统和实时控制系统？l 何谓硬实时？何谓软时实？何谓硬实时？何谓软时实？l 网络与分布式操作系统有

35、何区别？网络与分布式操作系统有何区别？l 进程与程序有何区别？进程与程序有何区别？l 进程与线程有何区别？进程与线程有何区别？25操作系统课程总结操作系统课程总结 第一章第一章 概论概论 第二章第二章 操作系统接口操作系统接口 第三章第三章 进程机制与并发程序设计进程机制与并发程序设计 第四章第四章 存储管理存储管理 第五章第五章 I/O系统系统 第六章第六章 文件系统文件系统26操作系统操作系统-计算机资源管理程序计算机资源管理程序27第一章第一章 概论（概论（1） 存储程序式计算机与操作系统存储程序式计算机与操作系统顺序计算模型顺序计算模型并行计算模型并行计算模型冯冯.诺依曼计算机诺依曼计

36、算机/非冯非冯.诺依曼计算机诺依曼计算机 存储程序式计算机存储程序式计算机 操作系统类型操作系统类型批量处理批量处理 （单道、多道）（单道、多道）分时分时 实时实时 网络网络 分布式分布式 （与网络系统的区别）（与网络系统的区别）通用操作系统通用操作系统28第一章第一章 概论（概论（2） 现代操作系统的基本特征现代操作系统的基本特征程序执行的程序执行的并发性并发性资源资源共享性共享性虚拟性和不确定性虚拟性和不确定性 分析操作系统的几种观点分析操作系统的几种观点用户观点：虚拟机，操作系统的外部接口用户观点：虚拟机，操作系统的外部接口进程观点：操作系统运行阶段的实体单位，运行控制实体进程观点：操作

37、系统运行阶段的实体单位，运行控制实体资源观点：操作系统在设计阶段模块的静态划分资源观点：操作系统在设计阶段模块的静态划分模块分层观点：操作系统的静态体系结构，在资源观点下模块分层观点：操作系统的静态体系结构，在资源观点下设计的功能模块的调用方式设计的功能模块的调用方式 操作系统的用户界面操作系统的用户界面系统调用与交互命令系统调用与交互命令29第一章第一章 概论（概论（3） 操作系统定义操作系统定义 OS执行时，处理机的状态执行时，处理机的状态 特权指令特权指令 广义指令广义指令 中断指令中断指令 操作系统的可移植性操作系统的可移植性 开放式的操作系统开放式的操作系统 操作系统功能操作系统功能

38、30第二章第二章 操作系统接口操作系统接口 Linux的安装的安装操作系统的存放和启动操作系统的存放和启动自由软件（提供源代码）自由软件（提供源代码） Linux的使用的使用操作系统的外部控制特点操作系统的外部控制特点 系统调用的概念和使用系统调用的概念和使用以编程方式使用操作系统，对操作系统功能以编程方式使用操作系统，对操作系统功能的调用的调用OS专门为用户程序设置的程序接口，也是专门为用户程序设置的程序接口，也是用户程序取得用户程序取得OS服务的唯一途径服务的唯一途径 Shell编程编程脚本语言的作用脚本语言的作用 Linux系统配置系统配置 31第三章第三章 进程机制与并发程序设计（进程

39、机制与并发程序设计（1） 进程进程定义（结构）、状态、与程序的区别、与线程的区别、为什么使用线程。定义（结构）、状态、与程序的区别、与线程的区别、为什么使用线程。 进程调度进程调度概念概念算法：算法：FCFS、优先级、轮转法等等、优先级、轮转法等等 同步与互斥同步与互斥概念概念 同步：多个进程之间的一种协同关系同步：多个进程之间的一种协同关系 互斥：多个进程之间的一种竞争关系（涉及到临界资源和临界区）互斥：多个进程之间的一种竞争关系（涉及到临界资源和临界区）临界资源、临界区、信号量临界资源、临界区、信号量工具：工具： 同步原语同步原语P、V操作的定义（低级通信原语）操作的定义（低级通信原语）

40、、管程、消息缓冲区、管程、消息缓冲区(send和和receive原语原语-高级通信原语高级通信原语)32第三章第三章 进程机制与并发程序设计（进程机制与并发程序设计（2）同步机制应遵循的准则同步机制应遵循的准则 空闲让进空闲让进 临界区无进程时，允许其他进程进入临界区无进程时，允许其他进程进入 忙则等待忙则等待 临界区有进程时，其他进程须等待，保证互斥临界区有进程时，其他进程须等待，保证互斥 有限等待有限等待 在有限时间内使进程进入临界区，避免死等在有限时间内使进程进入临界区，避免死等 让权等待让权等待 等进入临界区的进程，释放处理机，避免忙等等进入临界区的进程，释放处理机，避免忙等 经典的同

41、步与互斥问题经典的同步与互斥问题生产者生产者/消费者问题消费者问题 涉及同步与互斥问题（生产者涉及同步与互斥问题（生产者/消费者，库房的使用权）消费者，库房的使用权）读者读者/写者问题写者问题 仅涉及互斥问题（读者仅涉及互斥问题（读者/写者对文件的访问，读者计数器的访问）写者对文件的访问，读者计数器的访问）五个哲学家就餐问题五个哲学家就餐问题 仅涉及互斥问题（叉子的使用）仅涉及互斥问题（叉子的使用）睡觉的理发师睡觉的理发师 涉及同步与互斥问题（理发师涉及同步与互斥问题（理发师/顾客，座椅等待队列的访问）顾客，座椅等待队列的访问）单行路上交通死锁的避免问题单行路上交通死锁的避免问题 仅涉及互斥问

42、题（路口的使用权）仅涉及互斥问题（路口的使用权）33第三章第三章 进程机制与并发程序设计（进程机制与并发程序设计（3） 死锁问题死锁问题死锁定义死锁定义死锁存在的必要条件死锁存在的必要条件处理死锁的四种策略处理死锁的四种策略 忽略死锁问题忽略死锁问题 鸵鸟算法（对死锁视而不见）鸵鸟算法（对死锁视而不见） 死锁的预防：破坏必要条件死锁的预防：破坏必要条件 避免：银行家算法避免：银行家算法 检测与解除：检测与解除： 进程资源图的化简进程资源图的化简 当死锁发生时，撤销代价最小当死锁发生时，撤销代价最小的进程的进程 考虑代价的范围考虑代价的范围 进程优先级进程优先级 作业种类作业种类 进程已执行时间

43、与剩余部进程已执行时间与剩余部分所需执行时间分所需执行时间34第三章第三章 进程机制与并发程序设计（进程机制与并发程序设计（4）检查状态安全与否的步骤：在请求矩阵中，是否有一行中相应的值均不大于向量F中对应的值若是，则可满足该行对应的进程资源申请，标记该进程为结束，并将资源加到向量F上重复以上两步，直到所有进程都标记为结束向量注释：G-总资源数组P-已分配资源数组F-剩余资源数组=G-P死锁避免方法总结死锁避免方法总结FG35第三章第三章 进程机制与并发程序设计（进程机制与并发程序设计（5） 并发程序设计并发程序设计涉及进程或者线程的程序设计就是并发程序设计涉及进程或者线程的程序设计就是并发程

44、序设计在在Linux中可以使用中可以使用C函数形式的系统调用函数形式的系统调用fork( )，execl( ) 建立进程和加载文件建立进程和加载文件Windows中可在编程语言：中可在编程语言： JAVA C/C+ VB.NET C# .NET Delphi等等利用涉及进程或者线程的利用涉及进程或者线程的API进行程序设计进行程序设计36第四章第四章 存储管理（存储管理（1） 基本概念基本概念重定位：重定位： 把装入模块中的相对地址转换为绝对地址的过程称为把装入模块中的相对地址转换为绝对地址的过程称为重定位重定位 静态重定位静态重定位 地址变换只是在装入时一次完成，以后不再改变，即由地址变换只

45、是在装入时一次完成，以后不再改变，即由装入程序负责完成装入程序负责完成 动态重定位动态重定位 地址变换推迟到程序要真正运行时进行，既由地址变换地址变换推迟到程序要真正运行时进行，既由地址变换机构负责完成机构负责完成地址变换机构：地址变换机构： 实现逻辑地址到物理地址的转换机构实现逻辑地址到物理地址的转换机构37第四章第四章 存储管理（存储管理（2） 基本概念基本概念虚拟存储器：虚拟存储器： 具有请求调入功能和置换具有请求调入功能和置换功能，能从逻辑上对内存功能，能从逻辑上对内存容量进行扩充的一种存储容量进行扩充的一种存储器系统器系统 思考题思考题二级页表地址映射问题二级页表地址映射问题38第四

46、章第四章 存储管理（存储管理（3） 基本概念基本概念名空间、地址空间、物理名空间、地址空间、物理空间空间内存零头（碎片）内存零头（碎片） 不能被利用的小分区不能被利用的小分区联想存储器（快表）联想存储器（快表） 具有并行查询能力的特殊具有并行查询能力的特殊高速缓冲存储器高速缓冲存储器符号符号源程序源程序目标目标代码代码可执行可执行代码代码汇编汇编编译编译连接连接地址重定位地址重定位名字空间名字空间地址空间地址空间存储空间存储空间39第四章第四章 存储管理（存储管理（4） 基本概念基本概念工作集：工作集： 在某段时间间隔里，在某段时间间隔里，进程实际要访问的进程实际要访问的页面集合页面集合程序的

47、局部性原理程序的局部性原理 空间局部性空间局部性 时间局部性时间局部性40第四章第四章 存储管理（存储管理（5） 主要管理技术、主要数据主要管理技术、主要数据结构、硬件支持、实现原结构、硬件支持、实现原理理分区：分区表、界地址寄存分区：分区表、界地址寄存器、地址变换机构、程序浮器、地址变换机构、程序浮动时机动时机分页：页表、页表地址寄存分页：页表、页表地址寄存器、地址变换机构器、地址变换机构分段：段表、段表地址寄存分段：段表、段表地址寄存器、地址变换机构器、地址变换机构段页式：段表段页式：段表+页表、段表页表、段表地址寄存器、地址变换机构地址寄存器、地址变换机构41第四章第四章 存储管理（存储

48、管理（6） 硬件支持、实现原理硬件支持、实现原理存储保护的手段存储保护的手段 界地址寄存器、上下界寄存器界地址寄存器、上下界寄存器 与页表、段表长度比较判断与页表、段表长度比较判断段表寄存器段表寄存器段表始址段表始址段表长度段表长度 段超长段超长段号段号s页号页号p页内地址页内地址 块内地址块内地址块号块号页表页表段表段表01230123页表长度页表长度页表始址页表始址b42第四章第四章 存储管理（存储管理（7） 存储分配算法存储分配算法最佳适应最佳适应最坏适应最坏适应最先适应最先适应下次适应下次适应 淘汰算法淘汰算法FIFOOPTLRU等等等等 使用存储管理系统调用的例子使用存储管理系统调用的例子43第五章第五章 输入输入/输出系统（输出系统（1） 设备管理的基本过程