操作系统考前整理

一操作系统概论1.1.1 操作系统的概念操作系统是配置在计算机硬件平台上的第一层软件，是一组控制和管理计算机系统硬件和软件资源，合理地组织计算机工作流程，并为用户使用计算机提供方便的程序和数据的集合 理解操作系统的四种观点： 用户观点。操作系统是用户与计算机之间的接口，是用户使用计算机的界面。 系统观点。操作系统是计算机系统资源的管理者和控制中心。 软件观点。操作系统是与硬件直接相邻的第一层软件，其它软件和程序的运行都依赖于它的支持。 系统发展观点。操作系统是一台虚拟扩展机，是对计算机硬件功能的首次扩充。1.1.2 操作系统的分层结构1. 内核层：操作系统的核心部分，提供基础性、结构性的基本功能，是唯一直接与硬件打交道的层次。2. 服务层：接受来自应用程序或命令层的服务请求，并将这些服务请求翻译成详细的指令传送给内核，或将处理结果送回给请求服务的程序。 I I 硬 #八！/ 访问I/O设备。 访问存储设备。 文件操作。 其他服务。3. 命令层：提供了用户接口界面，是操作系统中唯一直接与用户打交道的部分。1.1.3 操作系统的特征1. 并发性。在多道程序环境下，宏观上在一段时间内有多道程序在内存中同时运行，但每一时刻仍然只有一道程序执行，这些程序是分时交替地执行。区别 ：并行性,两个事件同时发生2. 共享性。指系统资源可以供内存中的多个并发程序共同使用。 互斥共享 同时共享并发性和共享性是操作系统的两个最基本的特征。3. 虚拟性。将一个物理实体映射为若干个逻辑实体。4. 异步性。指程序的执行过程和执行结果的不可预测1.1.4 操作系统的功能1. 处理机管理 进程控制。 进程同步。 进程通信。 进程调度。2. 存储器管理 内存分配。 内存保护。 地址映射 内存扩充。3. 设备管理 缓冲管理。 设备分配。 设备处理。4. 作业管理 提供安全的用户登录方法和方便的用户使用界面。提供直观的用户信息记录形式。 提供公平的作业调度策略。5. 文件管理 文件存储空间管理。 目录管理。 文件读/写管理。 文件保护。1.3 操作系统的分类1.3.1 批处理操作系统 用户将一批作业提交给操作系统后，就由操作系统来控制它们自动运行，不需要用户干预。1. 单道批处理系统磁带上的各道用户作业顺序地进入内存，正常情况下，各道用户作业完成的顺序与它们进入内存的顺序完全相同。(1) 联机单道批处理系统联机就是指用户作业的I/O操作完全是由CPU来控制和处理的。(2) 脱机单道批处理系统脱机是指用户作业的 I/O 操作完全脱离了主机的控制。单道批处理系统的特点：单道性独占性自动性封闭性2. 多道批处理系统 多道就是允许多个用户作业同时进入内存交替执行，共享系统资源。多道批处理系统的主要性能技术指标 资源利用率：资源利用率=作业(程序、进程)占用设备的总时间十作业(程序、进程)运行的总时间。吞吐量周转时间 多道批处理系统的特点：多道性：共享性无序性调度性：作业完成需要两次调度：作业调度和进程调度。1.3.2 分时操作系统多用户多任务、交互式的操作系统。1.3.3 实时操作系统 实时系统对可靠性和安全性的要求极高2. 实时系统与分时系统的区别实时系统能够在限定的时间内执行完所规定的功能，并能在限定的时间内对外部异步事件作出响应。分时系统按照相等的时间片调度用户作业轮流运行，作业运行的优先级由调度程序自动计算，而不由 用户控制，系统无法实时响应外部异步事件。1.3.4网络操作系统(NOS)1.3.5 分布式系统各台计算机之间无主次之分，任意两台计算机之间可以进行信息交换和资源共享。 分布式操作系统是一个统一的操作系统。 资源进一步共享。 透明性。 自治性。分布式和可靠性是分布式系统的最大优点。1.4 操作系统的运行环境(1) 特权 特权指令只能供操作系统使用，不允许用户程序使用。指令和非特权指令非特权指令是允许用户程序直接使用的指令。操作系统既可使用特权指令，也可使用非特权指令。(2) 处理器状态 管态目态 目的，是为了保护操作系统程序(2)操作系统对主存采取的存储保护方法界地址寄存器存储保护键1.4.2 中断和异常5种中断的优先级由高到低依次为：机器故障中断-访管中断-程序中断-外中断-I/O中断。1)异常的定义异常又称为“陷入”。是由正在执行的程序自身产生的，并且是与程序的运行同步产生的。因此，异常不可屏蔽(2)产生异常的原因 程序错误。 系统调用。二进程管理程序的顺序执行有3个特征： 1.顺序性。 2.封闭性。 3.可再现性。2.1.2 程序的并发执行2. 程序的并发执行指两个或两个以上的程序，在系统中处于已经开始执行，但尚未结束的状态。例如，输入、计算、打印三个程序，对一批作业进行处理时，存在以下的前趋关系：Ii - Ci, IF Ii+1, Ci-Pi, Ci-Ci+1, Pi-Pi+13. 程序并发执行的特征 1)间断性。 (2)失去封闭性。 (3)不可再现性。1. 什么是进程？ 进程是OS结构的基础。 进程是一个正在执行的程序。 进程是程序在一个数据集合上顺序执行时发生的活动。 可以分配给处理器并由处理器执行的一个实体。3. 进程的特征动态性。并发性。 独立性。 异步性。 结构性。动态性、并发性和异步性是进程最基本的特征。4. 进程与程序的关系 进程是动态的，程序是静态的。 进程是暂时的，程序是永久的。 程序是进程的组成部分之一。 一个已存在的进程可以创建新的进程，一个已存在的程序不能形成新的程序。2.2.1PCBPCB 是标识进程的存在、刻画进程瞬间特征的数据结构。PCB能够唯一标志一个进程，OS通过检测PCB的存在来感知一个进程的存在，通过PCB来管理和控制进程的运行。2.2.2 进程状态一个进程可以有创建、阻塞、就绪、运行、结束五种状态。其中，运行、就绪、阻塞是一个进程的基本状态， 创建-就绪 就绪-运行 运行-结束 运行-就绪 运行-阻塞 阻塞-就绪 就绪-结束 阻塞-结束例2.1 :在一个分时OS中，进程可能出现如图2.5所示的进程状态转换，请分析该示意图，说明有哪5种进程状态转换，并简要说明产生对应转换的原因。解：1.运行态-就绪态。正在运行中的进程因处理机时间片用完，必须让出处理机，由运行态-就绪态。2. 运行态-阻塞态：正在运行中的进程因为请求数据资源而被阻塞，从运行态-阻塞态。3. 运行态-阻塞态：正在运行中的进程因等待I/O设备而由运行态-阻塞态。4. 阻塞态-就绪态：被阻塞的进程因获得数据资源而由阻塞态-就绪态。5. 阻塞态-就绪态：被阻塞的进程因获得I/O设备由阻塞态-就绪态。例2.2 :进程A的工作流程如图2.6所示，如果该进程只有就绪、运行、阻塞三种状态，并且进程A被进程调度程序选中后即可投入运行，时间片q=200ms，请顺序列出进程A从开始到结束，所经历的主要状态转换过程并简要说明原因。简求二;卩虧过i-紀皿i-紀皿阳2,5逊住朮工比竝I解：进程A从开始到结束，经历了 7次状态转换。(1) 运行态-就绪态：一开始，进程A被调度程序选中投入运行，做完200ms计算操作后，因时间片到，必须让出处理机，由运行态-就绪态。进程A的计算操作尚需50ms才能完成。(2) 运行态-阻塞态：某时刻，进程A重新被调度投入运行，完成剩余的50ms计算操作后，请求磁盘I/O而等待，由运行态-阻塞态。(3) 就绪态-运行态：当进程A获得磁盘I/O后，具备了运行的条件，由就绪态-运行态。(4) 运行态-阻塞态。进程A再做50ms计算操作后，请求磁带I/O而等待，由运行态-阻塞态。(5) 运行态-就绪态。当磁带I/O请求满足后，进程A由阻塞态-就绪态，某时刻又被调度程序选中执行，从就绪态-运行态，但做200ms计算操作后，由于时间片用完，必须让出处 理机，从运行态-就绪态。(6) 就绪态-阻塞态。某时刻，调度程序选中进程A执行，但因进程A又提出打印请求，从就绪态-阻塞态 运行态：进程在处理机上运行时的状态。 活跃就绪态：进程在主存并且可被调度的状态。 静止就绪（挂起就绪）：进程被对换到外存时的就绪状态，为不能被直接调度的状态，只有当主存中没有活跃就绪态进程，或者是挂起就绪态进程具有更高的优先级，系统将把挂起就 绪态进程调回主存并转换为活跃就绪。 活跃阻塞态：进程已在主存，一旦等待的事件产生便进入活跃就绪状态。 静止阻塞态：进程对换到外存时的阻塞状态，一旦等待的事件产生便进入静止就绪状态。1. 处理机的三级调度运行频率：低级调度-中级调度-高级调度。响应时间=计算完成所消耗的时间/预计要消耗的时间计算完成所消耗的时间=等待时间+运行时间例2.3 ：一个作业8:00到达系统，其估计运行时间为 1小时。若10:00 开始运行该作业，计算响应时间。解：响应时间=计算完成所消耗的时间/预计要消耗的时间，消耗时间=等待时间+运行时间=2+1=3 小时。作业预计运行时间 1 小时，所以响应时间=3/1=3 小时。2.4.5 处理机的典型调度算法1. FCFS 调度算法按照作业或进程进入系统的先后顺序调度运行。特点： 比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，不利于I/O繁忙的作业。例2.4 :假设有3个作业同时到达系统。J1运行 2.5小时，J2和J3各运行20分钟。系统按J1、J2、J3的顺序运行。计算它们的平均等待时间，并画出3个作业运行时的甘特图。解：平均等待时间= （0+150+170）/3507（分钟）。3 个作业运行的甘特图如下：例2.5 :假设系统中有3个进程P1、P2和P3，它们的运行时间依次为24ms、3ms、5ms。 如果进程以P1、P2、P3的顺序在0时刻到达系统，并采用FCFS调度算法，画出3个进程执行的甘特图。 计算其平均等待时间。解：P1、P2、P3顺序到达时，3个进程的执行甘特图如下：P內1111iiiiii111 进程时间（单位：ms）CPU024 27323个进程的平均等待时间二（0+24+27） /3=17mso2, SJF调度算法在作业（进程）队列中选择运行时间最短的作业（进程）来运行口作业（进程）的运行时间有4种相关时间:（1）周转时间。指作业提交到完成之间的时间间隔作业i的周转时间Ti可表示为：TTci-Tsi （周转时间二完成时间-提交时间）（2）平均周转（等待）时间。指多个作业周转时间的平均 值。n个作业的平均周转吋间T可表示为：T=(T1+T2+-+Tn)/n例2.6 :假设3个作业同时到达系统，J】运行2.5小时，J2和J3各运行20分钟。系统按SJF算法运行这3个作业，计算3个作业的平均等待时间。解： 3 个作业的平均等待时间=（0+20+40）/3=20（分钟）（3）带权周转时间。指作业（进程）的周转时间与作业（进程）实际运行时间之比。W i=T/Ts（带权周转时间=周转时间/运行时间）例2.7 :假定3个作业同时到达系统。J1运行 2.5小时，J2和J3各运行20分钟。系统按短作业调度法运行这3个作业。计算三个作业的带权周转时间。解： Wi=Ti/TsTi=0+20+40=60（ 分钟）Tn=20+20+150=190（ 分钟）Wi=60/190 a 31.6（4）平均带权周转时间。指多个作业（进程）的带权周转时间的平均值。n个作业的平均带权周转时间W可表示为：W=（W1+W2+.Wn）/n例2.8 :假设有一组作业（或进程），它们的提交时间及要求运行的时间如表2.1所示（单位：小时，按十进制时间计算），系统采用SJF调度算法。计算该组作业的平均周转时间T和平均 带权周转时间 W。2- 1件业握空屋运1?时冋表作业号锻仝时间18:002. 028:500. 539-00仇149:500. 2解：（1）作业i的周转时间T.可表示为：T i=Tci-Tsi作业的平均周转时间T可表示为：T=(T +T2+.+Tn)/n = (2.0+1.1+0.8+2.3)/4=1.55(2)带权周转时间 Wi 可表示为：Wi=Ti/Tsn 个作业的平均带权周转时间 W=(W1+W2+. +Wn)/n=(2.0/2.0+1.1/0.1+0.8/0.2+2.3/0.5)/4=5.15。3. HRN 算法 响应比是系统响应时间与作业运行时间的比值。每调度一个作业投入运行时，计算后备作业队列中每个作业的响应比，挑选响应比高者投入运行。响应比=响应时间/运行时间=(等待时间+运行时间)/运行时间=1+等待时间/运行时间例2.9 :有A和B两个作业分别在7:00和8:30到达系统，它们的预测计算时间分别为0.8小时和0.1小时，系统9:00开始以HRN调度算法进行调度。计算在单道执行时，这两个作业被选中的次序及被选中时的响应比。解： 9:00 开始调度时，两个作业的响应比如下：作业A的响应比=1+120(分钟)/48(分钟) = 3.5作业 B 的响应比=1+30(分钟)/6(分钟)=6作业 A 的响应比=1+(120+6)/48=3.625。例2.10：假设一个进程组有5个进程，它们均在时刻0 到达系统，到达顺序为P P农r Ps,执行时间分 别为3、X 4. 5. 2,它们的优先级别为1、2 3. 4 5,采用优级调度算法乜画出5个进程执行过程的甘 特图，并计算其平均等待时间。解：5个进程执行过程的甘特图如下：逬程t P4 P3 ?2 P1CPU ;:;aiIIIIIIIIIIII4II时间：(单位；ms)02711 12155个进程的平均等待时间=(0+2+7+11+12)/5二6. 4ms0例2.11 :有3个进程同时到达系统，它们的运行时间分别是P112分钟，P24分钟，P32分钟。系统分配给3个进程的时间片均为2分钟，采用轮转算法。求3个进程的平均周转时 间。解：第1次轮转：P1运行 1个时间片2分钟，接着P2运行 1个时间片2分钟，然后P3运行 1个时间片2分钟。P3完成后，其周转时间=4+2=6(分钟)。第2次轮转：P1运行1个时间片2分钟，接着P2运行1个时间片2分钟。P3在第1次轮转时已经完成，所以P2完成后，P2的周转时间=6+4=10（分钟）。第3次轮转：P2和P3均已完成，只乘下P1未完成，P1运行6分钟（3个时间片）完成，其周转时间=10+6=16（分钟）。平均周转时间=（6+10+16）/3於10.7（分钟）。6. RRMF 算法例2.12 :假设系统中有3个反馈队列Q1、Q2、Q3，时间片分别为2、4、8现在有3个作业J1、J2、J3分别在时刻0、时刻1、时刻3到达。它们所需要的CPU时间片分别是3、2、1个。请说明采用对RRMF算法时，对这3个作业的调度执行过程。解：1.时刻0 : J1到达并进入到队列Q1,运行1个时间片后，时间片还未到， J2 到达。2时刻1 : J2到达时，由于时间片仍然由J1掌控，因而在Q1中等待。J1在运行了 1个时间片后，已完成在队列Q1中的2个时间片限制，于是被置于队列Q2等待被调度，处理 机分配给J2。3.时刻2 : J1进入Q2等待调度，J2获得CPU开始运行。4时刻3 : J3到达，由于J2的时间片未到，因此J3在队列Q1中等待调度，J1也在队列Q2中等待调度。5时刻4 : J2处理完成，由于J3和J1都在等待调度，但J3所在队列比J1所在队列优先级高，故J3被调度，J1继续在队列Q2中等待。6.时刻5 : J3经过1个时间片，完成。7时刻6 :由于队列Q1已空闲，于是开始调度队列Q2中的作业，则J1得到处理器开始运行。J1再经过一个时间片，完成了任务。于是整个调度过程结束2.5.1 线程的定义从不同的角度对线程有多种抽象的定义。1. 线程是进程中的一个实体，是被系统独立调度和分配的基本单位。2. 线程自己基本上不拥有系统资源，只拥有一些在运行中必不可少的资源，但它可以与同属一个进程的其他线程共享所拥有的全部资源。3. 一个线程可以创建和撤消另一个线程。4. 同一个进程中的线程之间可以并发执行。5. 由于线程之间的相互制约，致使线程在运行过程中也呈现出间断性。相应地，线程也具有就绪、阻塞和运行三种基本状态。进程并发控制和死锁3.3.1 死锁的基本概念 死锁是指多个进程因为竞争资源或者相互通信而处于永久阻塞的状态，如果没有外力的作用，这些进程都将无法向前推进。3.3.2 产生死锁的两个固有原因1. 系统资源不足。2. 进程推进顺序不合法。3.3.3 产生死锁的四个必要条件1.互斥条件。2. 不可剥夺条件。3. 保持和等待条件。4. 环路等待条件。例3.1 :假设系统中有两个进程P1（计算）和P2（打印）要共享一个临界资源（如单缓冲区），采用信号量解决这两个进程之间的同步。解：S1,S2:integer;S1: = 1;S2:=0;parbeginPc:begin computernextnumber;P(S1)；addthenumbertobufferV(S2);endPp ： beginP(S2);takenextnumberfrombufferV(S1);printthenumber endparend例 3.2：为了确保公交车行驶安全，司售人员必须协同工作。只有当售票员关好车门并发出可以行驶的信号后，司机才能启动汽车行驶；只有当汽车到站并停稳后，售票员才能打开车 门让乘客下车、上车。当前汽车正在始发站停车上客。根据上述描述，利用 PV 操作设计必要的信号灯及赋初值，写出司售人员之间的同步过程。解：设信号量Stop表示汽车停止，信号量run表示汽车行驶。汽车当前正在始发站停车上客，stop=0。BEGINintegerstop ， runstop:=0 ；run:=0；COBEGINProcessdriver ；BEGINL1： P(run)；启动汽车；正常行驶；到站停车；V(stop) ；GOTOL1ENDProcessconductor ；BEGINL2 :乘客上车；关车门；售票；口 73 IP(stop) ；开车门；乘客下车；GOTOL2；ENDCOENDEND例 3.3:阅览室有 200 个座位。读者进入阅览室时需要首先在登记表上登记。登记表为每一座位列一表目，包括座位号和读者姓名。读者离开时需要消掉登记的信息。问:1.为描述读者的动作，应编写几个程序？设置几个进程？2. 试用 PV 操作描述读者进程之间的同步关系。解: (1)读者有两个动作:一是填表进入阅览室，二是阅读完毕后消掉登记信息离开阅览室。两个动作各对应一个程序，即有两个进程。(2)用PV操作描述读者进程之间的同步关系。 Seats :记录座位数，初值Seats=200。 Readers :记录读者人数，初值Readers=0。 mutex :互斥信号量，用于控制读者进入阅览室和离开阅览室两个动作，初值mutex=1。读者进入阅览室的动作描述如下:getinWhile(TRUE)P(Seats)；P(mutex)；填写登记表；进入阅览室读书；V(mutex) ；V(readers) ；读者离开阅览室的动作描述:getin :While(TRUE)P(readers)；P(mutex) ；消掉登记；离开阅览室；V(mutex)V(seats) ；例 3.4 ：对于生产者-消费者问题，如果缓冲区中的缓冲单元只有一个，生产者和消费者各只有一人，如图 3.5 所示。用 PV 操作实现生产者和消费者的同步操作 解：设置两个信号量：(1) empty :只有一个缓冲单元，因此使empty=1。full :记录缓冲单元数，最初，缓冲单元中没有产品，因此，full=O。对应的程序结构如下:Semaphoreempty=1;Semaphorefull=O;Main()cobeginproducerwhile(true)P(empty);送产品到缓冲区;V(full);consumerwhile(true)P(full);从缓冲区取产品;V(empty);coend3. 哲学家进餐问题一般解法: 设每支筷子为一个临界资源，不可能同时被两人使用，为防止每支筷子被两人同时使用，给每支筷子对应一个信号量，5个信号量构成信号量数组Semaphorestick5，所有信号量均赋初值1,表示5支筷子。 一个哲学家只有同时拿到他左、右两边的筷子后才能进餐。semaphorestick5=(1,1,1,1,1);main()cobeginphilosopher(0);philosopher(1);philosopher(2);philosopher(3);philosopher(4);coendphilosopher(inti)while(true)思考；P(sticki);P(stick(i+1)%5);进餐V(sticki);V(stick(i+1)%5);注：这个算法可能会引起进程死锁。四存储器的 guanli4.1.2 分区管理1. 内存分区的目的 初始化内存空间，以便存储数据。 将不同的操作系统隔离开，以保证多个操作系统可以在一个磁盘上正常运行。 更好地对磁盘进行管理，以充分利用磁盘空间4.2 覆盖与交换技术目的是为了提高内存的利用率。4. 交换与覆盖的区别 交换不要求给出程序段之间的覆盖结构。 交换在进程或作业之间进行，而覆盖在同一进程 覆盖只能覆盖与覆盖程序段无关的程序段，而交换打破了一个程序一旦进入主存，便一直运行到结束的限制，但运行的进程大小仍受实际主存空间的限制计算 P 和 W 的公式为：P=INT(A/L)W=AmodL通过查页表，得到页号P对应的物理地址块号q，物理地址E=qxL+W。 例4.4 :设页面大小L为1KB ,页号2对应的物理块号为B=8，计算逻辑地址A=2500的物理地址E。解: P=INT(2500/1KB)=2W=2500mod1KB=452页号2对应的物理块号为8，则逻辑地址2500对应的物理地址E=8x 1024+452=8644。例4.5 :在分页存储管理系统中,逻辑地址结构长度为18位，其中11 - 17位为页号,0 - 10位为页内偏移量。若有一个作业的各页依次放入2、3、7号物理块中,问: 主存容量最大为多少KB ?分为多少块？每块有多大?O= 逻辑地址1500应在几号页内？对应的物理地址是多少？解:页表有3个表项，即(0,2)、(1,3)、(2,7)，如下图所示。 逻辑地址长度18位，故最大主存容量=2诞=256翎。页内偏移量W为0 10位共11位，故页面大小L=2no每块大小=页面大小=211。物理块总数=218/211=128块。 逻辑地址A=1500，对应的页号=int(1500/211)=0 ,页内偏移量W=1500，0页号对应物理块号为2，故物理地址E=2x2n+1500=5596。例 4.6:在一个分页式存储管理系统中，页表的内容如下图所示。问：若页大小为4KB，则地址转换机构将相对地址0T5T -lit1解：相对地址0在第0页第0字节，0页对应有内存块号为2。当前页大小4KB，故第 2块的物理地址应为：2x4096(4KB)+0=8192。例4.7 :某台计算机为每个进程提供了 65536B的地址空间，假若采用页式存储管理方案： 划分为8K大小的页。某一个进程有32768B的正文、16396B的数据段和15284B的堆栈段。这个进程能否装入该地址？ 若页面大小为512B，该进程能否放下？(一个页面不能同时包含两个不同段的成份)解：页面大小为8K，则共有216/213=8个页面，而进程共需32768B/8K+16396B/8K+15284B/8K=4+3+2=9个页面。故该进程不能装入该地址。页面大小为 512B，则共有 216/29=128 个页面，而进程共需 32768B/0.5K+16396B/0.5K+15284B/0.5K=64+33 +30=127个页面。故页面大小为512B，该进程能放下。例4.8 :假设一个分页存储管理系统中具有快表，多数活动页表项都可以在其中。如果页表放在内存中，内存访问时间是1ps，如果快表的命中率为85%，则有效访问时间是多少？如果快表的命中率为 50%，则有效访问时间是多少？解：有效访问时间=2x内存访问时间+快表访问时间-内存访问时间x快表命中率。 若快表的命中率为85%，则有效访问时间=2x1ps+0-1psx85%=1.15ps。 若快表的命中率为50%，则有效访问时间=2x1ps+0-1psx50%=1.5ps。例4.9 :为满足264地址空间的作业运行，采用多级分页存储管理方式，假设页面大小为4KB，在页表中的每页表项需要占8B，为了满足系统的分页管理，至少应采用多少级页表？画 出逻辑地址形式图。解:首先计算页表中能够存放多少个页表项。页表项个数=页面大小*每个页表项的大小页面大小=4KB=2i2B，每个页表项为8B=23B，因此，一个页表中可以存放2辽十23=29=512个页表项。设有n层分页，64位逻辑地址形式如下图所示。第11页号勰页号 VIU第谥页号页内翩量因为页面大小=2i2B，所以页内偏移量占12位。因为每层页表的大小怀超过一页，所以每层的页号不超过10位(一页的大小默认为1O24=2io)，因此有10xn + 1264，n应, 6(26)，即要满足系统的分页管理，至少应采用 6 级页表。例 4.10:某页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，问:(1) 主存分块大小是多少？(2) 程序最多可分为多少个页面？解：因为页号14位，页内偏移量=24-14=10位，所以页的大小为21oB，即主存分块大小为2“B。 (2)因为程序最多占有的页面数不能超过地址总线确定的大小，否则程序无法正确寻址，因此，本题的程序最多可分为 214个页面。例4.11 :设有8页的逻辑空间，每页有1024B，它们被映射到32块的物理存储区中。问：(1) 逻辑地址的有效位是多少位？(2) 物理地址至少是多少位？解：逻辑空间8页=23，即页号位数为3位，每页大小为1024=210B，即页内偏移量为10位，所以，逻辑地址有效数为3 + 10=13位，如下图所示。12JJ J(J页号贝内鴨務(2)系统内存块32个=25 ，即内存块号至少占5位，每个内存块的大小与页面相同，即需要10位来表示，因此物理地址至少需要5+10=15位来表示。4.4 段式存储管理4.4.1 段式管理的实现原理4.5 虚拟内存管理虚拟存储技术实现的依据是程序的局部性原理4.5.7 常用的虚拟存储技术 请求分页存储管理。 请求分段存储管理。 请求段页式存储管理 例4.15 :某虚拟存储器的用户编程空间共32个页面，每页长为1KB，内存16KB。假定某时刻用户页表中已OJLO-1m - r心 I - m“I a-al 心i net调入内存的页面和物理块号的对照如表4.4所示。问：此时，指令中地址空间(逻辑地址)至少需要多少位？逻辑地址0A5C(H)所对应的物理地址是什么？解：地址空间位数=页面位数+页内地址位数。编程空间32个页面，页面位数=5位；每页长度1KB，即页内地址为10位。故指令地址空间位数=5 + 10=15位。物理地址=块号x每页大小+位移量。已知页号P=INT(2652/1KB)=2，表中页号2对应的物理块号=4。位移量=逻辑地址位数-页号位数。逻辑地址0A5C(H) = (2652)10，位移量 D=2652-(2x 1024)=604。故逻辑地址 0A5C(H)对应的物理地址为：4x1024+604=(4700) =(1001001011100) =125C(H)。例4.16 :某虚拟存储器的用户编程空间共32个页面，每页1KB，主存16KB。假定某时刻该用户页表中已调入主存的页面的页号和物理块号为： (0,5)， (1,0)， (2,4)， (3,7)。 求出虚地址0A5C(H)和1A5C(H)对应的物理地址。 若在内存中找不到对应的页面，会出现什么情况？解：已知页面大小=1KB，虚地址A1=0A5C(H)=2642，对应的页号P1=INT(2652/1KB)=2，对应物理块号为4 ,页内偏移量 W1=2652-2x 1024=604，物理地址 E1=4x 1024+604=4700=125C(H)。虚地址 A2=1A5C(H)=6748，对应页号 P2=INT(6748/1024)=6。由题目可知，在内存中找不到对应的页面号6，所以会产生缺页中断。4.6.6 页面置换法1.OPT(最佳)算法从内存中选择永远不再需要的页面，或者在最长的时间以后，才需要访问的页面予以淘汰。优点：能保证获得最低的缺页率。缺点：一种不实用的理想化的置换算法。例 4.17：假设系统为某进程分配了 3 个物理块，页面走向为： 7， 0， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 1， 2， 0， 1， 7， 0， 1，求采用 OPT 算法时缺页中断的次数和置换次数 解：表4- 5 0PTSS的粽贝情况2. FIFO 算法总是选择在内存中驻留时间最长的页面淘汰，即先进先出。例 4.18 ：假设系统为某进程分配了 3 个物理块，考虑页面走向为： 7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1，求采用 FIFO 淘汰算法时缺页中断的次数和置换次数。表4. 6采用FIFO算法的峽页情况贡面走向1C12304230321201701物理块1777222电44000777物理块200033322211100物理块31110003332221峡页否VVVVVVvVVVVVVVV3. LRU（最近最久未使用）算法选择最近一段时间内最长时间未被访问过的页面淘汰。例4.19 :假设系统为某进程分配了 3个物理块，页面走向为：7,0,1,2,0,3,0,4,2, 3,0,3,2, 1,2 ,0, 1,7,0, 1,求采用LRU页面淘汰算法时缺页中断次数。 解：表耒用LRU#法的缺页情况4.6.7 工作集和抖动工作集就是指在某段时间内作业运行所要访问的那些页面的集合。 在内存和外存之间频繁地来回调入调出页面的现象称为抖动。5.1.1 文件文件是存储在外部存储介质上的、具有符号名的一组相关信息的集合。5.1.2 文件系统OS中负责存取和管理文件信息的机构,由管理文件所需的数据结构和相应的管理软件以及访问文件的一组操作组成文件系统的功能： 实现文件的“按名存取”。 统一管理文件存储空间，实施空间的分配和回收。 实现文件信息共享并提供文件的保护和保密措施。 向用户提供一个方便使用的接口。 系统维护及向用户提供有关信息。 提高文件的执行效率。 提供与I/0的统一接口。5.1.3 常用文件系统1. 基于 Windows 的文件系统总容量 磁盘最大分区 FAT168G2G FAT3232G4G（2）NTFS2T不受限目录管理的功能有：“按名存取”。提高对目录的检索速度。 文件共享。 允许文件重名。1. FCB（FCB 线性表或文件控制块）FCB包含的主要内容：文件名。访问权限。 属主。 物理地址。 逻辑结构。 物理结构。 管理信息。3.多级目录结构优点：层次清楚。解决了文件重名问题。缺点：增加了磁盘访问次数，影响查询速度。5.5.1 磁盘存储器的特点 存储容量大，存取速度较快，可以随机存取。 是实现虚拟存储器或其他虚拟设备的必要硬件。 是存放程序和数据的主要外存设备5.5.6 磁盘调度算法1. FCFS（先来先服务）算法按照用户作业或进程到达系统的时间先后顺序来处理请求 优点：简单、公平，缺点：平均寻道时间较长。例5.8 :在FCFS算法下，磁头移动路径如下图所示，求总共移过的磁道数。解：总共移过的磁道数=(98-53)+(183-98)+(183-37)+(122-37)+(122-14)+(124-14)+(124-65)+(67-65)=6402.SCAN(电梯调度)算法SCAN 算法又称为“扫描算法”。总是从磁头当前位置开始，选择沿臂的移动方向最近的柱面，若该方向无访问请求，即改变臂的移动方向，处理所遇到的最近的 I/O 请求。类似于电梯的调度原则。例5.9 :采用SCAN算法，磁头移动路径如下图5所示，计算总移动磁道数。总移动磁道数=(53-37)+(37-14)+(14-0)+(65-0)+(67-65)+(98-67)+(122-98)+(124-122)+(183-124)=2363.SSTF(最短寻道时间优先)算法总是先执行查找时间最短的那个磁盘请求，从而较“先来先服务”算法有较好的寻道能力，但是不能保证平均寻道时间最短例 5.10:采用 SSTF 算法，磁头移动路径如下图所示，计算总移动磁道数。总移动磁道数=(65-53)+(67-65)+(67-37)+(37-14)+(98-14)+(122-98)+(124-122)+(183-124)=2364. CSCAN (循环扫描调度)算法移动臂总是从0号柱面至最大柱面顺序扫描，然后，直接返回 0号柱面重复进行，归途中不再服务，构成了一个循环。如下图所示。例5.11 :假设计算机系统采用CSCAN(循环扫描)磁盘调度策略，使用2KB的内存空间记录16384个磁盘的空闲状态。请说明在上述条件下如何进行磁盘块的空闲状态管理。设某单面磁盘的旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动(如图5.29所示) ，磁道号的请求队列为50 ， 90， 30， 120 ，对请求队列中的每个磁道需要取1个随机分布的扇区，则读完这个扇区点共需要多少时间？图反却一牛磁盘结构如果将磁盘替换为随机访问Flash半导体存储器(如 U盘)，是否有比CSCAN更高效的磁盘调度策略？如果 有，请给出磁盘调度策略的名称并说明理由，如果没 有，也说明理由。解：使用位示图法表示磁盘的空闲状态，每一位表 示一个磁道块是否为空闲，共需要16384/32=512个字 =512X4B=2KB,正好可放在系统提供的内存中。 采用CSCAN调度法，访问磁道的顺序为120，30，50，90，则移动磁道长度=(120-100)+(120-30)+(50-30)+(90-50) = 170，总的移动磁道时间为170x1ms二 170ms。每分钟旋转 6000 转，则平均旋转延迟为 60/(6000x2) = 5ms，总的旋转延迟时间= 5msx4=20ms。每分钟旋转6000转，则读取一个磁道上的一个扇区的平均读取时间为10ms/100=0.1ms，总的读取扇区的时间=0.1msx4=0.4ms。 采用FCFS(先来先服务)调度策略更高效。这是因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可以直接按I/O的先后顺序服例5.12 :假设有一个活动头磁盘有200道，编号从0 199。当前磁头正在155道上服务，并且在此之前完成的是173道的访盘请求。现有如下访盘请求序列(磁盘号): 155,143,187,198,138,75,44,129,168,87,81。请给出采用下列算法后，磁头移动的顺序(画出示意图)和移动总量(总磁道数)。(1) SSTF 调度算法。(2) SCAN 调度算法。解: (1)SSTF。磁头移动顺序:155,143,138,129,168,187,198,87,81,75,44。4475 fil 8712913H143 誌 lfiS IR7 I9fi磁头移动总量：(155-129) + (198-129) + (198-44) =249o(2)SCANc磁头移动顺序：155,143,13& 129, 87, 81, 75, 44, 168,187,馬 81 87129138 M3 155168187198磁头移动总量：(155-44) + (198-44)二265。6.1.1 作业的定义作业是用户在一次计算过程中，或者一次事务处理过程中，要求计算机系统所做的工作的总称。 作业由程序、数据和作业说明书三部分组成。6.1.2 作业的状态1. 提交状态 2.后备状态3.运行状态 4.完成状态6.1.3 操作系统作业管理的功能1. 作业输入2. 作业输出3. 作业处理作业调度作业控制 作业后备。6.1.4JCL 和 JCB1. JCL系统提供给用户书写作业说明书的语言。2. 作业说明书作业基本描述作业控制描述 资源要求描述3. JCBOS 对作业进行管理和调度的数据结构，是作业说明书在系统中生成的一张表格，用于记录作业运行时所要求的资源、预计执行时间、执行优先级等信息6.1.5 作业说明书与作业控制块的异同1.作业说明书主要包含三方面的内容：作业的基本描述、作业控制描述和资源要求描述。2. JCB 是作业说明书在系统中生成的一张表格，用于记录该作业所要求的资源情况，预计执行时间和执行优先级等。7.1.2 操作系统对 I/O 设备管理的目标1.实现数据传输与变换。2. 提高设备的使用效率。3. 提供接口，方便用户使用外设。4. 统一管理，提高外设的可靠性和安全性。7.1.3 设备管理功能1.实现设备并行性和缓冲区的有效管理。2. 提供与进程管理系统的接口。3. 设备分配与回收。4. 监视设备状态。5. 设备控制和中断处理。6. 实现虚拟设备。7.3.3DMA 控制方式1.DMA 控制方式的实现原理DMA 称为成组数据传送方式或直接内存存取方式。基本思想是：在外设和内存之间开辟直接数据交换通路，设备和内存之间可以成批地进行数据交换，而不用 CPU 干预，从而 大大减轻了 CPU的负担，又使I/O数据传送速度大幅度提高。作业例 5.4 ：有一个文件系统如图5.18 所示，（1）可否建立F与R的链接？为什么？（2）可否删除R?为什么？（3）可否删除N ?为什么？答：（1）可以，F是目录，R是文件，通过连接符实现文件在多个目录中共享。（2 ）不一定，因为R可以被它的目标文件和M文件共享，取决于系统共享的方法，如果是索引文件指针，R不可删除，因为删除后目标指针悬空基于符号共享的方法文件R可 被删除。（3 ）不一定，因为N目录下有一个子目录P共享了 R，由于R不一定能删除，所以N不一定能删除。第一章 作业解答1.简述操作系统的主要特征（见教材）。2设内存中有3道依次执行的程序A、B、C。它们的相应操作时间如下表所示。AIA20-1()lA15BC103030处6040(1)画出单道运行的时间关系图。计算3道程序完成时间和CPU的利用率。(3) 画出多道运行时程序A和B进行计算和I/O2操作的关系图。(4) 计算多道方式程序A和B运行时CPU和I/O2的利用率。解：(1)单道方式下 3 道程序运行的时间关系图。(2)单道方式下 3 道程序运行的总时间为：20+40+15+10+30+60+30+20+40=265s单道方式下 CPU 的利用率为：(40+30+30)/26538%(3) 多道方式运行时程序A和B进行计算和I/O2操作的关系图计算 ;:B40; A15B20 ;i” (单札0405575105(4) 多道方式下程序 A、 B 运行的总时间为：40+15+30+20=105s多道方式下 CPU 的利用率为：(40+30)/105 M7%多道方式下I/O郭利用率为：(40+15+20)/105 於71%第二章作业*1*分析下图有哪4种进程状态转换，并简要说明转换原因.(f执行=请求2设有4个作业同时到达，运行时间和优先数如下表所示。若 采用最短作业优先调度算法，计算作业的平均周转时间。I/O完成/d卵片完 进程调度作业的运行时间和优先数作业号所需运行吋间(小吋)优先数1222533374351就绪-运行：处于就绪状态的进程，已具备了运行的条件，但由于未能获得CPU,仍然不能运行2运行-阻塞：处于运行态的进程申请新资源而又不能立即被满足时，由运行态变成阻塞态。如运行中的进程需要等待文件的输入，系统便自动转入系统控制程序，进行文件输入, 在文件输入过程中，该进程进入阻塞状态，而系统将控制转给进程调度程序，进程调度程序根据调度算法把CPU分配给处于就绪态的其他进程，即运行进程遇I/O请求时，发生该状 态转换。(3) 阻塞-就绪：被阻塞的进程在其被阻塞的原因获得解除后，并不能立即投入运行，需要通过进程调度程序统一调度才能获得CPU，于是将其状态由阻塞态变成就绪态继续等待 CPU。只有当进程调度程序把CPU再次分配给它时，才可恢复曾被中断的现场继续运行，即阻塞进程的I/O请求完成时，发生该状态的转换。(4) 运行-就绪：正在执行的进程，因时间片用完而被暂停执行，或在采用抢占方式调度算法的系统中，当有更高优先级的 进程要运行而被迫让出处理机时，该进程便由执行状态转变为就绪状态。2. 设有4个作业同时到达，运行时间和优先数如下表所示。若采用最短作业优先调度算法，计算作业的平均周转时间。作业i的周转时间Ti=作业完成时间-作业提交时间。作业运行次序为1、4、2、3 ，分别用时2、5、10、18 ，平均周转时间为：T= (2+5+10+18)/4=8.75(小时)。第三章第一次作业：有相同数量的红豆和黑豆混装在一只袋子里了，现在要把它们分拣出来，要求： 用进程A专门拣红豆，进程B专门拣黑豆。 每个进程每次只能从袋子里拣一颗豆子，当一个进程在拣豆子时不允许另一个进程去拣豆子。写出用P、V操作实现进程A、B同步操作的程序结构(程序语言不限)。第三章第一次作业参考答案begin semaphoremutex; mutex:=1;cobeginprocessAbeginL1:P(mutex);拣红豆；V(mutex);gotoL1;end;processBbeginL2:P(mutex);拣黑豆；V(mutex);gotoL2;end;coend;end;