第4章 资源管理技术

1、第第4章章 资源管理技术资源管理技术第 2 页4.1 操作系统的概念操作系统的概念4.2 多道程序设计多道程序设计4.3 存储空间的组织存储空间的组织第 3 页4.1.1 操作系统的概念和任务操作系统的概念和任务4.1.2 操作系统的发展过程操作系统的发展过程4.1.3 操作系统的分类操作系统的分类第 4 页显示器显示器键盘键盘 CPU（处理机）（处理机）内存内存计算机一般由：处理机（计算机一般由：处理机（CPU）、存储器及）、存储器及I/O设备组成。设备组成。问题：如此多而复杂的硬件，用户如何控制和使用呢？问题：如此多而复杂的硬件，用户如何控制和使用呢？为计算机配置！第 5 页应用程序应用程

2、序用户程序用户程序操作系统虚拟机操作系统虚拟机操作系统操作系统裸裸 机机1. 裸机的使用是不方裸机的使用是不方便的；便的；2. 在裸机之上装配一在裸机之上装配一些些基本的控制软件基本的控制软件，让这些软件自动完成让这些软件自动完成基本功能；基本功能；3. 在这些软件的基础在这些软件的基础之上进行扩充和完善，之上进行扩充和完善，提供给用户所要求的提供给用户所要求的功能。功能。第 6 页是计算机系统中是计算机系统中直接控制和管理直接控制和管理各种软硬件资源，各种软硬件资源，以方便用户以方便用户充分而有效地利用这些资源的充分而有效地利用这些资源的程序的集合程序的集合第 7 页提供给用户易用统一的手段

3、提供给用户易用统一的手段 u有效有效地控制各种软硬件资源，使之得到充分利用地控制各种软硬件资源，使之得到充分利用保持忙碌和有序占用保持忙碌和有序占用u合理合理组织系统工作流程，改善系统性能组织系统工作流程，改善系统性能提高系统效率提高系统效率u为用户方便的使用计算机提供为用户方便的使用计算机提供良好良好的环境的环境提高用户使用效率提高用户使用效率模块化，易添加和修改模块化，易添加和修改u对应用程序最大可能的提供开放统一的环境对应用程序最大可能的提供开放统一的环境u应用程序能方便地移植和互操作应用程序能方便地移植和互操作第 8 页操作系统是位于用户和计算机系统之间的接口操作系统是位于用户和计算机

4、系统之间的接口从用户角度：从用户角度：用户可以通过各种接口，获得访问、使用用户可以通过各种接口，获得访问、使用系统资源的能力；系统资源的能力；从系统角度：从系统角度：系统在有序管理计算机硬件系统前提下，系统在有序管理计算机硬件系统前提下，向用户提供调用接口。向用户提供调用接口。处理机管理：处理机管理：纪录处理机状态，按策略分配处理机；纪录处理机状态，按策略分配处理机；存储器管理：存储器管理：纪录存储器使用情况，按策略分配，保护纪录存储器使用情况，按策略分配，保护信息不受破坏；信息不受破坏；I/O管理：管理：按要求和策略分配设备，优化设备调度，提高按要求和策略分配设备，优化设备调度，提高设备使用

5、效率；设备使用效率；信息管理：信息管理：以文件方式组织信息。方便的查询和保护。以文件方式组织信息。方便的查询和保护。第 9 页t从从 到到 人工操作缓慢人工操作缓慢 机器按照事先编辑好的过程完成任务的转换机器按照事先编辑好的过程完成任务的转换t从从 到到 CPU速度迅速提高而速度迅速提高而I/O设备依然缓慢，设备依然缓慢， CPU花大花大量时间等待设备量时间等待设备 输入输出在外围机控制下进行输入输出在外围机控制下进行t从从 到到 第 10 页 多道程序设计技术是在计算机多道程序设计技术是在计算机中中相互相互独立的程序，它们在管理程序的控制下独立的程序，它们在管理程序的控制下地运行。地运行。主

6、存中同时存放几道相互独立的程序；主存中同时存放几道相互独立的程序；几道程序都处于运行过程中，从用户的角几道程序都处于运行过程中，从用户的角度来看，它们在同时推进；度来看，它们在同时推进；任意一个时刻，只能有一个程序占有处理任意一个时刻，只能有一个程序占有处理机，从处理机的角度来看，多道程序轮流使用处理机，它机，从处理机的角度来看，多道程序轮流使用处理机，它们是交替推进的。们是交替推进的。第 11 页I/O中断请求中断请求I/O完成完成第 12 页 把把CPU响应时间分成若干个小时间单位（时间片）轮流分响应时间分成若干个小时间单位（时间片）轮流分配给各个联机用户使用。如果一个用户程序在分配给它的

7、时配给各个联机用户使用。如果一个用户程序在分配给它的时间片内没有完成，则暂时中断执行，等待下一轮计算。间片内没有完成，则暂时中断执行，等待下一轮计算。t作业作业123123 让用户通过控制台（终端）直接操作、控制自己程序运行让用户通过控制台（终端）直接操作、控制自己程序运行的操作方式称为联机工作方式。的操作方式称为联机工作方式。第 13 页提供用户使用计算机资源的方式，包提供用户使用计算机资源的方式，包括人机交互方式（括人机交互方式（命令方式命令方式）和从程序中调用计算）和从程序中调用计算机资源的方式（机资源的方式（系统调用方式系统调用方式）。）。处理机管理处理机管理存储器管理存储器管理设备管

8、理设备管理软件资源管理（文件系统）软件资源管理（文件系统）第 14 页 一般的计算机中只有一个处理机，一般的计算机中只有一个处理机，处理机是计算处理机是计算机系统中竞争最为激烈的资源。机系统中竞争最为激烈的资源。处理机管理负责处处理机管理负责处理机的理机的调度、分配、回收调度、分配、回收。保证处理机能得到充分。保证处理机能得到充分的利用。的利用。 存储器管理特指对存储器管理特指对资源的管理。程序必须进资源的管理。程序必须进入内存才能运行，因此内存也是计算机系统中的紧入内存才能运行，因此内存也是计算机系统中的紧俏资源。存储器管理功能有：俏资源。存储器管理功能有：内存分配与回收、地内存分配与回收、

9、地址映射、存储保护、内存的扩充。址映射、存储保护、内存的扩充。第 15 页 负责计算机系统中除负责计算机系统中除CPU和内存外的所有外部设和内存外的所有外部设备的管理，包括：备的管理，包括：设备分配、设备传输控制、设备设备分配、设备传输控制、设备无关性。无关性。 负责管理系统中的所有程序、数据以及文档资料负责管理系统中的所有程序、数据以及文档资料等信息。这些信息以文件的形式存在，因此软件资等信息。这些信息以文件的形式存在，因此软件资源管理也称源管理也称。主要功能包括：。主要功能包括：文件存储空文件存储空间管理、文件目录管理、文件控制管理间管理、文件目录管理、文件控制管理。第 16 页n 背景：

10、背景：u 系统资源十分昂贵系统资源十分昂贵u 手工输入作业的速度与手工输入作业的速度与CPU的速度不匹配的速度不匹配n 解决方案：解决方案：u 作业成批进入系统后备队列作业成批进入系统后备队列u 系统按照一定的策略自动调度作业运行系统按照一定的策略自动调度作业运行n 发展：发展：u 单道批处理系统单道批处理系统u 多道批处理系统多道批处理系统第 17 页单道批处理系统单道批处理系统多道批处理系统多道批处理系统第 18 页t能根据作业对系统资源的需求和系统当前状能根据作业对系统资源的需求和系统当前状态，充分调度资源。态，充分调度资源。t作业进入系统后，系统自动调度，管理员或作业进入系统后，系统自

11、动调度，管理员或用户不能干预系统的调度。用户不能干预系统的调度。第 19 页t分时系统的提出：解决人机交互问题，进行及时响应，多分时系统的提出：解决人机交互问题，进行及时响应，多用户用户。t一台连接多个终端的计算机称为一台连接多个终端的计算机称为。t在分时计算机上采用分时技术实现的操作系统称为在分时计算机上采用分时技术实现的操作系统称为。t 多个联机用户同时使用一台计算机。多个联机用户同时使用一台计算机。t 每个联机用户都感觉是独占计算机。每个联机用户都感觉是独占计算机。t 用户采用用户采用“一问一答一问一答”的方式使用计算机。的方式使用计算机。第 20 页第 21 页t实时系统的提出：分时系

12、统的响应往往要等待一个循环周实时系统的提出：分时系统的响应往往要等待一个循环周期，实时系统必须在规定的时间内对用户请求或外部事件期，实时系统必须在规定的时间内对用户请求或外部事件及时响应。及时响应。t能满足用户响应时限要求的操作系统称为能满足用户响应时限要求的操作系统称为。实时采集现场数据，完成实时采集现场数据，完成自动化控制自动化控制特点：特点： 响应速度足够快响应速度足够快 可靠性高可靠性高例：导弹导航例：导弹导航根据用户要求进行信息检根据用户要求进行信息检索和处理索和处理特点：特点： 强大的数据库强大的数据库 操作简便、查询快速操作简便、查询快速例：远程订票系统例：远程订票系统第 22

13、页t磁盘操作系统磁盘操作系统 其代表的是其代表的是MSDOS 设备管理、文件系统功能设备管理、文件系统功能tWindows系统系统 图形用户界面图形用户界面 多任务、多线程多任务、多线程 可剥夺式调度可剥夺式调度 段页式虚拟存储管理技术段页式虚拟存储管理技术 动态连接动态连接第 23 页 操作系统是计算机上必须配置的系统软件，它是计算机操作系统是计算机上必须配置的系统软件，它是计算机的的“管家管家”，负责计算机系统中所有软硬件资源的管理，负责计算机系统中所有软硬件资源的管理，目标是为了目标是为了方便用户充分而有效地利用这些资源方便用户充分而有效地利用这些资源。 操作系统的发展历史中，操作系统的

14、发展历史中，和和的出现，标志着操作系统的形成。的出现，标志着操作系统的形成。 从资源管理的角度来看，操作系统的四大功能是：从资源管理的角度来看，操作系统的四大功能是：、和和。 主要的操作系统类型有：主要的操作系统类型有：、。第 24 页4.2.1 并发程序设计并发程序设计4.2.2 进程进程4.2.3 进程之间的通信进程之间的通信4.2.4 多道程序的组织多道程序的组织第 25 页 顺序程序的特点顺序程序的特点: :(1) (1) 顺序性。顺序性。程序所规定的动作在机器上严格地按顺序程序所规定的动作在机器上严格地按顺序执行，每个动作的执行都以前一个动作的结束为前提条执行，每个动作的执行都以前一

15、个动作的结束为前提条件，即程序和机器执行它的活动严格一一对应。件，即程序和机器执行它的活动严格一一对应。(2) (2) 封闭性封闭性。程序一旦开始运行，其计算结果只取决于。程序一旦开始运行，其计算结果只取决于程序本身，不受外界因素的影响，即只有程序本身的动程序本身，不受外界因素的影响，即只有程序本身的动作才能改变程序的运行环境。作才能改变程序的运行环境。(3) (3) 可再现性可再现性。程序的执行结果与其执行速度无关。只。程序的执行结果与其执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果，且处理机在执行程序的两个动

16、作之会得到相同的结果，且处理机在执行程序的两个动作之间如有停顿也不会影响程序的执行结果。间如有停顿也不会影响程序的执行结果。第 26 页 然而，为增强计算机系统的处理能力和提高各种然而，为增强计算机系统的处理能力和提高各种资源的利用率，往往要求计算机系统能够同时处理多资源的利用率，往往要求计算机系统能够同时处理多个具有独立功能的程序。通常采用并行操作技术，使个具有独立功能的程序。通常采用并行操作技术，使系统中的各种硬件资源尽量做到并行工作。系统中的各种硬件资源尽量做到并行工作。 程序的并发执行程序的并发执行指两个或两个以上的程序在执指两个或两个以上的程序在执行时间上是重叠的。系统中各个部分不再

17、以单纯的串行时间上是重叠的。系统中各个部分不再以单纯的串行方式工作。换句话说，在任一时刻，系统中不再只行方式工作。换句话说，在任一时刻，系统中不再只有一个活动，而存在着许多并行的活动。从硬件方面有一个活动，而存在着许多并行的活动。从硬件方面看，处理机，各种外设，存储部件常常并行地工作着；看，处理机，各种外设，存储部件常常并行地工作着；从程序活动方面看，则可能有若干程序同时或者相互从程序活动方面看，则可能有若干程序同时或者相互穿插地在系统中被执行。穿插地在系统中被执行。并发执行的新问题：并发执行的新问题：第 27 页问题问题1 并发程序没有封闭性并发程序没有封闭性第 28 页问题问题2 程序与其

18、执行过程不是一一对应的关系程序与其执行过程不是一一对应的关系第 29 页问题问题3 程序并发执行可以互相制约程序并发执行可以互相制约第 30 页第 31 页1. 进程的基本概念进程的基本概念进程进程指一个具有一定独立功能的程序关于某个数据指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。集合的一次运行活动。进程是可以并发执行的程序的执行过程，它是控制程序进程是可以并发执行的程序的执行过程，它是控制程序管理下的基本的多道程序单位。管理下的基本的多道程序单位。第 32 页(1) (1) 进程是程序在处理机上的一次执行过程，它是动态进程是程序在处理机上的一次执行过程，它是动态 的概念。而程

19、序只是一组指令的有序集合，其本身的概念。而程序只是一组指令的有序集合，其本身 没有任何运行的含义，它是一个静态的概念。没有任何运行的含义，它是一个静态的概念。(2) (2) 进程是程序的执行过程，是一次运行活动。因此，进程是程序的执行过程，是一次运行活动。因此， 进程具有一定的生命期，它能够动态地产生和消亡。进程具有一定的生命期，它能够动态地产生和消亡。 而程序是可以作为一种软件资源长期保存的，它的而程序是可以作为一种软件资源长期保存的，它的 存在是永久的。存在是永久的。(3) (3) 进程是程序的执行过程，因此，进程的组成应包括进程是程序的执行过程，因此，进程的组成应包括 程序、数据与记录进

20、程状态信息的程序、数据与记录进程状态信息的“进程控制块进程控制块”。(4) (4) 一个程序可能对应多个进程。一个程序可能对应多个进程。(5) (5) 一个进程可以包含多个程序。一个进程可以包含多个程序。2、进程和程序的区别、进程和程序的区别第 33 页 就绪状态就绪状态(ready) 存在于处理机调度队列中的那些进存在于处理机调度队列中的那些进程，它们已经准备就绪，一旦得到程，它们已经准备就绪，一旦得到CPU，就可以立即运行，就可以立即运行，这些进程所处的状态称为就绪状态。这些进程所处的状态称为就绪状态。 运行状态运行状态(running) 当进程得到处理机控制权时，它当进程得到处理机控制权

21、时，它的程序正在处理机上运行，该进程所处的状态为运行状态。的程序正在处理机上运行，该进程所处的状态为运行状态。 等待状态等待状态(wait) 若一个进程正等待着某一事件发生（若一个进程正等待着某一事件发生（如等待输入输出操作的完成）而暂时停止执行，这时，即使如等待输入输出操作的完成）而暂时停止执行，这时，即使给它给它CPU时间，它也无法执行，则称该进程处于等待状态（时间，它也无法执行，则称该进程处于等待状态（又可称为又可称为阻塞状态阻塞状态或或挂起状态挂起状态）。）。第 34 页运运 行行等等 待待就就 绪绪服务请求服务请求/等待事件等待事件服务完成服务完成/事件来到事件来到分配到分配到CPU

22、时间片用完时间片用完有一种状态变迁是永远也不可能发生的。有一种状态变迁是永远也不可能发生的。 进程随着自身的推进和外界条件的变化而进程随着自身的推进和外界条件的变化而从一个状态从一个状态变换为另一个状态称为变换为另一个状态称为。第 35 页一个进程包含一个进程包含4个组成部分：个组成部分：程序程序描述进程要完成的功能的指令序列；描述进程要完成的功能的指令序列；数据数据程序加工的对象；程序加工的对象；工作区工作区程序执行使用的内存区域，如用户栈或系统栈；程序执行使用的内存区域，如用户栈或系统栈；进程控制块进程控制块存放进程控制和管理信息的数据结构。存放进程控制和管理信息的数据结构。进程控制块进程

23、控制块PCB（Process Control Block）是进程存在的标）是进程存在的标志！是进程的志！是进程的。进程创建时建立进程创建时建立PCB。在进程的生命周期内，在进程的生命周期内，OS通过对通过对PCB的管理来实现对进程的管理来实现对进程的管理。的管理。进程撤消时删除相应的进程撤消时删除相应的PCB。第 36 页 进程控制块是进程组成中最关键的部分，其中含有进程进程控制块是进程组成中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，它是的描述信息和控制信息，是进程动态特性的集中反映，它是系统对进程识别和控制的依据。系统对进程识别和控制的依据。PCB程序程序数据

24、集合数据集合进程名进程名特征信息特征信息现场保护区现场保护区进程状态信息进程状态信息调度优先权调度优先权其它信息其它信息族系关系族系关系进程实体信息进程实体信息通信信息通信信息资源需求分配信息资源需求分配信息第 37 页 对系统中的进程实施有效的管理和控制。具体表现为控制对系统中的进程实施有效的管理和控制。具体表现为控制进程进入不同的状态。进程进入不同的状态。新进程新进程结束结束 第 38 页 第 39 页6.死锁问题死锁问题死锁死锁若干个进程均因互相若干个进程均因互相“无知地无知地”等待对方所占有的等待对方所占有的资源而无限地等待。资源而无限地等待。第 40 页例：假设系统中有例：假设系统中

25、有1010台磁带机，由台磁带机，由A A，B B，C C三个进程所共享三个进程所共享现假定现假定A A，B B，C C已分别占用了已分别占用了2 2台，台，3 3台和台和2 2台磁带机，它们台磁带机，它们的最大需求量分别为的最大需求量分别为4 4台，台，6 6台和台和8 8台。并且还假定每个进程台。并且还假定每个进程只有满足了最大需求量后才可能释放其所有的资源。只有满足了最大需求量后才可能释放其所有的资源。第 41 页死锁的四个必要条件：死锁的四个必要条件：(1) (1) 资源的独占使用。资源的独占使用。(2) (2) 资源的非抢占分配。资源的非抢占分配。(3) (3) 资源的部分分配。资源的

26、部分分配。(4) (4) 对资源的循环等待。对资源的循环等待。第 42 页三个基本概念：三个基本概念：一次仅允许一个进程使用的资源称为临界资源。一次仅允许一个进程使用的资源称为临界资源。许多物理设备（如打印机等）和软件资源（如变量、数据、队许多物理设备（如打印机等）和软件资源（如变量、数据、队列等）都具有这种独占性的特点。列等）都具有这种独占性的特点。在进程中访问临界资源的那段代码称为临界区。在进程中访问临界资源的那段代码称为临界区。要注意区分临界资源与临界区。要注意区分临界资源与临界区。当一个进程正在访问某临界区时，不允许其它进程当一个进程正在访问某临界区时，不允许其它进程进入其相应的临界区

27、，这种相互制约的关系称为互斥。进入其相应的临界区，这种相互制约的关系称为互斥。例如：飞机订票系统中各个订票点对机票库的访问例如：飞机订票系统中各个订票点对机票库的访问反映了进程间的反映了进程间的竞争竞争与与合作合作第 43 页进入区进入区退出区退出区进入区进入区退出区退出区改变资源改变资源状态状态释放资源释放资源唤醒等待唤醒等待进程进程进程进程 1进程进程 2等待资等待资源释放源释放第 44 页问题：问题：如何保证进程之间是互斥的进入临界区的呢？如何保证进程之间是互斥的进入临界区的呢？答：答：操作系统提供了进程间同步和互斥的机制，程序中使用操作系统提供了进程间同步和互斥的机制，程序中使用这些机

28、制来保证执行中的互斥进入。其中最常见的机制就是这些机制来保证执行中的互斥进入。其中最常见的机制就是。 信号灯是一个二元组信号灯是一个二元组(s, q)，其中：，其中：s 是一个具有是一个具有非负初值非负初值的整型变量，的整型变量，q 是一个初始状态为空的队列指针。是一个初始状态为空的队列指针。 通过对信号灯的通过对信号灯的P、V操作，进程可以实现相互间的互斥。操作，进程可以实现相互间的互斥。第 45 页P操作的实现：操作的实现：（1）s 值减值减1；（2）若相减结果大于等于）若相减结果大于等于0， 则进程继续执行；则进程继续执行；（3）若结果小于）若结果小于0，则该进程，则该进程挂起。挂起。注

29、：注：挂起该进程包括：保留挂起该进程包括：保留调用进程调用进程CPU现场；置现场；置“等等待待”状态；入等待队列；转状态；入等待队列；转进程调度；进程调度；V操作的实现：操作的实现：（1）s 值加值加1；（2）若相加结果大于）若相加结果大于0，进，进 程继续执行；程继续执行；（3）否则，唤醒一个等待该）否则，唤醒一个等待该信号灯的进程，然后本进程信号灯的进程，然后本进程继续执行。继续执行。注：注：等待该信号灯的进程也等待该信号灯的进程也就是队列就是队列q 中的进程。中的进程。P操作表示对资源的操作表示对资源的V操作表示对资源的操作表示对资源的第 46 页问题：问题：x代表某航班机座号，代表某航

30、班机座号，p1和和p2两个售票进程，售票工两个售票进程，售票工作是对变量作是对变量x加加1。试用信号灯的。试用信号灯的P、V操作实现这两个进程操作实现这两个进程的互斥。的互斥。设：设：S为互斥信号灯，初值为为互斥信号灯，初值为1 ；p1( ) p(S)；x=x+1 ；v(S)；p2( ) p(S)；x=x+1 ；v(S)；第 47 页 为完成某个任务，并发进程在一些关键点可能需要相互为完成某个任务，并发进程在一些关键点可能需要相互等待与互通消息等待与互通消息, , 这种关系称为这种关系称为。同步进程间是一同步进程间是一种种关系关系门诊医生：门诊医生： 开开化验单；化验单； 等等化验结果；化验结

31、果； 继续诊病；继续诊病；化验员：化验员： 等等化验单；化验单； 化验；化验； 填写化验结果；填写化验结果； 第 48 页 计算进程计算进程 cp 和打印进程和打印进程 op 共用一个缓冲区，为了完成正共用一个缓冲区，为了完成正确的计算与打印，试用信号灯实现这两个进程的同步。确的计算与打印，试用信号灯实现这两个进程的同步。 缓冲区缓冲区bufop cp cp 进程把计算结果送入进程把计算结果送入 buf 之后，之后，op 进程才能从进程才能从 buf 中取出结果打印，中取出结果打印，即即。 op 进程把进程把 buf 中的数据取出打印中的数据取出打印之后，之后，cp 进程才能把下一个计算结进程

32、才能把下一个计算结果送入果送入 buf 中，即中，即。设置：设置：两个信号灯两个信号灯Sa和和Sb： Sa：表示缓冲区中是否有可供打印的计算结果，其初值为：表示缓冲区中是否有可供打印的计算结果，其初值为0； Sb ：表示缓冲区有无空位置存放新的信息，其初值为：表示缓冲区有无空位置存放新的信息，其初值为1。第 49 页main( )int Sa=0； /* 0表示表示buf中无可打印的信息中无可打印的信息 */int Sb=1； /* 1表示表示buf中有空位置存放新信息中有空位置存放新信息 */cobegincp( )；op( )；coendcp( ) while (计算未完成计算未完成) 得

33、到一个计算结果；得到一个计算结果；P(Sb)；将数送到缓冲区中；将数送到缓冲区中；V(Sa)； op( ) while (打印工作未完成打印工作未完成) P(Sa) ；从缓冲区中取一数；从缓冲区中取一数； V(Sb) ；从打印机上输出；从打印机上输出； 第 50 页宏观调度：宏观调度：选择辅存上的后备作业进入系统，并做作业选择辅存上的后备作业进入系统，并做作业完成的善后处理工作。完成的善后处理工作。微观调度：微观调度：当当CPU空闲时，选择一个就绪进程去运行。空闲时，选择一个就绪进程去运行。先来先服务调度算法先来先服务调度算法 按作业来到的先后次序进行调度。按作业来到的先后次序进行调度。 这种

34、算法优先考虑在系统中等待时间最长的作业，而不管它这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。要求运行时间的长短。短作业优先调度算法短作业优先调度算法 按作业运行时间的长短进行调度。按作业运行时间的长短进行调度。 它总是选取计算时间最短的作业为下一个服务对象。它总是选取计算时间最短的作业为下一个服务对象。第 51 页运行运行就绪就绪完成完成等待等待后备后备提交提交进入内存执行进入内存执行第 52 页 当处理机空闲时，根据一定的调度策略从就绪队列中选择当处理机空闲时，根据一定的调度策略从就绪队列中选择一个进程去运行，分配一个处理机时间。一个进程去运行，分配一个处理机时间

35、。选择哪个就选择哪个就绪进程呢？绪进程呢？进程调度算法进程调度算法第 53 页预先确定各进程的优先数，系统把处理预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权（优先数和一定机的使用权赋予就绪队列中具备最高优先权（优先数和一定的优先级相对应）的就绪进程。的优先级相对应）的就绪进程。例如：在实时系统中，实时任务的优先级高，当实时任务到达例如：在实时系统中，实时任务的优先级高，当实时任务到达时，采用优先数调度算法的进程调度程序就会优先选择实时任时，采用优先数调度算法的进程调度程序就会优先选择实时任务运行。务运行。当当CPU空闲时，选取就绪队列首元素，空闲时，选取就绪队列首元

36、素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。入就绪队列末端。例如：在分时系统中，往往采用循环轮转调度算法，以保证对例如：在分时系统中，往往采用循环轮转调度算法，以保证对每个用户的公平响应。每个用户的公平响应。第 54 页作业调度和进程调度是作业调度和进程调度是CPU主要的两级调度。主要的两级调度。 作业调度和进程调度的区别作业调度和进程调度的区别 作业调度（宏观调度）作业调度（宏观调度） 进程调度（微观调度）进程调度（微观调度） 为进程活动做准备，即有获得为进程活动做准备，即有获得处理机的资格处理机的资格 使进程活

37、动起来，即分配得到使进程活动起来，即分配得到了处理机了处理机 调度次数少调度次数少 调度频率高调度频率高 有的系统不设作业调度有的系统不设作业调度 进程调度必不可少进程调度必不可少 第 55 页进程概念的引入进程概念的引入程序的顺序执行和并发执行的特点程序的顺序执行和并发执行的特点进程概念的基本概念进程概念的基本概念 1. 进程定义（定义、进程与程序的区别进程定义（定义、进程与程序的区别 ）2. 进程状态（三个基本状态、状态变迁图）进程状态（三个基本状态、状态变迁图）3. 进程描述（进程描述（pcb结构、定义、作用）结构、定义、作用）进程的互斥与同步进程的互斥与同步1. 临界资源临界资源 2.

38、 临界区临界区3. 互斥和同步互斥和同步4. 用信号灯的用信号灯的P、V操作实现进程的互斥与同步操作实现进程的互斥与同步第 56 页4.3.1 内存储器的管理技术内存储器的管理技术4.3.2 外存储器中文件的组织结构外存储器中文件的组织结构第 57 页存储管理的目的：存储管理的目的：理由理由1：存储器分为主存和辅存（二级存储），存储器分为主存和辅存（二级存储），所有程序必须调入主存才能运行，而所有程序必须调入主存才能运行，而主存空间有主存空间有限限，所以必须对主存进行管理。，所以必须对主存进行管理。理由理由2：主存的空间分为系统区和用户区，系统主存的空间分为系统区和用户区，系统区用来存放操作系

39、统等信息，区用来存放操作系统等信息，用户区存放用户的用户区存放用户的程序和数据程序和数据，存储管理是指对用户区进行管理。，存储管理是指对用户区进行管理。应当尽量方便用户，提高主存空间利用率。应当尽量方便用户，提高主存空间利用率。 第 58 页主要有主要有5项内容：项内容：v主存空间的分配和回收主存空间的分配和回收v地址转换地址转换（或地址映射或地址映射）v主存空间的扩充主存空间的扩充v存储的保护（存储的保护（或信息保护或信息保护）v主存空间的共享主存空间的共享 作业进入内存或进程动态作业进入内存或进程动态申请主存空间时，申请主存空间时，OSOS该将该将哪块空闲区分配出去？作哪块空闲区分配出去？

40、作业或进程执行完毕，业或进程执行完毕，OSOS又又如何收回这些区域？如何收回这些区域？逻辑地址如何转换为物理地址？逻辑地址如何转换为物理地址？不转换就不能正确运行程序。不转换就不能正确运行程序。用户程序太大，内存装不用户程序太大，内存装不下怎么办？下怎么办？虚拟存储虚拟存储技术，逻辑地址顺序排，技术，逻辑地址顺序排，物理地址分段转。物理地址分段转。内存中各作业或进程应当内存中各作业或进程应当在各自规定区域内操作，在各自规定区域内操作，要保证互不干扰。要保证互不干扰。多个作业用到公共程序或数多个作业用到公共程序或数据，可放入某空间让大家都据，可放入某空间让大家都能调用，共享主存空间。能调用，共享

41、主存空间。（与第（与第4项有矛盾）项有矛盾）第 59 页第 60 页mov r1,5001230100500599作业地址空间作业地址空间 mov r1 , 50012301000256k-1存储空间存储空间110015001600 1000500逻辑地址逻辑地址这种系统采用的是这种系统采用的是存储管理存储管理第 61 页给每个作业划分一个区（这是多道情况，给每个作业划分一个区（这是多道情况，DOS单用户单用户单任务不必分区），全部内存（除驻留的单任务不必分区），全部内存（除驻留的OS外）连续分配给外）连续分配给用户即可。又分为用户即可。又分为“固定分区固定分区”和和“可变分区可变分区”。固定

42、式分区固定式分区把内存先分成大小固定的（空）区，再把作把内存先分成大小固定的（空）区，再把作业一一往里套送；业一一往里套送；实现法：实现法：建立建立“分区分配表分区分配表”，设，设“已分配已分配/未分配未分配”状态标状态标志志第 62 页按装入的按装入的作业大小来分区作业大小来分区，保证初始无碎片。但系统，保证初始无碎片。但系统运行一段时间后，随着作业的进出释放，就会留下很多分运行一段时间后，随着作业的进出释放，就会留下很多分区（且分区长度可变），要用两张表才能描述（已分配的区（且分区长度可变），要用两张表才能描述（已分配的表和空闲分区表）。表和空闲分区表）。 分区存储管理的特点；分区存储管理

43、的特点；优点：简单可靠优点：简单可靠 缺点：碎片多（虽然可以进行碎片整理，但缺点：碎片多（虽然可以进行碎片整理，但CPU耗时多）耗时多） 第 63 页u每个程序完全载入内存，并占用连续的地址。每个程序完全载入内存，并占用连续的地址。u分区的大小必须由内存管理器预先决定。分区的大小必须由内存管理器预先决定。u即使分区在计算机启动时很合适，但随着程序交换载入内即使分区在计算机启动时很合适，但随着程序交换载入内存后有可能出现空闲区。存后有可能出现空闲区。u当空闲区过多时，会增加系统负担。当空闲区过多时，会增加系统负担。第 64 页设计思想：为解决碎片问题，允许作业不连续存放，可设计思想：为解决碎片问

44、题，允许作业不连续存放，可以把以把主存空间等分为主存空间等分为若干小若干小块块，同时把，同时把外存作业外存作业尺寸也尺寸也等分为等分为若干若干“页页”，并让块和页尺寸相等（例如，并让块和页尺寸相等（例如1K、4K、32K等）等） ，分得越小，碎片越少。，分得越小，碎片越少。请注意：内存请注意：内存Cache+主存主存页式存储管理实现方案：页式存储管理实现方案：只要只要“不连续不连续”，势必要，势必要用到数据结构中的用到数据结构中的“链表链表”和和“索引索引”概念。可以用概念。可以用“页表页表”将作业的将作业的“页页”与主存的与主存的“块块”关联起来。关联起来。第 65 页程序在内存中不必是连续

45、的。程序在内存中不必是连续的。整个程序必须全部载入内存。整个程序必须全部载入内存。第 66 页问题：问题：作业的物理地址空间由连续变成分散后，如何保证程序作业的物理地址空间由连续变成分散后，如何保证程序的正确寻址呢？的正确寻址呢？方法：方法：使用使用来记录页与内存块之间的对应关系。页来记录页与内存块之间的对应关系。页面映像表简称面映像表简称。10KB 101KB01KB2KB3KB 1主存空间主存空间作业作业2地址空间地址空间2KB3KB4KB5KB6KB7KB8KB9KB01KB2KB 1作业作业1地址空间地址空间01KB 1作业作业3地址空间地址空间0516页号页号块号块号02140827

46、作业作业1页表页表作业作业2页表页表作业作业3页表页表OSOS第 67 页若将作业预先一次性全部装入主存，则称为若将作业预先一次性全部装入主存，则称为静态静态页式管理页式管理页式存储管理还可分为两种方法：页式存储管理还可分为两种方法：静态静态页式管理页式管理 和和 虚拟虚拟页式管理页式管理。若允许部分页面先调入主存执行，然后根据需要再陆续调入若允许部分页面先调入主存执行，然后根据需要再陆续调入其他页面，则称为其他页面，则称为虚拟虚拟页式管理，即内存外存统一管理。页式管理，即内存外存统一管理。若主存空间不若主存空间不够大怎么办？够大怎么办？那就不装！一定要保证那就不装！一定要保证作业总页数作业总

47、页数主存空闲块总数主存空闲块总数需要解决需要解决2个问题：个问题：怎知作业页怎知作业页在不在主存？不在主存时怎样处理？在不在主存？不在主存时怎样处理？此时页表至少要增添两项属性！此时页表至少要增添两项属性！第 68 页讨讨 论：论： 此表何时建立？此表何时建立？作业调入内存时就边调入边建立了。作业调入内存时就边调入边建立了。 程序页在不在主存，看缺页中断标志标志（程序页在不在主存，看缺页中断标志标志（ 0在在1不在）；不在）；进入之后改标志为进入之后改标志为0；退出之后改为；退出之后改为1； 不在主存时，发出缺页中断申请，找到主存一空闲块之不在主存时，发出缺页中断申请，找到主存一空闲块之后，赶

48、紧从磁盘调入，接着改变标志；后，赶紧从磁盘调入，接着改变标志； 万一主存没有空闲区怎么办？要淘汰一些页面，腾出空万一主存没有空闲区怎么办？要淘汰一些页面，腾出空间调入新页间调入新页。逻辑页号逻辑页号主存块号主存块号中断标志中断标志磁盘位置磁盘位置090（在主存中）（在主存中）a11110a22 1a33 1a4第 69 页l l 先进先出算法（先进先出算法（FIFO） 页号进入时生成队列，淘汰队首；页号进入时生成队列，淘汰队首； l l 最近最久未使用算法（最近最久未使用算法（LRU，Least Recently Used） 近期未使用，记录上次引用后的近期未使用，记录上次引用后的驻留时间驻留

49、时间l l 最近最少使用算法（最近最少使用算法（LFU，Least Frequently Used） 近期未访问，设置近期未访问，设置访问计数器访问计数器第 70 页问题：问题：若一段程序分在两页上怎么办？若一段程序分在两页上怎么办？方案：方案：将作业按逻辑内容长短分段调入，防止分在两页上。将作业按逻辑内容长短分段调入，防止分在两页上。谁来分段？谁来分段？由程序员或编译系统来分段。由程序员或编译系统来分段。 具体实现：具体实现：建立段表。建立段表。 第 71 页 若程序分成若程序分成N段却无法一次放入内存怎么办？段却无法一次放入内存怎么办？ 用段式虚拟存储方式分批调入，方法同页式。用段式虚拟存

50、储方式分批调入，方法同页式。 若一段太大，内存无法提供连续空间怎么办？若一段太大，内存无法提供连续空间怎么办？ 段页式存储管理，段内再分页，多建一个索引表段页式存储管理，段内再分页，多建一个索引表到内存。到内存。存取内存中的一条指令至少要访问几次内存？存取内存中的一条指令至少要访问几次内存？至少要访问至少要访问三次三次内存。前提是指令的逻辑地址已知，内存。前提是指令的逻辑地址已知，即段号和页号已知。即段号和页号已知。先根据控制寄存器访问段表，得到与该段对应的页先根据控制寄存器访问段表，得到与该段对应的页表首址；表首址；访问页表，得到其页号对应的内存块号；访问页表，得到其页号对应的内存块号； 以

51、块号与页内地址拼接得到该指令的绝对物理地址。以块号与页内地址拼接得到该指令的绝对物理地址。第 72 页什么是文件？什么是文件？ 文件是在逻辑上具有完整意义的信息集合，它有一个名字以文件是在逻辑上具有完整意义的信息集合，它有一个名字以供标识，文件名是有供标识，文件名是有若干约束若干约束的字符串。的字符串。什么是文件系统？什么是文件系统？ 文件系统是操作系统中文件系统是操作系统中负责管理和存取文件信息负责管理和存取文件信息的软件机构。的软件机构。负责负责: 辅存空间的管理和文件的存储辅存空间的管理和文件的存储 构造文件结构构造文件结构 提供文件存取功能提供文件存取功能 提供文件共享功能提供文件共享

52、功能 提供文件保护功能提供文件保护功能计算机数据管理的重大发展计算机数据管理的重大发展用户不需要关心用户不需要关心信息的存储细节信息的存储细节第 73 页(1) 流式文件（无结构文件）流式文件（无结构文件） 的流式文件是相关的有序字符的集合。文件长度即的流式文件是相关的有序字符的集合。文件长度即为所含字符数。如源程序、中间代码等。为所含字符数。如源程序、中间代码等。例如：例如：C语言文件语言文件class.c(2) 记录式文件记录式文件 记录式文件是一种记录式文件是一种的文件。这种文件在逻辑上被看成的文件。这种文件在逻辑上被看成一组连续顺序的记录集合，每个记录由彼此相关的域构成。一组连续顺序的

53、记录集合，每个记录由彼此相关的域构成。 如果所有记录的长度都相同，则这种文件为如果所有记录的长度都相同，则这种文件为定长记录文件定长记录文件。定长记录文件的长度记录个数定长记录文件的长度记录个数记录长度记录长度例如：学生登记表文件例如：学生登记表文件student.dbf李铭李铭925678925678武昌武昌关山街武昌武昌关山街125125号号430074430074司马乐司马乐925679925679北京北京北京海军路北京海军路8888号号100034100034记录记录1记录记录2第 74 页(1) 顺序存取顺序存取 即后一次存取总是在前一次存取的基础上进行的，即后一次存取总是在前一次存

54、取的基础上进行的，所以不给出具体的存取位置。所以不给出具体的存取位置。(2) 随机存取随机存取 即在请求对某个文件进行存取时，要指出其始存即在请求对某个文件进行存取时，要指出其始存取位置取位置( 如记录号、字符序号如记录号、字符序号)。 文件的物理结构指文件在存储器中的存储结构。即一个文件在文件的物理结构指文件在存储器中的存储结构。即一个文件在辅存中的安置、链接和编目的方法。常用的文件物理结构形式有：辅存中的安置、链接和编目的方法。常用的文件物理结构形式有：t 连续文件连续文件t 链接文件（串联文件）链接文件（串联文件）t 索引文件索引文件第 75 页连续文件结构由一组分配在磁盘连续文件结构由

55、一组分配在磁盘连续连续区域的物理块组成。区域的物理块组成。文件文件A 3 100 r0 r1 r2 磁盘块号磁盘块号100101102文件目录文件目录文件文件A目录项目录项第 76 页 链接文件结构是按顺序由若干个串联的物理块组成的，链接文件结构是按顺序由若干个串联的物理块组成的，每个物理块的最末一个字每个物理块的最末一个字( (或第一个字或第一个字) )作为链接字，它指出作为链接字，它指出后继块的物理地址。后继块的物理地址。链接链接文件文件A 100 r1 57 r2 r0 150磁盘块号磁盘块号 100磁盘块号磁盘块号 150磁盘块号磁盘块号 57文件目录文件目录文件文件A目录项目录项第

56、77 页 将逻辑文件顺序地划分成长度与物理存储块长度相同的逻将逻辑文件顺序地划分成长度与物理存储块长度相同的逻辑块，然后建立逻辑块号与物理块号的对照表。这张表称为辑块，然后建立逻辑块号与物理块号的对照表。这张表称为该文件的索引表。该文件的索引表。文件文件A索引表指针索引表指针文件文件A目录项目录项 r0 r1文件目录文件目录 逻辑块号逻辑块号 物理块号物理块号 0 23 1 19 2 26 3 29 r2 r3磁盘块号磁盘块号 23磁盘块号磁盘块号 19磁盘块号磁盘块号 26磁盘块号磁盘块号 29文件索引表文件索引表第 78 页文文件件的的多多级级索索引引结结构构 根据统计，文件容量不超过根据

57、统计，文件容量不超过10块块(5120 B)的文件占文件总数的的文件占文件总数的80%，而这，而这10块通过直接寻址就能得到文件的物理块块通过直接寻址就能得到文件的物理块号，只是对于大于号，只是对于大于10块的约占总数块的约占总数20%的的文件才采用间接寻址。这种结构的优点与文件才采用间接寻址。这种结构的优点与一般索引文件结构一样，只是对于约一般索引文件结构一样，只是对于约20%的文件由于多次取索引而影响速度。的文件由于多次取索引而影响速度。例：设有混合分配的文件，其文件索引结点有例：设有混合分配的文件，其文件索引结点有13个地址项个地址项iaddr（0）-iaddr（12）。其中）。其中0-

58、9项项为直接地址分配，为直接地址分配，10、11、12项分别为一级、项分别为一级、二级、三级索引分配，盘块大小为二级、三级索引分配，盘块大小为4KB，每个，每个盘块号占盘块号占4个字节。分析长度为个字节。分析长度为8MB的文件，的文件，需采用几级索引分配方式存放。需采用几级索引分配方式存放。 t盘块大小为盘块大小为4KB，在文件的直接地址中，可存放的，在文件的直接地址中，可存放的文件最大长度为文件最大长度为104KB=40KB。t每个盘块号占每个盘块号占4个字节，一个盘块可存放个字节，一个盘块可存放1K个索引个索引盘块号。盘块号。t一 级 索 引 中 可 存 放 的 文 件 最 大 长 度 为

59、一 级 索 引 中 可 存 放 的 文 件 最 大 长 度 为1K4KB=4MB，二级索引可存放的文件最大长度，二级索引可存放的文件最大长度为为1K1K4KB=4GBt现文件长度为现文件长度为8MB，需采用二级索引分配方式才能，需采用二级索引分配方式才能存放该文件存放该文件 答案答案第 82 页 什么是文件目录？什么是文件目录？ 文件系统的主要功能是实现按名存取，用户只需向系统提文件系统的主要功能是实现按名存取，用户只需向系统提供一个文件的符号名，系统就能准确地找出所要的文件。为供一个文件的符号名，系统就能准确地找出所要的文件。为此系统应记录文件名与其存储地址的映射关系，以及该文件此系统应记录

60、文件名与其存储地址的映射关系，以及该文件的使用特性及访问权限等信息，这些信息存放在一个称为文的使用特性及访问权限等信息，这些信息存放在一个称为文件目录的数据结构中。件目录的数据结构中。 所谓文件目录，是指用于记录系统中所有文件的所谓文件目录，是指用于记录系统中所有文件的的的。t 文件名文件名t 文件的逻辑结构文件的逻辑结构t 文件的物理位置文件的物理位置t 存取控制信息（不同用户对该文件的使用权限）存取控制信息（不同用户对该文件的使用权限）t 管理信息（如文件的创建时间管理信息（如文件的创建时间、最后一次存取时间等）、最后一次存取时间等）t 文件类型（如数据文件，目录文件等）文件类型（如数据文