演示文稿操作系统原理

（优选）操作系统原理目前一页\总数二百三十一页\编于二点1、《操作系统原理》教材2、《操作系统原理实验大纲》指导教材3、《操作系统课件》多媒体教案

课程使用的媒体目前二页\总数二百三十一页\编于二点一、操作系统的有关概念二、进程管理三、存储器管理目前三页\总数二百三十一页\编于二点计算机发展简史操作系统的发展过程目前四页\总数二百三十一页\编于二点计算机发展简史

按硬件发展划分为四代。目前五页\总数二百三十一页\编于二点对计算规律的模拟存储程序式计算机目前六页\总数二百三十一页\编于二点存储程序式计算机模型存储程序式计算机模型的基本方案是，如要使计算机能够自动地计算，必须有一个存储器用来存储程序和数据；同时要有一个运算器，用以执行指定的操作；有一个控制器，以便实现自动操作；另外，辅以输入/输出部件，以便输入原始数据和输出计算结果。于是形成了现代计算机的基本组成形式。如图1.1所示。目前七页\总数二百三十一页\编于二点图1.1存储程序计算机的组成目前八页\总数二百三十一页\编于二点操作系统的发展过程

按技术发展与分支划分类别目前九页\总数二百三十一页\编于二点操作系统的类型

早期批处理 执行系统 多道成批系统 分时、实时系统、个人机系统 多处理机、分布式系统目前十页\总数二百三十一页\编于二点无操作系统的计算机从第一代计算机诞生到20世纪50年代中期还未出现操作系统，这时的计算机采用人工操作方式。其过程是：

图1.2手工操作计算机目前十一页\总数二百三十一页\编于二点单道批处理系统与多道批处理系统及执行系统所谓批处理系统是指加载在计算机上的一个系统软件，在它的控制下，计算机能够自动地成批地处理一个或多个用户的作业。首先出现的是联机批处理系统。如下图所示。目前十二页\总数二百三十一页\编于二点脱离主机控制的输入/输出批处理系统

在外设处理数据时，主机处理“忙等”状态，这样高速的主机与慢速的外设矛盾就显现出来。为了克服与缓解主机与外设的矛盾。我们引入脱机批处理系统，即脱离主机控制的输入/输出批处理系统。如图1.4所示。目前十三页\总数二百三十一页\编于二点图1.4脱机批处理系统目前十四页\总数二百三十一页\编于二点在单道批处理系统中，内存中仅有一道作业，中断和通道技术出现以后，虽然可以实现输入/输出设备与中央处理机并行操作，但由于属于同一道作业的可并发执行的进程不多，大多数进程是有同步关系的，这使系统中仍有较多的空闲资源，致使系统的性能较差。为了进一步提高资源的利用率和系统对作业的吞吐量，在60年代中期，引入了多道程序设计技术，由此而形成了多道批处理系统。单道程序与多道程序的执行过程如图1.5和图1.6所示。

目前十五页\总数二百三十一页\编于二点目前十六页\总数二百三十一页\编于二点在操作系统中引入多道程序设计技术以后，会使系统具有以下特征。（1）多道性

（2）无序性

（3）宏观上并行、微观上串行

（4）调度性

目前十七页\总数二百三十一页\编于二点分时系统分时技术是把处理机的时间分成很短的时间片，这些时间片轮流地分配给各个联机的各作业使用。如果某作业在分配给它的时间片用完时仍未完成，则该作业就暂时中断，等待下一轮运行，并把处理机的控制权让给另一个作业使用。这样在一个相对较短的时间间隔内，每个用户作业都能得到快速响应，以实现人机交互。目前十八页\总数二百三十一页\编于二点分时系统与多道批处理系统相比，具有完全不同的特征，由上所述可以归纳成以下几点：（1）多路性

（2）独立性

（3）及时性

（4）交互性

目前十九页\总数二百三十一页\编于二点什么是操作系统操作系统的性质目前二十页\总数二百三十一页\编于二点

操作系统是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的系统软件(或程序集合),是用户与计算机之间的接口。目前二十一页\总数二百三十一页\编于二点以下软件哪些是操作系统?UNIXWordDOSVBOfficeFoxProWindows98WindowsNTLinuxPowerPoint以下软件是操作系统：

UNIXDOSLinuxWindows98WindowsNT目前二十二页\总数二百三十一页\编于二点设置OS的目的扩充机器功能，方便用户使用。提高系统效率。目前二十三页\总数二百三十一页\编于二点操作系统的共同性质目前二十四页\总数二百三十一页\编于二点1、从功能上看

具有五大功能----存储器管理、处理机管理、设备管理、文件管理、用户接口目前二十五页\总数二百三十一页\编于二点2、从层次上看

是裸机之上的第一层软件,为其他软件的建立和运行提供基础。目前二十六页\总数二百三十一页\编于二点

裸机操作系统其他软件...用户1。4节目前二十七页\总数二百三十一页\编于二点3、从服务上看

提供众多基础服务,方便用户使用,构成软件平台。目前二十八页\总数二百三十一页\编于二点4、从内部特征上看---支持并发性---实现资源共享---完成进程的异步前进目前二十九页\总数二百三十一页\编于二点以多道成批系统为例并发共享不确定性目前三十页\总数二百三十一页\编于二点1.3OS的服务功能程序执行I/O操作文件系统管理出错检测资源分配统计保护目前三十一页\总数二百三十一页\编于二点一系统调用是应用程序与OS的接口进程或作业控制：实现进程或作业的所有活动文件管理和设备管理信息维护：用户与系统交互信息目前三十二页\总数二百三十一页\编于二点二系统程序文件管理状态信息文件修改程序设计语言支持程序装入与执行工具性软件命令解释程序的实现方法目前三十三页\总数二百三十一页\编于二点1.5操作系统逻辑结构设计

分层实现的软件设计方法目前三十四页\总数二百三十一页\编于二点1.5操作系统逻辑结构设计单块结构层次结构:分层实现的软件设计方法.虚拟机客户/服务器模型:再用户进程方式下实现系统的多数功能;核心只负责客户与服务器的通信;适用于分布式系统;注意对关键基础服务的处理.目前三十五页\总数二百三十一页\编于二点1。8UNIX系统的特点和结构UNIX的主要特点UNIX系统结构UNIX系统核心结构目前三十六页\总数二百三十一页\编于二点一、操作系统的有关概念二、进程管理三、存储器管理目前三十七页\总数二百三十一页\编于二点进程概念目前三十八页\总数二百三十一页\编于二点程序的顺序执行

与并发执行目前三十九页\总数二百三十一页\编于二点

程序的顺序执行

概念 一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。 例如：目前四十页\总数二百三十一页\编于二点程序顺序执行的特点1顺序性

处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2封闭性 程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。

目前四十一页\总数二百三十一页\编于二点程序顺序执行的特点（续）3可再现性 程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。

O=f(I),f是与时间无关的函数目前四十二页\总数二百三十一页\编于二点

程序的并发执行例： 在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,3,...,n)。 这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。目前四十三页\总数二百三十一页\编于二点

程序的并发执行

例如：P1与I2，C1与I2,I3与P1是可以同时执行的。 I1、C1、P1的执行必须严格按照I1，C1，P1的顺序。 I1、I2、I3、I4轮流使用同一输入设备。时间资源目前四十四页\总数二百三十一页\编于二点程序的并发执行定义

若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。目前四十五页\总数二百三十一页\编于二点

程序的并发执行分析

优点：程序的并发执行提高了资源的利用率。

注意有限制规则： 同一作业的处理步骤的执行必须严格按照规定的顺序； 同一独占资源上的不同作业的处理步骤不能同时执行。目前四十六页\总数二百三十一页\编于二点程序的顺序执行与并发执行

假设有一个程序由S0～Sn+1个语句，先顺序执行S0，然后并发执行S1～Sn语句，最后顺序执行Sn+1。目前四十七页\总数二百三十一页\编于二点程序并发执行的特点一、失去了程序的封闭性 程序A程序Bn:=0;……………打印nn:=n+1;K1K2S

如果程序执行的结果是一个与时间无关的函数，即具有封闭性。程序B打印0程序B打印1目前四十八页\总数二百三十一页\编于二点

程序并发执行的特点二、程序与计算不再一一对应

在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。目前四十九页\总数二百三十一页\编于二点

程序并发执行的特点程序与计算不再一一对应示例

程序A程序B……CallC……CallC程序C…程序A和B在执行过程中都调用了程序C目前五十页\总数二百三十一页\编于二点

程序并发执行的特点三、程序并发执行可以相互制约

在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。 注意区别不能同时与有先后次序两种制约。 目前五十一页\总数二百三十一页\编于二点

程序并发执行的特点程序并发执行的相互制约示例

目前五十二页\总数二百三十一页\编于二点并发活动——进程的引人操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念－－进程。目前五十三页\总数二百三十一页\编于二点进程的定义行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)进程，即是程序在并发环境中的执行过程。目前五十四页\总数二百三十一页\编于二点进程与程序的区别（1）进程是动态概念；程序是静态概念进程具有并发性，宏观上同时运行；程序本身具有顺序性，程序的并发执行是通过进程实现的进程具有独立性，是一个能独立运行的单位，是系统资源分配的基本单位，是运行调度的基本单位；程序本身没有此特性目前五十五页\总数二百三十一页\编于二点进程与程序的区别（2）进程和程序无一一对应关系，一个进程可顺序执行多个程序；一个程序可由多个进程共用进程异步前进，会相互制约；程序不具备此特性进程实体具有一定结构，组成进程映象；程序没有这种结构目前五十六页\总数二百三十一页\编于二点进程与程序的区别示例例子： 光盘（CD、VCD、DVD）光盘（程序）-放光盘的活动（进程）目前五十七页\总数二百三十一页\编于二点理解进程概念进程的运行状态及其变迁进程的组成进程映像进程环境目前五十八页\总数二百三十一页\编于二点进程的运行状态及其变迁进程在系统中的活动规律是： 执行-暂停-执行进程的运行状态反映进程的动态性。进程的三种基本状态：运行状态就绪状态封锁状态（又称不可运行、挂起）目前五十九页\总数二百三十一页\编于二点进程的三种基本状态运行状态：进程得到CPU控制权，它的程序正在运行。（在系统中，总只有一个进程处于此状态）就绪状态：已经准备就绪，一旦得到CPU，就立即可以运行。（有多个进程处于此状态）封锁状态：正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行。目前六十页\总数二百三十一页\编于二点进程的状态变化就绪运行挂起？？目前六十一页\总数二百三十一页\编于二点PCB程序数据集合进程的组成基本内容的确定?目前六十二页\总数二百三十一页\编于二点进程与PCB的关系每个进程有唯一的PCB系统中所有进程都有自己的PCB操作系统依据PCB管理进程目前六十三页\总数二百三十一页\编于二点进程与PCB的关系操作系统利用PCB实现进程的动态和并发PCB是进程存在的唯一标志目前六十四页\总数二百三十一页\编于二点Pcb表组织a…b…-1…pcb1N个pcb2…………pcbiPcb-addr?空间大小??目前六十五页\总数二百三十一页\编于二点UNIX的进程映像进程状态变迁关系进程映像：PCB的实现、核心栈与用户栈（图2-10UNIX进程映像结构）目前六十六页\总数二百三十一页\编于二点进程环境用户级环境寄存器环境系统级环境目前六十七页\总数二百三十一页\编于二点1、进程与程序的区别2、进程的组成3、进程的同步与互斥目前六十八页\总数二百三十一页\编于二点进程控制原语Fork()Wait(stat_addr)Exitexec目前六十九页\总数二百三十一页\编于二点进程在活动中会相互制约所有进程都是相互独立的进程以异步方式并发执行目前七十页\总数二百三十一页\编于二点同步

同步是进程间共同完成一项任务时直接发生相互作用的关系目前七十一页\总数二百三十一页\编于二点——同步进程间具有合作关系——在执行时间上必须按一定的顺序协调进行目前七十二页\总数二百三十一页\编于二点互斥

互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系目前七十三页\总数二百三十一页\编于二点——互斥进程彼此在逻辑上是完全无关的

——它们的运行不具有时间 次序的特征目前七十四页\总数二百三十一页\编于二点——临界资源和临界区——信号量——P、V操作目前七十五页\总数二百三十一页\编于二点临界资源

一次仅允许一个进程使用的共享资源如：打印机、内存单元、表格目前七十六页\总数二百三十一页\编于二点临界区在每个进程中访问临界资源的那段程序有限进入原则唯一原则有限离开原则目前七十七页\总数二百三十一页\编于二点进程间的通信——临界资源和临界区——信号量——P、V操作目前七十八页\总数二百三十一页\编于二点信号量

信号量是一种数据结构一般由两个成员组成：数值指针?目前七十九页\总数二百三十一页\编于二点信号量

一般说来，信号量的值与相应资源的使用情况有关信号量的值仅由P、V操作改变目前八十页\总数二百三十一页\编于二点进程间的通信——临界资源和临界区——信号量——P、V操作目前八十一页\总数二百三十一页\编于二点P、V操作都是原语P：申请一个单位资源（P47）V：释放一个单位资源（P47）目前八十二页\总数二百三十一页\编于二点P操作P(s):若S<0，入等待队列若S>=0，继续取s值减1目前八十三页\总数二百三十一页\编于二点V操作V(s):若S<=0，唤醒一等待队列进程若S>0，继续取s值加1目前八十四页\总数二百三十一页\编于二点用P、V原语实现互斥例：打印机分配互斥信号量mutex（初值为1）Pa为分配进程Pb为释放进程目前八十五页\总数二百三十一页\编于二点Pa：...P（mutex）分配打印机（读写分配表）V（mutex）...Pb：...P（mutex）释放打印机（读写分配表）V（mutex）...目前八十六页\总数二百三十一页\编于二点用P、V原语实现简单同步例：供者和用者对单缓冲区的同步信号量：S1——缓冲区空否（初值为1）S2——缓冲区满否（初值为0）目前八十七页\总数二百三十一页\编于二点

供者进程L1：P（S1）启动读卡机

…

收到输入结束中断

V（S2）

gotoL1

用者进程L2：P（S2）从缓冲区取出信息

…

V（S1）

gotoL2目前八十八页\总数二百三十一页\编于二点用P、V原语实现同步设上例中缓冲区容量为n，分析信号灯的设置与状态变化范围（生产者-消费者问题P49）

目前八十九页\总数二百三十一页\编于二点其它进程通信方式信号量集方式管程消息缓冲通信目前九十页\总数二百三十一页\编于二点UNIX中的进程通信Sleep和wakeup进程跟踪S_5的ipc:消息机制，共享内存，信号量。目前九十一页\总数二百三十一页\编于二点处理机管理目标：提高CPU的有效运行时间如何实现？ 根据CPU的特点和进程管理的需要来设计管理方法目前九十二页\总数二百三十一页\编于二点CPU资源的特点是一种时间资源具有唯一性与独占性影响系统效率的关键因素进程运行的必备资源目前九十三页\总数二百三十一页\编于二点CPU效率的影响因素并发 总有请求CPU的进程CPU时间分片 在效率与交互性上权衡现场交换代价 只做必须做的工作目前九十四页\总数二百三十一页\编于二点处理机的二级调度宏观作业调度：算法复杂、间隔长、宏观环境微观进程调度：算法简单、调度频繁、微观状态目前九十五页\总数二百三十一页\编于二点作业调度作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。作业调度功能：记录已进入系统的各作业的情况（JCB，JobControlBlock）；按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；为被选中的作业创建进程，并且为其申请系统资源；作业加束后作善后处理工作。目前九十六页\总数二百三十一页\编于二点作业控制块（JCB）每个作业进入系统时由系统为其建立一个作业控制块JCB（JobControlBlock)，它是存放作业控制和管理信息的数据结构，主要信息见下图。目前九十七页\总数二百三十一页\编于二点调度性能的衡量

作业调度算法规定了从后备作业中选择作业进入系统内存的原则，这些原则的性能如何，就是本节所讨论的问题。确定调度算法时应考虑的因素应与系统的整体设计目标一致考虑系统中各种资源的负载均匀保证作业的执行对一些专用资源的使用特性的考虑目前九十八页\总数二百三十一页\编于二点调度性能的衡量调度性能的衡量通常采用平均周转时间和带权平均周转时间作业的周转时间：ti=tci-tsiti:作业周转时间tci：作业完成时间tsi:作业提交时间目前九十九页\总数二百三十一页\编于二点调度性能的衡量目前一百页\总数二百三十一页\编于二点先来先服务调度

算法和短作业优先调度算法目前一百零一页\总数二百三十一页\编于二点进程调度调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这种进程将进入相应的等待队列中，并让出CPU，调用进程分派程序选择一个就绪进程占用CPU；当一进程被唤醒时，这种进程将插入到就绪进程队列中。在一般的操作系统教材中把上述功能称为进程调度。目前一百零二页\总数二百三十一页\编于二点调度/分派结构处理机分配由调度和分派两个功能组成。调度：组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。分派：是指当处理机空闲时，从就绪队列队首中移一个PCB，并将该进程投入运行。目前一百零三页\总数二百三十一页\编于二点调度/分派结构pcb1schedulersuspwakeupreceive…pcb2pcb3pcb4…dispatchercpuReady-qpcb5目前一百零四页\总数二百三十一页\编于二点调度/分派结构pcb2schedulersuspwakeupreceive…pcb5pcb3pcb4…dispatchercpu分开Ready-qpcb1目前一百零五页\总数二百三十一页\编于二点进程调度功能保护现场入就绪队列算法实现处理机分派恢复现场目前一百零六页\总数二百三十一页\编于二点进程调度的功能记录和保持系统中所有进程的有关情况和状态特征

有关进程调度的信息是记录在PCB中的，在进程调度中用到的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。目前一百零七页\总数二百三十一页\编于二点进程调度的功能决定分配（处理机）策略确定进程调度的策略，例如，先来先服务、优先数调度策略，调度策略的不同，组织就绪进程队列的方式也不同。先来先服务调度策略，就绪队列要按等待时间大到小的顺序排队；优先数调度，则就绪进程队列要按优先数的升疗（或降序）的方式排队。等等。目前一百零八页\总数二百三十一页\编于二点进程调度的功能实施处理机的分配总而言之，进程调度包括：调度算法的选择（调度算法）调度时机的选择（调度时机）实施进程调度（调度程序）目前一百零九页\总数二百三十一页\编于二点进程调度的功能调度时机（UNIX系统中）：（1）进程自动放弃处理机：当进程进入高低优先级睡眠状态时

（在sleep()程序中）；在进程进入暂停状态时（在stop()程序中）；进程进入僵死状态时（在exit()程序中）；目前一百一十页\总数二百三十一页\编于二点进程调度的功能在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。（2）强迫调度目前一百一十一页\总数二百三十一页\编于二点调度方式优先数高者进程是否抢占正在运行进程资源非剥夺方式剥夺方式选择可抢占策略：优先数+抢占标志（u,v）目前一百一十二页\总数二百三十一页\编于二点进程调度的功能实施进程调度的程序称为进程调度程序（或称调度程序），在通常的操作系统原理中，该程序属于系统进程的执行程序，有的操作系统是把进程调度程序作一个特别的处理，如早期的操作系统中把进程调度程序称为交通控制程序，不属于系统中的任何进程。在UNIX系统中，进程调度程序swtch()分属个不同的进程，即调用swtch()的进程、让出处理机的进程、0进程、被调度到的进程。目前一百一十三页\总数二百三十一页\编于二点调度性能的衡量

选择策略时考虑因素整体目标、负载均衡、资源特性、用户满意调度性能指标平均周转时间，平均带权周转时间CPU利用率吞吐量就绪等待时间响应时间目前一百一十四页\总数二百三十一页\编于二点调度策略

先来先服务调度短作业优先调度响应比高者优先调度优先数调度均衡调度多级队列法多级反馈队列法目前一百一十五页\总数二百三十一页\编于二点进程优先数调度算法优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。目前一百一十六页\总数二百三十一页\编于二点进程优先数调度算法静态：进程的优先数在进程创建时确定后就不再变化确定进程优先数：系统确定：（运行时间、使用资源，进程的类型）用户确定：（紧迫程度，计费与进程优先数有关）系统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）目前一百一十七页\总数二百三十一页\编于二点进程优先数调度算法动态进程优先数：

系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标。目前一百一十八页\总数二百三十一页\编于二点循环轮转调度算法时间片完，入队列末端；q=t/n简单循环轮转调度可变时间片轮转调度多重时间片循环调度目前一百一十九页\总数二百三十一页\编于二点循环轮转调度

循环轮转调度实际上是一种先来先服务算法的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程让出CPU，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。目前一百二十页\总数二百三十一页\编于二点循环轮转调度目前一百二十一页\总数二百三十一页\编于二点循环轮转调度

系统按进程转换成就绪状态的时间的降序排队，调度程序每次调度，总是从队首移出一程的PCB，然后，将此进程投入运行（由就绪状态转换成运行状态）。一个运行时间片到的进程从运行状态转换成就绪状态后，排在就绪队列的队尾。评价：优点是实现简单、系统开销小缺点是不灵活，当系统中进程较少时，系统开销变大。 为什么？由于该算法简单易于实现，且系统开销较小，早期的分时操作系统和目前一些应用系统中广泛采用了这种调度算法。目前一百二十二页\总数二百三十一页\编于二点循环轮转调度可变时间片轮转调度为了克服前种调度算法的缺点，人们设计出一种可变时间片的调度算法，其思想是：时间片的大小是可变的，系统可根据系统中当前的进程数来确定时间片的大小。这种算法从理论上克服了系统中进程数很少时系统开销大的缺点，但修改时间片的大小，统计系统进程的数量也需要消耗系统时间，还有一个调整时间片大小的周期，太大，等于是固定时间片，太小，系统开销很大，得不尝失。目前一百二十三页\总数二百三十一页\编于二点调度用的进程状态变迁图

在这个图中新创建的进程进入低优就绪状态，一个运行进程因时间片到（实际上是计算量大的进程）而转换成低优就绪；进程因等待I/O完成而转换高优就绪.目前一百二十四页\总数二百三十一页\编于二点调度用的进程状态变迁图调度程序首先看高优就绪进程队列是否为空，若不为空，则从高优就绪进程中选择一个进程占用CPU，否则，从低优就绪队列中选择。这种调度效果能充分地利用系统资源。为什么？UNIX系统的进程调度状态变迁图，与前一种调度变迁图有着异曲同功的效果。目前一百二十五页\总数二百三十一页\编于二点调度用进程状态变迁图中就绪运行等待1低就绪高就绪等待2目前一百二十六页\总数二百三十一页\编于二点UNIX中的进程调度进程调度：调度时机，调度算法Shell工作原理系统初启目前一百二十七页\总数二百三十一页\编于二点UNIX系统的进程调度UNIX调度算法我们从调度算法、调度时机、调度程序三个方面来分析UNIX系统的进程调度。调度算法

UNIX系统采用优先数调度算法，每个进程有一个进程优先数，p_pri是proc结构中的一个变量，其取值范围是－127～127，其值越小，进程的优先级越高（即，调度程序总是从就绪状态的进程中选择一个优先数最小的进程占用CPU）。目前一百二十八页\总数二百三十一页\编于二点UNIX调度算法优先数的确定：系统设置在进程进入睡眠状态时，在SLEEP（）中设置将要进入睡眠状态进程的优先数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。目前一百二十九页\总数二百三十一页\编于二点UNIX调度算法进程进入高优先级睡眠的原因：（1）0＃进程（－100优先数）；（2）因资源请求得不到满足的进程，磁盘（－80），打印机（－20），…；（3）等待块设备I/O完成的进程，（－50）。进程进入低优先级睡眠的原因：(1）因等待字符设备I/O完成的进程，（0～20的优先数）；(2)所有处于用户态运行进程，优先数一般情况下为大于100。这样做的目的是为什么？为使系统资源得到充分的利用，换句话说，是为了提高系统资源的使用效率。目前一百三十页\总数二百三十一页\编于二点UNIX调度算法优先数的计算计算公式：

p_pri={127,(p_cpu/16+p_nice+PUSER)其中：

p_cpu进程占用CPU的程度

p_nice用户通过系统调用nice(priority)设置的进程优先数。

PUSER常数，其值为100目前一百三十一页\总数二百三十一页\编于二点UNIX调度算法目前一百三十二页\总数二百三十一页\编于二点UNIX调度算法UNIX系统的设计者采用了一个巧妙的方法，既避免了繁杂的统计工作，也不需做浮点运行算。（这就是我们要学习的工程能力，或称分析问题和解决问题的能力，学会和记往一两个科学的定理和公式并不难，难的是怎样将这些普遍的理论用于实际的工程之中，UNIX系统中有很多值得我们学习的地方，对p_cpu的处理就是其中之一，这里并不要求把UNIX中的p_cpu的处理完全记住，而是要通过对它的了解，学会处理实际工程问题的方法。）目前一百三十三页\总数二百三十一页\编于二点UNIX调度算法UINX系统中对p_cpu的处理：

每个时钟中断：p_cpu++;

每秒钟（时钟中断）：

if(p_cpu-SCHMAG<0)p_cpu=0;

其中：SCHMAG调度魔数10在计算p_pri的公式中，PUSER是个常数，由于用户不可能频繁地设置进程的优先数，所以p_nice实际上也是个常数，那么决定p_pri的实际上就是p_cpu。根据UNIX系统与调度算法可得出如下的一个负反馈的过程，从这个过程中可看出什么？目前一百三十四页\总数二百三十一页\编于二点UNIX调度算法这种负反馈的效果使得系统中在用户态下运行的进程能均衡地得到处理机，达到UNIX系统的设计目标。（UNIX系统什么设计目标？）目前一百三十五页\总数二百三十一页\编于二点UNIX调度算法计算优先数的时机在UNIX系统中什么时候计算进程的优先数？计算哪些进程的优先数？会不会改变系统设置的进程的优先数？目前一百三十六页\总数二百三十一页\编于二点UNIX调度算法计算进程优先数的时机：在时钟中断处理程序中，每秒末计算满足下面条件进程的优先数：

p_pri>PUSER现运行进程在自陷处理程序trap()末尾重新计算本进程的优先数.

目的:调用nice()设置的本进程的优先数p_nice的改变反映到p_pri中去；现运行进程在执行时钟中断处理程序时，若发现中断前为用户态，则每隔1秒钟重新计算本进程的优先数。因为现运行进程已经占用了一些CPU的时间，要反映到p_pri中去。目前一百三十七页\总数二百三十一页\编于二点UNIX调度算法这三种重新计算（调整）进程优先数都没有修改由系统设置的进程优先数，从而保证了处于核心态的进程能尽快地得到CPU，使得系统资源（设备）能得到充分地利用，提高了系统资源的使用效率，而计算进程的优先数又使得系统中所有处于用户态的进程能较均衡地占用CPU，保证了各用户终端的响应时间，实现了分时操作系统的特性。目前一百三十八页\总数二百三十一页\编于二点UNIX调度时机调度时机（UNIX系统中）：1）进程自动放弃处理机在进程进入高低优先级睡眠状态时（在sleep()程序中）；在进程进入暂停状态时（在stop()程序中）；进程进入僵死状态时（在exit()程序中）；2）强迫调度在中断自陷总控程序中，当先前态是用户态，且runrun标志大于0，则进行强迫调度，强行剥夺现运行进程的处理机，转进程调度程序。目前一百三十九页\总数二百三十一页\编于二点UNIX调度时机Runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度，出现这种情况有两种可能：高低优先级睡眠进程被唤醒后其优先级高于现运行进程；当一个进程占用一段时间的CPU后，它的优先级要降低，造成现运行进程的优先级低于系统中的其它就绪进程（时间片到是其中的一种情况）。目前一百四十页\总数二百三十一页\编于二点UNIX系统调度程序UNIX系统中的进程调度程序是swtch，所以，在绝大多数关于UNIX系统的文献中称为进程切换程序。目前一百四十一页\总数二百三十一页\编于二点UNIX调度程序目前一百四十二页\总数二百三十一页\编于二点UNIX调度程序UNIX系统的进程调度程序有以下特点：1.swtch()程序分属三个不同的进程：调用它的程序（即将让出处理机的进程）0号进程被选中的进程2.调度程序中属于0号进程的那段程序是在0号进程处于睡眠状态下执行的，这一点非常特别，在操作系统中，仅此一例。目前一百四十三页\总数二百三十一页\编于二点

资源分配与调度资源管理概述资源分配机构资源分配策略死锁问题目前一百四十四页\总数二百三十一页\编于二点资源管理概述简便、有效的使用资源资源管理任务资源分类统一的实现机制——机构和策 略目前一百四十五页\总数二百三十一页\编于二点

资源分类物理资源与程序资源单入口资源与多入口资源等同资源虚拟资源目前一百四十六页\总数二百三十一页\编于二点

资源分配机构资源描述器rd（P103）资源信息块目前一百四十七页\总数二百三十一页\编于二点等待队列头指针可利用资源队列头指针资源分配程序入口地址ribpcb1rd1…………所有rd在同一队列？资源信息块目前一百四十八页\总数二百三十一页\编于二点资源分配策略触发时机分配策略实质排对站管理等同资源选取目前一百四十九页\总数二百三十一页\编于二点一、先请求先服务按请求发生的先后次序排队总能调度简单迅速短作业响应比问题目前一百五十页\总数二百三十一页\编于二点二、优先调度按优先数的大小次序排队灵活设计多排队站优先数设计问题目前一百五十一页\总数二百三十一页\编于二点三、适应调度按工作集的大小次序排队主存与CPU合作效率最大工作集的动态计算问题实现的复杂度目前一百五十二页\总数二百三十一页\编于二点四、均衡调度按系统资源空闲的大小次序动态调度系统效率最大负载均衡不适合细化处理目前一百五十三页\总数二百三十一页\编于二点五、针对设备特性的调度按设备特性次序排队（P107）服务时间最短旋转排序目前一百五十四页\总数二百三十一页\编于二点死锁问题

概念起因分析解决方法预防目前一百五十五页\总数二百三十一页\编于二点死锁概念

并发与竞争部分满足死锁（P109）目前一百五十六页\总数二百三十一页\编于二点死锁起因分析资源稀缺、鼓励竞争联合推进路线（P110）进程-资源有向图（P111）死锁起因死锁必要条件目前一百五十七页\总数二百三十一页\编于二点死锁起因资源不足进程推进顺序非法目前一百五十八页\总数二百三十一页\编于二点死锁必要条件

资源互斥使用不剥夺条件部分分配环路条件目前一百五十九页\总数二百三十一页\编于二点死锁解决方法

假脱机技术可抢占的进程调度策略静态分配资源动态有控分配检测并修复目前一百六十页\总数二百三十一页\编于二点死锁预防

有序资源分配法（P118题）银行算法（P115）预先分配资源目前一百六十一页\总数二百三十一页\编于二点一、操作系统的有关概念二、进程管理三、存储器管理目前一百六十二页\总数二百三十一页\编于二点

Cpu与主存

独占微观独占，宏观共享目前一百六十三页\总数二百三十一页\编于二点概念存储器storage,memory能接收数据和保存数据、而且能根据命令提供这些数据的装置。目前一百六十四页\总数二百三十一页\编于二点概念存储器分成两类：内存储器（简称内存、主存、物理存储器）处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。目前一百六十五页\总数二百三十一页\编于二点存储器的层次结构存储系统设计三个问题：容量、速度和成本容量：需求无止境速度：能匹配处理器的速度成本问题：成本和其它部件相比应在合适范围之内目前一百六十六页\总数二百三十一页\编于二点容量、速度和成本三个目标不可能同时达到最优，要作权衡存取速度快，每比特价格高容量大，每比特价格越低，同时存取速度也越慢解决方案：采用层次化的存储体系结构当沿着层次下降时每比特的价格将下降，容量将增大速度将变慢，处理器的访问频率也将下降目前一百六十七页\总数二百三十一页\编于二点层次化的存储体系结构目前一百六十八页\总数二百三十一页\编于二点存储访问局部性原理提高存储系统效能关键点：程序存储访问局部性原理程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相同的指令集合对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域处理器主要和存储器的局部打交道,在经过一段时间以后，使用的代码和数据集合会改变目前一百六十九页\总数二百三十一页\编于二点概念程序的逻辑结构程序地址：用户编程序时所用的地址（或称逻辑地址、虚地址），基本单位可与内存的基本单位相同，也可以不相同。程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。目前一百七十页\总数二百三十一页\编于二点程序的逻辑组织内存组织方式：一维线性 程序组织方式：一维线性二维段式（模块化、分级保护、动态连接）目前一百七十一页\总数二百三十一页\编于二点codedataheapstack程序2虚地址空间data2stack1code1heap1code2stack2data1heap2OScodeOSdataOSheap&stacks程序1虚地址空间codedataheapstack内存地址转换目前一百七十二页\总数二百三十一页\编于二点

重定位把逻辑地址转变为内存的物理地址的过程目前一百七十三页\总数二百三十一页\编于二点

物理主存与逻辑主存用户程序默认主存地址0--k-1,实际对应n--n+k-1目前一百七十四页\总数二百三十一页\编于二点

相对地址（或逻辑地址）用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为相对地址目前一百七十五页\总数二百三十一页\编于二点LOAD1,50012345LOAD1,5001234501005007005000510055005700程序A的地址空间程序A的内存空间..................目前一百七十六页\总数二百三十一页\编于二点

绝对地址（或物理地址）内存中各物理存储单元的地址是从统一的基地址顺序编址，这种地址称为绝对地址目前一百七十七页\总数二百三十一页\编于二点主存映射方式建立虚-实地址间的对应关系编程或编译时确定地址映射关系（不能浮动）静态地址映射（一次浮动）动态地址映射目前一百七十八页\总数二百三十一页\编于二点静态地址映射静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的。在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如左图所示。评价:优点是实现简单，不要硬件的支持。缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。目前一百七十九页\总数二百三十一页\编于二点静态地址映射目前一百八十页\总数二百三十一页\编于二点

动态地址映射

动态地址映射是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间。重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。目前一百八十一页\总数二百三十一页\编于二点动态地址映射动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。系统中设置了重定位寄存器。目前一百八十二页\总数二百三十一页\编于二点存储管理的功能（1）内存分配——为每个进程分配一定的内存空间（2）地址映射——把程序中所用的相对地址转换成内存的物理地址目前一百八十三页\总数二百三十一页\编于二点存储管理的功能（3）内存保护——检查地址的合法性，防止越界访问（4）内存扩充——解决“求大于供”的问题，采用虚拟存储技术目前一百八十四页\总数二百三十一页\编于二点主存共享方式

按区分配——按逻辑分页分配——按物理目前一百八十五页\总数二百三十一页\编于二点内存分配

在多道程序设计的环境中，内存分配的功能包括：制定分配策略、构造分配用的数据结构、响应系统的内存分配的请求和回收系统释放的内存区。内存管理策略有三种：放置策略决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；调入策略决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调；淘汰策略当内存不足时，决定将某些信息调出内存的策略。目前一百八十六页\总数二百三十一页\编于二点分区存贮管理

固定分区分配动态分区分配(p96)目前一百八十七页\总数二百三十一页\编于二点分区分配放置策略合适的概念首次适应算法最佳适应算法最坏适应算法

目前一百八十八页\总数二百三十一页\编于二点

碎片问题（紧缩）目前一百八十九页\总数二百三十一页\编于二点存储保护方法

上下界防护基址、限长寄存器保护目前一百九十页\总数二百三十一页\编于二点存储保护两种存储保护技术的区别1、寄存器的设置不同；2、判别式中用的判别条件不同上下界寄存器保护法用的是物理地址基址、限长寄存器保护法用的是程序的逻辑地址对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。目前一百九十一页\总数二百三十一页\编于二点多道程序对换技术以用户为单位独占内存如何减少对换信息量？部分换出与恢复目前一百九十二页\总数二百三十一页\编于二点提供虚存问题的提出物理存储器的结构是个一维的线性空间，容量是有限的。用户程序结构：一维空间一个用户程序就是一个程序，并且程序和数据是不分离的；二维空间

程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的；n维空间即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。目前一百九十三页\总数二百三十一页\编于二点提供虚存如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。目前一百九十四页\总数二百三十一页\编于二点提供虚存虚拟存储器

为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。虚拟存储器需要大容量的外存储器的支持，或称物资基础。目前一百九十五页\总数二百三十一页\编于二点虚拟存储器的基本特征（1）虚拟扩充——不是物理上，而是逻辑上扩充了内存容量（2）部分装入——每个作业（进程）不是全部一次性地装入内存，而是只装入其一部分目前一百九十六页\总数二百三十一页\编于二点虚拟存储器的基本特征（3）离散分配——每个作业（进程）装入内存的那部分不必占用连续的内存空间，而是“见缝插针”目前一百九十七页\总数二百三十一页\编于二点虚拟存储器的基本特征（4）多次对换——在一个进程运行期间，它所需的全部程序和数据要分成多次调入内存目前一百九十八页\总数二百三十一页\编于二点虚拟主存的优点

透明使用主存方便存储保护程序可浮动充分利用主存

目前一百九十九页\总数二百三十一页\编于二点分页存贮管理

页式系统页式地址变换请调策略淘汰策略目前二百页\总数二百三十一页\编于二点页式存储管理页式系统应解决的问题分区存储管理的主要问题是碎片问题。在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。目前二百零一页\总数二百三十一页\编于二点分页的概念程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是为2n,通常为1KB，2KB，nKB等。目前二百零二页\总数二百三十一页\编于二点页式地址变换页表：虚页-物理块对照表虚地址结构：页号+偏移页式地址变换分地址-查页表-合地址

目前二百零三页\总数二百三十一页\编于二点页式地址变换虚地址结构(程序字)

虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。假定页面大小1024字节，虚地址共占用2个字节(16位)

页号页内地址（位移量）

PW151090目前二百零四页\总数二百三十一页\编于二点页式地址变换-虚地址结构目前二百零五页\总数二百三十一页\编于二点页式地址变换目前二百零六页\总数二百三十一页\编于二点页式地址变换页式地址映射虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出将虚地址转换成二进制的数；按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；根据题意产生页表；将位移量直接复制到内存地址寄存器的低位部分；以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。目前二百零七页\总数二百三十一页\编于二点页式地址变换页式地址映射虚地址以十进制数给出页号＝虚地址％页大小位移量＝虚地址mod页大小根据题意产生页表；以页号查页表，得到对应页装入内存的块号内存地址＝块号×页大小＋位移量目前二百零八页\总数二百三十一页\编于二点请调策略问题的提出在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。目前二百零九页\总数二百三十一页\编于二点请调策略请求分页概念请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行。目前二百一十页\总数二百三十一页\编于二点请求分页的基本思想（1）请求分页=分页+请求

逻辑空间分页物理空间分块页与块同样大页连续块离散用页号查页表硬件做重定位分页目前二百一十一页\总数二百三十一页\编于二点请