最全计算机操作系统期末复习课件

计算机操作系统复习

2022年11月25日1计算机操作系统复习

2022年11月22日1标题添加点击此处输入相关文本内容点击此处输入相关文本内容前言点击此处输入相关文本内容标题添加点击此处输入相关文本内容2标题添加点击此处输入相点击此处输入前言点击此处输入标题添加点课程主要内容教材内容操作系统引论（第1章）进程管理（第2章）处理机调度与死锁（第3章）存储管理（第4章）设备管理（第5章）文件管理（第6章）UNIX系统内核结构(第10章）3课程主要内容教材内容3计算题类型总结利用信号量实现进程同步处理机调度算法（周转时间）银行家算法分区存储管理算法逻辑地址物理地址变换请求分页中的页面置换算法磁盘访问时间磁盘调度算法（平均移道数）混合索引分配文件控制块和索引结点位示图4计算题类型总结利用信号量实现进程同步4第一章操作系统引论

5第一章操作系统引论

51.3操作系统的基本特征并发性(Concurrence)共享性(Sharing)虚拟性(Virtual)异步性(Asynchronism)基本特征:最重要特性，其它三种特性以此为前提。61.3操作系统的基本特征并发性(Concurrence)操作系统的形成单道批处理系统多道批处理系统操作系统的形成在多道程序系统中增设一组软件以有效加以解决，同时增设方便用户使用计算机的软件，这样便形成了操作系统。操作系统：是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序集合。7操作系统的形成单道批处理系统操作系统：是一组控制和管理计算机操作系统的结构设计传统的操作系统结构无结构操作系统模块化OS结构分层式OS结构现代操作系统结构微内核的OS结构：将客户/服务器技术、面向对象技术用于OS中所形成的OS结构。8操作系统的结构设计传统的操作系统结构8第二章进程管理

9第二章进程管理

92、进程process的基本特征

（1）结构特征从结构上看，每个进程（进程实体）都是由程序段、数据段及进程控制块（PCB）组成。

（2）动态性

进程的实质是程序在处理机上的一次执行过程，因此是动态性的。所以动态性是进程的最基本的特征。同时动态性还表现在进程则是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而消亡。进程的定义、特征102、进程process的基本特征进程的定义、特征10

进程在运行期间并非固定处于某个状态，而是不断从一个状态转换到另一个状态。二、进程状态2、进程状态转换11进程在运行期间并非固定处于某个状态，而是不断从一个状态转换具有挂起状态的进程状态活动就绪执行挂起调度时间片完活动阻塞事件发生等待事件静止就绪静止阻塞激活挂起事件发生激活挂起12具有挂起状态的进程状态活动就绪执行挂起调度时间片完活动阻塞事线程的基本概念进程是资源分配的单位，而线程是处理机调度的单位。一个进程可以创建一个或多个线程。多个线程会争夺CPU，在不同的状态之间进行转换。线程也是一个动态的概念，也有一个从创建到消亡的生命过程，具多种状态。同一进程中的所有线程都具有相同的地址空间（进程的地址空间）。13线程的基本概念进程是资源分配的单位，而线程是处理机调度的单位线程的实现方式

线程的实现方式内核支持线程的实现直接利用系统调用进行线程控制。用户级线程的实现不能直接利用系统调用。为了取得内核的服务（获得系统资源），需要借助中间系统（运行时系统、轻型进程）。14线程的实现方式线程的实现方式14同步机制应遵循的规则空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。忙则等待:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入死等状态。让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。15同步机制应遵循的规则空闲让进:当无进程处于临界区时，表明临界信号量机制信号量机制信号量用于表示资源数目或请求使用某一资源的进程个数的整型量。整型信号量记录型信号量信号量集（AND信号量集、一般信号量集）16信号量机制信号量机制16利用信号量实现进程同步例：进程A与进程B共享同一文件file，设此文件要求互斥使用，则可将file作为临界资源，有关file的使用程序段分别为临界区CSA和CSB。

semaphoremutex=1;PA:{ L1：P(mutex); CSA;

V(mutex);

remainderofprocessA; GOTOL1;}PB:{ L2:P(mutex); CSB;

V(mutex); remainderofprocessB;GOTOL2;}

17利用信号量实现进程同步例：进程A与进程B共享同一文件fileS1S3S2S4S5S6S7S8例：利用信号量来描述前趋图关系利用信号量实现进程同步18S1S3S2S4S5S6S7S8例：利用信号量来描述前趋图关

具有8个结点的前趋图。图中的前趋图中共有10条有向边，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信号量实现进程同步19具有8个结点的前趋图。图中的前趋图中共有10条有向边Structsmaphorea,b,c,d,e,f,g,h,i,j=0,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利用信号量实现进程同步20Structsmaphorea,b,c,d,e,f,g,2.4经典进程的同步问题

在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者—消费者问题哲学家进餐问题读者—写者问题其他同步问题212.4经典进程的同步问题在多道程序“哲学家进餐”问题问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。解决死锁问题的例子22“哲学家进餐”问题问题描述：解决死锁问题的例子22哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。23哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。设置一个初值为4的信号量r，只允许4个哲学家同时去拿左筷子，这样就能保证至少有一个哲学家可以就餐，不会出现饿死和死锁的现象。原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。24哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};semaphorer=4;voidphilosopher(inti){while(true){think();wait(r);//请求进餐wait(chopstick[i]);//请求左手边的筷子wait(chopstick[(i+1)mod5]);//请求右手边的筷子eat();signal(chopstick[(i+1)mod5]);//释放右手边的筷子signal(chopstick[i]);//释放左手边的筷子signal(r);//释放信号量rthink();}}25哲学家进餐问题的改进解法semaphorechopstic哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。解法1：利用AND型信号量机制实现。原理：多个临界资源，要么全部分配，要么一个都不分配，因此不会出现死锁的情形。26哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();Swait(chopstick[i];chopstick[(i+1)mod5]);eat();Ssignal(chopstick[(i+1)mod5];chopstick[i]);think();}}27哲学家进餐问题的改进解法semaphorechopstic哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。解法2：利用信号量的保护机制实现。原理：通过互斥信号量mutex对eat()之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现。28哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起哲学家进餐问题的改进解法semaphoremutex=1;semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();wait(mutex);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);signal(mutex);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);think();

}}29哲学家进餐问题的改进解法semaphoremutex=哲学家进餐问题的改进解法方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。原理：按照下图，将是2,3号哲学家竞争3号筷子，4,5号哲学家竞争5号筷子。1号哲学家不需要竞争。最后总会有一个哲学家能获得两支筷子而进餐。先申请的哲学家会较先可以吃饭并释放筷子，因此不会出现饿死的哲学家。122133445530哲学家进餐问题的改进解法方法三：规定奇数号哲学家先拿左筷子再哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){if(imod2==0)//偶数哲学家，先右后左。{wait(chopstick[(i+1)mod5]);wait(chopstick[i]);eat();signal(chopstick[i]);signal(chopstick[(i+1)mod5]);}Else//奇数哲学家，先左后右。{wait(chopstick[i]);wait(chopstick[(i+1)mod5]);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);}}}31哲学家进餐问题的改进解法semaphorechopstic第三章处理机调度与死锁

32第三章处理机调度与死锁

32提交作业调度作业调度作业状态转换图后备退出完成一、调度的层次就绪阻塞就绪阻塞运行交换调度进程调度（线程调度）33提交作业调度作业调度作业状态转换图后备退出完成一、调度的层次FCFS例题例：下面三个作业几乎同时到达系统并立即进行FCFS调度：作业名所需CPU时间作业128作业210作业31假设提交顺序为1、2、3，则平均作业周转时间T=若提交顺序改为作业2、1、3，则T=若提交顺序改为作业3、2、1，则T=由此可以看出，FCFS调度算法的平均作业周转时间与作业提交的顺序有关。(28+38+39)/3=35(10+38+39)/3=29(1+11+39)/3=1734FCFS例题例：下面三个作业几乎同时到达系统并立即进行FCF进程调度算法先来先服务FCFS例1：进程名到达时间服务时间A01B1100C

2

1D3

10035进程调度算法先来先服务FCFS35周转时间服务时间完成时间-到达时间开始时间+服务时间上一个进程的完成时间1 101 1001101 102100100102 2021991.9936周转时间服务时间完成时间-到达时间开始时间+服务时间上一个进执行顺序：SJF/SPF（非抢占式）A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84周转时间＝结束时间-到达时间带权周转时间＝周转/服务37执行顺序：SJF/SPF（非抢占式）A033103ABCDE基本思想：多级反馈队列调度算法是时间片轮转算法和优先级调度算法的综合和发展，通过动态调整进程优先级和时间片大小，不必事先估计进程的执行时间。多级反馈队列可兼顾多方面的系统目标，是目前公认的一种较好的进程调度算法。FCFS+优先级+RR+抢占七、多级反馈队列调度算法38基本思想：七、多级反馈队列调度算法38七、多级反馈队列调度算法---实现思想（1）设置多个就绪队列，并为每个队列赋予不同的优先级。队列1的优先级最高，其余队列逐个降低。（2）每个队列中进程执行时间片的大小也各不相同，进程所在队列的优先级越高，其相应的时间片就越短。（3）当一个新进程进入系统时，首先将它放入队列1的末尾，按FCFS等待调度。如能完成，便可准备撤离系统，反之由调度程序将其转入队列2的末尾，按FCFS再次等待调度，如此下去，最后进入队列n按RR算法调度执行。（4）仅当队列1为空时，才调度队列2中的进程运行。若一个队列中的进程正执行，此时有新进程进入优先级较高的队列中，则新进程将抢占运行，原进程转移至本队列队尾。39七、多级反馈队列调度算法---实现思想（1）设置多个就绪队列二、产生死锁的原因竞争资源进程间推进顺序非法三、产生死锁的必要条件

互斥条件（mutualexclusion）请求和保持条件（hold-while-applying）不剥夺条件（nonpreemption）环路等待条件（circularwait）40二、产生死锁的原因竞争资源三、产生死锁的必要条件四、处理死锁的基本方法目前处理死锁的基本方法有：预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。解除死锁：当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。银行家算法41四、处理死锁的基本方法目前处理死锁的基本方法有：银行家算法4银行家算法假定系统中有5个进程P0到P4，3类资源及数量分别为A(10个），B（5个），C（7个），T0时刻的资源分配情况如下

表1T0时刻的资源分配表42银行家算法假定系统中有5个进程P0到P4，3类资源及数量分（1）T0时刻的安全性利用安全性算法对T0时刻的资源分配情况进行分析:T0时刻存在着一个安全序列{P1,P3,P4,P2,P0}，故系统是安全的。表2T0时刻的安全性检查表532true332532743true743745true745104710471057truetrue332ABCAvailable43（1）T0时刻的安全性T0时刻存在着一个安全序列{P1,P(2)

P1请求资源Request1(1,0,2)

P1发出请求向量Request1(1,0,2)，已知Need1(1,2,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、Allocation44(2)P1请求资源Request1(1,0,2)P1P1请求资源Request1(1,0,2)时的资源分配表(302)(020)(230)45P1请求资源Request1(1,0,2)时的资源分配表(3由安全性检查分析得知：此时刻存在着一个安全序列{P1,P3,P4,P2,P0}，故系统是安全的，可以立即将P1所申请的资源分配给它。4)利用安全性算法检查资源分配后此时系统是否安全P1请求资源Request1(1,0,2)时的安全性检查表230532true532743true743745true7451047true10471057true46由安全性检查分析得知：此时刻存在着一个安全序列{P1（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)，表示资源不够，则让P4等待47（3）P4请求资源Request4(3,3,0)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分配资源，并修改相应的向量。48(4)P0请求资源Request0(0,2,0)P0发表5P0请求资源Request0(0,2,0)时的资源分配表[210][030][723]

4)进行安全性检查资源分配后此时系统是否安全，因Avaliable(2,1,0)已不能满足任何进程需要，故系统进入不安全状态，此时系统不分配资源。49表5P0请求资源Request0(0,2,0)时的资源分第四章存储管理

50第四章存储管理

504.2连续分配存储管理方式连续分配方式（分区技术）：指为一个用户程序分配一片连续的内存空间。

单一连续分区分配（静态分区技术）：仅用于单用户单任务系统固定分区分配（静态分区技术）：可用于多道系统可变分区分配（动态分区技术）可重定位可变分区分配（动态分区技术）：引入了动态重定位和内存紧凑技术伙伴系统（动态分区技术）静态分区：作业装入时一次完成，分区大小及边界在运行时不能改变。动态分区：根据作业大小动态地建立分区，分区的大小、数目可变。514.2连续分配存储管理方式连续分配方式（分区技术）：指为2、分区分配算法为了将一个作业装入内存，应按照一定的分配算法从空闲分区表（链）中选出一个满足作业需求的分区分配给作业。目前常用分配算法有：首次适应算法（First-Fit）循环首次适应算法（Next-Fit）最佳适应算法（Best-Fit）最坏适应算法（Worst-Fit）按地址递增的次序排列。按容量大小递增的次序排列。按容量大小递减的次序排列。522、分区分配算法为了将一个作业装入内存，应按照一定的分配算法4.3基本分页存储管理方式基本分页存储管理方式在分页存储管理方式中，如果不具备页面对换功能，不支持虚拟存储器功能，这种存储管理方式称为纯分页或基本分页存储管理方式。在调度作业运行时，必须将它的所有页面一次调入内存，但逻辑上连续的各个页所对应的内存块可以不连续。特殊的固定分区+离散分配534.3基本分页存储管理方式基本分页存储管理方式53三、地址结构逻辑地址：例：地址长为32位，其中0-11位为页内地址，即每页的大小为212=4KB；12-31位为页号，地址空间最多允许有220=1M页。物理地址：例：地址长为22位，其中0-11位为块内地址，即每块的大小为212=4KB，与页相等；12-21位为块号，内存地址空间最多允许有210=1K块。

3112110页号p位移量w2112110块号b块内位移d54三、地址结构逻辑地址：31

给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：

其中，INT是整除函数，mod是取余函数。例如，系统的页面大小为1KB，设A=2170B，则由上式可以求得P=2，d=122。

已知逻辑地址求页号和页内地址页从0开始编号三、地址结构55给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号三、地址结构例题例：设有一页式存储管理系统，向用户提供的逻辑地址空间最大为16页，每页2048B，内存总共有8个存储块，试问逻辑地址至少应为多少位？内存空间有多大？解：（1）页式存储管理系统的逻辑地址为：其中页内地址表每页的大小即2048B=2*1024B=211B，所以页内地址为11位；页号表最多允许的页数即16页=24页，所以页号为4位。故逻辑地址至少应为15位。（2）物理地址为：其中块内地址表每块的大小与页大小相等，所以块内地址也为11位；其中块号表内存空间最多允许的块数即8块=23块，所以块号为3位。故内存空间至少应为14位，即214=16KB。56三、地址结构例题例：设有一页式存储管理系统，向用户提供的逻辑四、地址变换例题例1：若在一分页存储管理系统中，某作业的页表如下表所示，已知页面大小为1024B，试将十进制逻辑地址1011，2148，5012转化为相应的物理地址。57四、地址变换例题例1：若在一分页存储管理系统中，某作业的页表四、地址变换例题解：设页号为P，页内位移为W，逻辑地址为A，内存地址为M，页面大小为L，则P=int(A/L)W=AmodL对于逻辑地址1011P=int(1011/1024)=0W=1011mod1024=1011A=1011=(0,1011)查页表第0页在第2块，所以物理地址为M=1024*2+1011=3059。58四、地址变换例题解：设页号为P，页内位移为W，逻辑地址为A，四、地址变换例题对于逻辑地址为2148P=int(2148/1024)=2W=2148mod1024=100A=2148=(2,100)查页表第2页在第1块，所以物理地址为M=1024*1+100=1124。对于逻辑地址5012P=int(5012/1024)=4W=5012mod1024=916因页号超过页表长度，该逻辑地址非法。59四、地址变换例题对于逻辑地址为214859有效访问内存的时间

T=PTLB*（TTLB+TM）+（1-PTLB

）*（TTLB+2TM

）其中,PTLB为快表的命中率,TTLB为快表的访问时间,TM为内存的访问时间具有快表的地址变换机构938220页表长度页表始址45224528823120+<页表寄存器逻辑地址物理地址越界中断页合法页表快表TTLB：访问快表但没有命中2TM：分别访问页表和数据60有效访问内存的时间具有快表的地址变换机构938220页表长度例：

有一页式系统，其页表存放在主存中。（1）如果对主存的一次存取需要100ns，试问实现一次页面访问的存取时间是多少？（2）如果系统加有快表，对快表的一次存取需要20ns,若平均命中率为85%，试问此时的存取时间为多少？解：（1）页表放主存中，则实现一次页面访问需2次访问主存，一次是访问页表，确定所存取页面的物理块，从而得到其物理地址，一次根据物理地址存取页面数据。所以实现一次页面访问的存取时间为：100ns*2=200ns（2）系统有快表，则实现一次页面访问的存取时间为：

0.85*(20ns+100ns)+(1-0.85)*(20ns+2*100ns)=135ns

有效内存访问时间例题61例：有一页式系统，其页表存放在主存中。有效内存访问时间例题在为作业分配内存时以段为单位，分配一段连续的物理地址空间；段间不必连续。作业的逻辑地址空间是二维的，其逻辑地址由段号和段内地址组成。地址映射需要CPU的硬件支持（地址变换机构）注：内存分配分页管理中，逻辑地址是线性地址（一维）。分段管理中，段号S和段内位移d不能形成一个线性地址，因为它实际上是代表着段长和段内位移两个变量。由于这两个变量没有特定的限制范围而无法用一个变量来替代，因此分段管理的逻辑地址是二维地址。62在为作业分配内存时以段为单位，分配一段连续的物理地址空间；段例1、在一个段式存储管理系统中，其段表为：段号内存起始地址段长02105001235020210090313505904193895试求右表中逻辑地址对应的物理地址是什么？解：逻辑地址为：逻辑地址对应的物理地址为：210+430=640。逻辑地址因为段内地址120>段长90，所以该段为非法段。分段地址变换例题63例1、在一个段式存储管理系统中，其段表为：分段地址变换例题6分页和分段的主要区别二者优点的结合----段页式存储管理64分页和分段的主要区别二者优点的结合----段页式存储管理64存储管理策略分类存储管理：实存管理分区（Partitioning）（连续分配方式）（包括固定分区、可变分区和伙伴系统）分页（Paging）分段（Segmentation）段页式（Segmentationwithpaging）虚存管理请求分页（Demandpaging）--主流技术请求分段（Demandsegmentation）请求段页式（DemandSWP）离散分配65存储管理策略分类存储管理：离散分配65虚拟存储器的概念虚拟存储技术的种类请求分页请求分段请求段页式速度和容量虚拟存储量的扩大是以牺牲CPU工作时间以及内外存交换时间为代价。虚拟存储器的容量取决于主存与辅存的容量，最大容量是由计算机的地址结构决定。虚拟存储器的逻辑地址空间理论上不受物理存储器的限制。如32位机器，虚拟存储器的最大容量就是4G，再大CPU无法直接访问。66虚拟存储器的概念虚拟存储技术的种类66二、虚拟存储器的实现方法1、分页请求系统在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。它允许只装入若干页的用户程序和数据，便可启动运行，以后在硬件支持下通过调页功能和置换页功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。系统须设置相应的硬件支持和软件：（1）硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。（2）软件：请求调页功能和页置换功能的软件。67二、虚拟存储器的实现方法1、分页请求系统674.7请求分页中的页面置换算法常用的页面置换算法：最佳置换算法OPT：选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。先进先出置换算法FIFO：选择先进入内存的页面予以淘汰。最近最久未使用置换算法LRU：选择最近一段时间最长时间没有被访问过的页面予以淘汰。684.7请求分页中的页面置换算法常用的页面置换算法：最佳置换算法(Optimal,OPT)例

假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最佳置换页面淘汰算法时的缺页率？注：实际上这种算法无法实现，因为页面访问的未来顺序很难精确预测，但可用该算法评价其它算法的优劣。1缺缺缺缺缺缺缺12312121212121212333444442555555(7/12)最佳置换算法：选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。69最佳置换算法(Optimal,OPT)例假定系统为某进程分先进先出置换算法(FIFO)例题1、假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用先进先出页面淘汰算法时的缺页率？(9/12)70先进先出置换算法(FIFO)例题1、假定系统为某进程分配了3最近最久未使用算法LRU例最近最久未使用算法（LRU,LeastRecentlyUsed）例：假定系统为某进程分配了3个物理块，进程运行时的页面走向为1,2,3,4,1,2,5,1,2,3,4,5，开始时3个物理块均为空，计算采用最近最久未使用页面淘汰算法时的缺页率？(10/12)最近最久未使用置换算法：选择最近一段时间最长时间没有被访问过的页面予以淘汰。71最近最久未使用算法LRU例最近最久未使用算法（LRU,Le第五章设备管理

72第五章设备管理

725.5.4.SPOOLing技术SPOOLing（SimultaneousPeripheralOperationsOn-Line，外部设备联机并行操作），也称假脱机技术。SPOOLing是指在多道程序的环境下，利用多道程序中的一道或两道程序来模拟外围控制机，从而在联机的条件下实现脱机I/O的功能。735.5.4.SPOOLing技术SPOOLing（Sim5.5.4.SPOOLing技术设计思想：可以用常驻内存的进程去模拟一台外围机，从而用一台主机就可完成脱机技术中需用三台计算机完成的工作。功能:

把独占设备改造为逻辑共享设备。把一台物理I/O设备虚拟为多台逻辑I/O设备。组成：专门负责I/O的常驻内存的进程；输入井、输出井；输入缓冲区、输出缓冲区。745.5.4.SPOOLing技术设计思想：可以用常驻内存1、磁盘性能磁盘性能简述数据的组织磁盘结构：磁道、柱面、扇区磁盘物理块的地址：磁头号、柱面号、扇区号存储容量＝磁头（盘面）数×磁道（柱面）数×每道扇区数×每扇区字节数假定一块硬盘磁头数为4，柱面数为2048，每个磁道有扇区2048，每个扇区记录1KB（字节），该硬盘储存容量为：4×2048×2048×1024/1024/1024/1024=16G4×2048×2048×1024/1000/1000/1000=17.2G（厂家）751、磁盘性能磁盘性能简述751、磁盘性能访问时间寻道时间Ts：将磁头从当前位置移到指定磁道所经历的时间Ts=m×n+s。s为启动磁臂的时间，n为移动的磁道数，m为常数。旋转延迟时间Tr：指定扇区移动到磁头下面所经历的时间。设每秒r转，则Tr＝1/2r（均值）传输时间Tt：将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间Tt＝b/rN。其中b：读写字节数，N：每道上的字节数。控制器时间Tc访问时间Ta：Ta=m×n+s+1/2r+b/rN+Tc761、磁盘性能访问时间761、磁盘性能例：假设磁盘空闲（没有排队延迟）。平均寻道时间是9ms，传输速度是4MB/s，转速是7200rpm，控制器的开销是1ms。问读或写一个512字节的扇区的平均时间是多少？解：访问时间=寻道时间+旋转延迟时间+传输时间+控制器时间访问时间=9ms+0.5/7200(rpm)+0.5(k)/4(MB/s)+1ms=9ms+0.5/7200/60/1000+0.5/(4×1024/1000)+1ms≈9+4.2+0.122+1=14.322ms1秒等于1000毫秒771、磁盘性能例：假设磁盘空闲（没有排队延迟）。平均寻道时间磁盘调度算法磁盘调度算法早期的磁盘调度算法先来先服务FCFS最短寻道时间优先SSTF扫描算法扫描(SCAN)/电梯(LOOK)算法循环扫描(CSCAN)算法本教材不区分SCAN算法和LOOK算法，我们做题时都按LOOK算法解决（不扫描到头！）78磁盘调度算法磁盘调度算法78FCFS先来先服务按进程请求访问磁盘的先后次序进行调度磁头臂来回反复移动，增长了等待时间，对机械结构不利79FCFS先来先服务按进程请求访问磁盘的先后次序进行调度磁最短寻道时间优先（SSTF）选择从当前磁头位置所需寻道时间最短的请求。可能使一些申请者在较长时间内得不得服务的机会80最短寻道时间优先（SSTF）选择从当前磁头位置所需寻道时间最假定磁头向磁道号增加的方向移动。Scan/Look算法81假定磁头向磁道号增加的方向移动。Scan/Look算法81第六章文件管理

82第六章文件管理

826.2文件逻辑结构对任一文件存在着两种形式的结构：文件的逻辑结构（文件组织）从用户观点出发，所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于物理特性。顺序文件、索引文件、索引顺序文件文件的物理结构（文件的存储结构）从系统的观点出发，是指文件在外存上的存储组织形式，与存储介质的存储性能有关。顺序文件、链接文件、索引文件注：文件的逻辑结构和物理结构都将影响文件的检索速度。836.2文件逻辑结构对任一文件存在着两种形式的结构：83多级索引分配如果每个盘块的大小为1KB，每个盘块号占4个字节，则在一个索引块中可存放256个盘块号。在两级索引时，最多可存放的盘块号总数N=256×256=64K个，即所允许的文件最大长度为64MB。如果每个盘块的大小为4KB，每个盘块号占4个字节，单级索引时所允许的文件最大长度为如果采用两级级索引时最大文件长度为1024×4KB=4MB1024×1024×4KB=4GB84多级索引分配如果每个盘块的大小为1KB，每个盘块号占4个字混合索引分配直接地址(多个)一次间接地址二次间接地址混合索引分配：地址项既采用了直接地址，又采用了多级索引分配方式。索引结点（FCB主部）索引块85混合索引分配直接地址(多个)一次间接地址二次间接地址混合索引练习题例：存放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项（索引项），第0-9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘块的大小为512字节，盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址。问：（1）该文件系统允许文件的最大长度是多少？（2）将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。（3）假设某个文件的FCB己在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？512/3≈17086练习题例：存放在某个磁盘上的文件系统，采用混合索引分配方式，练习题解：（1）该文件系统中一个文件的最大长度可达：

10+170+170×170+170×170×170=4942080块，共4942080×512字节=2471040KB

≈2.36GB或用如下解法：直接索引项可管理上限：10×0.5KB=5KB；一次间接索引项可管理上限：170×0.5KB=85KB；二次间接索引项可管理上限：170×170×0.5KB=14450KB；三次间接索引项可管理上限：170×170×170×0.5KB=2456500KB；可管理文件上限：5KB+85KB+14450KB+2456500KB。87练习题解：（1）该文件系统中一个文件的最大长度可达：87练习题解：（2）

5000／512得到商为9，余数为392，即字节偏移量5000对应的逻辑块号为9，块内偏移量为392。由于9<10，故可直接从该文件的FCB的第9个地址项处得到物理盘块号，块内偏移量为392。15000／512得到商为29，余数为152，即字节偏移量15000对应的逻辑块号为29，块内偏移量为152。由于10<29<10+170，而29-10=19，故可从FCB的第10个地址项，即一次间址项中得到一次间址块的地址；并从一次间址块的第19项（即该块的第57~59这3个字节）中获得对应的物理盘块号，块内偏移量为152。

盘块号用3个字节描述88练习题解：（2）盘块号用3个字节描述88练习题150000／512得到商为292，余数为496，即字节偏移量150000对应的逻辑块号为292，块内偏移量为496。由于10+170<292<10+170+170×170，而292-(10+170)=112，112／170得到商为0，余数为112，故可从FCB的第11个地址项，即二次间址项中得到二次间址块的地址，并从二次间址块的第0项中获得一个一次间址块的地址，再从这一次间址块的第112项中获得对应的物理盘块号，块内偏移量为496。89练习题150000／512得到商为292，余数为496，即字练习题

（3）假设某个文件的FCB己在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘，最多需要几次访问磁盘？解：由于文件的FCB己在内存，为了访问文件中某个位置的内容，最少需要1次访问磁盘（即可通过直接地址直接读文件盘块），最多需要4次访问磁盘（第一次是读三次间址块，第二次是读二次间址块，第三次是读一次间址块，第四次是读文件盘块）。90练习题（3）假设某个文件的FCB己在内存，但其他信息均在文件控制块（FCB）文件目录文件目录是一种数据结构，用于标识系统中的文件及其物理地址，将文件名映射到外存物理位置，供检索时使用。目录项构成文件目录的项目（目录项就是FCB）文件目录：文件控制块的有序集合。目录文件为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件。文件目录和目录文件是同一事物的两种称谓。从用途角度来看称其为文件目录，从实现角度来看称其为目录文件。91文件控制块（FCB）文件目录文件目录和目录文件是同一事物的两索引结点索引结点引入文件目录通常是存放在磁盘上的，当文件很多时，文件目录可能要占用大量的盘块。在查找目录的过程中，先将存放目录文件的第一个盘块中的目录调入内存，然后把用户所给定的文件名与目录项中的文件名逐一比较。若未找到指定文件，便再将下一个盘块中的目录项调入内存。设目录文件所占用的盘块数为N，按此方法查找，则查找一个目录项平均需要调入盘块(N+1)/2次。92索引结点索引结点引入92解：在引入索引节点前，256个目录项的目录总共需要占用256×64／512=32个盘块。在目录中检索到一个文件平均启动磁盘次数为（1+32）／2=16.5。

在引入索引节点后，每个目录项中只需存放文件名和索引节点的编号，因此256个目录项的目录总共需要占用256×（8+2）／512=5个盘块。因此，找到匹配的目录项平均需要启动3次磁盘；而得到索引结点编号后还需启动磁盘将对应文件的索引结点读入内存，故平均需要启动磁盘4次。文件控制块和索引结点93解：在引入索引节点前，256个目录项的目录总共需要占用2566.5文件存储空间的管理文件存储空间的管理可采用连续分配和离散分配方式。内存分配基本不采用连续分配方式。外存管理中，小文件经常采用连续分配方式，大文件采用离散分配方式。存储空间的管理方法空闲表法和空闲链法位示图法成组链接法文件存储器空间布局946.5文件存储空间的管理文件存储空间的管理可采用连续分配和6.5.2位示图法位示图（二维）利用二进制的一位（bit）来表示磁盘中一个盘块的使用情况。每个字节的每一位都对应了一个物理块的状态。当该位取1时，表示对应的物理块已分配；取0时表示该物理块未分配。空闲空间表现为位图或位向量。特点：占空间少，可放入内存，易于访问。956.5.2位示图法位示图（二维）95位示图法12345678910123456796位示图法1234练习题1例1：设某系统的磁盘有500块，块号为：0，1，2，3，…，499。（1）若用位示图法管理这500块的盘空间，当字长为32位时，此位示图占了几个字？（2）第i字的第j位对应的块号是多少？（其中：i=0，1，2，…，j=0，1，2，3，…）解：（1）位示图法就是在内存用一些字建立一张位示图，用其中的每一位表示一个盘块的使用情况，通常用“1”表示占用，“0”表示空闲。因此，本问题中位示图所占的字数为：500／32=15.625≈16。（2）第i字的第j位对应的块号N=32*i+j。97练习题1例1：设某系统的磁盘有500块，块号为：0，1，2，提问与解答环节Questionsandanswers98提问与解答环节98添加标题添加标题添加标题添加标题此处结束语点击此处添加段落文本.您的内容打在这里，或通过复制您的文本后在此框中选择粘贴并选择只保留文字99添加标题添加添加添加标题此处结束语点击此处添加段落文本.感谢聆听Theusercandemonstrateonaprojectororcomputer,orprintthepresentationandmakeitintoafilm讲师：XXXX日期：20XX.X月100感谢聆听讲师：XXXX日期：20XX.X月100计算机操作系统复习

2022年11月25日101计算机操作系统复习

2022年11月22日1标题添加点击此处输入相关文本内容点击此处输入相关文本内容前言点击此处输入相关文本内容标题添加点击此处输入相关文本内容102标题添加点击此处输入相点击此处输入前言点击此处输入标题添加点课程主要内容教材内容操作系统引论（第1章）进程管理（第2章）处理机调度与死锁（第3章）存储管理（第4章）设备管理（第5章）文件管理（第6章）UNIX系统内核结构(第10章）103课程主要内容教材内容3计算题类型总结利用信号量实现进程同步处理机调度算法（周转时间）银行家算法分区存储管理算法逻辑地址物理地址变换请求分页中的页面置换算法磁盘访问时间磁盘调度算法（平均移道数）混合索引分配文件控制块和索引结点位示图104计算题类型总结利用信号量实现进程同步4第一章操作系统引论

105第一章操作系统引论

51.3操作系统的基本特征并发性(Concurrence)共享性(Sharing)虚拟性(Virtual)异步性(Asynchronism)基本特征:最重要特性，其它三种特性以此为前提。1061.3操作系统的基本特征并发性(Concurrence)操作系统的形成单道批处理系统多道批处理系统操作系统的形成在多道程序系统中增设一组软件以有效加以解决，同时增设方便用户使用计算机的软件，这样便形成了操作系统。操作系统：是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序集合。107操作系统的形成单道批处理系统操作系统：是一组控制和管理计算机操作系统的结构设计传统的操作系统结构无结构操作系统模块化OS结构分层式OS结构现代操作系统结构微内核的OS结构：将客户/服务器技术、面向对象技术用于OS中所形成的OS结构。108操作系统的结构设计传统的操作系统结构8第二章进程管理

109第二章进程管理

92、进程process的基本特征

（1）结构特征从结构上看，每个进程（进程实体）都是由程序段、数据段及进程控制块（PCB）组成。

（2）动态性

进程的实质是程序在处理机上的一次执行过程，因此是动态性的。所以动态性是进程的最基本的特征。同时动态性还表现在进程则是有生命期的，它因创建而产生，因调度而执行，因得不到资源而暂停，因撤消而消亡。进程的定义、特征1102、进程process的基本特征进程的定义、特征10

进程在运行期间并非固定处于某个状态，而是不断从一个状态转换到另一个状态。二、进程状态2、进程状态转换111进程在运行期间并非固定处于某个状态，而是不断从一个状态转换具有挂起状态的进程状态活动就绪执行挂起调度时间片完活动阻塞事件发生等待事件静止就绪静止阻塞激活挂起事件发生激活挂起112具有挂起状态的进程状态活动就绪执行挂起调度时间片完活动阻塞事线程的基本概念进程是资源分配的单位，而线程是处理机调度的单位。一个进程可以创建一个或多个线程。多个线程会争夺CPU，在不同的状态之间进行转换。线程也是一个动态的概念，也有一个从创建到消亡的生命过程，具多种状态。同一进程中的所有线程都具有相同的地址空间（进程的地址空间）。113线程的基本概念进程是资源分配的单位，而线程是处理机调度的单位线程的实现方式

线程的实现方式内核支持线程的实现直接利用系统调用进行线程控制。用户级线程的实现不能直接利用系统调用。为了取得内核的服务（获得系统资源），需要借助中间系统（运行时系统、轻型进程）。114线程的实现方式线程的实现方式14同步机制应遵循的规则空闲让进:当无进程处于临界区时，表明临界资源处于空闲状态，应允许一个请求进入临界区的进程立即进入自己的临界区，以有效地利用临界资源。忙则等待:当已有进程进入临界区时，表明临界资源正在被访问，因而其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。有限等待:对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入死等状态。让权等待:当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。115同步机制应遵循的规则空闲让进:当无进程处于临界区时，表明临界信号量机制信号量机制信号量用于表示资源数目或请求使用某一资源的进程个数的整型量。整型信号量记录型信号量信号量集（AND信号量集、一般信号量集）116信号量机制信号量机制16利用信号量实现进程同步例：进程A与进程B共享同一文件file，设此文件要求互斥使用，则可将file作为临界资源，有关file的使用程序段分别为临界区CSA和CSB。

semaphoremutex=1;PA:{ L1：P(mutex); CSA;

V(mutex);

remainderofprocessA; GOTOL1;}PB:{ L2:P(mutex); CSB;

V(mutex); remainderofprocessB;GOTOL2;}

117利用信号量实现进程同步例：进程A与进程B共享同一文件fileS1S3S2S4S5S6S7S8例：利用信号量来描述前趋图关系利用信号量实现进程同步118S1S3S2S4S5S6S7S8例：利用信号量来描述前趋图关

具有8个结点的前趋图。图中的前趋图中共有10条有向边，可设10个信号量，初值均为0；有8个结点，可设计成8个并发进程，具体描述如下：S1S3S2S4S5S6S7S8agefbcdhij利用信号量实现进程同步119具有8个结点的前趋图。图中的前趋图中共有10条有向边Structsmaphorea,b,c,d,e,f,g,h,i,j=0,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利用信号量实现进程同步120Structsmaphorea,b,c,d,e,f,g,2.4经典进程的同步问题

在多道程序环境下，进程同步问题十分重要，出现一系列经典的进程同步问题，其中有代表性有：生产者—消费者问题哲学家进餐问题读者—写者问题其他同步问题1212.4经典进程的同步问题在多道程序“哲学家进餐”问题问题描述：有五个哲学家，他们的生活方式是交替地进行思考和进餐。他们共用一张圆桌，分别坐在五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥饿时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。解决死锁问题的例子122“哲学家进餐”问题问题描述：解决死锁问题的例子22哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。123哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿左筷子，最终能保证至少有一位哲学家能进餐，并在用完后释放两只筷子供他人使用。设置一个初值为4的信号量r，只允许4个哲学家同时去拿左筷子，这样就能保证至少有一个哲学家可以就餐，不会出现饿死和死锁的现象。原理：至多只允许四个哲学家同时进餐，以保证至少有一个哲学家能够进餐，最终总会释放出他所使用过的两支筷子，从而可使更多的哲学家进餐。124哲学家进餐问题的改进解法方法一：至多只允许四位哲学家同时去拿哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};semaphorer=4;voidphilosopher(inti){while(true){think();wait(r);//请求进餐wait(chopstick[i]);//请求左手边的筷子wait(chopstick[(i+1)mod5]);//请求右手边的筷子eat();signal(chopstick[(i+1)mod5]);//释放右手边的筷子signal(chopstick[i]);//释放左手边的筷子signal(r);//释放信号量rthink();}}125哲学家进餐问题的改进解法semaphorechopstic哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。解法1：利用AND型信号量机制实现。原理：多个临界资源，要么全部分配，要么一个都不分配，因此不会出现死锁的情形。126哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();Swait(chopstick[i];chopstick[(i+1)mod5]);eat();Ssignal(chopstick[(i+1)mod5];chopstick[i]);think();}}127哲学家进餐问题的改进解法semaphorechopstic哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起时才允许进餐。解法2：利用信号量的保护机制实现。原理：通过互斥信号量mutex对eat()之前取左侧和右侧筷子的操作进行保护，可以防止死锁的出现。128哲学家进餐问题的改进解法方法二：仅当哲学家的左右手筷子都拿起哲学家进餐问题的改进解法semaphoremutex=1;semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){think();wait(mutex);wait(chopstick[i]);wait(chopstick[(i+1)mod5]);signal(mutex);eat();signal(chopstick[(i+1)mod5]);signal(chopstick[i]);think();

}}129哲学家进餐问题的改进解法semaphoremutex=哲学家进餐问题的改进解法方法三：规定奇数号哲学家先拿左筷子再拿右筷子，而偶数号哲学家相反。原理：按照下图，将是2,3号哲学家竞争3号筷子，4,5号哲学家竞争5号筷子。1号哲学家不需要竞争。最后总会有一个哲学家能获得两支筷子而进餐。先申请的哲学家会较先可以吃饭并释放筷子，因此不会出现饿死的哲学家。1221334455130哲学家进餐问题的改进解法方法三：规定奇数号哲学家先拿左筷子再哲学家进餐问题的改进解法semaphorechopstick[5]={1，1，1，1，1};voidphilosopher(inti){while(true){if(imod2==0)//偶数哲学家，先右后左。{wait(chopstick[(i+1)mod5]);wait(chopstick[i]);eat();signal(chops