操作系统课件(汪飞)

计算机操作系统汪飞信息科学与技术学院

E-mail:wangxiaoxian@ Tel作系统的分类2批处理系统3分时系统4实时系统5网络操作系统6分布式操作系统7多处理机操作系统1单用户(微机)操作系统多道批处理操作系统优点：1.吞吐量大。2.资源利用率高。缺点：1.平均周转时间长。2.没有交互。分时操作系统分时(timesharing)相关概念多个交互用户并发地使用一个设备。系统轮流地处理各个用户作业。

分时的时间单位称为时间片。每个用户平均只得到处理机有效速度的1/n。分时系统的特点1.同时性2.独立性3.及时性4.交互性分时系统的重要指标响应时间实时系统实时(realtime)系统分类实时控制系统:军事指挥与控制系统、过程控制设备等。实时(事务)处理系统：航空公司ERP系统。实时系统基本特征事件驱动设计，即当接收某些外部信息后，由系统选择执行某一程序，完成相应的实时任务。必须调度和管理实时任务的操作系统实时任务—执行与计算机系统外部事件有关系，并且为了有效且正确地与外部环境交互，必须满足一个或多个最后期限的任务。一.并发性(Concurrence)

操作系统的主要特征二.共享性(Sharing)三.虚拟性(Virtual)四.不确定性(Uncertainty)1.程序执行结果不确定。2.程序异步执行。3.2.2进程的调度状态1.进程的基本调度状态及其转换进程占有处理机进程具备运行条件，等待分配处理机进程等待某一事件完成进程调度程序完成进程的五种基本状态新进程就绪阻塞运行结束接纳时间片到进程调度完成I/O完成或事件发生I/O请求或等待某事件3.2.2进程的调度状态进程调度状态的细分PCB已经创建，但进程未加载到主存中进程自行结束、或被取消具有挂起操作的进程状态转换进程调度状态的细分没有就绪态进程；增加内存空间。增加内存空间(高优先级阻塞态进程即将就绪)时间片到，增加内存空间进程阻塞原语的实现

中断处理机，终止运行，保存CPU状态，进程状态改为(活跃)阻塞态，并插入到阻塞队列中；从(活跃)就绪队列中，选择一进程投入运行。进程阻塞和唤醒进程调用阻塞原语将自己阻塞进程唤醒原语的实现

将被唤醒进程从相应的(活跃或静止)阻塞队列中清除；若进程状态为静止阻塞，改为静止就绪态，等待被激活；若进程状态为活跃阻塞，改为(活跃)就绪态，插入就绪队列中，等待调度。“发现者”进程调用唤醒原语3.4.2进程调度算法的设计引起进程调度的时机现运行进程正常运行结束，或出错异常结束。现运行进程因某种原因，从运行态进入阻塞态。现运行进程因执行某种原语操作，进入阻塞态。一个具有更高优先级的进程进入就绪队列。分配给该进程运行的时间片用完。调度的类型按调度的层次可分为：

高级调度(长程调度、接纳调度、作业调度)

决定哪一个作业可以进入系统中被处理。接受新进程。执行频率较低。每次执行作业调度时，都需做出以下两个决定：（1）接纳多少作业（2）接纳哪些作业在批处理机系统中，需要有作业(高级)调度，而在分时系统和实时系统中，无须作业(高级)调度。中级调度(中程调度)执行交换决策，即在内存与外存对换区之间进行进程交换。执行频率略微频繁。为了提高内存的利用率。低级调度(短程调度)

精确地决定下一次执行哪一个进程。执行最为频繁。2.进程调度方式

非剥夺方式

处理机继续运行当前进程，直至该进程完成或发生某事件而进入阻塞态时，才将处理机分配给重要或紧迫的进程。有更高优先级的进程进入就绪队列时，如何分配处理机，属于低级(短程)调度。优点：简单、系统开销小。缺点：可能导致系统性能恶化。进程调度算法的设计2.进程调度方式

剥夺方式有重要或紧迫的进程到达时，暂停当前进程的执行，并把处理机分配给新进程。剥夺原则：时间片原则优先权原则短作业优先原则优点：为所有的进程提供较好的服务。缺点：系统开销相对较大。进程调度算法的设计(26+10+6)/3=14先进先出调度算法最短CPU运行期优先调度算法最高响应比优先调度算法静态优先级法动态优先级法时间片轮转调度算法多级队列调度算法多级反馈队列调度(多队列轮转)算法3.4.3进程调度算法最短CPU运行期优先(SCBF)调度算法进程调度算法思想从就绪队列中选出下一个CPU执行期最短的进程，为之分配处理机使之运行。非剥夺方式。优点：较好的调度性能。缺点：难以确定下一个CPU执行期。进程调度算法最高响应比优先(HRRN)调度算法进程调度算法调度规则当前进程完成或发生阻塞时，选择R值最大的就绪进程。优点：很好的平衡长短进程。缺点：需要估计进程的服务时间。归一化周转时间，它是进程周转时间和进程服务时间的比。表明一个进程的相对延迟。R=(waittime+servicetime)/servicetime进程服务时间开始时间结束时间周转时间RP110111P210011011011.01P31101102102102P41001022022022.02时间片轮转调度算法(简单轮转法)进程调度算法调度规则把所有就绪进程按照FCFS(FIFO)规则排成一个队列。将处理机分配给队首进程，并规定它执行一个给定时间。时间片用完时，剥夺进程的执行，将其送至就绪队列末尾。返回第二步。时间片的确定系统响应时间、就绪队列中的进程数、进程的转换时间、计算机的处理能力。时间片(q)与系统响应时间T的关系T=NqN为就绪队列中的进程数信号量P，V操作利用信号量实现进程互斥利用信号量实现进程同步经典进程同步和互斥问题3.6.2信号量和P、V操作P、V操作

P、V操作是定义在信号量S上的两个操作。P操作定义：P(S):(1)S=S-1;(2)若S>=0,则调用P(S)的进程继续运行；(3)若S<0,则调用P(S)的进程被阻塞，并把它插入到等待信号量S的阻塞队列中；信号量和P、V操作含义：S>0时的数值代表某类资源可用的数量；执行P操作意味着分配一个单元的资源；S<=0代表已无资源可用(S=0代表资源刚好分配完),此时S的绝对值代表等待S的阻塞队列中的进程数。V操作定义：V(S):(1)S=S+1;(2)若S>0,则调用V(S)的进程继续运行；(3)若S<=0,从等待信号量S的阻塞队列中唤醒队首进程，然后调用V(S)的进程继续运行；P、V操作信号量和P、V操作含义：执行V操作意味着释放一个单元的资源；S<=0表示等待S的阻塞队列中仍有被阻塞的进程，因此应接着执行唤醒操作。信号量S初值为1,P操作限制每次只有一个进程进入临界区。退出时调用V操作，保证了进程在临界区逗留有限时间。V操作会唤醒等待S的阻塞队列的首进程，避免进程“死等”。信号量和P、V操作实例1：用信号量实现司机和售票员的同步利用信号量实现进程的同步信号量和P、V操作S1和S2分别是司机和售票员的私用信号量，初值均为0。S1用于司机检查售票员是否关车门。S2用于售票员检查司机是否到站停车。2、读者---写者问题描述：

有一个许多进程共享的数据区，这个数据区可以是一个文件，或是主存中的一块空间，有一些只读取这个数据区的进程(reader)和一些只往数据区中写数据的进程(writer)。此外还必须满足以下条件：任意多的进程可以同时读这个文件。一次只有一个写进程可以往文件中写。(互斥)如果一个写进程正在往文件中写，则禁止任何读进程读文件，以免访问到错误信息。(互斥)经典进程同步问题读者---写者问题举例共享数据区—图书馆目录读者—通过目录查书的用户写者—可修改目录的图书管理员多个用户可以同时通过目录查书。一次只能一个图书管理员修改目录。图书管理员修改目录时不允许用户查书。经典进程同步问题读者---写者问题解决方案读者优先经典进程同步问题设置信号量S，初值为1,读者和写者公有。设置全局变量rc,用于记录读进程个数。设置信号量Sr，初值为1,多个读者拥有。确保rc被正确更新。只要一个写进程正在访问文件，其它写进程和读进程都不能访问该文件。为允许多个读进程，第一试图读的进程需要等待写进程写完。当至少有一个读进程在读时，随后的读进程无须等待，可以直接进入。产生死锁的原因和必要条件对死锁采取的对策死锁的预防死锁的避免系统模型死锁的检测死锁的解除3.7死锁由多个进程因竞争资源而造成的一种僵局(一些进程处于无休止的阻塞状态)，若无外力作用，这些进程将永远不能再向前推进。死锁死锁与进程对资源的操作有关(请求、获得和释放)。死锁与各进程对资源操作的顺序有关。3.７.5死锁的避免安全状态系统能够按某种进程顺序，如<P1,P2,…,Pn>(安全序列)，为每个进程分配其所需资源，直至最大需求，使每个进程都可顺利完成。不安全状态系统不存在一个安全序列。“死锁避免”允许三个必要条件，动态决定是否允许当前的资源分配请求，确保不会达到死锁点。死锁死锁单项资源的银行家算法设系统有10台磁带机，由A,B,C三个进程共享。第四章存储器管理4.1

存储管理的基本概念

4.2

早期的存储管理4.3分页存储管理4.4请求分页存储管理4.5分段存储管理4.6段页式存储管理存储管理的基本概念虚拟存储器概念的引入若一个程序的地址空间超过主存可用空间，则在执行时该程序时，将其一部分地址空间放在主存，剩余部分放在辅存。当访问的信息不在主存时，由操作系统把它从辅存调入主存。从用户角度，计算机系统好像拥有一个比实际主存大得多的存储器。这个存储器被称为虚拟存储器。二、先进先出(FIFO)置换算法请求分页存储管理置换策略

从主存中移出驻留在主存时间最长的页面，即先进入主存的页面，先被淘汰。实现方法

假设分配给作业的存储块数为m，建立一个由m个元素构成的循环队列和一个替换指针。队列按照页面调入主存的顺序排列，每个元素存放调入的页面号，替换指针始终指向最早进入的页面。利用存储块表建立队列请求分页存储管理FIFO置换算法实例请求分页存储管理假设作业的主存容量(驻留集)为3块(实页)，运行时需要访问的页面的顺序(页面走向)为2,3,2,1,5,2,4,5,3,2,5,2.特点：适用于按线性顺序访问地址空间的情况，否则效率不高。三、最近最久未用(LRU)置换算法请求分页存储管理置换策略

从主存中移出最近一段时间内最久未用的页面，即上次使用距当前最远的页面。特点

LRU性能接近于OPT，实现比较困难。需要记录并及时更新每页先前的访问历史。无论用软件还是硬件实现，开销都比较大。LRU置换算法实例请求分页存储管理假设作业的主存容量(驻留集)为3块(实页)，运行时需要访问的页面的顺序(页面走向)为2,3,2,1,5,2,4,5,3,2,5,2.分页原理基本思想

把一个作业的逻辑地址空间划分为一些容量相等的片，这些片称为页面。把实际主存空间也划分为同样大小的片，这些片称为块。通过适当地址变换，使作业逻辑地址空间的一页对应物理空间的一块。分页存储管理分页存储管理1.作业的逻辑空间的页面是连续的，而变换到物理空间的各块可以不邻接。2.页面的大小可任意指定，通常是2的幂。3.逻辑地址空间和物理地址空间的对应关系由页面变换表(PMT)给出。每个作业都有一个页面变换表或页表。4.页面变换表可保证程序执行的正确性。分页存储管理页面变换表可保证程序执行的正确性地址变换机构动态地址变换机构自动将逻辑地址(虚拟地址)划分为页号和页内地址两部分。利用页表将页号用块号代替，从而得到物理地址。分页存储管理动态地址变换分页存储管理请求分页存储管理算法流程请求分页存储管理

如果系统出现缺页中断频率过高，反复进行入页和出页，这种现象称为“抖动”，或系统“颤动”。应尽量避免“抖动”发生。分段存储管理原理分段存储管理作业的地址空间作业的地址空间按其逻辑结构被划分为一些段，每段都有自己的名字和规定的一个段号，而且都是一段连续的线性地址空间。一个段可定义为一组逻辑信息，如一个主程序、一个或多个子程序、数组或工作区。假设某段段名为X,那么[X]表示段X的段号。分段系统中的作业的地址空间与分页系统的区别1.分页系统的作业地址空间是一个单一的线性地址空间，分段系统的作业地址空间是二维的。2.页是信息的物理单位，大小固定，对用户不可见，系统用于对主存的管理。段是信息的逻辑单位，长度不定，用户可见，可在编程时确定，也可在编译时由编译程序对源程序编译时根据信息的性质进行划分。3.分页存储管理实现单段式虚拟存储系统，而分段存储管理实现多段式虚拟存储系统。分段存储管理分段地址变换过程分段存储管理I/O系统的硬件组成I/O控制方式I/O系统中的软件组织缓冲管理设备分配SPOOLING技术磁盘存储器的管理第五章设备管理

CPU和设备之间的数据传送以块为基本单位。DMA方式的特点

仅在传送开始和完毕时才需要CPU的干预，整块数据传送是在控制器控制下完成。

对外设的管理和操作仍由CPU控制，当外设数目较多且种类不同时，管理和控制将会变得很复杂。引入通道

CPU每发送一条I/O指令，仅能传送一个连续的数据块，若要读/写若干个离散的数据块，需要发出多条I/O指令且进行多次中断处理。引入缓冲的原因：

缓和CPU与I/O设备间速度不匹配的矛盾；

提高CPU和I/O设备间的并行性。缓冲的引入缓冲技术缓冲技术缓冲的四种设置(1)Cache：由较为便宜的半导体材料制成。(2)I/O设备或控制器内部的纯硬件缓冲区。(3)内存中开辟的缓冲区：如I/O设备缓冲区。

脱机I/O技术(假脱机技术—SPOOLing技术)

为慢速设备在辅存上开辟的缓冲区。SPOOLing

(假脱机技术)当系统中出现多道程序后，利用一道程序模拟脱机输入时外围控制器的功能，把低速I/O设备上的数据传输到磁盘上；再用另一道程序来模拟脱机输出时外围控制器的功能，把数据从磁盘传输到低速输出设备上。这样，在主机的直接控制下，实现脱机输入输出功能。SPOOLing系统的组成输入井和输出井；输入缓冲区和输出缓冲区；输入进程SPi和输出进程SPo。SPOOLing系统的组成图输入进程SP1输出进程SP0输入缓冲区B1输出缓冲区B0输入井输出井输入设备输出设备磁盘收容从低速I/O设备输入的数据收容用户进程需要输出的数据暂存由输入设备送来的数据，然后再送入输入井暂存由输出井送来的数据，然后再送给输出设备模拟脱机输入时的外围计算机模拟脱机输出时的外围计算机SPOOLing系统的特点

提高了I/O速度：有关低速I/O设备的操作演变为高速磁盘设备的操作。将独占设备改造为共享设备。实现了虚拟设备功能先来先服务(FCFS)算法调度策略：根据进程请求访问磁盘的先后顺序进行调度。优点：公平、简单；缺点：没有对寻道进行优化，平均寻道时间较长。随机调度。实例：假设磁盘有200个磁道，当前从磁盘的第100道开始处理，被请求的磁道，按接收顺序分别为：55、58、39、18、160、150、38、184。调度策略：总是先完成距当前存取磁臂距离最近的柱面(磁道)上的输入输出请求。最短寻道时间优先(ShortestSeekTimeFirst,SSTF)特点：性能优于FCFS；不能保证平均寻道时间最短；可能导致某些进程“饿死”。调度策略：存取臂从磁盘的一端出发，向另一端移动，遇到需要访问的柱面就完成访问请求，直至到达磁盘的另一端，即这个方向上的最后一个磁道，或者在这个方向上没有其它请求为止。接着，存取臂移动方向倒转服务方向，沿相反方向完成扫描，完成这一方向上的访问请求。扫描算法(SCAN)不仅考虑到欲访问的柱面与当前柱面的距离，更优先考虑的是磁头的当前移动方向。电梯调度算法特点：避免进程“饿死”；对最近刚通过的柱面(磁道)不公平。第六章文件管理文件和文件系统文件的结构和存取方法文件目录文件存储空间的管理文件系统和用户之间的接口用户观点：文件系统如何呈现在用户面前。

一个文件由什么组成，如何命名，如何保护文件，可以进行何种操作。两种观点逻辑文件：用户看到的建立在逻辑结构上的文件。操作系统观点：

文件目录怎样实现，怎样管理存储空间，文件存储位置、磁盘的实际运作方式等。两种观点物理文件：存储在物理设备(磁盘、可移动磁盘、光存储介质)上的文件。2.链接(串联)结构

一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。

优点：提高了磁盘空间利用率，不会造成物理块的浪费。有利于文件的插入和删除有利于文件动态扩充文件的物理结构文件名始址末址jeep9