计算机操作系统原理.ppt

《计算机操作系统原理.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统原理.ppt（170页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机操作系统原理李国2007.12.3基本授课内容一、操作系统引论二、进程管理三、处理机调度与死锁四、存储器管理五、设备管理六、文件管理七、操作系统接口第一章 操作系统引论1.1 操作系统的目标和作用1.2 操作系统的发展过程1.3 操作系统的基本特性1.4 操作系统的主要功能 1.5 操作系统的结构设计1.1操作系统的目标和作用一、操作系统的目标方便性有效性可扩充性开放性二、操作系统的作用 1、作为用户与计算机硬件系统之间的接口。2、作为计算机系统资源的管理者主要包括四类资源：处理机、存储器、I/O设备以及信息（数据与程序）。3、操作系统用作扩充机器虚拟机：在裸机的基础上，每增加一层新的操

2、作系统的软件，就变成了功能更为强大的虚拟机或虚机器。三、推动操作系统发展的主要动力三、推动操作系统发展的主要动力1、不断提高计算机资源利用率2、方便用户3、器件的不断更新换代4、计算机体系结构的不断发展。1.2 操作系统的发展过程一、无操作系统的计算机系统1、人工操作方式 （1946 50年代，电子管时代）年代，电子管时代）【特点特点】：计算机资源昂贵：计算机资源昂贵，没有操作系统，没有操作系统【工作方式工作方式】：用户：用户既是程序员、操作员，还是计算机专业人员；用户：用户既是程序员、操作员，还是计算机专业人员；编程语言：为机器语言；编程语言：为机器语言；输入输出：纸带或卡片；输入输出：纸带

3、或卡片；【计算机的工作特点计算机的工作特点】：用户独占全机：用户独占计算机所有资源，资源利用率低；用户独占全机：用户独占计算机所有资源，资源利用率低；CPU等待用户：计算前，手工装入纸带或卡片；计算完成后，手工等待用户：计算前，手工装入纸带或卡片；计算完成后，手工卸取纸带或卡片；卸取纸带或卡片；CPU利用率低；利用率低；【主要矛盾主要矛盾】：计算机处理能力的提高，手工操作的低效率计算机处理能力的提高，手工操作的低效率用户独占全机的所有资源；用户独占全机的所有资源；2、脱机输入/输出方式 引入外围机控制数据的提前录入和延后输出，具体参照P5 图1-2二、单道批处理系统1、单道批处理系统的处理过程

4、引入监督程序，成批的作业首先在外存排队等待，由监督程序负责将每一个作业装入内存，处理完成后，再掉调入下一个作业，直至运行完毕。2、单道批处理系统的特征自动性顺序性单道性三、多道批处理系统1、多道程序设计的基本概念用户提交的作业都先存放在外存的后备队列中，由作业调度程序按一定的算法选择若干作业调入内存，共享CPU和系统的各种资源。2、多道批处理的特征（1）多道性：在内存中有多个程序（严格而言为进程）同时执行（宏观上）；（2）无序性：进入内存的顺序与执行完的顺序无关；（3）调度性：经过2次调度，先调度到内存，转换为进程后，进行进程调度，要CPU进行执行。3、多道批处理系统的优缺点：（1）资源利用率

5、高了；（2）系统吞吐量大了；（3）平均周转时间长；（4）无交互能力。4、多道批处理系统需要解决的问题（1）处理机管理问题（2）内存管理问题（3）I/O设备管理问题（4）文件管理问题（5）作业管理问题处理上述问题组成一系列程序的集合，由此构成了完整意义上的操作系统。操作系统的定义：操作系统是一组控制和管理计算机硬件和软件资源，合理的组织计算机工作流程以及方便用户使用的程序的集合。四、分时系统1、定义：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。分时系统的结构示意图2、分时系统实现的关键问题（1）及时接收：多路卡（2）及时处

6、理：分时间片的原则。为此：（1）用户作业可以直接进入内存 （2）时间片选择大小要适当。3、分时系统的特征：（1）多路性（2）独立性（3）及时性（4）交互性五、实时系统1、理解：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致的运行。2、实时系统的应用领域：实时控制：要求与被控制的变化速度相比，其反应速度足够快；工作安全可；需要人工干预时，操作简便。如生产过程控制，宇航自动控制等。实时信息处理系统：要求计算机能够在容许的延迟时间内，相应外部的事件请求，完成对该事件的处理，并控制所有的实时设备和实时任务协调运行。如飞机订票系统,期货、股票交易系统等。3、实

7、时系统与分时系统的比较（1）多路性（2）独立性（3）及时性（4）交互性（5）高可靠性1.3操作系统的基本特性一、并发性(concurrency)多个事件在同一时间段内发生。操作系统是一个并发系统，各进程间的并发，系统与应用间的并发。操作系统要完成这些并发过程的管理。并行(parallel)是指在同一时刻发生。在多道程序处理时，宏观上并发，微观上交替执行（在单处理器情况下）。程序的静态实体是可执行文件，而动态实体是进程（或称作任务），并发指的是进程。二、共享性(sharing)多个进程共享有限的计算机系统资源。操作系统要对系统资源进行合理分配和使用。资源在一个时间段内交替被多个进程所用。互斥共享

8、方式（如音频设备），资源分配后到释放前，不能被其他进程所用。同时访问方式，（如可重入代码，磁盘文件）。资源分配难以达到最优化三、虚拟性(virtual)一个物理实体映射为若干个对应的逻辑实体（分时或分空间）。虚拟是操作系统管理系统资源的重要手段，可提高资源利用率。CPU每个用户（进程）的“虚处理机”。存储器每个进程都占有的地址空间（指令数据堆栈）。显示设备多窗口或虚拟终端如虚拟光驱。四、异步性(asynchronism)异步性也称不确定性，指进程的执行顺序和执行时间及执行结果的不确定性：程序执行结果不确定，不可再现。相同输入与环境下多次运行结果不同。多道程序设计环境下，程序按异步方式运行。多个

9、进程并发执行，“时走时停”，不可预知每个进程的运行推进快慢，引发执行顺序与时间的不确定。1.4 操作系统的主要功能一、处理机管理功能：可归结为进程管理，包括以下方面 进程控制：进程的创建和撤消、进程状态的转换等；进程同步：协调进程执行的顺序关系；进程通信；调度：作业调度和进程调度两层。二、存储器管理功能：1、内存分配2、内存保护3、地址映射4、内存扩充 三、设备管理功能：1、设备分配2、设备处理（相当于启动）3、缓冲管理 4、虚拟设备 四、文件管理功能：1、文件存储空间管理2、目录管理3、文件读写管理4、文件保护。五、用户接口：1、命令接口2、程序接口3、图形接口1.5操作系统的结构设计一、传

10、统的操作系统结构1、无结构操作系统操作系统是由一组过程的集合，各过程之间相互调用，在操作系统内部不存在任何结构，也因此称为整体系统结构2、模块化操作系统结构操作系统是由按其功能划分为若干个具有一定独立性和大小的模块。每个模块具有某个方面的管理功能，规定好模块之间的接口。3、分层式操作系统结构从物理机器开始，在上面不断添加新的层次软件，实现若干功能，构成满足需要的操作系统。二、微内核操作系统1、微内核是20世纪90年代发展的现代操作系统内核结构，典型的操作系统如WindowsNT。实现了以微内核为操作系统核心，以客户/服务器为基础，并且采取了面向对象的程序设计方法的新型体系结构。2、客户/服务器

11、模式操作系统划分为两部分：一部分用于提供各种服务的一组服务器，如进程服务器、存储器服务器等，运行在用户态；另一部分是内核，用于处理客户和服务器之间的通信。CPU执行内核程序运行在核心态。3、微内核技术：（1）定义：精心设计的，能实现现代操作系统核心功能的小型内核，与一般操作系统不同，更小更精练，运行在核心态，开机长驻内存，并非一个完整的操作系统，是构建通用操作系统的重要基础。（2）微内核的基本功能-进程管理-存储器管理-进程通信管理-I/O设备管理第二章 进程管理2.1进程的基本概念一、程序的顺序执行及特征1、参照课本P27 图2-12、特征：顺序性封闭性可再现性二、程序的并发执行及其特征1、

12、前趋图：利用有向无环图中结点描述进程，有向弧描述进程执行顺序。2、并发执行的特征间断性失去并发性不可再现性I1I2I3I4C1C2C3C4P1P2P3P4三、进程的特征与状态1、进程的特征（1）结构特征：进程实体主要包括程序段、数据段和进程控制块三部分。（2）动态性是进程最基本的特征，表现在进程的创建、状态的转换、撤消等进程是有生命周期的，程序本身是静态的。（3）并发性，所谓前面提到程序的并发实质上是进程的并发（4）独立性：CPU进行调度的独立单位以及进行资源分配的基本单位（5）异步性，推进顺序是异步的。2、进程的定义：（1）进程是程序的一次执行。（2）进程是一个程序及其数据在处理机上顺序执行

13、时所发生的活动。（3）进程是一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。3、进程的三种基本状态（1）就绪状态：当进程刚刚建立后处于就绪状态，具备所有资源，只差CPU调度就可执行，一个系统中处于就绪状态的进程有多个，构成就绪队列。（2）执行状态：获得CPU，进行执行，在单处理机内只有1个执行状态进程；（3）阻塞状态：处于执行状态的进程因为发生某事件而暂时无法继续执行，如等待I/O，申请缓冲区等，可以根据不同的阻塞原因放到不同的阻塞队列中，从而构成阻塞队列。程序1程序2程度段数据段 程度段数据段 进程1进程2进

14、程1进程2Pcb区域进程1pcb进程2pcb进程i pcb四、进程控制块1、进程控制块的作用进程控制块（PCB）是为了描述和控制进程的运行，为进程定义的数据结构，属于进程实体的一部分，是操作系统中最重要的记录型数据结构，记录了操作系统所需要的、用于描述进程当前情况及控制进程运行的全部信息，操作系统通过PCB来对并发执行的进程来进行控制和管理的。进程存在的唯一标志是PCB。2、进程控制块的基本组成（1）进程标识符：a.内部标识符就是PCB区中的标号，是数字。b.外部标识符就是进程的实际名字（2）处理机的状态，中断时处理状态的保护，断点地址保护（3）进程调度所需信息（如进程状态、优先级、进程等待时

15、间及阻塞原因等（4）进程控制信息：如程序段和数据段的地址、资源清单、进程同步与通信机制、进程队列中各进程的链接指针。3、PCB的组织方式：（1）链接方式（2）索引方式2.2进程控制一、进程控制中心：操作系统内核通过原语操作实现。1、内核是基于硬件的第一层软件扩充，并长驻内存。它为系统对进程和资源进行控制和管理，提供了良好的环境。内核通常包括中断处理、时钟管理、进程控制、进程通信和调度原语，以及资源管理中的基本操作等。2、所谓原语，是由若干条机器指令构成，用以完成特定功能的一段程序，为了保证其操作的正确性，它应该是原子操作，即原语是一个不可分割的操作。二、基本进程控制原语1、进程创建原语（1）申

16、请空白PCB（2）为新进程分配资源。（3）初始化进程控制块（4）将新进程插入到就绪队列。2、进程终止原语（1）根据标识符，从PCB集合中检索出该进程的PCB，读出进程状态。（2）若被终止进程属执行状态，需要重新调度新进程执行。（3）该进程所有子孙进程一并终止。（4）被终止进程的全部资源都被释放。3、进程阻塞原语block()（1）将阻塞进程由执行状态变为阻塞状态，并加入到阻塞队列中（2）系统重新调度新进程进行执行。4、进程唤醒原语wakeup()将被唤醒进程状态由阻塞变换为就绪状态，从阻塞队列中删除，加入到就绪队列中。2.3 进程同步一、进程同步的基本概念1、两种形式的制约关系（1）间接相互制

17、约关系：因为临界资源的特性造成进程间的制约。（2）直接相互制约关系：进程之间相互协作、互相制约关系。2、临界资源：如打印机、磁带机等一段时间内只允许一个进程进行使用的资源。3、临界区：每个进程中访问临界资源的那段代码成为临界区。整个程序段分为：进入区、临界区、退出区以及剩余区。4、同步机制应遵循的规则：（1）空闲让进（2）忙则等待（3）有限等待（4）让权等待 二、信号量机制：1、整型信号量Wait(s):while s0 do no-op s:=s-1;Signal(s):s:=s+1;2、记录型信号量Wait(s):s.value=s.value-1;if s.value0 block(s.

18、l);Signal(s):s.value=s.value+1;if s.value=0 wakeup(s.l)记录型信号量的物理意义Wait:相当于分配资源的过程。若有资源进行分配，则分配后就不会小于0，因此可以完全执行完Wait原语，然后进入临界区，如减1后出现小于0的情况则表示实际上已经没有资源可以分配了，因此该进程要放到阻塞队列L中，此时S.VALUE的绝对值就是阻塞进程的数量。Signal:相当于释放资源的过程。一个进程执行完正常释放资源，但加1后仍小于等于0表示它原来是个负数，因此阻塞队列里有等待该资源没有满足的阻塞进程，因此，在释放资源的同时要唤醒阻塞进程。如加1后正常的正数，就光

19、释放完资源就结束了。3、记录型信号量的应用（1）实现互斥对于N个进程对1个临界资源的互斥共享，每个进程的算法描述：VAR Mutex：=1；进程pi：Repeat Wait（Mutex）；临界区；Signal（Mutex）until false;（2）实现前趋关系：见p45 图2-10Var a,b,c,d,e,f,g:=0,0,0,0,0,0,0S1:s1;signal(a);signal(b);S2:wait(a);s2;signal(c);signal(d);S3:wait(b);s3;signal(e);S4:wait(c);s4;signal(f);S5:wait(d);s3;sig

20、nal(g);S6:wait(e);wait(f);wait(g);s6;3、利用信号量实现进程同步1个数据缓冲区输入进程输出进程输入进程：输入进程：Repeat 输入数据；输入数据；wait(P1);放数据入缓冲区；放数据入缓冲区；signal(P2);until false;计算进程：计算进程：Repeat wait(p2);从缓冲区取数据；从缓冲区取数据；signal(P1);计算数据；计算数据；until false;.4经典进程同步问题一、生产者-消费者问题生产者进程消费者进程具有n个缓冲区的缓冲池 多个生产者进程和多个消费者进程共享一个有多个生产者进程和多个消费者进程共享一个有N个

21、缓冲区个缓冲区的缓冲池，生产者进程负责输入数据，消费者进程负责输出的缓冲池，生产者进程负责输入数据，消费者进程负责输出数据，两个相互合作。用信号量机制把每个进程的执行过程数据，两个相互合作。用信号量机制把每个进程的执行过程表达出来。因为缓冲区是临界资源，一段时间内只能有表达出来。因为缓冲区是临界资源，一段时间内只能有1个进个进程使用，所以，对缓冲区的放数据及取数据只能有一个进程程使用，所以，对缓冲区的放数据及取数据只能有一个进程来使用缓冲区，存在互斥问题；同时，生产来使用缓冲区，存在互斥问题；同时，生产-与消费构成同步与消费构成同步关系，相互合作，互相制约。关系，相互合作，互相制约。VAR m

22、utex:=1,empty=n;full=0;buffter0.n-1;in out:=0,0;生产者进程i：Repeat 生产数据nextp；wait(empty);wait(mutex);bufferin:=nextp;in=(in+1)%n;signal(full);until false;消费者进程i：Repeat wait(full);wait(mutex);Nextc=buffer(out);out=(out+1)%n;signal(empty);until false;二、哲学家就餐问题 5个哲学家围做一个圆桌，5支筷子分布与每人的两侧，每人先是思考问题，然后拿起左右两边的筷子就

23、餐，后放筷子继续思考问题。用信号量机制描述每人的活动过程。分析：筷子5支，都属于临界资源，因此互斥使用；哲学家i：Repeat wait(SM);wait(chopsticki);wait(chopstick(i+1)%5);就餐；signal(chopsticki);signal(chopstick(i+1)%5);signal(sm);继续思考；until false;Chopstick0.4=1;sm=4(5支筷子最多允许4个人同时去抢，才总有一个人拿到2支，才能吃饭，他放下后别人可以继续用，若允许5个人都抢，可能会出现一人1支筷子，出现僵持死锁状态)三、读者-写者问题一个数据文件可以同

24、时允许有多个读者进行访问，但每次只允许1个写者进行修改，读者和写者不能同时出现。分析：把多个读者作为一个整体来考虑，则加上 n个写者的话，这n+1个对象对数据块互斥访问，需要1个互斥信号量wmutex=1来控制;另外对于读者整体中，考虑与写者互斥的只是第一个读者来时要考虑的，有了第一个，其他读者就可以跟着进来，同样，释放资源时候也只是最后一个读者，其他读者想走就撤就可以。为了表示到底有多少读者，引入记数变量readcount，而对变量的使用，属于临界资源，一次只允许一个进程使用，所以再引入信号量rwmutex=1;读者进程i：REPAET wait(rmutex);if readcout=0

25、wait(wmutex);Readcount+;signal(rmutex);访问数据文件；wait(rmutex);Readcount-;if readcout=0 wait(wmutex);signal(rmutex);until false;写者进程i：REPAET wait(wmutex);修改文件；signal(wmutex);until false;例题1、司机与售票员的合作问题VAR S1=1;S2=0;司机：Wait(s1);启动车辆；正常行车；到站停车Signal(s2);售票员：Wait(s2);开车门；上下乘客；关车门Signal(s1);售票例题2：假定阅览室能容纳10

26、0个人阅读，读者进入和离开阅览室时，都必须在阅览室门口的一个登记表上登记。假定每次只允许一个人登记和撤消登记，设阅览室内有100个座位，用信号量机制描述读者进程的同步算法。读者进程i:Var s=100;mutex=1;Wait(s);Wait(mutex);查登记表，并置某座位为占用态Signal(mutex);在座位上坐下阅读；Wait(mutex);查登记表，并置某座位为空闲状态Signal(mutex);Signal(s);例题：桌子上有一只盘子只能放一只水果，爸爸专门向盘子中放苹果，妈妈专门向盘子中放橘子，一个儿子专等吃盘子中的橘子，一个女儿专等吃盘子中的苹果。用信号量机制实现他们之

27、间的同步机制。Var s=1,s1=s2=0爸爸：准备苹果；wait(s);将苹果放在盘子内；signal(s1);妈妈：准备橘子；wait(s);将橘子放在盘子内；signal(s2);女儿：wait(s1);从盘子上拿走苹果；signal(s);吃苹果；儿子：wait(s2);从盘子上拿走橘子；signal(s);吃橘子；2.5管程机制一、定义：一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据。引入管程的目的是避免信号量机制书写中的麻烦，具体例子参考P53。2.6进程通信一、进程通信的类型1、共享存储器系统（1）基于共享数据结

28、构的通信方式（2）基于共享存储区的通信方式2、消息传递系统（1）直接通信方式：Send(receiver,message);Receive(sender,message);（2）间接通信方式Send(mailbox,message);Receive(mailbox,message);3、管道通信：所谓管道是用于连接一个读进程和一个写进程以实现他们通信的一个共享文件，又名Pipe文件，本身提供了互斥和同步进程的能力。）二、消息缓冲队列通信机制1、消息缓冲队列通信机制中的数据结构Type message buffer=record sender:发送者进程标识符；size:消息长度；text:消息

29、正文；next:指向下一个消息缓冲区的指针 end2、PCB中有关通信的数据项Mq:消息队列队首指针；Mutex:消息队列互斥信号量Sm:消息队列资源信号量3、发送原语Procedure send(receiver,a)BeginGetbuf(a.size,i);i.sender=a.sizer;i.size=a.size;i.text=a.size;i.next=0;Getid(pcb set,receiver.j);Wait(j.mutex);Insert(j.mq,i);Signal(j.mutex);Signal(j.sm);End;4、接收原语Procedure receive(b)

30、BeginJ=internal name;Wait(j.sm);Wait(j.mutex);Remove(j.mq,i);Signal(j.mutex);b.sender=i.sizer;b.size=i.size;b.text=i.size;End;2.7线程一、线程的基本概念1、线程的引入进程的两个属性：资源分配的独立单位；CPU调度的独立单位。进一步提高并发程度和减少系统开销引入线程。2、线程的属性（1）轻型实体（2）独立调度和分派的基本单位（3）可并发执行（4）共享进程资源。第三章 处理机调度与死锁3.1处理机调度的基本概念一、高级、中级和低级调度1、高级调度（作业调度）：由作业调度程

31、序按照一定算法选择若干作业进入内存，创建出进程，分配必要的资源，将新进程挂到就绪队列中。（1）接纳多少作业（2）接纳哪些作业2、低级调度（进程调度）：决定就绪队列的进程谁获得处理机，然后再由分派程序执行把处理机分配给该进程。非抢占方式：一旦处理机分配给某个进程就要它一直执行下去，直至进程完成或者发生某事件而被阻塞时，才再把处理机分配给其他进程。抢占方式：正在执行的进程，若有新的优先级更高的进程到来后则停止正在执行的进程，新进程抢占CPU。抢占的标准为：（1）优先权原则；（2）短作业优先原则；（3）时间片原则。3、中级调度存储管理中的对换功能，把内存中暂时不运行的进程换出到外存对换区，而把外存中

32、具备运行条件的进程换入内存，称为中级调度。二、调度队列模型1、仅有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型3、同时具有三级调度的调度队列模型三、选择调度方式和调度算法的若干准则1、面向用户的准则（1）周转时间：从作业被提交给系统开始，到作业完成为止的这段时间间隔。包括四部分时间：作业在外存后备队列上等待调度的时间、进程在就绪队列上等待进程调度的时间、进程在CPU上执行的时间、进程等待I/O操作完成的时间。平均周转时间平均带权周转时间（2）响应时间。（3）截止时间的保证（4）优先权准则2、面向系统的准则（1）系统吞吐量高（2）处理机利用率好（3）各类资源的平衡利用。3.2 调度

33、算法一、先来先服务和短作业优先调度算法1、先来先服务调度算法算法思想：（1）作业调度：每次调度都从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源，创建进程，然后放入就绪队列。（2）进程调度：每次调度是从就绪队列中，选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。通常要考虑，目前系统是否满足进程资源要求。例子参考P76二、短作业（进程）优先调度算法对短作业或短进程进行优先调度的算法。短作业调度算法是从后备队列中选择一个后若干个估计运行时间最短的作业，将它们内调入内存运行。短进程调度是从就绪队列中选出一估计运行时间最短的进程，分配处理机。注：（1）F

34、CFS算法不利于短作业。（2）SJF算法不利于长作业。作业名进入输入井需计算时间（分）需要内存容量（KB）A8：064215B8：183060C8：302450D8：362410E8：421220作业名进入内存开始执行结束执行周转时间带权周转A8：068：068：484242/42B8：188：489：186060/30D8：369：189：426666/24C9：189：4210：069696/24E9：1810：0610：189696/12FCFS：作业名进入内存开始执行结束执行周转时间带权周转A8：068：068：484242/42D8：368：489：123636/24E9：129：1

35、29：244242/12B8：189：249：549696/30C9：549：5410：18108108/24SJF：三、高优先权优先调度算法1、优先权调度算法的类型（1）非抢占方式：一旦处理机分配给某个进程后，该进程一直执行下去，直至完成，其它进程不得抢占CPU。（2）抢占方式：把处理机分配给优先权最高的进程执行，若来新进程优先级更高，则抢占CPU。2、优先权的类型：（1）静态优先权：创建进程时确定，整个运行期间保持不变。一般用0-255或0-7中的某个整数来表示，有的系统中数字越大，优先级越高，有的系统相反。（2）动态优先权：随着进程的推进或等待时间的增加，优先权而发生改变。作业名进入输入

36、井需计算时间（分）优先级（数大级高）A8：00601B8：30502C8：40304D8：50103非强占方式：ACDB强占方式：A-B-C-D-B-A3、高响应比优先调度算法（1）优先权的确定：优先权=（等待时间+要求服务时间）/要求服务时间（2）高响应比优先调度算法既照顾到了短作业，又考虑了长作业。四、基于时间片的轮转调度算法1、时间片轮转法将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。2、多级反馈队列调度算法是目前公认的一种较好的调度算法：a.设定多个就绪队列，每个队列设定不同优先级，由高到低，每个队列中进程获得时间片有小到大

37、；b.新进程进入内存，先放第1队列的末尾，按FCFS原则进行运行，单位时间片运行完结束，否则放到第2队列末尾，依次类推，直至全部放到最后一级队列，完全采取时间片轮转原则进行运行c.仅当前面队列全部空闲时，才运行后面队列中的进程，若正在执行第I级队列的某进程，来一个新进程，则将当前执行进程放到该级队列的末尾，专而执行新进程。兼顾了长作业和短作业，采用了FCFS以及时间片轮转和优先级高低综合运用的一种调度算法。3.5产生死锁的原因和必要条件一、死锁的定义和原因1、定义：所谓死锁是指多个进程在运行过程中因争夺资源而造成的一种僵局，若无外力作用，它们都将无法再向前推进。2、产生死锁的原因（1）竞争资源

38、：可剥夺和非剥夺性资源/临时性资源（2）进程间推进顺序非法。二、产生死锁的必要条件（1）互斥条件：资源本身的特性（2）请求和保持条件：在请求不到新资源的时候进程不释放原来的资源（3）不剥夺条件：进程获得的资源，为使用完前不可被剥夺（4）环路等待条件：进程对资源的请求形成一个请求环形链 三、处理死锁的基本方法1、预防死锁2、避免死锁3、检测死锁4、解除死锁3.6 预防死锁的方法一、预防死锁1、打破请求和保持条件：要求进程一次性申请到全部资源后再运行，不会产生死锁，但效率降低2、打破不剥夺条件：要求进程提出新资源要求不被满足后，必须释放原来的保持的资源，损失代价严重；3、打破环路等待条件：对资源进

39、行线性排序编号，要求每个进程必须从低号到高号申请资源，而不考虑进程实际申请资源的先后顺序。二、系统安全状态1、安全状态：系统能按某种进程顺序（p1,p2,pn）序列，来为某个进程pi分配其所需要资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。进入不安全状态，进而会出现死锁状态，但并非所有不安全状态都进入死锁状态。2、安全状态举例。三、利用银行家算法避免死锁1、数据结构：（1）n个进程对m 类资源的最大需求情况构成最大需求矩阵Max；（2）分配矩阵Allocation表示当前已经分配的资源情况；（3）目前还差多少资源就可

40、运行完毕构成需求矩阵Need；（4）目前系统的 m类资源的可用数量Available一维数组。Needi,j=Maxi,j-Allocationi,j2、银行家算法：主要用来判断在当前状态下如果有进程提出资源请求request，看是否能满足该请求：a：判断请求的合法性，是否满足小于NEED矩阵中的向量；b：请求的可满足性判断，是否小于available向量；c：试探分配，修改相应的参数availableallocationneed;d：进行安全性检查，若分配后安全，则进行分配，若判断从此进入了不安全状态，则恢复原来数据，对进程请求不予满足。3、安全性算法检查：（1）设定两个向量work=ava

41、ilable;finishi=true（2）从进程集合中找到一个能满足下述条件的进程：finishi=false;needij workj;若找到，执行步骤3，否则执行步骤4（3）当进程pi获得资源后，可顺利执行，直到执行，并释放出分配给它的资源workj=workj+allocationij;finishi=true;Go to step2(4)如果所有进程finishi=true都满足，则系统处于安全状态，否则处于不安全状态。4、银行家算法举例。MAXA B CALLOCATIONA B CNEEDA B CAVAILABLEA B CP07 5 30 1 07 4 33 3 2P13 2

42、 22 0 01 2 2P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 1（1）当前状态是否安全（2）p1请求（1，0，2）是否可以分配。（3）p4请求（3，3，0）是否可以分配（4）p0请求（0，2，0）是否可以分配3.7死锁的检测与解除一、死锁的检测1、资源分配图：2、死锁定理：当且仅当S状态的资源分配图是不可完全简化的。该充分条件被称为死锁定理。3、死锁检测算法。P100二、死锁的解除1、剥夺资源2、撤消进程第四章 存储器管理4.1 程序的装入和链接一、程序的执行过程（1）编译（2）链接（3）装入二、程序的装入1、绝对装入方式：编译时知

43、道程序驻留在内存的什么位置，编译后产生绝对地址的目标代码，将程序装入内存，程序的逻辑地址与实际物理地址完全相同，不需要进行地址变换。绝对装入方式只适用于单道程序环境。2、可重定位装入方式：把装入时对目标程序中指令和数据的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。不允许程序运行时在内存中移动位置。3、动态运行时装入方式：采取动态重定位方式进行地址变换。三、程序的链接1、静态链接：程序运行前先链接，再装入内存。（1）对相对地址的改变（2）变换外部调用符号2、装入时动态链接：装入内存时，边装入边链接。3、运行时动态链接：某些模块的链接推迟到执行时才执

44、行，用不到的模块可以不调入内存。4.2连续分配方式为程序分配一个连续的存储空间。一、单一连续分配技术：只能应用与单用户单任务操作系统，如DOS，整个内存空间除了常驻内存的操作系统内核所占的系统区外，其他都是分配给用户程序的用户区。系统区用户区二、固定分区分配方式：属于最简单的多道程序的存储管理方式，1、划分分区的方法：（1）分区大小相等（2）分区大小不等分区的数量的确定也就决定了在内存中只能安排多少程序同时存放和执行。一个分区里只能放一个作业，不管剩余多少空间，都不能再分配给别的作业了。因此内存利用率不会太高。2、内存分配：将各区建立一个分区使用表，表示分区号、分区的大小、分区的起始地址以及分

45、区的状态（即已分配还是未分配），作为将来分配给作业的一个数据结构。三、动态分区分配1、分区分配的数据结构：主要有空闲分区表或者空闲分配链，把每个空闲分区的序号、大小和其始地址，作为一个表目存放在空闲分区表或链结点内，作为分配的依据。2、分区分配算法：（1）首次适应算法：把空闲分区按地址递增的顺序排列，从第一个分区开始搜索到第一个满足作业需求的分区进行分配，剩余的空间作为新的空闲区，将来仍然作为分配对象。缺点，每次都从地址低的部分进行搜索，低址部分会比较琐碎，增加系统开销。（2）循环首次适应算法，在首次适应算法基础上下一个作业的搜索从上次找到的空闲分区的下一个空闲分区开始查找，该算法会使空闲分区

46、比较均匀，但缺少大分区。（3）最佳适应算法：将空闲分区按大小递增的顺序排列，每次选择最恰当的分区分配给作业，但剩余的空间往往是最小的，有可能因为太小就不能满足任何一个作业的内存需求而造成浪费，我们称之为内存“零头”或者“碎片”。（4）最坏适应算法：要求空闲分区按地址递减的顺序排列，每次选取最大的空闲分区分配给作业，因为由此剩下的空闲区也是最大的，更容易分配出去，但会缺乏大分区。4、分区分配操作（1）分配内存：参考P110图4-6（2）回收内存：当一个作业执行完毕，释放内存空间时，需要涉及和前后空闲区的合并问题，若回收区前面是一个空闲区的，则只修改前空闲区的大小就可以合并了，若回收区后面是空闲区

47、，则需修改后面空闲区的大小和起始地址进行合并，若回收区前后都是空闲区，则回收就要三者合并，将第一空闲区的大小修改，删除后面一个空闲分区表项，造成总的空闲分区表数量减1，若回收区上下都没有空闲区，则在空闲分区表中添加一个新的表项。五、可重定位分区分配1、动态重定位的引入（1）“零头”或“碎片”（2）“拼接”或“紧凑”2、动态重定位的实现：地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行的，故称动态重定位。3、动态重定位的分区分配算法。参考P112图4-10六、对换：所谓对换是把内存中暂时不运行的进程或者暂时不用的程序和数据，调出到外存上，腾出足够的内存空间，把已具备运行条件的进程

48、或进程所需要的程序和数据，调入到内存。对换是提高内存利用率的有效措施。4.3 基本分页存储管理方式一、页面与页表1、页面、块：将一个进程的逻辑地址分成若干个大小相等的片，称为页面或页。每个页面从0开始编号，同时将内存空间也分成与页面大小相等的物理块，也称为页框或块。2、页面大小：每个页面大小是1KB，2KB或者4KB，都是2的幂，3、页表：为了实现页面与物理块的对应，引入一张页面和它存储的物理块的映射表称为页表。页表中主要有页号和它对应的物理块号两项，4、地址结构（1）根据页面大小，从逻辑地址的低位确定出页内偏移量，剩余二进制位表示页号。从而将逻辑地址分解成两部分。如P114（2）数学计算公式

49、：p=int(A/L)d=A%L p表示页号，d表示页内偏移量。页号块号02132136已知页面大小为1024字节，逻辑地址分别是1011，2148，3000。4000。5012答案：3059，1124，1976，7072，逻辑地址非法二、地址变换机构1、基本地址变换机构：在进程没有执行前，页表在内存的起始地址和页表的长度存储在进程的PCB内，当进程获得执行后，页表起始地址和页表长度放到了页表寄存器内。2、基本地址变换过程：首先将逻辑地址转换为p和d两部分，根据页表寄存器内页的长度判断该页号是否属于越界访问，若没有越界，根据页表在内存的起始地址找到页表，查找到该页对应的索引项，得出该页号对应的

50、实际物理块，同时，页内偏移量同时也是物理块的偏移量，因此，物理块号*块的大小（1KB或4KB）+偏移量=实际物理地址；或者物理块号的二进制编码加上偏移量的二进制代码表示组成实际物理地址。3、具有快表的地址变换机构（1）快表：联想寄存器，在地址变换机构中增设的具有并行查寻能力的特殊的高速缓冲寄存器，用以存放当前访问的那些页表项。（2）地址变换过程：给出逻辑地址后，先到快表中查找索引项，若有，直接地址变换就可以形成物理地址而不用访问主存了，若快表中没有，再到内存去查找页表，从中找到物理块号进行地址变换，但同时要把该索引项重新写到联想寄存器内，若已满，则换出认为不再需要的索引项。这样，根据程序执行的