操作系统原理课件

对计算规律的模拟对计算规律的模拟存储程序式计算机存储程序式计算机存储程序式计算机模型存储程序式计算机模型l存储程序式计算机模型的基本方案是，如要使计算存储程序式计算机模型的基本方案是，如要使计算机能够自动地计算，必须有一个存储器用来存储程机能够自动地计算，必须有一个存储器用来存储程序和数据；同时要有一个运算器，用以执行指定的序和数据；同时要有一个运算器，用以执行指定的操作；有一个控制器，以便实现自动操作；另外，操作；有一个控制器，以便实现自动操作；另外，辅以输入辅以输入/输出部件，以便输入原始数据和输出计输出部件，以便输入原始数据和输出计算结果。于是形成了现代计算机的基本组成形式。算结果。于是形成了现代计算机的基本组成形式。如图如图1.1所示。所示。图图1.1 存储程序计算机的组成存储程序计算机的组成 无操作系统的计算机无操作系统的计算机l从第一代计算机诞生到从第一代计算机诞生到20世纪世纪50年代中期还未出年代中期还未出现操作系统，这时的计算机采用人工操作方式。其现操作系统，这时的计算机采用人工操作方式。其过程是：过程是：图图1.2 手工操作计算机手工操作计算机单道批处理系统与多道批处理单道批处理系统与多道批处理系统及执行系统系统及执行系统l所谓批处理系统是指加载在计算机上的一个系统软所谓批处理系统是指加载在计算机上的一个系统软件，在它的控制下，计算机能够自动地成批地处理件，在它的控制下，计算机能够自动地成批地处理一个或多个用户的作业。一个或多个用户的作业。l首先出现的是联机批处理系统。如下图所示。首先出现的是联机批处理系统。如下图所示。脱离主机控制的输入脱离主机控制的输入/输出批处理输出批处理系统系统 l在外设处理数据时，主机处理在外设处理数据时，主机处理“忙等忙等”状态，这样状态，这样高速的主机与慢速的外设矛盾就显现出来。为了克高速的主机与慢速的外设矛盾就显现出来。为了克服与缓解主机与外设的矛盾。我们引入脱机批处理服与缓解主机与外设的矛盾。我们引入脱机批处理系统，即脱离主机控制的输入系统，即脱离主机控制的输入/输出批处理系统。输出批处理系统。如图如图1.4所示。所示。图图1.4 脱机批处理系统脱机批处理系统l在单道批处理系统中，内存中仅有一道作业，中断和通道在单道批处理系统中，内存中仅有一道作业，中断和通道技术出现以后，虽然可以实现输入技术出现以后，虽然可以实现输入/输出设备与中央处理机输出设备与中央处理机并行操作，但由于属于同一道作业的可并发执行的进程不并行操作，但由于属于同一道作业的可并发执行的进程不多，大多数进程是有同步关系的，这使系统中仍有较多的多，大多数进程是有同步关系的，这使系统中仍有较多的空闲资源，致使系统的性能较差。为了进一步提高资源的空闲资源，致使系统的性能较差。为了进一步提高资源的利用率和系统对作业的吞吐量，在利用率和系统对作业的吞吐量，在60年代中期，引入了多年代中期，引入了多道程序设计技术，由此而形成了多道批处理系统。单道程道程序设计技术，由此而形成了多道批处理系统。单道程序与多道程序的执行过程如图序与多道程序的执行过程如图1.5和图和图1.6所示。所示。在操作系统中引入多道程序设计技在操作系统中引入多道程序设计技术以后，会使系统具有以下特征。术以后，会使系统具有以下特征。l（1）多道性）多道性 l（2）无序性）无序性 l（3）宏观上并行、微观上串行）宏观上并行、微观上串行 l（4）调度性）调度性 分时系统分时系统l分时技术是把处理机的时间分成很短的时间片，这分时技术是把处理机的时间分成很短的时间片，这些时间片轮流地分配给各个联机的各作业使用。如些时间片轮流地分配给各个联机的各作业使用。如果某作业在分配给它的时间片用完时仍未完成，则果某作业在分配给它的时间片用完时仍未完成，则该作业就暂时中断，等待下一轮运行，并把处理机该作业就暂时中断，等待下一轮运行，并把处理机的控制权让给另一个作业使用。这样在一个相对较的控制权让给另一个作业使用。这样在一个相对较短的时间间隔内，每个用户作业都能得到快速响应，短的时间间隔内，每个用户作业都能得到快速响应，以实现人机交互。以实现人机交互。l分时系统与多道批处理系统相比，具有完分时系统与多道批处理系统相比，具有完全不同的特征，由上所述可以归纳成以下全不同的特征，由上所述可以归纳成以下几点：几点：（1）多路性）多路性（2）独立性）独立性（3）及时性）及时性（4）交互性）交互性 设置设置OS的目的的目的l扩充机器功能，方便用户使用。扩充机器功能，方便用户使用。l提高系统效率。提高系统效率。裸机裸机操作系统操作系统其他软件其他软件.用户用户1。4节节以多道成批系统以多道成批系统为例为例l并发并发l共享共享l不确定性不确定性1.3 OS的服务功能的服务功能l程序执行程序执行lI/O操作操作l文件系统管理文件系统管理l出错检测出错检测l资源分配资源分配l统计统计l保护保护一一 系统调用系统调用l是应用程序与是应用程序与OS的接口的接口l进程或作业控制：实现进程或作业的所有活动进程或作业控制：实现进程或作业的所有活动l文件管理和设备管理文件管理和设备管理l信息维护：用户与系统交互信息信息维护：用户与系统交互信息二二 系统程序系统程序l文件管理文件管理l状态信息状态信息l文件修改文件修改l程序设计语言支持程序设计语言支持l程序装入与执行程序装入与执行l工具性软件工具性软件l命令解释程序的实现方法命令解释程序的实现方法l单块结构单块结构l层次结构层次结构:分层实现的软件设计方法分层实现的软件设计方法.l虚拟机虚拟机l客户客户/服务器模型服务器模型:再用户进程方式下实现系统的多再用户进程方式下实现系统的多数功能数功能;核心只负责客户与服务器的通信核心只负责客户与服务器的通信;适用于适用于分布式系统分布式系统;注意对关键基础服务的处理注意对关键基础服务的处理.1。8 UNIX系统的特点和结构系统的特点和结构lUNIX的主要特点的主要特点lUNIX系统结构系统结构lUNIX系统核心结构系统核心结构进程概念进程概念程序的顺序执行程序的顺序执行与并发执行与并发执行程序的顺序执行程序的顺序执行概念概念一个程序由若干个程序段组成，而这些程序段的执行一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执必须是顺序的，这种程序执行的方式就称为程序的顺序执行。行。例如：例如：1 1 顺序性顺序性处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2 2 封闭性封闭性程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。3 3 可再现性可再现性程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。O=f(I),f是与时间无关的函数例：例：在系统中有在系统中有n n个作业，每个作业都有三个个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即处理步骤，输入数据、处理、输出，即I Ii i,C,Ci i,P,Pi i(i=1,2,3,.,n)(i=1,2,3,.,n)。这些作业系统中执行时是对时间的偏序，这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。序的，但有些操作是可以同时执行的。例如：例如：P1P1与与I2I2，C1C1与与I2,I3I2,I3与与P1P1是可以同时执是可以同时执行的。行的。I1I1、C1C1、P1P1的执行必的执行必须严格按照须严格按照I1I1，C1C1，P1P1的的顺序。顺序。I1I1、I2I2、I3I3、I4I4轮流使用同一输入设备。轮流使用同一输入设备。时间时间资源资源若干个程序段同时在系统中运行，这些程序的若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。是很小的，也称这几个程序段是并发执行的。PQR并发执行区优点：优点：注意有限制规则：注意有限制规则：同一同一作业作业的处理步骤的执行必须严格按照规定的处理步骤的执行必须严格按照规定的的顺序顺序；同一独占资源上同一独占资源上的不同的不同作业的处理步骤作业的处理步骤不不能同时能同时执行。执行。假设有一个程假设有一个程序由序由S0S0Sn+1Sn+1个个语句，先顺序执语句，先顺序执行行S0S0，然后并发，然后并发执行执行 S1S1SnSn语句，语句，最 后 顺 序 执 行最 后 顺 序 执 行Sn+1 Sn+1。一、失去了程序的一、失去了程序的封闭性封闭性程序程序A程序程序Bn:=0;打印打印nn:=n+1;K1K2S如果程序执行如果程序执行的结果是一个与时的结果是一个与时间无关的函数，即间无关的函数，即具有具有封闭性封闭性。程序程序B打印打印0程序程序B打印打印1程序并发执行的特点程序并发执行的特点二、程序与计算不再一一对应二、程序与计算不再一一对应在程序顺序执行时，一个程序总是对应在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用户环境下，可能同时有多个用户调用C C语言语言的编译程序，这就是典型的一个程序对应多的编译程序，这就是典型的一个程序对应多个用户源程序的情况。个用户源程序的情况。程序并发执行的特点程序并发执行的特点程序与计算不再一一对应示例程序与计算不再一一对应示例程序程序A程序程序BCall CCall C程序程序C程序程序A和和B在执行过程中都调用了程序在执行过程中都调用了程序C 程序并发执行的特点程序并发执行的特点三、程序并发执行可以相互制约三、程序并发执行可以相互制约在多道程序设计的环境下，程序是并发在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在执行的。即系统中有多道程序在“同时同时”执执行，这些程序之间要共享系统的资源，程序行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。互制约，有直接的，也有间接。注意区别注意区别不能同时不能同时与与有先后次序有先后次序两种制两种制约。约。程序并发执行的特点程序并发执行的特点程序并发执行的相互制约示例程序并发执行的相互制约示例并发活动并发活动进程的引人进程的引人l操作系统的特性之一是并发与共享，即在系统中操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。运行程序之间的通信、程序之间的合作与协同等符。l要解决这些问题，用程序的概念已经不能描述程序要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程在内存中运行的状态，必须引人新的概念进程。进程的定义进程的定义l行为的一个规则叫做程序，程序在处理机上执行时行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程所发生的活动称为进程（DijkstraDijkstra)。l进程是这样的计算部分，它是可以和其它计算并行进程是这样的计算部分，它是可以和其它计算并行的一个计算。的一个计算。(Donovan)(Donovan)l进程（有时称为任务）是一个程序与其数据一道通进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（过处理机的执行所发生的活动。（Alan.C.Shaw)Alan.C.Shaw)l进程是执行中的程序。（进程是执行中的程序。（Ken Thompson and Ken Thompson and Dennis Ritchie)Dennis Ritchie)l进程，即是程序在并发环境中的执行过程进程，即是程序在并发环境中的执行过程 。进程与程序的区别（进程与程序的区别（1 1）进程与程序的区别（进程与程序的区别（2 2）进程与程序的区别示例进程与程序的区别示例例子：例子：光盘（CD、VCD、DVD）光盘（程序）-放光盘的活动（进程）理解进程概念理解进程概念l进程的运行状态及其变迁进程的运行状态及其变迁l进程的组成进程的组成l进程映像进程映像l进程环境进程环境进程的运行状态及其变迁进程的运行状态及其变迁l进程在系统中的活动规律是：进程在系统中的活动规律是：执行执行-暂停暂停-执行执行l进程的运行状态反映进程的动态性。进程的运行状态反映进程的动态性。l进程的三种基本状态：进程的三种基本状态：l 运行状态运行状态l 就绪状态就绪状态l 封锁状态（又称不可运行、挂起）封锁状态（又称不可运行、挂起）进程的三种基本状态进程的三种基本状态l运行状态运行状态 ：进程得到：进程得到CPUCPU控制权，它的程序控制权，它的程序正在运行。（在系统中，总只有一个进程处正在运行。（在系统中，总只有一个进程处于此状态于此状态）l就绪状态就绪状态：已经准备就绪，一旦得到已经准备就绪，一旦得到CPUCPU，就立即可以运行。（有多个进程处于此状态）就立即可以运行。（有多个进程处于此状态）l封锁状态封锁状态：正在等待某个事件的发生（如等正在等待某个事件的发生（如等待待I/OI/O的完成），而暂停执行，这时，即使给的完成），而暂停执行，这时，即使给它它CPUCPU时间，它也无法执行。时间，它也无法执行。就绪就绪运行运行挂起挂起？基本内容的确定基本内容的确定?ab-1pcb1N个个pcb2pcbiPcb-addr?空间大小空间大小?UNIX的进程映像的进程映像l进程状态进程状态l变迁关系变迁关系l进程映像：进程映像：PCB的实现、核心栈与的实现、核心栈与用户栈（图用户栈（图2-10 UNIX进程映像结进程映像结构构）进程环境进程环境l用户级环境用户级环境l寄存器环境寄存器环境l系统级环境系统级环境临界资源和临界区临界资源和临界区信号量信号量P、V操作操作临界资源和临界区临界资源和临界区信号量信号量P、V操作操作?临界资源和临界区临界资源和临界区信号量信号量P、V操作操作P：申请一个单位资源（：申请一个单位资源（P47）V：释放一个单位资源（：释放一个单位资源（P47）P(s):若若S=0，继续，继续取取s值减值减1V(s):若若S0，继续，继续取取s值加值加1例：打印机分配例：打印机分配互斥信号量互斥信号量mutex（初值为（初值为1）Pa为分配进程为分配进程Pb为释放进程为释放进程例：供者和用者对单缓冲区的同步例：供者和用者对单缓冲区的同步信号量：信号量：S1缓冲区空否（初值为缓冲区空否（初值为1）S2缓冲区满否（初值为缓冲区满否（初值为0）设上例中缓冲区容量为设上例中缓冲区容量为n，分析信，分析信号灯的设置与状态变化范围（生产号灯的设置与状态变化范围（生产者者-消费者问题消费者问题P49）其它进程通信方式其它进程通信方式l信号量集方式信号量集方式l管程管程l消息缓冲通信消息缓冲通信UNIX中的进程通信中的进程通信lSleep 和和wakeupl进程跟踪进程跟踪lS_5的的ipc:消息机制，共享内存，信号量。消息机制，共享内存，信号量。处理机的二级调度处理机的二级调度宏观作业调度：算法复杂、间隔长、宏观环境宏观作业调度：算法复杂、间隔长、宏观环境微观进程调度：算法简单、调度频繁、微观状态微观进程调度：算法简单、调度频繁、微观状态作业调度作业调度作业调度的主要任务是完成作业从后备状态到执行状作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。态和从执行状态到完成状态的转变。作业调度功能：作业调度功能：l记录已进入系统的各作业的情况（记录已进入系统的各作业的情况（JCBJCB，Job Job Control BlockControl Block）；）；l按一定的调度算法，从后备作业中选择一个按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；或几个作业进入系统内存；l为被选中的作业创建进程，并且为其申请系为被选中的作业创建进程，并且为其申请系统资源；统资源；l作业加束后作善后处理工作。作业加束后作善后处理工作。作业控制块（JCB）每个作业进入系统时由系统为其建立一个每个作业进入系统时由系统为其建立一个作业作业控制块控制块JCBJCB（Job Control Block)Job Control Block)，它是存放作业控制和，它是存放作业控制和管理信息的数据结构，主要信息见下图。管理信息的数据结构，主要信息见下图。调度性能的衡量调度性能的衡量 作业调度算法规定了从后备作业中选择作业作业调度算法规定了从后备作业中选择作业进入系统内存的原则，这些原则的性能如何，就是进入系统内存的原则，这些原则的性能如何，就是本节所讨论的问题。本节所讨论的问题。确定调度算法时应考虑的因素l应与系统的整体设计目标一致l考虑系统中各种资源的负载均匀l保证作业的执行l对一些专用资源的使用特性的考虑调度性能的衡量调度性能的衡量调度性能的衡量调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间作业的周转时间：ti=tci-tsiti:作业周转时间tci：作业完成时间tsi:作业提交时间调度性能的衡量调度性能的衡量先来先服务调度先来先服务调度算法和短作业优先调度算法算法和短作业优先调度算法进程调度进程调度调度调度/分派结构分派结构l处理机分配由调度和分派两个功能组成。处理机分配由调度和分派两个功能组成。l调度：组织和维护就绪进程队列。包括确定调度：组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程调度算法、按调度算法组织和维护就绪进程队列。队列。l分派：是指当处理机空闲时，从就绪队列队分派：是指当处理机空闲时，从就绪队列队首中移一个首中移一个PCBPCB，并将该进程投入运行。，并将该进程投入运行。pcb1schedulersuspwakeupreceivepcb2pcb3pcb4dispatchercpuReady-qpcb5pcb2schedulersuspwakeupreceivepcb5pcb3pcb4dispatchercpu分开分开Ready-qpcb1进程调度功能进程调度功能l保护现场保护现场l入就绪队列算法实现入就绪队列算法实现l处理机分派处理机分派l恢复现场恢复现场进程调度的功能进程调度的功能记录和保持系统中所有进程的有关情况和状态记录和保持系统中所有进程的有关情况和状态特征特征 有关进程调度的信息是记录在PCB中的，在进程调度中用到的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。进程调度的功能进程调度的功能决定分配（处理机）策略决定分配（处理机）策略确定进程调度的策略，例如，先来先服务、优先数调度策略，调度策略的不同，组织就绪进程队列的方式也不同。先来先服务调度策略，就绪队列要按等待时间大到小的顺序排队；优先数调度，则就绪进程队列要按优先数的升疗（或降序）的方式排队。等等。进程调度的功能进程调度的功能实施处理机的分配实施处理机的分配总而言之，进程调度包括：l调度算法的选择（调度算法）l调度时机的选择（调度时机）l实施进程调度（调度程序）进程调度的功能进程调度的功能调度时机（调度时机（UNIXUNIX系统中）：系统中）：（1）进程自动放弃处理机：l当进程进入高低优先级睡眠状态时 （在sleep()程序中）；l在进程进入暂停状态时（在stop()程序中）；l进程进入僵死状态时 （在exit()程序中）；进程调度的功能进程调度的功能在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。（2 2）强迫调度）强迫调度进程调度的功能进程调度的功能实施进程调度的程序称为进程调度程序（或称调度程序），在通常的操作系统原理中，该程序属于系统进程的执行程序，有的操作系统是把进程调度程序作一个特别的处理，如早期的操作系统中把进程调度程序称为交通控制程序，不属于系统中的任何进程。在UNIX系统中，进程调度程序swtch()分属个不同的进程，即调用swtch()的进程、让出处理机的进程、0进程、被调度到的进程。进程优先数调度算法进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。进程优先数调度算法进程优先数调度算法静态：进程的优先数在进程创建时确定后就不再变化确定进程优先数：系统确定：（运行时间、使用资源，进程的类型）用户确定：（紧迫程度，计费与进程优先数有关）系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）进程优先数调度算法进程优先数调度算法动态进程优先数：动态进程优先数：系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。循环轮转调度循环轮转调度 循环轮转调度实际上是一种先来先服务算法循环轮转调度实际上是一种先来先服务算法的调度算法，它把系统的响应时间分成大小相等的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程被调度到后，占用一个时间片，片用完后，该进程让出让出CPUCPU，由运行状态转换成就绪状态，排在就绪，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。队列的队尾。多个进程循环轮转。循环轮转调度循环轮转调度循环轮转调度循环轮转调度 系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。评价：l优点是实现简单、系统开销小l缺点是不灵活，当系统中进程较少时，系统开销变大。为什么？l由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。循环轮转调度循环轮转调度可变时间片轮转调度可变时间片轮转调度 为了克服前种调度算法的缺点，人们设计出一种可变时间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。调度用的进程状态变迁图调度用的进程状态变迁图 在这个图中新创建的进程进入低优就绪状态，在这个图中新创建的进程进入低优就绪状态，一个运行进程因时间片到（实际上是计算量大的进一个运行进程因时间片到（实际上是计算量大的进程）而转换成低优就绪；进程因等待程）而转换成低优就绪；进程因等待I/OI/O完成而转完成而转换高优就绪换高优就绪.调度用的进程状态变迁图调度用的进程状态变迁图l调度程序首先看高优就绪进程队列是否为空，若不为空，则从高优就绪进程中选择一个进程占用CPU，否则，从低优就绪队列中选择。这种调度效果能充分地利用系统资源。为什么？lUNIX系统的进程调度状态变迁图，与前一种调度变迁图有着异曲同功的效果。中就绪中就绪运行运行等待等待1低就绪低就绪高就绪高就绪等待等待2UNIX中的进程调度中的进程调度l进程调度：调度时机，调度算法进程调度：调度时机，调度算法lShell工作原理工作原理l系统初启系统初启UNIXUNIX系统的进程调度系统的进程调度UNIXUNIX调度算法调度算法l我们从调度算法、调度时机、调度程序三个方面来我们从调度算法、调度时机、调度程序三个方面来分析分析UNIXUNIX系统的进程调度。系统的进程调度。调度算法l UNIX系统采用优先数调度算法，每个进程有一个进程优先数，p_pri是proc结构中的一个变量，其取值范围是127127，其值越小，进程的优先级越高（即，调度程序总是从就绪状态的进程中选择一个优先数最小的进程占用CPU）。UNIXUNIX调度算法调度算法优先数的确定：优先数的确定：系统设置在进程进入睡眠状态时，在SLEEP（）中设置将要进入睡眠状态进程的优先数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。UNIXUNIX调度算法调度算法l进程进入高优先级睡眠的原因：进程进入高优先级睡眠的原因：（1）0进程（100优先数）；（2）因资源请求得不到满足的进程，磁盘（80），打印机 （20），；（3）等待块设备I/O完成的进程，（50）。l进程进入低优先级睡眠的原因：进程进入低优先级睡眠的原因：(1）因等待字符设备I/O完成的进程，（020的优先数）；(2)所有处于用户态运行进程，优先数一般情况下为大于100。l这样做的目的是为什么？这样做的目的是为什么？为使系统资源得到充分的利用，换句话说，是为了提高系统资源的使用效率。UNIXUNIX调度算法调度算法l优先数的计算优先数的计算计算公式：p_pri=127,(p_cpu/16+p_nice+PUSER)其中：p_cpu 进程占用CPU的程度 p_nice 用户通过系统调用nice(priority)设置 的进程优先数。PUSER 常数，其值为100UNIXUNIX调度算法调度算法UNIXUNIX调度算法调度算法 UNIX UNIX系统的设计者采用了一个巧妙的方法，系统的设计者采用了一个巧妙的方法，既避免了繁杂的统计工作，也不需做浮点运行算。既避免了繁杂的统计工作，也不需做浮点运行算。（这就是我们要学习的工程能力，或称分析问题和（这就是我们要学习的工程能力，或称分析问题和解决问题的能力，学会和记往一两个科学的定理和解决问题的能力，学会和记往一两个科学的定理和公式并不难，难的是怎样将这些普遍的理论用于实公式并不难，难的是怎样将这些普遍的理论用于实际的工程之中，际的工程之中，UNIXUNIX系统中有很多值得我们学习的系统中有很多值得我们学习的地方，对地方，对p_cpup_cpu的处理就是其中之一，这里并不要的处理就是其中之一，这里并不要求把求把UNIXUNIX中的中的p_cpup_cpu的处理完全记住，而是要通过的处理完全记住，而是要通过对它的了解，学会处理实际工程问题的方法。）对它的了解，学会处理实际工程问题的方法。）UNIXUNIX调度算法调度算法UINXUINX系统中对系统中对p_cpup_cpu的处理：的处理：每个时钟中断：p_cpu+;每秒钟（时钟中断）：if(p_cpu-SCHMAG PUSER现运行进程在自陷处理程序trap()末尾重新计算本进程的优先数.目的:调用nice()设置的本进程的优先数p_nice的改变反映到p_pri中去；现运行进程在执行时钟中断处理程序时，若发现中断前为用户态，则每隔1秒钟重新计算本进程的优先数。因为现运行进程已经占用了一些CPU的时间，要反映到p_pri中去。UNIXUNIX调度算法调度算法l这三种重新计算（调整）进程优先数都没有修改由这三种重新计算（调整）进程优先数都没有修改由系统设置的进程优先数，从而保证了处于核心态的系统设置的进程优先数，从而保证了处于核心态的进程能尽快地得到进程能尽快地得到CPUCPU，使得系统资源（设备）能，使得系统资源（设备）能得到充分地利用，提高了系统资源的使用效率，而得到充分地利用，提高了系统资源的使用效率，而计算进程的优先数又使得系统中所有处于用户态的计算进程的优先数又使得系统中所有处于用户态的进程能较均衡地占用进程能较均衡地占用CPUCPU，保证了各用户终端的响，保证了各用户终端的响应时间，实现了分时操作系统的特性。应时间，实现了分时操作系统的特性。UNIXUNIX调度时机调度时机调度时机（调度时机（UNIXUNIX系统中）：系统中）：1）进程自动放弃处理机l在进程进入高低优先级睡眠状态时（在sleep()程序中）；l在进程进入暂停状态时（在stop()程序中）；l进程进入僵死状态时（在exit()程序中）；2）强迫调度l在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。UNIXUNIX调度调度时机时机Runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。UNIXUNIX系统调度程序系统调度程序UNIXUNIX系统中的进程调度程序是系统中的进程调度程序是swtchswtch，所以，所以，在绝大多数关于在绝大多数关于UNIXUNIX系统的文献中称为进程系统的文献中称为进程切换程序。切换程序。UNIXUNIX调度程序调度程序UNIXUNIX调度程序调度程序lUNIXUNIX系统的进程调度程序有以下特点：系统的进程调度程序有以下特点：1.swtch()程序分属三个不同的进程：l调用它的程序（即将让出处理机的进程）l0号进程l被选中的进程2.调度程序中属于0号进程的那段程序是在0号进程处于睡眠状态下执行的，这一点非常特别，在操作系统中，仅此一例。等待队列头指针等待队列头指针可利用资源队列头指针可利用资源队列头指针资源分配程序入口地址资源分配程序入口地址ribpcb1rd1所有所有rd在同一队列？在同一队列？独占独占微观独占，宏观共享微观独占，宏观共享l概念概念存储器lstorage,memoryl能接收数据和保存数据、而且能根据命令提供这些数据的装置。概念概念l存储器分成两类：存储器分成两类：内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。存储器的层次结构存储器的层次结构存储系统设计三个问题：容量、速度和成本容量：需求无止境速度：能匹配处理器的速度成本问题：成本和其它部件相比应在合适范围之内容量、速度和成本 三个目标不可能同时达到最优，要作权衡 存取速度快，每比特价格高 容量大，每比特价格越低，同时存取速度也越慢解决方案：采用层次化的存储体系结构 当沿着层次下降时 每比特的价格将下降，容量将增大 速度将变慢，处理器的访问频率也将下降层次化的存储体系结构层次化的存储体系结构存储访问局部性原理存储访问局部性原理提高存储系统效能关键点：程序存储访问局部性原理 程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相同的指令集合 对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域处理器主要和存储器的局部打交道,在经过一段时间以后，使用的代码和数据集合会改变概念概念l程序的逻辑结构程序的逻辑结构程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。codedataheapstack程序2虚地址空间data2stack1code1heap1code2stack2data1heap2OS codeOS dataOS heap&stacks程序 1虚地址空间codedataheapstack内存内存地址转换地址转换 01005007005000510055005700.静态地址映射l 静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的。l 在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如左图所示。评价:l优点是实现简单，不要硬件的支持。l缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。静态地址映射静态地址映射 动态地址映射动态地址映射l 动态地址映射是由硬件地执行时完成的，程序动态地址映射是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省中不执行的程序就不做地址映射的工作，这样节省了了CPUCPU的时间的时间 。重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。动态地址映射动态地址映射动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。l 系统中设置了重定位寄存器。内存分配内存分配l 在多道程序设计的环境中，内存分配的功能包括：制定在多道程序设计的环境中，内存分配的功能包括：制定分配策略、构造分配用的数据结构、响应系统的内存分配分配策略、构造分配用的数据结构、响应系统的内存分配的请求和回收系统释放的内存区。内存管理策略有三种：的请求和回收系统释放的内存区。内存管理策略有三种：放置策略 决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；调入策略 决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调；淘汰策略 当内存不足时，决定将某些信息调出内存的策略。存储保护存储保护l两种存储保护技术的区别两种存储保护技术的区别1、寄存器的设置不同；2、判别式中用的判别条件不同上下界寄存器保护法用的是物理地址基址、限长寄存器保护法用的是程序的逻辑地址对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。多道程序对换技术多道程序对换技术l以用户为单位独占内存以用户为单位独占内存l如何减少对换信息量？如何减少对换信息量？l部分换出与恢复部分换出与恢复提供虚存提供虚存l问题的提出问题的提出物理存储器的结构是个一维的线性空间，容量是有限的。用户程序结构：l一维空间 一个用户程序就是一个程序，并且程序和数据是不分离的；l二维空间 程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的；ln维空间 即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。提供虚存提供虚存l如何将与物理内存结构不同，且大于物理内存容量如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。的原因，或称为虚拟存储技术发展的原动力。提供虚存提供虚存虚拟存储器l 为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。l 它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。l 现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。l 虚拟存储器需要大容量的外存储器的支持，或称物资基础。页式存储管理页式存储管理l页式系统应解决的问题页式系统应解决的问题分区存储管理的主要问题是碎片问题。l在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。l造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。分页的概念分页的概念l程序地址空间分成大小相等的页面，同时把内存也程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是存时，以页面为单位进行分配。页面的大小是为为2 2n n,通常为通常为1KB1KB，2KB2KB，nKBnKB等。等。页式地址变换页式地址变换l虚地址结构虚地址结构(程序字程序字)虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。假定页面大小1024字节，虚地址共占用2个字节(16位)页号 页内地址（位移量）P W 15 10 9 0页式地址变换页式地址变换-虚地址结构虚地址结构页式地址变换页式地址变换页式地址变换页式地址变换l页式地址映射页式地址映射虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出l将虚地址转换成二进制的数；l按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；l根据题意产生页表；l将位移量直接复制到内存地址寄存器的低位部分；l以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。页式地址变换页式地址变换l页式地址映射页式地址映射虚地址以十进制数给出l 页号虚地址页大小l 位移量虚地址 mod 页大小l 根据题意产生页表；l 以页号查页表，得到对应页装入内存的块号l 内存地址块号页大小位移量请调策略请调策略l问题的提出问题的提出在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。请调策略请调策略l请求分页概念请求分页概念 请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。分分 页页缺页中断处理：请调缺页中断处理：请调为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。l中断位：0 表示该页在内存，1示该页不在内存l引用位：0 表示最近没有进程访问，1示最近有进程访问l修改位：0 该页调入内存后没有修改，1页调入内存后修改过缺页中断处理的硬件支持缺页中断处理的硬件支持l采用相应技术加快页表的查询速度采用相应技术加快页表的查询速度 在页式存储技术中，我们可看到每访问一次内存，就要做两次访问内存的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。在早期的计算机系统中有的采用联想存储器的技术来加快查表的速度，有的采用寄存器做页表。缺页中断处理的硬件支持缺页中断处理的硬件支持l采用联想存储器加快页表的查询速度采用联想存储器加快页表的查询速度快表。使用快表的并行查找过程。程序局部化与命中率问题。缺页中断处理过程缺页中断处理过程l分地址分地址l取页号取页号l查页表查页表l缺页中断缺页中断l找空闲块找空闲块l淘汰块淘汰块l读入页面读入页面l中断返回中断返回硬件硬件软件软件请求分页的性能分析请求分页的性能分析l有效存取时间有效存取时间l缺页中断处理时间缺页中断处理时间l有效存取时间正比于缺页的比率有效存取时间正比于缺页的比率l为使速度下降控制在为使速度下降控制在10%以内，缺页率不得超过以内，缺页率不得超过0.00001淘汰策略淘汰策略物理页分配算法置换算法l当要索取一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。颠簸、抖动几种置换算法几种置换算法l先进先出算法先进先出算法先进入内存的页，先退出内存。实质上是淘汰在内存驻留时间最长的页。其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。这种算法简单，实现容易。几种置换算法几种置换算法l最佳算法最佳算法假定程序p共有n页，而系统分配给它的内存只有m块（1mn），并且以作业在执行的过程中页面置换的频率的高低来衡量算法的优劣。访问的页在内存，称访问成功，否则为失败。a=s+f a:访问的总次数 s：访问成功的次数 f：访问失败的次数几种置换算法几种置换算法缺页中断率f=f/a 则有：f f(r,m,p）最佳算法是指对于任何m和p，r:调度算法 有ff(r,m,p）最小。最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。几种置换算法几种置换算法l最久未使用淘汰算法最久未使用淘汰算法（lRUlRU算法）算法）当需要淘汰一页时，选择最长时间未使用的页。如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。算法的实现（硬件）：计数器近似LRU算法：NUR物理页分配算法物理页分配算法l最少块数最少块数指令系统设计决定最少块数指令系统设计决定最少块数l全局分配与局部分配全局分配与局部分配l等分法与比例分配等分法与比例分配法法工作集模型工作集模型l时间局部化与空间局部化时间局部化与空间局部化l工作集工作集lDM，将出现抖动，将出现抖动l工作集模型的实现工作集模型的实现页式系统的存储保护页式系统的存储保护页式系统的存储保护的方法类似于基址限长存储保护，当地址映射机构分离出页号和页内位移后。若0页号用户程序的总页数，则访问合法，否则访问越界。页式系统的存储保护还包括存取控制。在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。UNIX S_5的存储管理的存储管理l采用请求分页存储管理和对换技术采用请求分页存储管理和对换技术l对换：对换：map表表l每次对换尽可能多的数据，不使用缓冲。每次对换尽可能多的数据，不使用缓冲。l请求分页数据结构请求分页数据结构l淘汰进程淘汰进程l缺页处理缺页处理段式系统段式系统l 一个用户程序往往由几个程序段（主程序、子一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。进行分配，每个段的大小是不相等的。程序地址的组成：S：W例:lS1：XXXXlS2：XXXXlS3；XXXX段式系统段式系统段式系统段式系统l 以分区方式使用内存空间以分区方式使用内存空间l支持虚拟存储：分段调入支持虚拟存储：分段调入l快表的使用快表的使用l动态连接技术动态连接技术l缺段中断与连接中断缺段中断与连接中断 l段式保护与共享段式保护与共享l段式虚拟存储的优点和缺点段式虚拟存储的优点和缺点 段页式系统段页式系统在段式系统中，若段内分页，称为段页式系统。在段式系统中，若段内分页，称为段页式系统。段页式地址：段页式地址：s p ds p d段页式地址转换：查段表段页式地址转换：查段表 查页表查页表 合地址合地址快表的使用快表的使用段页式系统是目前最好的内存管理方法段页式系统是目前最好的内存管理方法试分析段页式系统的优点与缺点试分析段页式系统的优点与缺点段页式系统段页式系统目前流行的目前流行的UNIXUNIX系统采用这种存储管理的方式，一系统采用这种存储管理的方式，一个进程的图象分为个进程的图象分为U U区、共享正文区、用户栈区和区、共享正文区、用户栈区和数据区，各进程的各个区的大小是不相等的，只有数据区，各进程的各个区的大小是不相等的，只有U U区的大小是相等的。这里的区类似于段。每个段区的大小是相等的。这里的区类似于段。每个段又分成大小相等的页，内存的分配是以页为单位的。又分成大小相等的页，内存的分配是以页为单位的。因此，在因此，在UNIXUNIX系统中存储管理（上下文，系统中存储管理（上下文，contextcontext）机构包括区表和页表。机构包括区表和页表。