操作系统原理(西电版)课件

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,操 作 系 统 原 理,武汉大学计算机多媒体课程,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,）交互性,什么是操作系统,操作系统的性质,操作系统,是控制和管理计算机系统内各种硬件和软件资源、有效地组织多道程序运行的,系统软件,(或,程序集合,),是用户与计算机之间的接口。,以下软件哪些是操作系统?,UNIX Word DOS VB Office FoxPro Windows 98 Windows NT Linux PowerPoint,以下软件是操作系统：,UNIX DOS Linux Windows 98 Windows NT,设置OS的目的,扩充机器功能，方便用户使用。,提高系统效率。,操作系统的共同性质,1、从功能上看,具有,五大功能,-存储器管理、处理机管理、设备管理、文件管理、用户接口,2、从层次上看,是裸机之上的第一层软件,为其他软件的建立和运行提供基础。,裸机,操作系统,其他软件,. . .,用户,1。4节,3、从服务上看,提供众多基础服务,方便用户使用,构成软件平台。,4、从内部特征上看,-支持并发性,-实现资源共享,-完成进程的异步前进,以多道成批系统为例,并发,共享,不确定性,1.3 OS的服务功能,程序执行,I/O操作,文件系统管理,出错检测,资源分配,统计,保护,一 系统调用,是应用程序与OS的接口,进程或作业控制：实现进程或作业的所有活动,文件管理和设备管理,信息维护：用户与系统交互信息,二 系统程序,文件管理,状态信息,文件修改,程序设计语言支持,程序装入与执行,工具性软件,命令解释程序的实现方法,1.5操作系统逻辑结构设计,分层实现的软件设计方法,1.5操作系统逻辑结构设计,单块结构,层次结构:分层实现的软件设计方法.,虚拟机,客户/服务器模型:再用户进程方式下实现系统的多数功能; 核心只负责客户与服务器的通信; 适用于分布式系统; 注意对关键基础服务的处理.,1。8 UNIX系统的特点和结构,UNIX的主要特点,UNIX系统结构,UNIX系统核心结构,一、操作系统的有关概念,二、,进程管理,三、存储器管理,进程概念,程序的顺序执行与并发执行,程序的顺序执行,概念,一个程序由若干个程序段组成，而这些程序段的执行必须是顺序的，这种程序执行的方式就称为程序的顺序执行。,例如：,程序顺序执行的特点,1 顺序性,处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。,2 封闭性,程序一旦开始执行，其计算结果不受外界的影响，当程序的初始条件给定之后，其后的状态只能由程序本身确定，即只有本程序才能改变它。,程序顺序执行的特点（续）,3 可再现性,程序执行的结果与初始条件有关，而与执行时间无关。即只要程序的初始条件相同，它的执行结果是相同的，不论它在什么时间执行，也不管计算机的运行速度。,O=f(I), f是与时间无关的函数,程序的并发执行,例：,在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即I,i,C,i,P,i,(i=1,2,3,.,n)。,这些作业系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。,程序的并发执行,例如： P1与I2，C1与I2,I3与P1是可以同时执行的。,I1、C1、P1的执行必须严格按照I1，C1，P1的顺序。,I1、 I2、 I3、 I4轮流使用同一输入设备。,时间,资源,程序的并发执行定义,若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。,程序的并发执行分析,优点：,程序的并发执行,提高了资源的利用率,。,注意有限制规则：,同一,作业,的处理步骤的执行必须严格按照规定的,顺序,；,同一独占资源上,的不同,作业的处理步骤,不能同时,执行。,程序的顺序执行与并发执行,假设有一个程序由S0Sn+1个语句，先顺序执行S0，然后并发执行 S1Sn语句，最后顺序执行Sn+1 。,程序并发执行的特点,一、失去了程序的封闭性,程序A,程序B,n:=0;,打印,n,n:=n+1;,K1,K2,S,如果程序执行的结果是一个与时间无关的函数，即具有,封闭性,。,程序B打印0,程序B打印1,程序并发执行的特点,二、程序与计算不再一一对应,在程序顺序执行时，一个程序总是对应一个具体的计算，但在程序的并发执行时，可能有多用户共享使用同一个程序，但处理（计算）的对象却是不同的，例如，在多用户环境下，可能同时有多个用户调用C语言的编译程序，这就是典型的一个程序对应多个用户源程序的情况。,程序并发执行的特点,程序与计算不再一一对应示例,程序A,程序B,Call C,Call C,程序C,程序A和B在执行过程中都调用了程序C,程序并发执行的特点,三、程序并发执行可以相互制约,在多道程序设计的环境下，程序是并发执行的。即系统中有多道程序在“同时”执行，这些程序之间要共享系统的资源，程序之间有合作（通信）的关系。合作与竞争产生一系列的矛盾，这些矛盾实际上是一种相互制约，有直接的，也有间接。,注意区别,不能同时,与,有先后次序,两种制约。,程序并发执行的特点,程序并发执行的相互制约示例,并发活动进程的引人,操作系统的特性之一是并发与共享，即在系统中（内存）同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等符。,要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念进程。,进程的定义,行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。,进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan),进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C. Shaw),进程是执行中的程序。（Ken Thompson and Dennis Ritchie ),进程，即是程序在并发环境中的执行过程 。,进程与程序的区别（1）,进程是动态概念；程序是静态概念,进程具有并发性，宏观上同时运行；程序本身具有顺序性，程序的并发执行是通过进程实现的,进程具有独立性，是一个能独立运行的单位，是系统资源分配的基本单位，是运行调度的基本单位；程序本身没有此特性,进程与程序的区别（2）,进程和程序无一一对应关系，一个进程可顺序执行多个程序；一个程序可由多个进程共用,进程异步前进，会相互制约；程序不具备此特性,进程实体具有一定结构，组成进程映象；程序没有这种结构,进程与程序的区别示例,例子：,光盘（CD、VCD、DVD）,光盘（程序）-放光盘的活动（进程）,理解进程概念,进程的运行状态及其变迁,进程的组成,进程映像,进程环境,进程的运行状态及其变迁,进程在系统中的活动规律是：,执行-暂停-执行,进程的运行状态反映进程的动态性。,进程的三种基本状态：,运行状态,就绪状态,封锁状态（又称不可运行、挂起）,进程的三种基本状态,运行状态,：进程得到CPU控制权，它的程序正在运行。（在系统中，总只有一个进程处于此状态）,就绪状态,：,已经准备就绪，一旦得到CPU，就立即可以运行。（有多个进程处于此状态）,封锁状态,：,正在等待某个事件的发生（如等待I/O的完成），而暂停执行，这时，即使给它CPU时间，它也无法执行。,进程的状态变化,就绪,运行,挂起,？,？,PCB,程序,数据集合,进程的组成,基本内容的确定?,进程与PCB的关系,每个进程有唯一的PCB,系统中所有进程都有自己的PCB,操作系统依据PCB管理进程,进程与PCB的关系,操作系统利用PCB实现进程的动态和并发,PCB是进程存在的唯一标志,Pcb表组织,a,b,-1,pcb1,N个,pcb2,pcb,i,Pcb-addr,?,空间大小?,?,UNIX的进程映像,进程状态,变迁关系,进程映像：PCB的实现、核心栈与用户栈（图2-10 UNIX进程映像结构）,进程环境,用户级环境,寄存器环境,系统级环境,1、进程与程序的区别,2、进程的组成,3、进程的同步与互斥,进程控制原语,Fork(),Wait(stat_addr),Exit,exec,进程在活动中会相互制约,所有进程都是相互独立的,进程以异步方式并发执行,同步,同步是进程间共同完成一项任务时直接发生相互作用的关系,同步进程间具有合作关系,在执行时间上必须按一定的顺序协调进行,互斥,互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系,互斥进程彼此在逻辑上是完全无关的,它们的运行不具有时间次序的特征,临界资源和临界区,信号量,P、V操作,临界资源,一次仅允许一个进程使用的共享资源,如：打印机、内存单元、表格,临界区,在每个进程中访问临界资源的那段程序,有限进入原则,唯一原则,有限离开原则,进程间的通信,临界资源和临界区,信号量,P、V操作,信号量,信号量是一种数据结构,一般由两个成员组成：,数值,指针,?,信号量,一般说来，信号量的值与相应资源的使用情况有关,信号量的值仅由P、V操作改变,进程间的通信,临界资源和临界区,信号量,P、V操作,P、V操作都是原语,P：申请一个单位资源（P47）,V：释放一个单位资源（P47）,P操作,P(s):,若S=0，继续,取s值减1,V操作,V(s):,若S0，继续,取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）,goto L1,用者进程,L2：,P（S2）,从缓冲区取出信息,V（S1）,goto L2,用P、V原语实现同步,设上例中缓冲区容量为n，分析信号灯的设置与状态变化范围（生产者-消费者问题P49）,其它进程通信方式,信号量集方式,管程,消息缓冲通信,UNIX中的进程通信,Sleep 和wakeup,进程跟踪,S_5的ipc:消息机制，共享内存，信号量。,处理机管理,目标：提高CPU的有效运行时间,如何实现？,根据CPU的特点和进程管理的需要来设计管理方法,CPU资源的特点,是一种时间资源,具有唯一性与独占性,影响系统效率的关键因素,进程运行的必备资源,CPU效率的影响因素,并发,总有请求CPU的进程,CPU时间分片,在效率与交互性上权衡,现场交换代价,只做必须做的工作,处理机的二级调度,宏观作业调度：算法复杂、间隔长、宏观环境,微观进程调度：算法简单、调度频繁、微观状态,作业调度,作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。,作业调度功能：,记录已进入系统的各作业的情况（JCB，Job Control Block）；,按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；,为被选中的作业创建进程，并且为其申请系统资源；,作业加束后作善后处理工作。,作业控制块（JCB）,每个作业进入系统时由系统为其建立一个作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，主要信息见下图。,调度性能的衡量,作业调度算法规定了从后备作业中选择作业进入系统内存的原则，这些原则的性能如何，就是本节所讨论的问题。,确定调度算法时应考虑的因素,应与系统的整体设计目标一致,考虑系统中各种资源的负载均匀,保证作业的执行,对一些专用资源的使用特性的考虑,调度性能的衡量,调度性能的衡量,通常采用平均周转时间和带权平均周转时间,作业的周转时间,：,t,i,= t,ci,-t,si,t,i,:作业周转时间,t,ci,：作业完成时间,t,si,: 作业提交时间,调度性能的衡量,先来先服务调度算法和短作业优先调度算法,进程调度,调度与进程控制和进程通信的功能有密切的联系，当一个进程阻塞时，这种进程将进入相应的等待队列中，并让出CPU，调用进程分派程序选择一个就绪进程占用CPU；当一进程被唤醒时，这种进程将插入到就绪进程队列中。,在一般的操作系统教材中把上述功能称为进程调度。,调度/分派结构,处理机分配由调度和分派两个功能组成。,调度：组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。,分派：是指当处理机空闲时，从就绪队列队首中移一个PCB，并将该进程投入运行。,调度/分派结构,pcb1,scheduler,susp,wakeup,receive,pcb2,pcb3,pcb4,dispatcher,cpu,Ready-q,pcb5,调度/分派结构,pcb2,scheduler,susp,wakeup,receive,pcb5,pcb3,pcb4,dispatcher,cpu,分开,Ready-q,pcb1,进程调度功能,保护现场,入就绪队列算法实现,处理机分派,恢复现场,进程调度的功能,记录和保持系统中所有进程的有关情况和状态特征,有关进程调度的信息是记录在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结构中的一个变量，其取值范围是127127，其值越小，进程的优先级越高（即，调度程序总是从就绪状态的进程中选择一个优先数最小的进程占用CPU）。,UNIX调度算法,优先数的确定：,系统设置,在进程进入睡眠状态时，在SLEEP（）中设置将要进入睡眠状态进程的优先数，当该进程被唤醒后，就以系统给它设置的优先数去参与处理机的竟争。,UNIX调度算法,进程进入高优先级睡眠的原因：,（1）0进程（100优先数）；,（2）因资源请求得不到满足的进程，磁盘（80），打印机 （20），；,（3）等待块设备I/O完成的进程，（50）。,进程进入低优先级睡眠的原因：,(1）因等待字符设备I/O完成的进程，（020的优先数）；,(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 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）,资源信息块,等待队列头指针,可利用资源队列头指针,资源分配程序入口地址,rib,pcb1,rd1,所有rd在同一队列？,资源信息块,资源分配策略,触发时机,分配策略实质,排对站管理,等同资源选取,一、先请求先服务,按请求发生的先后次序排队,总能调度,简单迅速,短作业响应比问题,二、优先调度,按优先数的大小次序排队,灵活设计,多排队站,优先数设计问题,三、适应调度,按工作集的大小次序排队,主存与CPU合作效率最大,工作集的动态计算问题,实现的复杂度,四、均衡调度,按系统资源空闲的大小次序动态调度,系统效率最大,负载均衡,不适合细化处理,五、针对设备特性的调度,按设备特性次序排队（P107）,服务时间最短,旋转排序,死锁问题,概念,起因分析,解决方法,预防,死锁概念,并发与竞争,部分满足,死锁（P109）,死锁起因分析,资源稀缺、鼓励竞争,联合推进路线（P110）,进程-资源有向图（P111）,死锁起因,死锁必要条件,死锁起因,资源不足,进程推进顺序非法,死锁必要条件,资源互斥使用,不剥夺条件,部分分配,环路条件,死锁解决方法,假脱机技术,可抢占的进程调度策略,静态分配资源,动态有控分配,检测并修复,死锁预防,有序资源分配法（P118题）,银行算法（P115）,预先分配资源,一、操作系统的有关概念,二、进程管理,三、,存储器管理,Cpu与主存,独占,微观独占，宏观共享,概念,存储器,storage, memory,能接收数据和保存数据、而且能根据命令提供这些数据的装置。,概念,存储器分成两类：,内存储器（简称内存、主存、物理存储器）,处理机能直接访问的存储器。用来存放系统和用户的程序和数据，其特点是存取速度快，存储方式是以新换旧，断电信息丢失。,存储器的层次结构,存储系统设计三个问题：,容量、速度和成本,容量：需求无止境,速度：能匹配处理器的速度,成本问题：成本和其它部件相比应在合适范围之内,容量、速度和成本,三个目标不可能同时达到最优，要作权衡,存取速度快，每比特价格高,容量大，每比特价格越低，同时存取速度也越慢,解决方案：采用层次化的存储体系结构,当沿着层次下降时,每比特的价格将下降，容量将增大,速度将变慢，处理器的访问频率也将下降,层次化的存储体系结构,存储访问局部性原理,提高存储系统效能关键点：程序存储访问局部性原理,程序执行时，有很多的循环和子程序调用，一旦进入这样的程序段，就会重复存取相同的指令集合,对数据存取也有局部性，在较短的时间内，稳定地保持在一个存储器的局部区域,处理器主要和存储器的局部打交道,在经过一段时间以后，使用的代码和数据集合会改变,概念,程序的逻辑结构,程序地址：用户编程序时所用的地址（或称逻辑地址 、虚地址 ），基本单位可与内存的基本单位相同，也可以不相同。,程序地址空间（逻辑地址空间、虚地址空间）:用户的程序地址的集合称为逻辑地址空间，它的编址总是从0开始的，可以是一维线性空间，也可以是多维空间。,程序的逻辑组织,内存组织方式：一维线性,程序组织方式：,一维线性,二维段式（,模块化,、,分级保护,、,动态连接,）,code,data,heap,stack,程序2,虚地址空间,data2,stack1,code1,heap1,code2,stack2,data1,heap2,OS code,OS data,OS heap,& stacks,程序 1,虚地址空间,code,data,heap,stack,内存,地址转换,重定位,把逻辑地址转变为内存的物理地址的过程,物理主存与逻辑主存,用户程序默认主存地址0-k-1,实际对应n-n+k-1,相对地址（或逻辑地址）,用户程序经编译之后的每个目标模块都以0为基地址顺序编址，这种地址称为相对地址,LOAD 1, 500,12345,LOAD 1, 500,12345,0,100,500,700,5000,5100,5500,5700,程序A的地址空间,程序A的内存空间,. . .,. . .,. . .,. . .,. . .,. . .,绝对地址（或物理地址）,内存中各物理存储单元的地址是从统一的基地址顺序编址，这种地址称为绝对地址,主存映射方式,建立虚-实地址间的对应关系,编程或编译时确定地址映射关系（不能浮动）,静态地址映射（一次浮动）,动态地址映射,静态地址映射,静态地址映射是在程序装入内存时完成从逻辑地址到物理地址的转换的。,在一些早期的系统中都有一个装入程序（加载程序），它负责将用户程序装入系统，并将用户程序中使用的访问内存的逻辑地址转换成物理地址。如左图所示。,评价:,优点是实现简单，不要硬件的支持。,缺点是程序一旦装入内存，移动就比较困难。有时间上的浪费。在程序装入内存时要将所有访问内存的地址转换成物理地址。,静态地址映射,动态地址映射,动态地址映射是由硬件地执行时完成的，程序中不执行的程序就不做地址映射的工作，这样节省了CPU的时间 。,重定位寄存器的内容由操作系统用特权指令来设置，比较灵活。,实现动态地址映射必须有硬件的支持，并有一定的执行时间延迟。现代计算机系统中都采用动态地址映射技术。,动态地址映射,动态地址映射是在程序执行时由系统硬件完成从逻辑地址到物理地址的转换的。,系统中设置了重定位寄存器。,存储管理的功能,（1）,内存分配,为每个进程分配一定的内存空间,（2）,地址映射,把程序中所用的相对地址转换成内存的物理地址,存储管理的功能,（3）,内存保护,检查地址的合法性，防止越界访问,（4）,内存扩充,解决“求大于供”的问题，采用虚拟存储技术,主存共享方式,按区分配按逻辑,分页分配按物理,内存分配,在多道程序设计的环境中，内存分配的功能包括：制定分配策略、构造分配用的数据结构、响应系统的内存分配的请求和回收系统释放的内存区。内存管理策略有三种：,放置策略,决定内存中放置信息的区域（或位置），即如何在若干个空闲区中选择一个或几个空闲区的原则；,调入策略,决定信息装入内存的时机，有两种：在用户请求时调入，称为请调；根据某种算法，确定系统将要使用的信息，并在执行前预先调入内存，称为预调 ；,淘汰策略,当内存不足时，决定将某些信息调出内存的策略 。,分区存贮管理,固定分区分配,动态分区分配(p96),分区分配放置策略,合适的概念,首次适应算法,最佳适应算法,最坏适应算法,碎片问题（紧缩）,存储保护方法,上下界防护,基址、限长寄存器保护,存储保护,两种存储保护技术的区别,1、寄存器的设置不同；,2、判别式中用的判别条件不同,上下界寄存器保护法用的是物理地址,基址、限长寄存器保护法用的是程序的逻辑地址,对于合法的访问地址这两者的效率是相同的，对不合法的访问地址来说，上下界存储保护浪费的CPU时间相对来说要多些。,多道程序对换技术,以用户为单位独占内存,如何减少对换信息量？,部分换出与恢复,提供虚存,问题的提出,物理存储器的结构是个一维的线性空间，容量是有限的。,用户程序结构：,一维空间,一个用户程序就是一个程序，并且程序和数据是不分离的；,二维空间,程序由主程序和若干个子程序（或函数）组成，并且程序与数据是分离的；,n维空间,即一个大型程序，由一个主模块和多个子模块组成，其中，各子模块又由主程序和子程序（或函数）组成。,用户程序的大小，可能比内存容量小，也可能比内存容量大，有时候要大得多。,提供虚存,如何将与物理内存结构不同，且大于物理内存容量的用户程序装入运行？这就是提出研究虚拟存储器的原因，或称为虚拟存储技术发展的原动力。,提供虚存,虚拟存储器,为用户提供一种不受物理存储器结构和容量限制的存储器的技术称为虚拟存储器，或称虚拟存储技术。,它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间、乃至n维空间），并没有容量的限制。,现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。,虚拟存储器需要大容量的外存储器的支持，或称物资基础,。,虚拟存储器的基本特征,（1）,虚拟扩充,不是物理上，而是逻辑上扩充了内存容量,（2）,部分装入,每个作业（进程）不是全部一次性地装入内存，而是只装入其一 部分,虚拟存储器的基本特征,（3）,离散分配,每个作业（进程）装入内存的那部分不必占用连续的内存空间，而是“见缝插针”,虚拟存储器的基本特征,（4）,多次对换,在一个进程运行期间，它所需的全部程序和数据要分成多次调入内存,虚拟主存的优点,透明使用主存,方便存储保护,程序可浮动,充分利用主存,分页存贮管理,页式系统,页式地址变换,请调策略,淘汰策略,页式存储管理,页式系统应解决的问题,分区存储管理的主要问题是碎片问题。,在采用分区存储管理的系统中，会形成一些非常小的分区，最终这些非常小的分区不能被系统中的任何用户（程序）利用而浪费。,造成这样问题的主要原因是用户程序装入内存时是整体装入的，为解决这个问题，提出了分页存储管理技术。,分页的概念,程序地址空间分成大小相等的页面，同时把内存也分成与页面大小相等的块，当一个用户程序装入内存时，以页面为单位进行分配。页面的大小是为2,n,通常为1KB，2KB，nKB等。,页式地址变换,页表：虚页-物理块对照表,虚地址结构,：页号+偏移,页式地址变换,分地址-查页表-合地址,页式地址变换,虚地址结构(程序字),虚地址是用户程序中的逻辑地址，它包括页号和页内地址（页内位移）。,区分页号和页内地址的依椐是页的大小，页内地址占虚地址的低位部分，页号占虚地址的高位部分。,假定页面大小1024字节，虚地址共占用2个字节(16位),页号 页内地址（位移量）,P W,15 10 9 0,页式地址变换-,虚地址结构,页式地址变换,页式地址变换,页式地址映射,虚地址（逻辑地址、程序地址）以十六进制、八进制、二进制的形式给出,将虚地址转换成二进制的数；,按页的大小分离出页号和位移量（低位部分是位移量，高位部分是页号）；,根据题意产生页表；,将位移量直接复制到内存地址寄存器的低位部分；,以页号查页表，得到对应页装入内存的块号，并将块号转换成二进制数填入地址寄存器的高位部分，从而形成内存地址。,页式地址变换,页式地址映射,虚地址以十进制数给出,页号虚地址页大小,位移量虚地址 mod 页大小,根据题意产生页表；,以页号查页表，得到对应页装入内存的块号,内存地址块号页大小位移量,请调策略,问题的提出,在页式存储管理提高了内存的利用效率，但并不为用户提供虚存，换句话说，当一个用户程序的页数大于当前总空闲内存块数时，系统就不能将该程序装入运行。即用户程序将受到物理内存大小的限制。为了解决这个问题，人们提出请求分页存储管理技术。,请调策略,请求分页概念,请求分页技术当一个用户程序要调入内存时，不是将该程序全部装入内存，而是只装入部分页到内存，就可启动程序运行，在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将在外存相应的页调入内存，该程序继续运行,。,请求分页的基本思想,（1）,请求分页=分页+请求,逻辑空间分页 物理空间分块,页与块同样大 页连续块离散,用页号查页表 硬件做重定位,分 页,请求分页的基本思想,（2）作业部分装入内存,（3）作业所占的内存块不连续,（4）硬件通过页表生成访问内存的地址,请求分页的基本思想,（5）若发生缺页，则进行缺页中断处理，将该页调入内存,（6）利用快表可以加速地址转换,缺页中断处理：请调,为了实现请求分页技术，页表应增加相应的内容，反映该页是否在内存，在外存的位置，在内存的时间的长短等。,中断位,：,0 表示该页在内存，1示该页不在内存,引用位,：,0 表示最近没有进程访问，1示最近有进程访问,修改位,：,0 该页调入内存后没有修改 ，1页调入内存后修改过,缺页中断处理的硬件支持,采用相应技术加快页表的查询速度,在页式存储技术中，我们可看到每访问一次内存，就要做,两次访问内存,的工作，即，查页表时要作一次访问内存的工作，然后是访问程序要求访问的内存，这样，存取速度降低一倍，将会影响整个系统的使用效率。在早期的计算机系统中有的,采用联想存储器的技术来加快查表的速度，有的采用寄存器做页表,。,缺页中断处理的硬件支持,采用联想存储器加快页表的查询速度,快表。,使用快表的并行查找过程。,程序局部化与命中率问题。,缺页中断处理过程,分地址,取页号,查页表,缺页中断,找空闲块,淘汰块,读入页面,中断返回,硬件,软件,请求分页的性能分析,有效存取时间,缺页中断处理时间,有效存取时间正比于缺页的比率,为使速度下降控制在10%以内，缺页率不得超过0.00001,淘汰策略,物理页分配算法,置换算法,当要索取一页面并送入到全满的内存中时，必须把已在内存中的某一页淘汰掉。用来选择淘汰哪一页的规则叫做置换算法。,颠簸、抖动,几种置换算法,先进先出算法,先进入内存的页，先退出内存。,实质上是淘汰在内存驻留时间最长的页。,其理由是：最早调入内存的页，不再被使用的可能性比近期调入内存的大。,这种算法简单，实现容易。,几种置换算法,最佳算法,假定程序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）最小。,最佳算法：当要调入一新页而必须淘汰一旧页时，所淘汰的页是以后不再使用的，或者是以后相当长的时间内不会使用的。这种算法是不可能的。,几种置换算法,最久未使用淘汰算法（lRU算法）,当需要淘汰一页时，选择最长时间未使用的页。,如果某页被访问，它可能马上还要被访问；相反，如果某页长时间未被访问，它可能最近也不可能被访问。,算法的实现（软件）：设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。淘汰一页时，总是从栈底抽出一个页号，它就是最久未使用的。,算法的实现（硬件）：计数器,近似LRU算法：NUR,物理页分配算法,最少块数指令系统设计决定最少块数,全局分配与局部分配,等分法与比例分配法,工作集模型,时间局部化与空间局部化,工作集,DM，将出现抖动,工作集模型的实现,页式系统的存储保护,页式系统的存储保护的方法类似于基址限长存储保护，当地址映射机构分离出页号和页内位移后。,若0页号用户程序的总页数，则访问合法，否则访问越界。,页式系统的存储保护还包括存取控制。,在页表中增加存取控制位，表示该页的存取控制权限，如r表示可读，w表示可读可写，e表示可执行。,当有一程序访问该页时，系统就按存取控制位设置的权限实施存取控制。,UNIX S_5的存储管理,采用请求分页存储管理和对换技术,对换：map表,每次对换尽可能多的数据，不使用缓冲。,请求分页数据结构,淘汰进程,缺页处理,段式系统,一个用户程序往往由几个程序段（主程序、子程序和函数）所组成，当一个程序装入内存时，按段进行分配，每个段的大小是不相等的。,程序地址的组成：S：W,例:,S1：XXXX,S2：XXXX,S3；XXXX,段式系统,段式系统,以分区方式使用内存空间,支持虚拟存储：分段调入,快表的使用,动态连接技术,缺段中断与连接中断,段式保护与共享,段式虚拟存储的优点和缺点,段页式系统,在段式系统中，若段内分页，称为段页式系统。,段页式地址：,s p d,段页式地址转换：查段表 查页表 合地址,快表的使用,段页式系统是目前最好的内存管理方法,试分析段页式系统的优点与缺点,段页式系统,目前流行的UNIX系统采用这种存储管理的方式，一个进程的图象分为U区、共享正文区、用户栈区和数据区，各进程的各个区的大小是不相等的，只有U区的大小是相等的。这里的区类似于段。每个段又分成大小相等的页，内存的分配是以页为单位的。因此，在UNIX系统中存储管理（上下文，context）机构包括区表和页表。,