操作系统知识重点-学生复习专用

1、操作系统复习重点操作系统复习重点重点知识点汇总整理重点知识点汇总整理考生复考生复习专用习专用2 1.2 操作系统的发展过程操作系统的发展过程无操作系统时代无操作系统时代单道批处理系统单道批处理系统多道批处理系统多道批处理系统分时系统分时系统实时系统实时系统微机操作系统微机操作系统31.3 操作系统的基本特性操作系统的基本特性 以多道程序设计为基础的现代操作系统以多道程序设计为基础的现代操作系统具有以下几个主要特征：具有以下几个主要特征：n并发性（并发性（ConcurrenceConcurrence）n共享性（共享性（SharingSharing）n异步性（异步性（AsynchronismAsy

2、nchronism）或称不确定性）或称不确定性（NondeterministicNondeterministic）n虚拟性（虚拟性（VirtualVirtual）4引入进程引入进程在多道程序系统中，为了能够并发执行，系统在多道程序系统中，为了能够并发执行，系统必须为每个程序建立进程。必须为每个程序建立进程。n程序是静态的，进程是动态的。程序是静态的，进程是动态的。n进程能支持并发，程序不能。进程能支持并发，程序不能。进程由一组机器指令、数据和堆栈组成，是一进程由一组机器指令、数据和堆栈组成，是一个能独立运行的活动实体。个能独立运行的活动实体。进程是资源分配的独立单位。进程是资源分配的独立单位。

3、多个进程能并发执行，进程运行时要占用一定多个进程能并发执行，进程运行时要占用一定的系统资源，如的系统资源，如CPU、存储空间和、存储空间和I/O设备等。设备等。51. 4操作系统功能操作系统功能操作系统有如下几个基本功能：操作系统有如下几个基本功能：u处理机管理u存储器管理u设备管理u文件管理u用户接口6（一）（一） 处理机管理处理机管理在传统的多道程序系统中，处理机的分配和运在传统的多道程序系统中，处理机的分配和运行都是以进程为基本单位，因而行都是以进程为基本单位，因而对处理机的管对处理机的管理可归结为对进程的管理理可归结为对进程的管理：进程控制进程控制n创建、撤销、状态转换创建、撤销、状态

4、转换进程同步进程同步n访问临界资源、协调合作次序访问临界资源、协调合作次序进程通信进程通信n合作进程的消息交换合作进程的消息交换调度调度n作业调度、进程调度作业调度、进程调度7（二）（二） 存储器管理存储器管理存储管理的主要任务是管理存储器资源，为多道程存储管理的主要任务是管理存储器资源，为多道程序运行提供有力支撑。存储管理的主要功能包括：序运行提供有力支撑。存储管理的主要功能包括： 内存分配内存分配n存储管理将根据用户程序的需要给它存储管理将根据用户程序的需要给它分配分配存储器资源，存储器资源，并在其使用完毕后并在其使用完毕后回收回收。 内存保护内存保护n存储管理要把各个用户程序存储管理要把

5、各个用户程序相互隔离相互隔离起来互不干扰，更起来互不干扰，更不允许用户程序访问操作系统的程序和数据，从而保护不允许用户程序访问操作系统的程序和数据，从而保护用户程序存放在存储器中的信息用户程序存放在存储器中的信息不被破坏不被破坏。 8（二）（二） 存储管理存储管理地址映射地址映射n进程进程逻辑地址逻辑地址到内存到内存物理地址物理地址的映射。这样程的映射。这样程序员无需知道自己的程序分配到内存的什么具序员无需知道自己的程序分配到内存的什么具体物理地址，仅仅知道自己的逻辑地址即可，体物理地址，仅仅知道自己的逻辑地址即可，体现了存储的无关性。体现了存储的无关性。内存扩充内存扩充n借助虚拟存储技术，借

6、助虚拟存储技术，从逻辑上扩充内存从逻辑上扩充内存，使用，使用户感觉到比实际大的多的内存，可使更多程序户感觉到比实际大的多的内存，可使更多程序并发运行。并发运行。n功能：请求调入、置换功能：请求调入、置换9（三）（三） 设备管理设备管理设备管理的设备管理的主要任务主要任务：管理各类外围设备管理各类外围设备，完成用户提出的，完成用户提出的I/O请求，加快请求，加快I/O信息的传送速度，信息的传送速度，发挥发挥I/O设备的并行性，提高设备的并行性，提高I/O设备设备的利用率；的利用率；以及提供每种设备的设备驱动程序和中以及提供每种设备的设备驱动程序和中断处理程序，断处理程序，向用户屏蔽硬件使用细节向

7、用户屏蔽硬件使用细节。10（三）（三） 设备管理设备管理设备管理的设备管理的主要功能主要功能：1.缓冲管理缓冲管理w缓冲区，缓和缓冲区，缓和CPU和和I/O速度不匹配的矛盾速度不匹配的矛盾w单缓冲、双缓冲、公用缓冲单缓冲、双缓冲、公用缓冲2.设备分配设备分配w为进程分配设备，以及设备控制器、通道为进程分配设备，以及设备控制器、通道3.设备处理设备处理w设备驱动程序：设备驱动程序：CPU和设备控制器之间的通信和设备控制器之间的通信11（四）文件管理（四）文件管理上述三种管理是针对计算机上述三种管理是针对计算机硬件资源硬件资源的管的管理。理。文件管理则是对系统的文件管理则是对系统的软件资源软件资源

8、的管理。的管理。在现代计算机中，通常把程序和数据以文在现代计算机中，通常把程序和数据以文件形式存储在外存储器上，供用户使用。件形式存储在外存储器上，供用户使用。为此，为此，OS需配置文件管理机构。需配置文件管理机构。12（四）文件管理的主要功能（四）文件管理的主要功能文件存储空间的管理文件存储空间的管理n为文件为文件分配外存分配外存空间，提高外存利用率空间，提高外存利用率n记录记录外存外存使用使用情况，情况，分配、回收分配、回收外存空间外存空间目录管理目录管理n为文件建立目录项，有效组织，为文件建立目录项，有效组织，按名存取按名存取文件的读文件的读/写管理和保护写管理和保护n向外存读取向外存读

9、取/写入数据写入数据n防止文件被非法窃取或破坏防止文件被非法窃取或破坏存取控制存取控制13（五）（五）OS与用户之间的接口与用户之间的接口1.用户接口用户接口n联机接口联机接口w命令，用户通过和终端交互控制作业命令，用户通过和终端交互控制作业n脱机接口脱机接口w作业控制语言作业控制语言(JCL)，用户通过，用户通过作业说明书作业说明书委托系统代委托系统代为控制作业为控制作业n图形用户接口图形用户接口w用直观图标、菜单、对话框替代命令，免于单调、繁琐用直观图标、菜单、对话框替代命令，免于单调、繁琐和记忆之累和记忆之累2.程序接口程序接口n供用户程序使用供用户程序使用OS服务的服务的系统调用系统调

10、用152.2.1 进程的描述进程的描述1.进程的定义和特征2.进程的基本状态及转换3.挂起操作和进程状态的转换4.进程管理中的数据结构162.2.1 进程的定义进程的定义进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。其他经典定义：n进程是程序的一次执行。n进程是一个程序及其数据在处理机上顺序执行时所发生的活动。n进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。17进程的相关概念进程的相关概念进程控制块(PCB: Process Control Block)n一个数据结构，用来描述进程的基本情况和活动过程，为操作系统管理和控制进程所必需。进程实

11、体n由程序段、数据段、PCB三部分构成n通常所说的进程实际上是指进程实体创建进程，实质上是创建进程实体中的PCB撤销进程，实质上是撤销进程的PCB18进程的特征进程的特征动态性n进程的实质：进程实体的一次执行过程n由创建而产生，由调度而执行，由撤销而消亡并发性n多个进程实体同存于内存中n能在同一段时间内同时运行独立性n能够独立运行、独立分配资源和独立接受调度的基本单位异步性n进程以各自独立的、不可预知的速度向前推进。19进程与程序的关系程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行

12、过程，它是一个动态的概念。念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。程序可以作为一种软件资料长期保存在某种介质上，而进程是有一定生程序可以作为一种软件资料长期保存在某种介质上，而进程是有一定生命期的，进程被创建后存在于内存中，进程消亡后生命期结束，不再存命期的，进程被创建后存在于内存中，进程消亡后生命期结束，不再存在。在。程序的每次运行都将创建新的进程，而进程一旦消亡，就无法再被执行。程序的每次运行都将创建新的进程，而进程一旦消亡，就无法再被执行。进程更能真实地描述并发，而程序不能进程更能真实地描述并发，而程序不能( (没有没有PCB)PCB)。进程能够独立运行、独立分配资

13、源和独立接受调度的基本单位，程序进程能够独立运行、独立分配资源和独立接受调度的基本单位，程序（没有（没有PCBPCB）不能作为独立的单位运行。）不能作为独立的单位运行。202.2.2 进程的基本状态进程的基本状态就绪就绪(Ready)状态状态执行执行(Running)状态状态阻塞阻塞(Blocked)状态状态21就绪就绪(Ready)就绪状态就绪状态n是指进程已处于准备好运行的状态，已经获得是指进程已处于准备好运行的状态，已经获得除除CPU以外以外的的所有必要资源所有必要资源，因其，因其CPU正被其他进程正被其他进程占用而无法执行，一旦获得占用而无法执行，一旦获得CPU, 可以立即执行。可以立

14、即执行。就绪进程就绪进程n处于就绪状态的进程称为就绪进程。处于就绪状态的进程称为就绪进程。就绪队列就绪队列n所有的就绪进程排成一个队列，等待获得所有的就绪进程排成一个队列，等待获得CPU。n队列的排序与调度策略有关。队列的排序与调度策略有关。22执行执行(Running)执行状态执行状态n是指当前进程已经是指当前进程已经获得获得CPU，其程序，其程序正在执行正在执行的的状态。状态。当前进程当前进程n正在执行的进程称为当前进程。正在执行的进程称为当前进程。单处理机系统单处理机系统n任一时刻，只有一个进程处于执行状态任一时刻，只有一个进程处于执行状态多处理机系统多处理机系统n可有多个进程同时处于执

15、行状态可有多个进程同时处于执行状态23阻塞阻塞(Blocked)阻塞状态阻塞状态n也叫也叫等待等待状态，是指状态，是指原本正在执行原本正在执行的进程由于的进程由于发生发生某事件某事件（如（如I/O请求，等待其他进程发来的信号）请求，等待其他进程发来的信号）而暂时无法继续执行的状态。而暂时无法继续执行的状态。n也就是说，进程的执行受到也就是说，进程的执行受到阻塞阻塞。阻塞进程阻塞进程n处于阻塞状态的进程称为阻塞进程。处于阻塞状态的进程称为阻塞进程。n阻塞进程尚阻塞进程尚不具备运行条件不具备运行条件，即使，即使CPU空闲它也无空闲它也无法使用。法使用。阻塞队列阻塞队列n进程在阻塞队列中等待进程在阻

16、塞队列中等待n按阻塞原因排成不同队列按阻塞原因排成不同队列(大系统常用大系统常用)24三种基本状态的转换三种基本状态的转换25引起进程状态转换的具体原因引起进程状态转换的具体原因就绪就绪 - 执行执行n调度调度程序选择一个新的进程执行程序选择一个新的进程执行执行执行 - 就绪就绪n当前进程当前进程用完了时间片用完了时间片；n当前进程被中断，被一个当前进程被中断，被一个更高优先级更高优先级的的就绪进程就绪进程抢占抢占CPU执行执行 - 阻塞阻塞(等待等待)n发生某事件，导致等待发生某事件，导致等待：如：如OS尚未完成进程请求的服务；进程尚未完成进程请求的服务；进程向向OS申请缓冲空间；对某资源的

17、访问尚不能进行；初始化申请缓冲空间；对某资源的访问尚不能进行；初始化I/O 且必须等待结果；等待某个进程提供输入且必须等待结果；等待某个进程提供输入, 阻塞阻塞(等待等待) - 就绪就绪n当所等待的事件发生当所等待的事件发生, 欠缺的运行条件被满足欠缺的运行条件被满足：如，得到所请求：如，得到所请求的资源；的资源；I/O操作完成；操作完成；OS完成进程请求的服务；得到申请的完成进程请求的服务；得到申请的缓冲区缓冲区; 等待的数据已经到达等待的数据已经到达; 26进程控制块的作用进程控制块的作用1.作为独立运行基本单位的标志系统通过PCB感知进程的存在PCB是进程存在的唯一标志2.实现间断性运行

18、方式保存被中断进程的CPU运行现场3.提供进程管理所需要的信息程序/数据保存位置资源清单4.提供进程调度所需要的信息5.实现与其他进程的同步和通信27进程控制块中的信息进程控制块中的信息1.进程标识符进程标识符(用于识别进程用于识别进程)n内部标识符：操作系统使用内部标识符：操作系统使用n外部标识符：用户使用外部标识符：用户使用2.处理机状态处理机状态n即处理机上下文，主要包括处理机中各种寄存器即处理机上下文，主要包括处理机中各种寄存器的内容：的内容：w通用寄存器通用寄存器w指令计数器指令计数器(PC)w程序状态字程序状态字(PSW)w用户栈指针用户栈指针n进程切换时，这些信息用来使当前进程被

19、上次中进程切换时，这些信息用来使当前进程被上次中断地方继续执行。断地方继续执行。28进程控制块的组织方式进程控制块的组织方式3.进程调度信息n进程状态n进程优先级n调度所需其他信息n事件(阻塞原因)4.进程控制信息n程序/数据的地址(内/外存首地址)n同步/通信机制(消息队列指针、信号量)n资源清单(需求、占用)n链接指针(队列中下一个PCB)29进程控制块的组织方式进程控制块的组织方式1.线性方式n所有进程组织在一张线性表中 w实现简单，但查找时需扫描整张表2.链接方式n相同状态进程的PCB链接成一个队列w就绪队列、阻塞队列、空白队列3.索引方式n按进程状态的不同，建立几张索引表n索引表的表

20、项：各进程PCB首址线性方式线性方式30链接方式链接方式31索引方式索引方式322.4 进程同步进程同步进程的进程的异步性异步性，和对，和对临界资源临界资源的争用，的争用，会给系统带来混乱。会给系统带来混乱。进程同步的进程同步的主要任务：主要任务：n对多个相关进程在对多个相关进程在执行次序上执行次序上进行进行协协调调，以使并发执行的诸进程之间能，以使并发执行的诸进程之间能有有效效地地共享共享资源和相互资源和相互合作合作，从而使程，从而使程序的执行具有序的执行具有可再现性可再现性。33进程间的两种制约关系进程间的两种制约关系间接间接相互制约相互制约n源于源于资源共享资源共享，即对资源的，即对资源

21、的竞争关系竞争关系，进程进程需要互斥地访问同一资源需要互斥地访问同一资源直接直接相互制约相互制约n源于源于进程合作进程合作，即，即协作关系协作关系，某些进程为完，某些进程为完成同一任务需要分工协作成同一任务需要分工协作34 同步机制应遵循的规则同步机制应遵循的规则1.空闲让进空闲让进n没有进程在临界区，表明临界资源空闲，应允许一个请求进没有进程在临界区，表明临界资源空闲，应允许一个请求进入临界区的进程立即进入临界区，以保证资源的入临界区的进程立即进入临界区，以保证资源的有效利用有效利用。2.忙则等待忙则等待n已有进程进入临界区，表明临界资源正在被访问，其他请求已有进程进入临界区，表明临界资源正

22、在被访问，其他请求进入临界区进程必须等待，以保证对临界资源的进入临界区进程必须等待，以保证对临界资源的互斥访问互斥访问。3.有限等待有限等待n一个进程不能无限地等待进入临界区，一个进程不能无限地等待进入临界区，避免避免“死等死等”。4.让权等待让权等待n进程若不能进入自己的临界区，应立即释放处理机，进程若不能进入自己的临界区，应立即释放处理机，避免避免“忙等忙等”。352.4.3 信号量机制信号量机制1.整型信号量2.记录型信号量3.AND型信号量4.信号量集361.整型信号量整型信号量定义定义S为一个用于为一个用于表示资源数目表示资源数目的的整型量整型量，除初始化外，除初始化外，仅能通过两个

23、标准的仅能通过两个标准的原子操作原子操作wait(S)和和signal(S)来访来访问。这两个操作也被称为问。这两个操作也被称为P、V操作。操作。 wait(S) while (S - 切换迅速、开销小切换迅速、开销小 3.3.可并发执行可并发执行n同一进程中的线程同一进程中的线程n不同进程中的线程不同进程中的线程4.4.共享进程资源共享进程资源n如，地址空间、已打开文件、信号量等等如，地址空间、已打开文件、信号量等等52线程的状态线程的状态状态参数n用于描述线程的一组数据，包括：w寄存器状态、堆栈、线程运行状态、优先级、线程专有存储器、信号屏蔽等线程运行状态n执行、就绪、阻塞第三章第三章 处

24、理机调度与死锁处理机调度与死锁543.1 处理机调度的层次 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。不同系统中，调度过程有差异： 批量型作业：作业调度+进程调度 终端型作业：进程调度 较完善的OS中，增加了中级调度，一个批处理型作业可能要经历三级调度。55处理机调度的三个层次1. 高级调度（作业调度、长程调度）2. 初级调度（进程调度、短程调度）3. 中级调度（中程调度）563.1.1 高级调度 高级调度又称为作业调度或长程调度，主要功能是根据某种算法，把外存上处于后备队列中的那些作业调入内存，调度的对象是作业。57作业的概念什么是作业：是用户在一次解题或一

25、个事务处理过程中要求计算机系统所做工作的集合。它包括用户程序、所需要的数据及控制命令等。作业是由一系列有序的作业步组成的。一个作业由3部分组成，即程序、数据及作业说明书。其中，作业说明书体现了用户对作业的控制意图。583.1.1 高级调度 (High Scheduling) 作业调度也称为接纳调度。在每次执行作业调度时，都须做出以下两个决定： 1) 接纳多少个作业 取决于多道程序度（允许多少道作业同时在内存） 2) 接纳哪些作业 取决于调度算法593.1.2. 低级调度(Low Level Scheduling) 低级调度称为进程调度或短程调度，调度的对象是进程。低级调度用于决定就绪队列中的哪

26、个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。低级调度的主要功能：保存处理机现场按某种算法选取进程把处理机分配给进程60进程调度中的三个基本机制排队器n将就绪进程按照一定的方式排成一个或多个队列，以便调度程序有效率地访问。分派器（Dispatcher, 分派程序）n从就绪队列上取出调度程序选中的进程，进行上下文切换，把处理机分配给它。上下文切换机制(CPU现场信息)n处理机切换时，会发生两对上下文切换：w保存当前进程上下文，装入分派程序上下文w移出分派程序，装入新选中进程的上下文61进程的两种调度方式 1.非抢占方式(Non-preemptive Mode)2.抢占方

27、式(Preemptive)62非抢占方式一旦处理机分配给某进程，就让它一直运行下去，不管它运行多长时间，不允许其他进程抢占已分配给它的处理机。除非进程完成而释放处理机，或进程阻塞时，才再把处理机分配给其他进程。63非抢占方式下的调度在采用非抢占调度方式时，可能引起进程调度的因素可归结为这样几个： 正在执行的进程执行完毕，或因发生某事件而不能再继续执行； 执行中的进程因提出I/O请求而暂停执行； 在进程通信或同步过程中执行了某种原语操作，如P操作(wait操作)、Block原语。64非抢占方式的优缺点优点：n实现简单、系统开销小，适用于批处理系统环境。缺点：n难以满足紧急任务的要求立即执行，不适

28、合分时系统和实时系统。65抢占方式抢占方式允许调度程序根据某种原则去暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。抢占方式是基于一定原则的：1.优先权原则；2.短作业(进程)优先原则； 3.时间片原则。 66抢占方式的优缺点优点:n防止一个长进程长时间占用处理机n能为大多数进程提供更公平的服务n能满足对响应时间需求严格的场合缺点：n调度开销较大673.1.3 中级调度(Intermediate-Level Scheduling) 中级调度又称中程调度(Medium-Term Scheduling)。 引入中级调度的主要目的，是为了提高内存利用率和系统吞吐量。 为此，应使那

29、些暂时不能运行的进程不再占用宝贵的内存资源，而将它们调至外存上去等待，把此时的进程状态称为就绪驻外存状态或挂起状态。当这些进程重又具备运行条件、且内存又稍有空闲时，由中级调度来决定把外存上的哪些又具备运行条件的就绪进程，重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。中级调度实际上就是存储器管理(第4章)中的对换功能。683.3 调度算法调度的实质：一种资源分配(CPU、内存)调度算法：根据系统资源分配策略制定的资源分配算法。不同的系统具有不同的资源分配目标，因而采用的调度算法也不同。n资源分配目标：倾向于满足用户交互还是充分利用计算机资源，吞吐量/响应时间/周转时间/优先权

30、/公平性调度算法的适用：进程调度，作业调度，或者都适用。693.3 调度算法 3.3.1 先来先服务和短作业(进程)优先调度算法 1. 先来先服务(FCFS，First Come, First Served)调度算法 适用：进程调度、作业调度 有利于长作业/进程，不利于短作业/进程 有利于CPU繁忙型作业/进程，不利于IO繁忙型作业/进程702. 短作业(进程)优先调度算法 短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)调度算法，是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。短进程

31、优先(SPF)调度算法，则是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。可有效降低作业/进程的平均等待时间。71图 3-4 FCFS和SJF调度算法的性能 SJF: Short Job First,短作业优先 72SJ(P)F缺点： (1) 该算法对长作业不利，如作业C的周转时间由10增至16，其带权周转时间由2增至3.1。更严重的是，如果有一长作业(进程)进入系统的后备队列(就绪队列)，由于调度程序总是优先调度那些(即使是后进来的)短作业(进程)，将导致长作业(进程)长期不被调度。（不利长作业） (2

32、) 该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业(进程)会被及时处理。（不及时） (3) 由于作业(进程)的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业优先调度。（不完全可靠） 73调度算法练习题74先来先服务调度算法和短作业优先调度算法340.8010.3010.100.209.50446.51.3010.8010.600.209.5042111.1010.1010.000.109.0033161.6010.6010.500.109.00344.62.3010.8010.300.508.502242

33、.0010.5010.000.508.502112.0010.008.002.008.001112.0010.008.002.008.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业先来先服务调度算法平均周转时间 t = 1.725平均带权周转时间 w = 6.875短作业优先调度算法平均周转时间 t = 1.55平均带权周转时间 w = 5.1575作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）J JO OB B1 18 8: :0 00 0 1 12 20 0J JO OB B2 28 8: :5 50 0 5 50 0J JO OB B3 39 9:

34、:0 00 0 1 10 0J JO OB B4 49 9: :5 50 0 2 20 0例题：单道环境下四个作业，它们进入系统的时间如例题：单道环境下四个作业，它们进入系统的时间如下：下：(1)给出给出FCFS , SJF下的作业执行次序下的作业执行次序(2)给出给出FCFS , SJF下的作业平均周转时间和带权平均下的作业平均周转时间和带权平均周转时间周转时间76作作业业进进入入时时间间估估计计运运行行时时间间（分分钟钟）SJF完完成成时时刻刻FCFS完完成成时时刻刻JOB18:0012010:0010:00JOB28:505011:2010:50JOB39:001010:1011:00J

35、OB49:502010:3011:20773.3.2 3.3.2 高优先权优先调度算法 1 1 优先级调度算法w优先级调度算法（priority-scheduling algorithmpriority-scheduling algorithm）是指每个进程都有一个优先级与其相关联，具有最高优先级的就绪进程会被分派到CPUCPU, ,具有相同优先级的进程按FCFSFCFS顺序调度。 w优先级通常为固定区间的数字，如0 0到7 7，或者0 0到40954095。不过，对于0 0是最高还是最低的优先级，并没有定论。有的系统用低数字表示低优先级，而有的系统使用低数字表示高优先级。78例3-23-2：

36、有5 5个进程P1P1、P2P2、P3P3、P4P4、P5P5，它们同时依次进入就绪队列，它们的优先数和需要的处理机时间如下： 进程 处理机时间 优先数 P1 10 3P1 10 3 P2 1 1 P2 1 1 P3 2 3 P3 2 3 P4 1 4 P4 1 4 P5 5 2 P5 5 2 忽略进程调度所花的时间，要求：（1 1）分别写出采用先来先服务调度算法和静态优先级调度算法中进程的执行次序；（2 2）分别计算各进程在就绪队列中的等待时间和平均等待时间。FCFSFCFS等待时间等待时间 静态优先级法等待时间静态优先级法等待时间 0 1 0 1 10 18 10 18 11 11 11

37、11 13 0 13 0 14 13 14 13 解:(1)采用FCFS调度算法时各进程的执行次序为：P1P2P3P4P5。 采用静态优先级调度算法时各进程的执行次序为： P4P1P3P5P2（假设优先数与优先权成正比）。 (2)FCFS中，平均等待时间（0+10+11+13+14）/59.6； 静态优先级法中，平均等待时间（1+18+11+0+13）/58.6793.3.2 高优先权优先调度算法 2. 优先权调度算法的类型 1) 非抢占式优先权算法 在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成； 或因发生某事件使该进程放弃处理机时，系统方可

38、再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。 80 2) 抢占式优先权调度算法 在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。 显然，这种抢占式的优先权调度算法，能更好地满足紧迫作业的要求，故而常用于要求比较严格的实时系统中， 以及对性能要求较高的批处理和分时系统中。 3.3.2 高优先权优先调度算法 813. 优先权的类型 1) 静态优先权 静态

39、优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如，07或0255中的某一整数， 又把该整数称为优先数。只是具体用法各异：有的系统用“0”表示最高优先权，当数值愈大时，其优先权愈低；而有的系统恰恰相反。 特点：简单易行，开销小，但不精确，低优先权作业可能长期不被调度。82 2) 动态优先权 动态优先权是指，在创建进程时所赋予的优先权，是可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如: 在就绪队列中的进程，随其等待时间的增加，优先权以速率a提高，避免优先权低的进程长期得不到执行； 或者当采用抢占式调度时，

40、正在执行的进程，随着执行时间的增加，优先权以速率b下降，防止一个长作业长期垄断CPU。2. 优先权的类型 833.3.高响应比优先调度算法该算法，就是每次调度一个作业投入运行时，计算后备作业表中每个作业的响应比，然后挑选响应比最高的投入运行。843. 高响应比优先调度算法 要求服务时间要求服务时间等待时间优先权引入动态优先权后，优先权的变化规律可描述为： 由于等待时间与服务时间之和，就是系统对该作业的响应时间，故该优先权又相当于响应比RP。据此，又可表示为： 要求服务时间响应时间要求服务时间要求服务时间等待时间优先权85高响应比优先调度算法举例46.51.3010.8010.600.209.5

41、042111.1010.1010.000.109.00334.22.1010.6010.100.508.502112.0010.008.002.008.001执行顺序带权周转时间周转时间完成时间开始时间运行时间提交时间作业高响应比优先调度算法平均周转时间 t = 1.625平均带权周转时间 w =5.67586 (1) 如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。 (2) 当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。 (3) 对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足

42、够长时，其优先级便可升到很高， 从而也可获得处理机。 缺点：每次调度前都要计算响应比，增加了系统开销。3. 高响应比优先调度算法 873.3.3 基于时间片的轮转调度算法 1. 时间片轮转法 在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则，排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内

43、，均能获得一时间片的处理机执行时间。883.3.3 基于时间片的轮转调度算法 2. 时间片大小的确定 在时间片轮转算法中，时间片的大小对系统性能有很大的影响，如选择很小的时间片，将很有利于短作业，但会频繁发生中断和进程上下文的切换；反之，如选择太长的时间片，使得每一个进程都能在一个时间片内完成，时间片轮转算法便退化为FCFS算法，无法满足交互式用户的需求。 时间片应略大于一次典型的交互所需要的时间。 举例见课本P95892. 多级反馈队列调度算法 (1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。 第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中

44、进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，第i+1个队列的时间片要比第i个队列的时间片长一倍。 图 3-7 是多级反馈队列调度算法的示意。 903.5 产生死锁的原因和必要条件多进程的并发执行，可改善系统的资源利用率，提高系统的吞吐量，但也可能发生一种危险死锁。死锁：n多个进程中运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们将无法再向前推进。91死锁产生的原因（1）资源有限。当系统中多个进程共享资源，如打印机、公用队列等，其数目不足以满足诸进程的需要，会引起

45、进程对资源的竞争而产生死锁。（2）并发进程间的推进顺序不当。进程在运行过程中，请求和释放资源的顺序不当，也会导致产生进程死锁。 92系统中的资源类型可剥夺性资源n资源分配给进程之后，可以被系统或其他进程剥夺。n如：CPU非剥夺性资源n资源一旦分配给进程，不能强行收回，只能等进程用完自行释放。n如：打印机临时性资源n由进程通信产生的，具有一定时效性的资源，如消息n相应地，CPU、打印机属永久性资源93资源竞争引起进程死锁1.竞争非剥夺性资源2.竞争临时性资源虽然竞争的资源类型有区别，但是产生死锁的原理相同，都出现了“进程资源”环路。n如图3-13，3-14.94进程推进顺序不当引起死锁进程运行具

46、有异步性特征，多个并发进程的推进顺序有多种可能性。n如果进程以某种顺序推进，不会引起死锁，称这种推进顺序是合法的n否则称进程的推进顺序非法（会引起死锁）w在进程推进示意图中，推进路线进入不安全区。95死锁产生的必要条件: :1.互斥条件：进程对分配到的资源进行排他性使用。2.请求和保持条件（部分分配条件）：进程在等待一新资源时继续占有已分配的资源。3.不剥夺条件：不能强行剥夺进程拥有的资源。4.环路等待条件：存在“进程资源”的环形链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。 96u 预防死锁：u指通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁

47、的发生。u 避免死锁：u指在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。u 检测死锁：u允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。u 解除死锁：u当检测出死锁后，便采取适当措施将进程从死锁状态中解脱出来。处理死锁的基本方法第四章第四章 存储器管理存储器管理984.3 连续分配方式连续分配方式连续分配方式：为一个用户程序分配一个连续的存储空间。1.1.单一连续分配2.2.固定分区分配3.3.动态分区分配4.4.动态重定位分区分配99单一连续分配单一连续分配最简单，只适用于单用户、单任务系统内存分为两部分：n系统区w

48、内存的低址部分，仅供OS使用n用户区w系统区以外的全部内存空间，供用户程序使用系统区用户区0mn地址：地址：0m内存缓冲区-打印机，打印 重复上述过程，直至队列为空，该进程阻塞自己，再有打印请求时才被唤醒163SPOOLing技术技术特点n提高I/O速度w对低速I/O的操作，演变为对磁盘(输入井、输出井)的操作n独占设备共享设备w没有分配实际设备，只是分配了输入井或输出井中的存储区和I/O请求表n实现虚拟设备功能w可使多个进程以独占方式同时使用一台物理设备，即一台物理设备被虚拟为多台逻辑设备1646.6 磁盘存储器的管理磁盘存储器的管理主要任务：设法改善磁盘系统的性能1.磁盘性能简述2.磁盘调

49、度3.磁盘高速缓存4.提高磁盘I/O速度的其他方法5.廉价磁盘冗余阵列165磁盘调度磁盘调度目标：减少寻道时间1. FCFS（Fisrt Come First Second）n特点：简单，寻道时间长，相当于随机访问模式。2. SSTF（最短寻道优先）166 FCFS调度算法调度算法 SSTF调度算法调度算法100道开始道开始被访问的下一被访问的下一个磁道个磁道移动距离移动距离5545583391918219072160701501038112184146平均寻道长度：平均寻道长度：55.3100道开始道开始被访问的下一被访问的下一个磁道个磁道移动距离移动距离901058325533916381

50、18201501321601018424平均寻道长度：平均寻道长度：27.5167磁盘调度磁盘调度3. 扫描(SCAN)算法nSSTF存在进程“饥饿”现象nSCAN算法w采用SSTF时，考虑当前移动方向考虑当前移动方向，一直移动到最外/内层磁道时，折返，进行反方向移动，可避免饥饿现象w寻道方向：，里外，外里，；4. 循环扫描CSCAN（图9-5）n一个方向读完，不是象SCAN那样反向扫描，而是循环扫描n寻道方向：，里外，里外，；或者相反n访问延迟：从2T减小为T+SmaxwT：单向扫描所有磁道的时间wSmax：从最里直接移动到最外(或者相反)的时间168SCAN调度算法调度算法 CSCAN调度

51、算法调度算法100道开始，增加方向道开始，增加方向被访问的下一被访问的下一个磁道个磁道移动距离移动距离1505016010184249094583255339163811820平均寻道长度：平均寻道长度：27.8100道开始，增加方向道开始，增加方向被访问的下一被访问的下一个磁道个磁道移动距离移动距离15050160101842418166382039155165839032平均寻道长度：平均寻道长度：35.8169磁盘调度磁盘调度5. NStepSCAN和FSCAN算法。NStepSCAN算法n将磁盘请求队列分为长为N的子队列m个，按FCFS处理各子队列，对每个子队列按SCAN处理。wN=1

52、时，退化为FCFSwN很大时，性能接近SCAN磁臂粘着(Armstickiness)：由于连续对某磁道访问引起的垄断访问NStepSCAN算法可避免粘着现象FSCAN算法nNStepSCAN算法的简化，只有两个队列n一个是当前扫描中的队列n一个是扫描期间新出现的磁盘I/O请求的队列第七章第七章 文件管理文件管理171文件管理的任务和功能文件管理的任务和功能任务任务n对文件和文件系统进行管理，方便用户使用，对文件和文件系统进行管理，方便用户使用，并保证文件的安全性并保证文件的安全性基本功能基本功能n文件存储空间的管理文件存储空间的管理n目录管理目录管理n文件读文件读/写管理和保护写管理和保护1727.1 文件和文件系统文件和文件系统1.文件、记录和数据项2.文件类型和文件系统模型173数据项数据项数据项是文件系统中最低级的数据组织形式基本数据项n可命名的最小逻辑单位(原子数据)，也称数据元素、字段n用于描述一个对象的某种属性n具有“名”、“型”和“值”组合数据项n由若干个基本数据项组成，简称组项174记录记录记录：一组相关数据项(值)的集合，是关于某对象的若干属性的描述关键字(key)：能唯一地标识一个记录的数据项（一个或多个数据项的组合）175文件文件文件：指由创建者定义、具有文件名