1、2022年年6月月10日日课程主要内容 教材内容 操作系统引论（第1章） 进程管理（第2章） 处理机调度与死锁（第3章） 存储管理（第4章） 设备管理（第5章） 文件管理（第6章） UNIX系统内核结构 (第10章）计算题类型总结 利用信号量实现进程同步 处理机调度算法（周转时间） 银行家算法 分区存储管理算法 逻辑地址物理地址变换 请求分页中的页面置换算法 磁盘访问时间 磁盘调度算法（平均移道数） 混合索引分配 文件控制块和索引结点 位示图第一章 操作系统引论1.3 操作系统的基本特征 并发性 (Concurrence) 共享性 (Sharing) 虚拟性 (Virtual) 异步性 (As
2、ynchronism)基本特征基本特征: :操作系统的形成 单道批处理系统 多道批处理系统 操作系统的形成在多道程序系统中增设一组软件以有效加以解决，同时增设方便用户使用计算机的软件，这样便形成了操作系统。操作系统的结构设计 传统的操作系统结构 无结构操作系统 模块化OS结构 分层式OS结构 现代操作系统结构 微内核的OS结构：将客户/服务器技术、面向对象技术用于OS 中所形成的 OS 结构。 第二章 进程管理2、进程process的基本特征 （1）结构特征 从结构上看，每个进程（进程实体）都是由程序段、数据段及进程控制块（PCB）组成。 （2）动态性 进程的实质是程序在处理机上的一次执行过程
3、，因此是动态性的。所以动态性是进程的最基本的特征。同时动态性还表现在进程则是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而消亡。进程的定义、特征n 进程在运行期间并非固定处于某个状态，而是不断进程在运行期间并非固定处于某个状态，而是不断从一个状态转换到另一个状态。从一个状态转换到另一个状态。二、进程状态2、进程状态转换具有挂起状态的进程状态活动就绪执行挂起调度时间片完活动阻塞事件发生等待事件静止就绪静止阻塞激活挂起事件发生激活挂起线程的基本概念 进程是资源分配的单位，而线程是处理机调度的单位。 一个进程可以创建一个或多个线程。 多个线程会争夺CPU，在不同的状态之间进行
4、转换。线程也是一个动态的概念，也有一个从创建到消亡的生命过程，具多种状态。 同一进程中的所有线程都具有相同的地址空间（进程的地址空间）。线程的实现方式 线程的实现方式 内核支持线程的实现 直接利用系统调用进行线程控制。 用户级线程的实现 不能直接利用系统调用。为了取得内核的服务（获得系统资源），需要借助中间系统（运行时系统、轻型进程）。同步机制应遵循的规则q空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。q忙则等待:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临
5、界资源的互斥访问。q有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入死等状态。q让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。信号量机制 信号量机制 信号量用于表示资源数目或请求使用某一资源的进程个数的整型量。整型信号量记录型信号量信号量集（AND信号量集、一般信号量集）利用信号量实现进程同步例：进程A与进程B共享同一文件file，设此文件要求互斥使用，则可将file作为临界资源，有关file的使用程序段分别为临界区CSA和CSB。semaphore mutex=1;PA:L1：P(mutex); CSA; V(mutex); r
6、emainder of process A;GOTO L1;PB:L2:P(mutex);CSB;V(mutex);remainder of process B; GOTO L2; S1S3S2S4S5S6S7S8例：利用信号量来描述前趋图关系例：利用信号量来描述前趋图关系利用信号量实现进程同步利用信号量实现进程同步 具有8个结点的前趋图。图中的前趋图中共有10条有向边，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信号量实现进程同步Struct smaphore a,b,c,d,e,f,g,h,i,j=0
7、,0,0,0,0,0,0,0,0,0cobegin S1;V(a);V(b);V(c); P(a);S2;V(d); P(b);S3;V(e);V(f); P(c);S4;V(g); P(d);P(e);S5;V(h); P(f);P(g);S6;V(i) P(h);P(i);S7;V(j); P(j);S8;coendS1S3S2S4S5S6S7S8agefbcdhij利用信号量实现进程同步2.4 经典进程的同步问题 在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者消费者问题哲学家进餐问题读者写者问题其他同步问题“哲学家进餐”问题 问题描述： 有五
8、个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。解决死锁问题的例子哲学家进餐问题的改进解法 方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。 方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。哲学家进餐问题的改进解法 方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有
9、一位哲学家能进餐，并在用完后释放两只筷子供他人使用。 设置一个初值为4的信号量r ，只允许4 个哲学家同时去拿左筷子，这样就能保证至少有一个哲学家可以就餐，不会出现饿死和死锁的现象。 原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。哲学家进餐问题的改进解法semaphore chopstick5=1，1，1，1，1; semaphore r=4; void philosopher(int i) while(true) think(); wait(r); /请求进餐 wait(chopsticki); /请求左手边
10、的筷子 wait(chopstick(i+1) mod 5); /请求右手边的筷子 eat(); signal(chopstick(i+1 ) mod 5); /释放右手边的筷子 signal(chopsticki); /释放左手边的筷子 signal(r); /释放信号量r think(); 哲学家进餐问题的改进解法 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。 解法1：利用AND 型信号量机制实现。 原理：多个临界资源，要么全部分配，要么一个都不分配，因此不会出现死锁的情形。哲学家进餐问题的改进解法semaphore chopstick5=1，1，1，1，1; void philos
11、opher(int i) while(true) think(); Swait(chopsticki; chopstick(i+1) mod 5); eat(); Ssignal(chopstick(i+1) mod 5; chopsticki); think(); 哲学家进餐问题的改进解法 方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。 解法2：利用信号量的保护机制实现。 原理：通过互斥信号量mutex对eat()之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现。哲学家进餐问题的改进解法semaphore mutex = 1; semaphore chopstick5=1，1，1，
12、1，1; void philosopher(int i) while(true) think(); wait(mutex); wait(chopsticki); wait(chopstick (i+1) mod 5); signal(mutex); eat(); signal(chopstick (i+1) mod 5); signal(chopsticki); think(); 哲学家进餐问题的改进解法 方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。 原理：按照下图，将是2,3号哲学家竞争3号筷子，4,5号哲学家竞争5号筷子。1号哲学家不需要竞争。最后总会有一个哲学家能获
13、得两支筷子而进餐。先申请的哲学家会较先可以吃饭并释放筷子，因此不会出现饿死的哲学家。1221334455哲学家进餐问题的改进解法semaphore chopstick5=1，1，1，1，1; void philosopher(int i) while(true) if(i mod 2 = 0) /偶数哲学家，先右后左。 wait (chopstick (i + 1) mod 5); wait (chopstick i) ; eat(); signal (chopstick i); signal (chopstick(i+1) mod 5); Else /奇数哲学家，先左后右。 wait (ch
14、opstick i) ; wait (chopstick (i+1) mod 5); eat(); signal (chopstick (i+1) mod 5); signal (chopstick i); 第三章 处理机调度与死锁提交提交作业调度作业调度作业调度作业调度作业状态转换图作业状态转换图后备后备退出退出完成完成一、调度的层次就绪就绪阻塞阻塞就绪就绪阻塞阻塞运行运行交换调度交换调度进程调度（线程调度）进程调度（线程调度）FCFS例题例：下面三个作业几乎同时到达系统并立即进行FCFS调度： 作业名 所需CPU时间 作业1 28 作业2 10 作业3 1 假设提交顺序为1、2、3，则平均
15、作业周转时间T = 若提交顺序改为作业2、1、3，则T= 若提交顺序改为作业3、2、1，则T= 由此可以看出，FCFS调度算法的平均作业周转时间与作业提交的顺序有关。(28+38+39)/3 = 35(10+38+39)/3=29(1+11+39)/3=17进程调度算法先来先服务FCFS 例1： 进程名 到达时间 服务时间 A 0 1 B 1 100 C 2 1 D 3 100进程名到达时间服务时间开始执行时间完成时间周转时间带权周转时间A01B1100C21D3100周转时间周转时间服务时间服务时间完成时间完成时间- -到达时间到达时间开始时间开始时间+ +服务时间服务时间上一个进程上一个进
16、程的完成时间的完成时间0 1 1 11 101 100 1101 102 100 100 102 202 199 1.99作业到达时间Tin服务时间Tr开始时间Ts 结束时间Tc周转时间T带权周转时间W平均时间 执行顺序：执行顺序：SJF/SPFSJF/SPF（非抢占式）（非抢占式）A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84周转时间结束时间周转时间结束时间-到达时间到达时间带权周转时间周转带权周转时间周转/服务服务q基本思想基本思想： 多级反馈队列调度算法是时间片轮转算法和多级反馈队列调度算法是时间片轮转算法
17、和优先级调度算法的综合和发展，通过优先级调度算法的综合和发展，通过动态调整进动态调整进程优先级和时间片大小，不必事先估计进程的执程优先级和时间片大小，不必事先估计进程的执行时间。行时间。q多级反馈队列可兼顾多方面的系统目标，是目前多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。公认的一种较好的进程调度算法。qFCFS + 优先级优先级 + RR + 抢占抢占七、多级反馈队列调度算法七、多级反馈队列调度算法-实现思想（1）设置）设置多个就绪队列多个就绪队列，并为每个队列赋予，并为每个队列赋予不同的优先级不同的优先级。队。队列列1的优先级最高，其余队列逐个降低。的优先级最高
18、，其余队列逐个降低。（2）每个队列中）每个队列中进程执行时间片的大小进程执行时间片的大小也各不相同，进程所在也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。队列的优先级越高，其相应的时间片就越短。（3）当一个）当一个新进程进入新进程进入系统时，首先将它放入队列系统时，首先将它放入队列1的末尾，的末尾，按按FCFS等待调度。如能完成，便可准备撤离系统，反之由调度等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列程序将其转入队列2的末尾，按的末尾，按FCFS再次等待调度，如此下去，再次等待调度，如此下去，最后进入最后进入队列队列n按按RR算法调度执行算法调度执行。（4）仅
19、当队列）仅当队列1为空时，才调度队列为空时，才调度队列2中的进程运行。若一个中的进程运行。若一个队列中的进程正执行，此时有新进程进入优先级较高的队列中，队列中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将则新进程将抢占运行抢占运行，原进程转移至本队列队尾。，原进程转移至本队列队尾。二、产生死锁的原因竞争资源进程间推进顺序非法三、产生死锁的必要条件三、产生死锁的必要条件 1. 互斥条件（互斥条件（mutual exclusion）2. 请求和保持条件（请求和保持条件（hold-while-applying）3. 不剥夺条件（不剥夺条件（non preemption）4. 环路等待条
20、件（环路等待条件（circular wait）四、处理死锁的基本方法目前处理死锁的基本方法有：预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。银行家算法银行家算法银行家算法 假定系统中有5个进程P0到P4，3类资源及数量分别为A(10个），B（5个），C（7个），T0时刻的资源分配情况如下M
21、axAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1表表1 T0时刻的资源分配表时刻的资源分配表WorkA B CNeedA B CAllocationA B CWork+ AllocationA B CFinishP07 4 30 1 0falseP11 2 22 0 0falseP26 0 03 0 2falseP30 1 12 1 1falseP44 3 10 0 2fal
22、se（1） T0时刻的安全性时刻的安全性利用利用安全性算法安全性算法对对T0时刻时刻的资源分配情况进行分析的资源分配情况进行分析:T0时刻存在着一个安全序列时刻存在着一个安全序列P1,P3,P4,P2,P0，故，故系统是安全系统是安全的。的。表表2 T0时刻时刻的安全性检查表的安全性检查表5 3 2true3 3 25 3 27 4 3true7 4 37 4 5true7 4 510 4 710 4 710 5 7truetrue3 3 2A B CAvailable(2) P1请求资源 Request1(1,0,2) P1发出请求向量Request1(1,0,2)，已知Need1 (1,2
23、,2)， Available (3,3,2)，系统按银行家算法进行检查:1) Request1 (1,0,2) Need1 (1,2,2)2) Request1 (1,0,2) Available (3,3,2)3) 系统试为P1分配资源，并修改相应的向量 Available、Need、AllocationMaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2 P13 2 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1P1请求资源请求资
24、源Request1(1,0,2)时的资源分配表时的资源分配表(3 0 2)( 0 2 0)(2 3 0)WorkA B CNeedA B CAllocationA B CWork+ AllocationA B CFinishP10 2 03 0 2 falseP30 1 12 1 1falseP44 3 10 0 2falseP26 0 03 0 2falseP07 4 30 1 0false 由安全性检查分析得知：由安全性检查分析得知： 此时刻存在着一个安全序列此时刻存在着一个安全序列P1,P3,P4,P2,P0，故，故系统是安全系统是安全的，可以立即将的，可以立即将P1所申请的资源所申请的
25、资源分配给它。分配给它。4)利用安全性算法检查资源分配后此时系统是否安全P1请求资源Request1(1,0,2)时的安全性检查表2 3 05 3 2true5 3 27 4 3true7 4 37 4 5true7 4 510 4 7true10 4 710 5 7true（3）P4请求资源请求资源Request4(3,3,0) P4发出请求向量发出请求向量Request4(3,3,0)，系统按银行家算法，系统按银行家算法进行检查进行检查:1) Request4(3,3,0)Need4 (4,3,1)2) Request4 (3,3,0) Available (2,3,0)，表示资源不够，表
26、示资源不够，则让则让P4等待等待(4)P0请求资源 Request0(0,2,0) P0发出请求向量Request0(0,2,0)，系统按银行家算法进行检查:1) Request0(0,2,0)Need0 (7,4,3)2) Request0 (0,2,0) Available (2,3,0)3) 系统试为P0分配资源，并修改相应的向量。MaxAllocationNeedAvailableA B CA B CA B CA B CP07 5 30 1 07 4 33 3 2(2 3 0)P13 2 22 0 01 2 2(3 0 2)(0 2 0)P29 0 23 0 26 0 0P32 2 2
27、2 1 10 1 1P44 3 30 0 24 3 1表表5 P0请求资源请求资源Request0(0,2,0)时的资源分配表时的资源分配表2 1 00 3 07 2 3 4) 进行安全性检查资源分配后此时系统是否安全，因进行安全性检查资源分配后此时系统是否安全，因Avaliable(2,1,0)已不能满已不能满足任何进程需要，故系统进入不安全状态，此时系统不分配资源。足任何进程需要，故系统进入不安全状态，此时系统不分配资源。第四章 存储管理4.2 连续分配存储管理方式q 连续分配方式（分区技术） ：指为一个用户程序分配一片连续的内存空间。 n单一连续分区分配（单一连续分区分配（静态分区技术静
28、态分区技术）：仅用于单用户）：仅用于单用户单任务系统单任务系统n固定分区分配（固定分区分配（静态分区技术静态分区技术）：可用于多道系统）：可用于多道系统n可变分区分配（可变分区分配（动态分区技术动态分区技术）n可重定位可变分区分配（可重定位可变分区分配（动态分区技术动态分区技术） ：引入了：引入了动态重定位和内存紧凑技术动态重定位和内存紧凑技术n伙伴系统（伙伴系统（动态分区技术动态分区技术）静态分区：作业装入时一次完成，分区大小及边界在运行时不能改变。静态分区：作业装入时一次完成，分区大小及边界在运行时不能改变。动态分区：根据作业大小动态地建立分区，分区的大小、数目可变。动态分区：根据作业大小
29、动态地建立分区，分区的大小、数目可变。2、分区分配算法 为了将一个作业装入内存，应按照一定的分配算法从空闲分区表（链）中选 出一个满足作业需求的分区分配给作业。目前常用分配算法有： 首次适应算法（First-Fit） 循环首次适应算法（Next-Fit） 最佳适应算法（Best-Fit） 最坏适应算法（Worst-Fit）按地址递增的次序排列。按地址递增的次序排列。按容量大小递增的次序排列。按容量大小递增的次序排列。按容量大小递减的次序排列。按容量大小递减的次序排列。4.3 基本分页存储管理方式n基本分页存储管理方式基本分页存储管理方式v在分页存储管理方式中，如果不具备页面对换功能，不在分页存
30、储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，这种存储管理方式称为纯分页或支持虚拟存储器功能，这种存储管理方式称为纯分页或基本基本分页存储管理方式分页存储管理方式 。v在调度作业运行时，必须将它的所有页面一次调入内存，在调度作业运行时，必须将它的所有页面一次调入内存，但逻辑上连续的各个页所对应的内存块可以不连续。但逻辑上连续的各个页所对应的内存块可以不连续。v特殊的固定分区特殊的固定分区+离散分配离散分配三、地址结构q 逻辑地址：例：地址长为32位，其中0-11位为页内地址，即每页的大小为212=4KB；12-31位为页号，地址空间最多允许有220 =1M页。q 物理地址：例：地
31、址长为22位，其中0-11位为块内地址，即每块的大小为212=4KB，与页相等；12-21位为块号，内存地址空间最多允许有210 =1K块。 31 12 11 0页号页号p位移量位移量w21 12 11 0块号块号b 块内位移块内位移d给定一个逻辑地址空间中的地址为给定一个逻辑地址空间中的地址为A，页面的大小为，页面的大小为L，则页号则页号P和页内地址和页内地址d可按下式求得：可按下式求得： APINTLdA mod L其中，其中，INT是整除函数，是整除函数，mod是取余函数。是取余函数。例如，系统的页面大小为例如，系统的页面大小为1 KB，设，设A = 2170 B，则由上式可，则由上式可
32、以求得以求得P = 2，d = 122。 q已知已知逻辑地址逻辑地址求页号和页内地址求页号和页内地址页从页从0开始编号开始编号三、地址结构三、地址结构三、地址结构例题例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即 2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即 16页=24页，所以页号为4位。故逻辑地址至少应为15位。 （2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为1
33、1位；其中块号表内存空间最多允许的块数即 8块=23块，所以块号为3位。故内存空间至少应为14位，即214 =16KB。页号p位移量w块号b块内偏移d四、地址变换例题例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将十进制逻辑地址1011，2148，5012转化为相应的物理地址。页号块号02132136四、地址变换例题 解：设页号为P，页内位移为W，逻辑地址为A，内存地址为M，页面大小为L，则 P = int ( A / L ) W = A mod L页号块号02132136对于逻辑地址对于逻辑地址1011P=int(1011/1024)=0W=1011 m
34、od 1024=1011A=1011=(0,1011)查页表第查页表第0页在第页在第2块，所以物理地址为块，所以物理地址为M=1024*2+1011= 3059。四、地址变换例题 对于逻辑地址为2148P= int (2148/1024)=2W=2148 mod 1024=100A=2148=(2,100)查页表第2页在第1块，所以物理地址为M=1024*1+100=1124。 对于逻辑地址5012P= int ( 5012/1024)=4W=5012 mod 1024=916因页号超过页表长度，该逻辑地址非法。页号块号02132136有效访问内存的时间有效访问内存的时间 T=PTLB*（TT
35、LB+TM）+ （1-PTLB ）*（ TTLB + 2TM ） 其中其中,PTLB为快表的命中率为快表的命中率,TTLB为快表的访问时间为快表的访问时间, TM为内存的访问时间为内存的访问时间具有快表的地址变换机构具有快表的地址变换机构938220页表长度页表长度页表始址页表始址45224528823120+段长90，所以该段为非法段。段号段内地址0430212004302120分段地址变换例题分页和分段的主要区别页式存储管理段式存储管理目的实现非连续分配， 解决碎片问题更好地满足用户需要信息单位页（物理单位）段（逻辑单位）大小固定（由系统定）不定（由用户程序定）内存分配单位页段作业地址空间
36、一维二维优点有效解决了碎片问题（没有外碎片，每个内碎片不超过页大小）；有效提高内存的利用率；程序不必连续存放。更好地实现数据共享与保护；段长可动态增长；便于动态链接二者优点的结合二者优点的结合-段页式存储管理段页式存储管理存储管理策略分类 存储管理： 实存管理 分区（Partitioning）（连续分配方式）（包括固定分区、可变分区和伙伴系统） 分页（Paging） 分段（Segmentation） 段页式（Segmentation with paging） 虚存管理 请求分页（Demand paging） - 主流技术 请求分段（Demand segmentation） 请求段页式（Dema
37、nd SWP ）离散分配离散分配虚拟存储器的概念 虚拟存储技术的种类 请求分页 请求分段 请求段页式 速度和容量 虚拟存储量的扩大是以牺牲CPU工作时间以及内外存交换时间为代价。 虚拟存储器的容量取决于主存与辅存的容量，最大容量是由计算机的地址结构决定。 虚拟存储器的逻辑地址空间理论上不受物理存储器的限制。 如32位机器，虚拟存储器的最大容量就是4G，再大CPU无法直接访问。二、虚拟存储器的实现方法1、分页请求系统 在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。 它允许只装入若干页的用户程序和数据，便可启动运行，以后在硬件支持下通过调页功能和置换页功能，陆续将
38、要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。 系统须设置相应的硬件支持和软件：（1）硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。（2）软件：请求调页功能和页置换功能的软件。4.7 请求分页中的页面置换算法 常用的页面置换算法： 最佳置换算法OPT：选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。先进先出置换算法FIFO：选择先进入内存的页面予以淘汰。最近最久未使用置换算法LRU：选择最近一段时间最长时间没有被访问过的页面予以淘汰。最佳置换算法(Optimal,OPT)例n 假定系统为某进程分配了假定系统为某进程分配了3个物理块个物理块，
39、进程运行时的页面，进程运行时的页面走向为走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时，开始时3个物理块均为空，个物理块均为空，计算采用计算采用最佳置换最佳置换页面淘汰算法时的缺页率？页面淘汰算法时的缺页率？注：注：实际上这种算法无法实现，因为页面访问的未来顺序很实际上这种算法无法实现，因为页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。难精确预测，但可用该算法评价其它算法的优劣。页面走向123412512345物理块1物理块2物理块3缺页1缺缺缺缺缺缺 缺缺缺缺缺缺缺缺12312121212121212333444442555555(7/12)最佳置换算法最佳
40、置换算法：选择永远不再需要的页面或最选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。长时间以后才需要访问的页面予以淘汰。先进先出置换算法(FIFO)例题1、假定系统为某进程分配了、假定系统为某进程分配了3个物理块个物理块，进程运行时的，进程运行时的页面走向为页面走向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时，开始时3个物理块均个物理块均为空，计算采用为空，计算采用先进先出先进先出页面淘汰算法时的缺页率？页面淘汰算法时的缺页率？页面走向123412512345物理块1111444555555物理块222211111333物理块33332222244缺页缺 缺 缺 缺
41、 缺 缺 缺缺 缺(9/12)最近最久未使用算法LRU例最近最久未使用算法（最近最久未使用算法（LRU, Least Recently Used）例：假定系统为某进程分配了例：假定系统为某进程分配了3个物理块个物理块，进程运行时的页面走，进程运行时的页面走向为向为 1,2,3,4,1,2,5,1,2,3,4,5，开始时，开始时3个物理块均为空，计算采个物理块均为空，计算采用用最近最久未使用最近最久未使用页面淘汰算法时的缺页率？页面淘汰算法时的缺页率？页面走向123412512345物理块1111444555333物理块222211111144物理块33332222225缺页缺 缺 缺 缺 缺
42、缺 缺缺 缺 缺(10/12)最近最久未使用置换算法最近最久未使用置换算法：选择最近一段时选择最近一段时间最长时间没有被访问过的页面予以淘汰。间最长时间没有被访问过的页面予以淘汰。第五章 设备管理5.5.4. SPOOLing技术 SPOOLing（Simultaneous Peripheral Operations On-Line，外部设备联机并行操作），也称假脱机技术。 SPOOLing 是指在多道程序的环境下，利用多道程序中的一道或两道程序来模拟外围控制机，从而在联机的条件下实现脱机 I/O 的功能。5.5.4. SPOOLing技术 设计思想：可以用常驻内存的进程去模拟一台外围机，从而
43、用一台主机就可完成脱机技术中需用三台计算机完成的工作。 功能: 把独占设备改造为逻辑共享设备。 把一台物理I/O设备虚拟为多台逻辑I/O设备。 组成：专门负责I/O的常驻内存的进程；输入井、输出井；输入缓冲区、输出缓冲区。1、磁盘性能 磁盘性能简述n数据的组织n磁盘结构：磁道、柱面、扇区n磁盘物理块的地址：磁头号、柱面号、扇区号n存储容量磁头（盘面）数磁道（柱面）数每道扇区数每扇区字节数n假定一块硬盘磁头数为4，柱面数为2048，每个磁道有扇区2048，每个扇区记录1KB（字节），该硬盘储存容量为：n4204820481024/1024/1024/1024 = 16 Gn42048204810
44、24/1000/1000/1000 = 17.2 G （厂家）1、磁盘性能 访问时间 寻道时间Ts：将磁头从当前位置移到指定磁道所经历的时间Ts=mn+s。s为启动磁臂的时间，n为移动的磁道数，m为常数。 旋转延迟时间Tr ：指定扇区移动到磁头下面所经历的时间。设每秒r转，则Tr1/2r（均值） 传输时间Tt：将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间Ttb/rN 。其中b：读写字节数，N：每道上的字节数。 控制器时间Tc 访问时间Ta：Ta=mn+s+1/2r+b/rN+Tc1、磁盘性能 例：假设磁盘空闲（ 没有排队延迟）。平均寻道时间是9ms，传输速 度是4MB/s，转速是720
45、0rpm，控制器的开销是 1ms。问读或写一个512字 节的扇区的平均时间是多少？ 解：访问时间=寻道时间+旋转延迟时间+传输时间+控制器时间 访问时间=9ms+0.5/7200(rpm)+0.5(k)/4(MB/s)+1ms = 9ms+0.5/7200/60/1000+0.5/ (41024/1000)+1ms 9+4.2+0.122+1=14.322ms1秒等于1000毫秒 磁盘调度算法 磁盘调度算法 早期的磁盘调度算法 先来先服务FCFS 最短寻道时间优先SSTF 扫描算法 扫描(SCAN)/电梯(LOOK)算法 循环扫描(CSCAN)算法 本教材不区分SCAN算法和LOOK算法，我们
46、做题时都按LOOK算法解决（不扫描到头！）FCFS 先来先服务按进程请求访问磁盘的先后次序进行调度下磁道下磁道移道数移道数98451838537146122 85141081241106559672总道数总道数640平均平均80磁头臂来回反复移动，增长了等待时间，对机械结构不利磁头臂来回反复移动，增长了等待时间，对机械结构不利最短寻道时间优先（SSTF）选择从当前磁头位置所需寻道时间最短的请求。选择从当前磁头位置所需寻道时间最短的请求。下磁道下磁道移道数移道数6512672373014 23988412224124218359总道数总道数236平均平均29.5可能使一些申请者在较长时间内得不得
47、服务的机会可能使一些申请者在较长时间内得不得服务的机会假定磁头向磁道号增加的方向移动。假定磁头向磁道号增加的方向移动。下磁道下磁道移道数移道数65126729831122 24124218359371461423总道数总道数299平均平均37.4Scan/Look算法算法第六章 文件管理6.2 文件逻辑结构 对任一文件存在着两种形式的结构： 文件的逻辑结构（文件组织）u从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性。u顺序文件、索引文件、索引顺序文件 文件的物理结构（文件的存储结构）u从系统的观点出发，是指文件在外存上的存储组织形式，与存储介质的存储
48、性能有关。u顺序文件、链接文件、索引文件 注：文件的逻辑结构和物理结构都将影响文件的检索速度。多级索引分配 如果每个盘块的大小为1 KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。在两级索引时， 最多可存放的盘块号总数N = 256256 = 64 K个，即所允许的文件最大长度为64 MB。 如果每个盘块的大小为4 KB，每个盘块号占4个字节，单级索引时所允许的文件最大长度为 如果采用两级级索引时最大文件长度为10244 KB =4MB102410244 KB =4GB混合索引分配混合索引分配：地址项既采用了直接地址，又采用了多级索引分配方式。练习题例：存放在某个磁盘上的文件
49、系统，采用混合索引分配方式，其FCB中共有13个地址项（索引项），第0-9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址。问： （1） 该文件系统允许文件的最大长度是多少？ （2） 将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。 （3） 假设某个文件的FCB己在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？练习题解：（1） 该文件系统中一个文件的最大
50、长度可达： 10 + 170 + 170170 + 170170170 = 4942080块，共 4942080512字节 = 2471040 KB 2.36GB或用如下解法：直接索引项可管理上限：100.5KB=5KB；一次间接索引项可管理上限：1700.5KB=85KB；二次间接索引项可管理上限：1701700.5KB=14450KB；三次间接索引项可管理上限：1701701700.5KB=2456500KB；可管理文件上限：5KB+85KB+14450KB+2456500KB。练习题解：（2） 5000512得到商为9，余数为392，即字节偏移量5000对应的逻辑块号为9，块内偏移量为3
