计算机操作系统原理讲义

作业：10%平时：20%期中考试：20%期末考试：50%日期周次讲课内容分章和分节的名称课内时数1第一章绪论41.1操作系统的历史1.2操作系统的概念1.3操作系统的功能2第二章操作系统用户界面23第三章进程管理3.1进程的概念3.2进程的描述3.3进程状态及其转换3.4进程控制3.5进程互斥3.6进程同步3.7进程通信3.8死锁问题3.9线程5实验一进程管理87第四章处理机调度24.1分级调度4.2作业调度4.3进程调度4.4调度算法4.5实时系统调度方法28实验二处理机调度49第五章存储管理85.1存储管理的功能5.2分区存储管理5.3覆盖与交换技术5.4页式管理5.5段式与段页式管理5.6局部性原理和抖动问题实验三存储管理4第六章文件系统86.1文件系统的概念6.2文件的逻辑结构与存取方法6.3文件的物理结构与存取设备6.4文件存储空间管理6.5文件目录管理6.6文件存取控制6.7文件的使用6.8文件系统的层次模型实验四文件管理6第七章设备管理88.1引言8.2数据传送控制方式8.3中断技术8.4缓冲技术8.5设备分配8.6I/O进程控制8.7设备驱动程序复习2硬件及固件(裸机)硬件及固件(裸机)1.操作系统的作用、分类2.处理机、作业、存储、设备、文件管理3.常用OS的知识、新型操作系统4.用户界面操作系统的英文名称为OperatingSystem,简称OS,它是计算机系统运行和工作必不可少的软件。无论是巨型机、大型机，不是中小型机，也无论是台式个人计算机，便携式微型机，还是连接多台计算机的计算机网络，都离不开操作系统。它构成了系统本身和作业赖以活动的物质基础和工作系统。)和软件(程序、数据、文档的统称)两部分组成的(图1.1)。其中软件部分又分为系统软件和应用软件。应用软件指的是为了某一类的应用而设计的程序，或用户为了解决某个特定问题而编制的程序操作系统、语言处理程序和常用的例行服务程序。操作系统是系统软件的基本部分。系统软件由计算机公司提供，面向机器本身，其算法和功能不依赖于特定的用户。它的主要任务是使得硬件所提供的能力可以得到充分的利用，支持用户应用软件的运行并提供恰当的服务。因此，系统软件的设计必须十分注意其正确性及效率。在计算机系统中，所有这些软、硬件资源(泛称资源)必须由一个统一的管理者来协调它们正确、可靠、高效地工作，这就是OS的使命。所以，如果将构成计算机系统的一切硬件系统和软件系统称为资源，则操作系统是控制和管理计算机硬件和软件资源，合理组织计算机工作流程以及方便用户的程序的集合。是最基本的系统软件，是硬件机器的第一级扩充(图1.2)。编辑软件，编译软件操作系统软件图1.1计算机系统的组成应用用户应用用户用户应用系统工具操作系统计算机硬件应用开发人员操作系统开发人员图1.2操作系统在计算机系统中的地位操作系统的地位：紧贴系统硬件之上，所有其他软件之下(是其他软件的共同环境)□有效性(系统管理人员的观点):管理和分配硬件、软件资源，合理地组织计算机4一、方便性(用户的观点):提供良好的、一致的用户接口，弥补硬件系统的类型和数量差别可扩充性(开放的观点):硬件的类型和规模、操作系统本身的功能和管理策略、(1)命令方式。这是指由OS提供了一组联机命令(语言),用户可通过键盘键入有关的操作系统的用户机器提供了操作系统的全部功能(系统调用、命令、作业控制语言等等),二、操作系统的OS的历史(形成和发展)用户同时使用不同的资源(例如外部设备、CPU等),既相对独立，又彼此协调。正是在这早期的计算机采用人工操作方式，由操作员将纸带(或卡片)装入纸带输入机(或卡片5输入机)等输入设备，通过输入设备将程序和数据输入计算机，当程序完成并人工取走纸带和计算结果后，才让下一用户上机操作。这种人工操作方式具有以下两个特点：(1)用户独占全机。一台计算机为一个用户独占，系统中的全部资源由他一人支配，因此用户可以较方便地使用各种资源，不会出现因资源已被其它用户占用而等待的现象。但资源(2)CPU等待人工操作。用户仅在上机时才能将纸带或卡片装入相应的输入设备，显然，充分，这在运行短程序时尤为突出。矛盾：①使用不方便；②串行操作可见，人工操作方式严重地降低了资源的利用率，此即所谓的人-机矛盾。随着CPU实现作业的自动过渡，因此出现了成批处理。2.早期批处理阶段在计算机发展的早期阶段，用户上机时需自己建立、运行作业，并最后作结尾处理。为用户作业合成一个作业执行序列时，监督程序自动地依次执行。早期的批处理可分为两种方设备是和主机直接相连打交道的。作业的执行过程大致为：②作业被做成穿孔纸带或卡片；③操作员有选择地将若干作业合成一批，通过输入设备(输入机或读卡机)把它们存入④监督程序读入一个作业(若系统资源能满足该作业要求);⑤从磁带调入汇编程序或编译程序，将用户作业源程序翻译成目标代码；⑥连接装配程序把编译后的目标代码及所需的子程序装配成一个可执行程序；⑧执行完毕，由善后处理程序输出计算结果；⑨再读入一个作业，重复步骤⑤-⑨;一批作业完成，返回到③,处理下一批作业。早期的联机批处理系统实现了作业的自动过渡，同手工操作阶段相比，计算机的使用效率提高了。但在这种批处理系统中，作业的输入输出是联机的，也就是说作业从输入机到磁带，由磁带调入内存，以至结果的输出打印都是由中央处理机直接控制的。在这种联机操作方式下，虽然解决了作业自动转接，从而减少作业建立和人工操作时间。但是随着处理机速度的不断提高，处理机和输入/输出设备之间的速度差距就形成了一对矛盾。即在执行结果的输出过程中，主机CPU仍处于停止等待状态，这样慢速的输入/出设备和快速主机之间仍脱机批处理系统由主机和外围机(卫星机)组成。为了解决输入机的低速问题，可将用户程序和数据，在一台外围机的控制下，预先从低速设备输入到磁带或磁盘上。当CPU需要这些数据时，再直接从磁带或磁盘上高速地调入内存。这样就大大地加速了输入过程。类似地，当CPU需要输出时，可立即将输出数据送到磁带或磁盘上，以后再在外围机的控制下，把磁带或磁盘上的处理结果通过相应的输出设备输出。这对程序的执行来说，显然是大大地加速了数据的输出过程。脱机输入输出过程如下图所示。脱机输入输出：程序和数据的输入输出都是在外围机的控制下完成的，或者说它慢速输入设备外围机们是脱离主机进行的，故称脱机输入输出。在早期的脱机I/0方式中，事先把一批作业输入到磁带上，这意味着作业的处理是成批的；为使这一批作业能自动连续地进行处理，在系统中还需配置监督程序，在它的控又把控制权还给监督程序，又由监督程序将第二个作业装入内存。这样自动地一个作业一个批处理系统是在解决人机矛盾和CPU与I/0速度不匹配的矛盾的过程中发展起来的，或者说，批处理技术旨在提高系统的吞吐量和资源的利用率。该系统的主要特征：①自动性(减少了手工操作)。实现了作业的自动过渡，改善了CPU与I/O的使用情况，提高了计算系统的处理能力。②顺序性。磁带上的各道作业是顺序地进入内存的，各道作业完成的顺序与它们进入内存的顺序之间，在正常情况下应当完全相同，亦即先调入内存的作业先完成。③单道性。在某一时刻，内存中仅有一道程序在运行，仅当该程序完成或发生异常情况时，才调入后继程序进入内存运行。①平均周转时间长。所谓周转时间是指从作业进行系统开始，到作业完成所经历的时间。由于在批处理系统中，一个作业一旦运行便将运行到完成，这必然使许多短作业的周转时②不能提供交互能力，用户使用机器不方便；③CPU利用率较低(单道、串行)。在进行批处理过程中，监督程序、系统程序和用户程序之间存在着一种调用关系，任何一个环节出了问题，整个系统都会停顿；用户程序也可能会败坏监督程序和系统程序，这时，只有操作员进行干预才能恢复。后来，通道和中断技术的使用，导致了操作系统进行执行系统阶段。所谓执行系统即是常驻内存的监督程序，不过其功能扩大了，它不仅要负责作业运行的自动调度，而且还要提供输入输出控制功能。但是，这时计算机系统运行的特征仍是单道顺序地处理作业，即用户作业仍然是一道一道作业顺序处理。那么，可能会出现两种情况：一是对于以计算为主的作业，输入输出量少，外围设备空闲(计算型作业);二是对于以输入输出为主的作业，主机又会造成空闲(I/O型作业)。这样，总的来说，计算机资源使用效率仍然不高。因此操作系统进入了多道程序阶段：多道程序合理搭配交替运行，充分利用资源，提高效率。*多道程序设计技术及多道批处理系统在早期批处理系统中，内存只存放一道程序，称为单道运行。这种系统的管理很简单，不存在高度管理的问题。但是这种单任务系统，对CPU的利用率极低。其原因是CPU经常要与外界交换数据，即进行输入/输出操作。而CPU的速度很快，外部设备的速度很慢，因此CPU除了花很少时间执行程序外，大部分时间在等待外设的输入/输出操作。亦即当该程序进行I/0操作时，CPU便处于等待I/0完成状态，致使CPU空闲。为提高CPU的利用率而引7入多道程序技术，所谓多道程序技术是指"将一个以上的作业放在内存并允许它们交替执行，共享系统中的各种资源"。当正在执行的程序因I/0而暂定执行时，CPU立即转去执行道程序设计技术提高了CPU的利用率，同时也显著改善了内存和I/0设备的利用率，从而也使系统的吞吐量获得大幅度提高。允许多道程序运行的系统称为多道程序系统。现代操作系统一般都基于多道程序设计技术。系统吞吐量(systemthroughput):指系统在单位时间内所完成的作业数目。②无序性。多个作业完成的先后顺序与它们进入内存的顺序之间，并无严格的对应关系，即先进入内存的作业可能较后甚至最后完成，而后进入内存的作业又可能先完成。④宏观上并行、微观上串行。进入系统的几道程序都处于运行过程中，即它们先后开始了各自的运行，但都未运行完毕；实际上，各道程序轮流地使用CPU交替执行。在批处理系统中采用多道程序设计技术，就形成了多道批处理系统。要处理的许多作业存放于外部存储器中，形成作业队列，等待运行。当需要调入作业时，将由操作系统中的作业调度程序对外存中的一批作业，根据其对资源的要求和一定的调度原则，调几个作业进入内存，让它们交替运行。当一个作业完成后，再调入一个或几个作业。这种处理方式，在内存中总是同时存在几道程序，系统资源得到比较充分的利用。多道程序及执行程序(常驻内存、功能扩大了的监控程序)的出现，标志着操作系统2.分时系统批处理方式下用户要得到自己的计算结果，必须等到系统处理完一批作业之后。这样虽然提高了CPU和系统设备的利用率，却给用户带来了很大的麻烦。为了解决两者的矛盾，引在计算机系统中，两个或两个以上事件按时间划分轮流地使用计算机系统中的某一资分时系统的实现一般采用时间片轮转的办法，使一台计算机同时为多个终端用户服务。若干个用户通过各自的终端，同时使用同一台计算机系统，但他们彼此之间并不感觉时间片是分时的时间单位。多个用户按时间片轮转，即每道程序一次运行一个时间片，用户通过终端与计算机发生交互作用，他们彼此一般不感觉到有别的用户存在，好象实现分时系统的关键是用户能与自己的作业交互作用，即用户在自己的终端上键入命令以请求系统服务，系统应能及时接收和及时处理该命令，并将处理结果立即返回给用户。此后，用户又可键入下一条命令，这样便实现了人-机交互。多道批处理系统和分时系统的出现标志着操作系统的基本形成。所谓"实时",是表示"及时",而实时系统是指系统能及时响应外部事件的请求在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。实时系统通常是在一个特定的应用中作为一种控制设备来使用的。实时系统的一个主要特点在于有严格的时间限制，即每一个信息接收、分析处理和发送的过程必须在规定的时间范围内完成。这就要求系统的一切活动都必须在一个严格的计时程序的控制下运行，中断信号对系统具有支配作用，而不象批处理系统(时间限制弱)和分时系统(时间限制不严格)那样在作业调度时较少地考虑时间上的要求。实时系统往往具有一定的专用性。与批处理系统、分时系统相比，实时系统的资源利用率可能较低。(1)实时控制系统。通常是指以计算机为中心的生产过程控实时采集现场数据，并对所采集的数据进行及时处理，进而自动地控制相应的执行机构，使某些参数(温度、压力、方位等)能按预定的规律变化，以保证产品质量和提高产量。(2)实时信息处理系统。计算机及时接收从远程终端发来的服务请求，根据用户提出的问题，对信息进行检索和处理，并在很短的时间内为用户做出正确的回答。典型的实时信息处理系统有：飞机订票系统、情报检索系统等。实时系统与分时系统的比较：交互能力响应时间分时系统通用强以用户能容忍的限度有一定要求实时系统专用弱严格的时限高要求实时处理是以瞬间响应为特征的。"实时"二字的含义是指计算机对于外来信息能够以足够快的速度进行处理，并在被控对象允许的时间范围内作出快速反应，其响应时间要求在称级、毫秒级甚至微秒级。实时系统的出现和应用的日益广泛，以及多道成批系统和分时系统的不断改进，使操4.新一代操作系统随着计算机技术的飞速发展，出现了智能计算和网络计算，并随之出现了微机操作系统、网络操作系统(NetworkperatingSystem)和分布式操作系统(DistributedOperatingSystem)等新型操作系统。在这个阶段，计算机系统和操作系统的发展都异常迅速，操作系统技术逐渐成熟，新的技术不断引入，具有开放环境、高效数据处理、友好人机界面、强功能开发支持，以及网络互连与通信功能、多媒体处理功能等。前面所介绍的三种基本OS,它们各有自己的特征，如批处理系统具有成批处理的特征，分时系统具有交互特征，实时系统具有实时特征，但它们都具有以下四个基本特征。并发性是指在某一时间间隔内，有若干个事件发生。并行性—在某一时刻，可能有若干事件发生。并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内，宏观上有多道程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能分时地交替执行。程序的并发执行能有效地改善资源利用率和提高系统的吞吐量，但显然会使操作系统由于增加了控制和管理各种并发活动的功能应该指出，通常的多个程序是不能并发执行的。系统必须分别为每个程序建立进程，以随时记录各个程序由于并发执行而形成的"停停走走"的状态中的信息，以备该进程再次获得处理机时，能从中取得现场信息而继续运行下去。所谓进程，简单地说，是指在系统中能独立运行和作为资源分配的基本单位，多个进程之间可以并发执行以及交换信息。有关进9(1)互斥共享——是指仅当一个作业(进程)使用完某资源并释放后，其他作业才能使用。通常，人们把在一段时间内只允许一个进程访问的资源称为"临界资源",如打印机、磁带(2)同时共享——指允许在一段时间内，若干个作业同时对某一资源进行访问，典"并发"和"共享"是操作系统的两个最基本特征，它们互为存在条件，即资源共享显然，如果n为某一物理设备所对应的虚拟的逻辑设备数，则虚拟设备的速度必然是物理设备速度的1/n。不确定性有两种含义：(1)程序执行的结果是不确定的，即对同一程序，使用相同的(1)CP/M:CP/M是ControlProgramMonitor的缩写。它是在1975年由DigitalResearch公司率先推出的、带有软盘系统的8位微机操作系统；Microsoft公司开发的MS-DOS操作系统。该操作系统在CP/M的基础上进行了较大的统也就成为事实上的16位微机单用户单任务操作系统的标准。(1)0S/2:由于MS-DOS的内存有效地址长度为20位，故寻址范围为1MB,而IBM是32位。*分布式操作系统批处理系统是在解决人一机矛盾和CPU与I/0设备速度不匹配这种矛盾的过程中，亦设备以及软件的利用率，该技术允许将多个作业同时放入内存，使它们交替执行，共享系统中的资源。将多道程序设计技术引入批处理系统，便形成多道批处理系统。操作系统的基本类型有以下三类：(1)批处理系统。该系统最重要的特征是系统自动地对作业进行处理；其主要优点是系统吞吐量大和资源利用率高；其缺点是平均周转时间长，和用户不能与自己的作业进行对话。(2)分时系统。该系统最主要的特征是用户可以与系统及自己的作业进行交互作用，因而方便了用户对程序的开发与调试。分时系统的四个基本特征是同时性、独占性、及时性和交互作用性。(3)实时系统。该系统最主要的特征是能及时地对特定输入做出反应，来控制相应的对象。它也具有分时系统的四个基本特征，但它对及时性的要求更严格，而其交互作用能力却较差。操作系统具有如下特征：(1)并发性。在某段时间内，有多道程序宏观上在同时运行，但在单处理机系统中，每一时刻仅能执行一道程序，故微观上，这些程序是在交替执行。(2)共享性。资源共享是指系统中的资源已不再为某个程序所独占，而是由多个用户共同使用。有两种实现资源共享的方式；(3)虚拟性。所设虚拟是指把一个物理上的实体变为若干个逻辑上的对应物。例如，多道程序技术可将一台物理CPU虚拟为多台逻辑CPU;(4)不确定性。作为操作系统特征的不确定性，是进程以异步方式运行。即进程是以一种人们不可预知的速度向前推进，但其运行结果总是确定的。从资源管理观点看，操作系统具有五大功能：(1)存储器管理。负责内存的分配、保护和扩充，以及进行逻辑地址到物理地址的转换；(2)处理机管理。处理机管理可归结为进程管理，用于实现进程的控制、同步、通信和调度；(3)设备管理。该功能包含缓冲管理、设备分配、设备处理以及虚拟设备等功能；(4)文件管理。实现对文件的存储空间、目录、读/写等的管理，并对文件提供保护；(5)作业管理。对作业进行调度和控制。由于操作系统的发展所形成的新的操作系统类型有：(1)微机操作系统。其中最有代表性的单用户、单任务微机操作系统是MS-DOS;多用户多任务的操作系统是UNIX。(2)多处理机操作系统。它是配置在多处理机系统中的操作系统。(3)网络操作系统。该操作系统在各主机操作的协助下，用户管理网络通信和资源共享，协调各主机上任务的运行。(4)分布式操作系统。该操作系统用于直接对系统中的各类资源进行管理，采用分布式通信和同步方式实现各主机上任务的并行执行。第二章作业管理统命令接口可完成用户作业的组织和控制。本章重点：作业的类型和作业控制、用户与操作系统之间的作业处理接口、作业的状态、作业调度。用户向系统注册登记，提交作业后，什么时候得以真正进入系统，由谁来为其创建进程呢?这是作业调度的任务。作业调度又称高级调度或宏观调度。作业调度程序的主要功能是：根据计算机管理人员所制定的规则(如作业优先数大小，要求资源的品种和数量、系统的均衡性等),从后备作业队列上选择一个或多个作业置于“运行”状态，并为它们分配必要的资源(如主存空间、外部设备等),建立相应的用户作业进程和为其服务的系统进程(如输入、输出进程),最后将它们的程序段调放主存以等待进程调度程序的调度。显然，由作业调度程序选择到的作业只有资格获得处理机，但不一定立刻就能占有它并在其上运行。至于一个已被调度程序调度到的作业，什么时候能真正在处理机上运行，则取决于"进程调度"所遵循的调度策略和作业性质。进程调度又称微观调度或低级调度。作业调度与进程调度之间的关系，可打个比喻来说明，前者像竞赛的"协调人",它能确定参加比赛(竞争处理机)的全体"选手",而后者像比赛场上的“裁判",决定哪个"选手”将取得胜利(获作业管理的主要功能是对用户作业进行合理调度，以提高系统的吞吐量或缩短作业的周转时间，并提供用户与操作系统的接口，以方便用户对自己的作业在整个运行过程中进行控制。一、作业的定义作业：作业是由用户提交给系统处理的一个基本任务(从用户目光看),它是由用户程序、数据以及对程序运行进行控制和处理的有关信息所组成(从系统角度看)。通常，一个作业又可分为若干个顺序处理的作业步，例如，在对一个用某高级语言编制的源程序进行调试处理时，往往要经过下述几大步骤：①编辑——这是调用编辑程序对指定的源程序文件进行输入或修改；②编译——对编辑后所得的文件进行编译、链接，以获得可执行的目标代码；③运行——对编译、链接后的程序进行运行，完成预期功能。作业步：作业由不同的顺序相连的作业步组成。作业步是在一个作业的处理过程中，计算机(1)用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。作业步：(2)系统的观点(批处理):作业由程序及数据(作业体)和作业说明书(作业控制语言)-—针对作业进行资源分配(1)计算型作业指任务中包含大量的计算，而其I/0较少的作业，通常的科学计算便属(1)批量型作业●脱机作业利用作业说明书实现作业的自动控制。在整个作业的运行过程中，只需根(2)交互型作业终端型作业也称交互型或会话型作业。这一类作业是用会话语言(如BASIC语言)系统作业称为"后台"作业。作业调度优先照顾终端型作业，即给它们较高的优先数。在终端服入(提交)"、"收容(后备)"、"执行"和"完成(终止)"四个阶段，相应地，作业就有四种状态(注：有些教材上认识作业只有后三种状态):1.进入状态(提交状态):2.后备状态(收容状态):3.3.塞"三个基本状态。4.4.就绪结束执行程序(进程)。此外，这个接口还为程序正常或异常终止给出适当的响应。当一个程序正在用不同，系统调用是通过中断方式转向相应子程序的，它工作在核心态(即特权方式),而系统调用是操作系统提供给软件开发人员的唯一接口，开发人员可利用它使用系统功能。OS核心中都有一组实现系统功能的过程(子程序),系统调用就是对上述过程的调用。用户程序陷入处理机构系统子程序入口地址表入口地址表1)保护处理机现场2)取系统用户功能号并寻找子程序入口B)恢复处理机现场并返回反系统调用图1系统调用的处理过程(1)设置系统调用号和参数，然后执行trap指令。□调用号作为指令的一部分(如早期UNIX),或装入到特定寄存器里(如：DOSint口参数装入到特定寄存器里，或以寄存器指针指向参数表(内存区域)。(2)人口的一般性处理。□保护CPU现场，改变CPU执行状态(处理机状态字PSW切换，地址空间表切换)(4)恢复CPU现场，将执行结果装入适当位置(类似于参数带入),执行中断返回指令(1)内部命令。这类命令的特点是程序短小，使用频繁。因此，它们在系统初启时就(2)外部命令。这类命令的程序较长，且各自独立地作为一个文件而驻留在磁盘上，§3.1(进程概念的引入)前趋图和程序的执行647有向无环图图中的每个结点可以表示一条语句、一个程序段或进程，结点间的有向边表示两个结点之间存在的偏序或前趋关系“→”。其中→={(P,P₃)|P₁必须在P;开始之前结束}。如果(P,P;)∈→,可写成P→Ps,称P:是P;的直接前趋，而P;是P₁的直接后继。在前趋图中，象结点1那样没有前趋的结点称为初始结点；象结点9那样没有后继的结点称为终止结点。此外，每个结点还具有一个重量，它可用该结点所含的程序量或结点的执行时间来计量。上图中有前趋关系如下：P₁→P₂,P₁→Ps,P₁→P,P₂→P₅,P₃→P₅,P→P₆,P→P-,P₅→P,P₆→P,P={P₁,P₂,P₃,P₄,Ps,P₆,P-,→={(Pi,P₂),(P₁,Ps),(Pi,P4),(P2,P₃),(Ps,Ps),(P,P₆),(P,P-),(Ps,P₃),PsPaPg三、程序的并发执行与特征1.程序的并发执行虽然对于一个程序的输入、计算和打印必须顺序执行，但在对一批程序进行处理时，则可使上述三种操作并发执行，以提高系统的吞吐量。例如，输入程序在输入第三个程序(I₃)的同时，计算程序可以正在对第二个程序进行计算(C₂),而打印程序正在打印第一个程序程序段并发(共行)执行的有向图程序的并发执行(concurrence)指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发是指宏观上在一段时间内有多道程序在同时运行，而微观上这些程序是在交替地执行。(并行(parallel)指两个或多个事件在同一时刻进行，例如，在具有中断的计算机系程序的并发执行虽然提高了系统的吞吐量，但也产生了下述一些新特征：2.程序并发执行所带来的影响(特征)(1)间断性程序在并发执行时，由于它们共享资源、或为完成同一项任务而相互合作，致使在并发程序这间形成了相互制约关系，例如，在上图中的I、C有P是三个相互合作的程序，当计算程序完成C-的计算后，若输入程序尚未完成I;的处理，则计算程序就无法进行C;的处理，致使第i个程序暂停运行，一旦使之暂停的因素消失后(即I:)处理已完成),第i个程序又可恢复执行。简言之，相互制约将导致并发程序具有"执行一暂停一执行"这种间断性的活动规律。(2)失去封闭性程序在并发执行时，是多个程序共享一台机器，因而机内资源的状态将由多个程序来改变，因此使程序的运行已失去了封闭性，这样，某程序在执行时，也必然会受到其他程序的影响，例如，当处理机资源被其他程序占有时，某程序必须等。(3)不可再现性程序在并发执行时，也将失去其可再现性。例如，有两个循环程序A和B,它们共享一个变量N。程序A每执行一次时都要做N:=N+1操作；程序B则每执行一次都要执行print(N)操作，然后再将N置成"0"。如下程序段所示：remainderofprogramAremainderofprogramB程序A和B以不同的速度运行，这样，可能发生下述三种情况(假定某时刻变量N的值为n)。在print(N)和N:=0之前，此时得到的N值分别为n+1,n+1,0在print(N)和N:=0之后，此时得到的N值分别为n,0,1在print(N)和N:=0之间，此时得到的N值分别为n,n+1,0上述情况说明，程序在并发执行时，已失去了封闭性，其计算结果已与并发程序的执行速度有关，从而使程序失去了可再现性，即经过多次执行后，得到的结果各不相同。程序并发执行时的不可再现性是绝对不允许的。为此，应采取某种措施使并发程序保持其“可再现性”。1966年Bernstein提出了两相邻语句(相邻程序段)Pi、P₂可以并发执行的条件。仅当满足该条件时，并发执行的程序才可能保持"可再现性"。这个条件也称为程序加以控制和描述，而专门为之配置了一个称为"进程控制块"的数据结构。其中，存放了进程标识符、进程运行的当前状态、程序和数据的地址，以及能保存该程序运行时CPU进程通常被定义为：进程是可并发执行的具有一定功能的程序段在给定数据集上的一立进程)是不能并发执行的(由于程序不反映执行过程)。(1)联系。程序是构成进程的组成部分之一，一个进程的运行目标是执行它所对应的数据和进程控制块三部分组成的。(2)区别。程序是静态的，而进程是动态的。进程既是程序的执行过程，因而进程是有生命期的，有诞生，亦有消亡。因此，程序的存在是永久的，而进程的存在是暂时的，动一个编译进程在运行时，要执行词法分析、语法分析、代码生成和优化等几个程序，或者一个编译程序可以同时生成几个编译进程，为几个用户服务。进程具有创建其他进程的功能，被创建的进程称为子进程，创建者称为父进程，从而构成进程家族。二、进程的基本状态及其转换1.进程的基本状态由进程运行的间断性，决定了进程至少具有下述三种基本状态：①就绪状态当进程已分配到除CPU以外的所有必要的资源后，只要能再获得处理机，便能立即执行，把进程这时的状态称为就绪状态。在一个系统中，可以有多个进程同时处于就绪状态，通常把它们排成一个队列，称为就绪队列。②执行状态指进程已获得处理机，其程序正在执行。在单处理机系统中，只能有一个进程正在执行状态。③阻塞状态进程因发生某事件(如请求I/0、申请缓冲空间等)而暂停执幌行时的状态，亦即进程的执行处于受到阻塞，故称这种暂停状态为阻塞状态，有时也称为"等待"状态，或"睡眠"状态。通常将处于阻塞状态的进程排成一个队列，称为阻塞队列。2.进程状态的转换处于就绪状态的进程，在进程调度程序为之分配了处理机之后，便由就绪状态转变为执行状态。正在执行的进程也称为当前进程。如果因时间片已完而被暂停执行时，该进程将由执行状态转变为就绪状态；如果因发生某事件而使进程的执行受阻(例如，进程请求访问某临界资源，而该资源正被其他进程访问),使之无法继续执行，该进程将由执行状态转变为阻塞状态。下图给出了进程的三种基本状态及各状态之间的转变。进程的三种基本状态及其转换需要说明的是，处于执行状态的进程因等待某事件而变为阻塞状态时，当等待的事件发生之后，被阻塞的进程并不恢复到执行状态，而是先转变到就绪状态，再由调度程序重新调度执行。原因很简单，当该进程被阻塞后，进程调度程序会立即把处理机分配给另一个处于1.进程控制块的作用为了描述和控制进程的运行，系统为每个进程定义了一个数据结构，该数据结构被称为进程控制块PCB(ProcessControlBlock)。所谓系统创建一个进程，就是由系统为某个程序设置一个PCB,用于对该进程进行控制和管理。进程任务完成，由系统收回其PCB,该进程便消亡。系统将根据某PCB而感知相应进程的存在，故说PCB是进程存在的唯一标志。2.进程控制块中的内容PCB中包含了进程的描述信息和控制信息。下图示出了PCB的内容。主要有：进程标识符现行状态现场保留区程序与数据地址互斥与同步机构进程通信机构进程优先数资源清单链接字家族联系(1)描述信息：信息量的多少依赖于OS的设计者。如：①进程标识符用于唯一地标识一个进程。*内部标识符在所有操作系统中，都为每一个进程赋予一个唯一的数字标识符，它通常是一个进程的序号，设置内部标识符主要是为了方便系统使用；*外部标识符它由创建提供，通常是由字母、数字所组成，往往是由用户(进程)在访问该进程时使用。②家族关系用于说明本进程与其它家族成员之间的关系。例如，指向父进程及子进程的针。因此，PCB中应有相应的项描述其家族关系。(2)现场信息信息量的多少依赖于CPU的结构①现行状态说明进程的当前状态，以作为调度程序分配处理机的依据。当进程处于阻塞状态时，要在PCB中说明阻塞的原因；②现场保留区用于保存进程由执行状态变为阻塞状态时的CPU现场信息。例如，程序状态字、通用寄存器、指令计数器等的内容；③程序和数据地址该进程的程序和数据存放在内存或外存中的地址。用以把进程控制块与其程序和数据联系起来。(3)控制及资源管理信息①进程的优先级表示进程使用CPU时优先级别的一整数。优先级高的进程可优先获得CPU;②互斥与同步机构实现进程间的互斥与同步时所必须的机构。例如，信号量或锁等；③资源清单它列出了进程所需资源及当前已分配到的资源；④链接字也称为进程队列指针，它给出了本进程所在队列中的下一个进程的PCB首址。总之，进程控制块PCB是系统感知进程存在的唯一实体。通过对PCB的操作，系统为有关进程分配资源从而使得有关进程得以可能被调度执行；而完成进程所要求功能的程序段的有关地址，以及程序段在进程过程中因某种原因被停止执行后的现场信息也都在PCB中。最后，当进程执行结束后，则通过释放PCB来释放进程所占有的各种资源。数据程序和与进程相关联的程序内存区程序-记录进程的有关信息(标识信息、状态信息、调度信息、通讯信息，占用资源信息，-标志进程的存在(与进程同时建立/撤消)。特定功能的程序段(内核)来创建、撤消进程以及完成进程各状态间的转换，从而达到多进1.系统态(核心态、管态)计算机的一种工作方式，在此方式下，可以执行任何指令，2.用户态(目态)计算机的另一种工作方式，在此方式下，不允许执行特权指令，只允6.内核的基本功能(1)中断处理。这是操作系统中内核的最基本功能，也是整个操作系统赖以活动的基础。通常，内核只对中断进行"有限的处理",然后便转由有关进程继续处理；(2)进程管理。进程管理的任务有四个：进程的建立和撤消；进程状态的资源→初始化PCB→插入就绪队列找出被撤消进程的PCB→该进程若正在执行，则终止该进行的执行→该进程若有子进程的PCB从所在队列(或链表)中清除，放回到空闲PCB队列。故而应先立即停止执行，把进程控制块中的现行状态由"执行"改为"阻塞",并将它插入到相同事件的阻塞(等待)队列，最后，转进程调度程序进行重新调度，将处理机分配给另一关进程(比如，用完并释放了该I/0设备的进程)调用唤醒原语weakup(),将等待该事件的进程唤醒。唤醒原语的操作有：先把被阻塞进程从等待该事件的阻塞队列中移出，将其从等待队列中摘下被唤醒进程→置进程的状态→将被唤醒进程送入就绪队列→转进程B提供数据。当该缓冲空时，计算进程B因不能获得所需数据而阻塞，当进程A把数据送入缓冲时，便将B唤醒；反之，进程A因不能再向缓冲区投放数据而阻塞，当进程B将缓冲区内数据取走时唤醒A。可见，诸进程在并发执行时，必须按照一定的次序执行。进程同步的定义如下：进程同步指多个相关进程在执行次序上的协调。用于保证这种关系的相应机制称为进计算进程不能开动计算；同样，若计算进程未从缓冲区中取走数据时，输入进程不能再启动下一次的输入。进程互斥也可被称作是一种特殊形式的同步。1.临界区(criticalsection)*临界资源：一次仅允许一个进程使用的资源。例如，有两个进程共享一个变量count:(R1和R2是处理机中的寄存器):当两个进程按下述顺序执行时但若P1和P2按另一种顺序对count进行修改R2:=R2+1;虽然P1和P2都各自对count作了加count:=R2;1操作，但最后的count却只增加了1。亦即其结果使count增加了2;发生了与执行顺序有关的错误。为了预防这种错误，对变量count应按临界资源处理，即令P1和P2互斥地使用count。进程中访问临界资源的那段代码称为临界区。为了实现对临界区的互斥访问，应保证诸进程互斥地进入自己的临界区。为此，每个进程在进入其临界区前，必须先提出申请，经允许后方可进入。称用以实现此请求的代码段为进入区。显然，在临界区后还应跟上一段退出区。进程代码中的其它部分称为剩留区。这样一个循环进程可描述为2.进程互斥不允许多于一个事件在同一时刻发生。亦即指在多道程序环境下，每次只允许一个进程对临界资源进行访问(不允许多于一个事件在同一时刻发生)。为此必须使诸进程互斥地进入自己的临界区。诸进程对临界资源的访问必须互斥。我们把每个进程中访问临界资源的那段代码称为临界区。显然，若能保证诸进程互斥进入自己的临界区，便可实现它对临界资源的互斥访问。3.同步机制应遵循的准则(1)空闲让进临界资源空闲时，允许一个请求进入临界区的进程立即进入自己的临界区，(2)忙则等待当临界资源正被访问时，其他试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。(3)有限等待对要求访问临界资源的进程，应能在有限的时间内进入自己的临界区，以unlock(key[S])unlock(key[进程已将key[S]的值置为1,也就是开锁状态，从而进程PA又可进入临界区S。只有在进singal(S).*利用信号量实现互斥(2)记录型信号量机制value:integer;L:listofprocess;ifS.value<0thenblock(SifS.value≤thenweakup号量链表中阻塞进程的数目。每次V操作，表示释放一个单位资源，故进行ifcount:thendestroyCPifcount:thendestroyIOP同步算法保证了两个进程按照计算一打印一计算一打印的次序执行。更具体地说：(1)当计算进程未把计算结果放入缓冲时，打印进程不能执行；(2)打印进程未把数据从缓冲区取走，计算进程不能执行。为互斥信号量，其取值范围为(1,0,-1);(这是记录型信号量时的值)。其中mutex=1表示进程1、进程2都未进入类名为S的临界区，mutex=0表示进程1或进程2已进入类名为S的临界区，sem=-1表示进程1和进程2中，一个进程已进入临界区，而另一个进程等待进入临界区。由此可见，在记录型信号量机制中，如果S.value的初值为1,表示只允许一个进程访问临界资源，此时的信号量便转化为上述互斥信号量。②P(mutex)和V(mutex)必须成对地出现。P、V操作是不可分割的。P、V操作"不可分割"的含义是指在同一个信号量上不能同时执行一个以上的P或V操作，亦即一个P或V操作的执行必须在另一个操作执行完毕以后进行，否则会产生与时间有关的错误。缺少P(mutex)将会引起系统混乱，不能保证对临界资源的互斥访问；而缺V(mutex)将会使该临界资源永久不被释放，从使而因等待该资源而阻塞的进程不再被唤醒。这是最著名的进程同步问题。常用于检验进程同步机制。它描述了一组生产者向一组消费者提供消息(message),它们共享一个有界缓冲池(bounded-bufferpool),生产者向其中投放消息，消费者从中取得消息。生产者一消费者问题是许多相互合作进程的一种抽象。例如，在输入时，输入进程是生产者，计算进程是消费者；在输出时，计算进程是生产者，打印进程利用信号量来解决生产者-消费者问题。假定缓冲池中具有n个缓冲区，每个缓冲区存放一个消息，可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。又假定这些生产者和消费者互相等效，只要缓冲池未满，生产者便可将消息送入缓冲池；只要缓冲池未空，消费者便可从缓冲池取走一个消息。生产者一消费者问题可描述如下：在生产者一消费者问题中应注意：●在每个程序中用于实现互斥的P(mutex)和V(mutex)必须成对出现。●对资源信号量empty和full的P、V操作同样需要成对出现，但它们分别处于不同的程序中，P(empty)在计算进程中，V(empty)则在打印进程中，计算进程若因执行P(empty)而阻塞，则以后将由打印进程将它唤醒。●在每个程序中的P操作顺序不能颠倒。应先执行对资源信号量的P操作，然后再执行对互斥信号量的P操作，否则可能引起进程死锁。读者一写者问题：问题：一数据文件或记录可被多个进程共享，其中有些进程要求读，而另一些进程要求写或修改。把只要求读的进程称为"读者",其它进程称为"写者"。允许多个读者同时读一个共享对象，但绝不允许一个写者和其它进程(读者或写者)同时访问共享对象，因为这种访问将违反Bernstein条件。所谓"读者一写者问题",是指保证一个写者与其它进程互斥地访问共享对象的同步问题。读者一写者问题常被用来测试新同步原语。分析：利用记录型信号量解决读者-写者问题②计数器readcount;/*用于表示共离区中的读者数目*/③readcount是临界资源，设互斥信号量为mcount;④共享区为临界资源，设信号量为mutex。这是一个同步问题。对读者，只要访问的共享对象的读者数目未超过且无写者访问该对象，便可进入临界区。对写者，必须在无一写者访问该对象时，方能进入临界区执行写操作。准备数据更新共享区取公共区中的数据哲学家进餐问题是另一种典型的同步问题，它是由Dijkstra提出并解决的。该问题是描述有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在同围的五张椅子上。在圆桌上有五个碗和五支筷子，平时一个哲学家进行思考，饥锇时便试图取用其左、右最靠近他的筷子，只有在他拿到两支筷子时才能进餐。进餐毕，放下筷子又继续思考。条件：如果筷子已在他人手上，则哲学家必须等待到他人吃完饭之后才能拿到筷子；任一哲学家在自己未拿到两支筷子吃饭之前，决不放下自己手中的筷子。显然，筷子是临界资源，在某一时刻只允许一个哲学家使用，因此，可以利用信号量机信号量构成信号量数组，其描述为：varchopstick:array[0..4]ofsemaphore:=所有信号量的初值为1,则第i个哲学家的活动可描述为：虽然上述解法可保证不会有两个相邻的哲学家同时进餐，但可能引起死锁。假如五个哲学家同时拿起各自左边的筷子，使五个信号量均为0,当他们再试图去拿右边的筷子时，他们都将无限期地等待。对于死锁可采用这样的几种解决方法：●至多只允许四个哲学家同时进餐，以保证至少有一个哲学家可以进餐，最后总会释放他所使用的两支筷子，从而使更多的哲学家进餐；●仅当哲学家左、右两支筷子均可用时，才允许他拿起筷子进餐；2号哲学家竞争1号筷子，3、4号哲学家竞争3号筷子，即五个哲学家都先竞争奇数号筷三、进程通信1.低级和高级进程通信方式一个作业可分为若干个能并发执行的进程，但它们应经常保持联系，以便协调一致地完成指定任务。这种联系是指在进程之间交换一定数量的信息。信息量可多可少，多则交换成千个数据，少则仅一个状态或数值。显然，进程同步是一种简单通信方式，进程通过修改信号量，可向另一进程表明临界资源是否可用。在生产者一消费者问题中，可由生产者进程向消费者进程传送一批消息，生产者通过缓冲池与消费者通信。应当指出，信号量机制作为同 (1)级进程通信进程的互斥和同步可归结为低级进程通信。在进程互斥中进程通过修改信号量，向其他进程表明临界资源是否可用；在生产者一消费者问题中，生产者通过缓冲池与消费者通信。应当指出，信号量机制作为同步工具是卓有成效的，但作为通信工具者每次只能从缓冲区中取得一个消息；(2)通信对用户不透明即设置共享数据结构，数据的传送、进程的互斥与同步都是由程序员去实现，操作系统只提供共享存储器。简言之，这种通信方式的效率低，不方便，故只适用于传送少量信息的情况。(2)级进程通信以较高的效率传送大量数据的一种通信方式。高级通信的目的不是为了控制进程的执行速度，而是为了交换信息。在这种通信方式中，程序员可直接利用系统提供的一组通信命令(通信原语),高效地传送大量数据，操作系统隐藏了实现通信的细节，这大大简化了通信程序编制上的复杂性。高级通信原语不仅保证相互制约的进程之间的正确关系，还同时实现了进程之间的信息交换。目前常用的高级通信机构有消息缓冲通信、管道通信和信箱通信。(1)消息缓冲通信(2)管道通信管道通信是由UNIX首创的，是一种重要的通信方式。管道通信以文件系统为基础。所谓管道，就是连接两个进程的一个打开的共享文件，专用于进程之间进行数据通信发送进程可以源源不断地从管道一端写入数据流，接收进程在需要时可以从管道的另一端读出数据。在对管道文件进行读写操作时，发送进程和接收进程要实施正确的同步和互斥，以确保通信的正确性。管道通信的实质是利用外存来进行数据通信，故具有传送数据量大的优点，信箱通信是一种简接通信方式。所谓信箱是一种数据结构，其中存放一个进程传送给另一个进程的一组消息，而以发送、接收、回答信件作为通信的基本方式。当一个进程希望与另一进程通信时，就创建一个链接两进程的信箱，通信时发送进程只要把信件投入信箱，而接收进程可以在任何时刻取走信件。这种通信方式可以分为单向信箱和双向信箱通信方式，后者是指发送进程要求接收进程予以回答。为了实现信箱通信，必须提供相应的原语，如创建信箱原语、撤消信箱原语、发送原语和接收原语等。1.死锁的概念(产生死锁的原因和必要条件)(1)竞争资源。为多个进程所共享的资源不足，引起它们对资源的竞争而产生死锁；(2)进程推进顺序不当。进程运动过程中，请求和释放资源的顺序不当，而导致进程2.死锁的起因(1)竞争资源引起死锁(2)进程推进顺序不当引起死锁进程推进顺序非法若并发进程P₁和P₂按P₁Req(R₁);P₂Req(R₂);P₁Req(R₂);(2)请求和保持条件(部分分配条件)进程每次申请它(4)环路等条件进程资源图构成的有向回答(在发生死锁时，必然存在一个进程—资我们可以通过使(2)、(3)、(4)三个必要条件不能成立的方法，来预防死锁的产生，至于必要条件(1),由于是设备的固有特性，不仅不能改变，还应设法加以保证。(1)摒弃“请求和保持”条件(2)摒弃"不剥夺"条件(3)摒弃“环路等待”条件入机的序号为1,打印机的序号为2,穿孔机为3,磁带机为4,磁盘为5。所有进程对资循环等待状态(用反证法),因而摒弃了“环路等待”条件。在采用这种策略时，由于总有(1)为系统中各种资源类型分配的序号，必须相对稳定，这就限制了新设备类型的增加；(2)尽管在为资源分配序号时，已考虑到大多数作业实际使用这些资源的顺序，但也经常不需事先采取各种限制措施去破坏产生死锁的必要条件，而是在资源的动态分配过程《计算机操作系统》教案(1)安全与不安全状态 (称<P,P₂,.,P。>为安全序列),来为每个进程分配其所需资源，直至程都能顺利完成(即所有并发进程都在该序列中)。若系统不存在这样一个安全序列，则称*安全状态之例假定系统有三个进程P₁、P₂、P,共有12台磁带机。进程P:、P₂、P₃分别要求10台、4台和9台。设在To时刻进程P₁、P₂、P₃已分别获得5台、2台和2台，尚有3台空闲磁带机进程号最大需求(台)已分配(台)未分配(台)53P₂P42P₃P92按此进程顺序分配资源，每个进程就都可顺利完成。如：将剩余的磁带机取2台分配给P₂,使之继续运行，待P₂完成便使可用资源增至5台，再将它们全部分配给P₁,待P:完成后释如果在To时刻以后，P₃请求1台磁带机，若系统此时把剩余3台中的1台分配给P₃,则系统进入不安全状态。因为，把未分配的2台分配给P₂,而P₂完成后只能释放出4台，既不能满足P₃,从而它们都无法推进到完成，于是，系统进入了不安全状态。由此可见，在P₃请求资源时，尽管系统中尚有可用的磁带机，但却不能为它分配，而需让它一直等待到(2)利用银行家算法避免死锁最有代表性的避免死锁算法，是Dijkstra的银行家算法。这是由于系统现金贷款的发放而得名。该算法的基本思想是：设当前资源分配状态为T₀,根据进程P₁发出的合理资源请求，系统资源试探性地将资源分配给它，形成一种新的状态T:,检查在这一章中，我们讨论OS中如何以CPU管理为核心进行讨论管理、控制用户进程执行的方法。本章重点：作业与进程的关系、作业调度策略与算法、进程调度策略与算法、几在多道程序环境下，进程数目往往多于处理机数目，致使它们争用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由进程调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能(吞吐量、响应时间)在很大程序上取决于进程调度性能的好坏，因而进程调度便成为操作系统设计的中心问题之一。然而，虽说处理机调度的主要目的，是为了分配处理机，但在不同的OS中所采用的调度方式是不完全相同的。在有的系统中仅采用一级调度，而有的系统则采用两级；在执行调方法即按调度的层次，把调度分为高级、中级和低级调度；另一种分类法也是较常用的，即按OS的类型分类，因而有批处理调度、分时调度和实时调度，还有多处理机调度。1.三级调度作业从进入内存并在后备队列上排队开始，直至完成，可能要经历下述三级调度：(1)高级调度(宏观调度)(HighLevelScheduling)又称作业调度，它决定把哪些后备队列中的作业调入内存，并为其创建进程，分配必要的资源，最后将所创建的进程挂在就绪队列上，以使该作业的进程获得竞争处理机的权利。在批处理系统中配有作业调度；在分时和实时系统中，通常都没有作业调度(因为在分时系统中，为了缩短响应时间，作业不是建立在外存，而是直接建立在内存中。因而分时系统中没有作业提交状态和后备状态。分时系统的输入信息经终端缓冲区为系统所接收，或者立即处理，或经交换调度暂存外存中)。高级调度的运行频率较低，如几分钟才调度一次，且调(2)低级调度(微观调度)(LowLevelScheduling)又称为进程调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。它决定就绪队列中哪个进程先获得处理机，然后再由分派程序执行将处理机分配给进程的操作。进程调度程序的运行频率很高，典型情况是几十毫秒一次。进程调度是最基本的调度，在三种类型的操作系统中都必须配置它。下图是一种调度模型。endend就绪队列CPUI/O阻塞队列I/O简单的排队调度模型又称进程对换中程调度，按一定算法在内存和外存之间进行进程对换，其目的是为了使内存紧张的情况得以缓和。中级调度的主要工作是将内存中处于阻塞状态的某些进程换至外存，腾出内存空间以便将外存上已具备执行条件的进程换入内存，准备执行。进程在运行期间可能要经历多次换进换出，在分时系统中常采用中级调度。2.与调度算法和性能有关的术语(1)周转时间(TurnaroundTime)周转时间是批处理系统中衡量调度性能的一个重要指标。对于一个作业来讲，从提交开始到完成为止的这段时间间隔称为该作业的周转时间。①作业在外存后备队列上等待进入内存的时间；②在就绪队列上等待获得处理机的时间；③在CPU上的执行时间；④等待I/O操作完成的时间。对于一个进程来说，它的周转时间是从第一次进入就绪队列开始，到进程运行完毕所经历的时间。当一个作业转换为一个进程时，进程的周转时间便是作业周转时间中的后三部分(2)响应时间(responseTime)它是分时系统中衡量调度性能的一个重要指标。所谓响应时间，是指从提交一个请求开始到首次产生响应为止(显示出结果)的一段时间间隔。它①把请求信息从键盘传送到计算机的时间；②计算机对请求进行处理的时间；③再将响应送回终端的时间。含有大量I/0操作的作业(简称I/0型作业),每个CPU执行期通常很短，例如为几十毫秒；对那些需要长期利用CPU进行计算的作业(简称计算型作业),CPU执行期可能长达数3.进程调度的方式进程调度有以下两种基本方式(1)非剥夺方式(非抢占方式)以这种调度方式运行时，不允许强行剥夺已经分配给某进程的处理机。例如，调度程序一旦把处理机分配给某进程后应让它一直运行下去，直至进程完成或发生某事件而阻塞时，才把处理机分配给另一进程。这种调度方式的优点是简单、系统开销小，但却可能导致系统性能的恶化，表现为：①当一个紧急任务到达时，它不能立即投入运行，以至于延误时机；②若干个后到的短作业，需等待先到的长作业运行完毕，致使短作业的周转时间较长。例如，有三个进程P₁、P₂、P₃先后(但又几乎在同时)到达，它们分别需要20、4和2个单位时间运行完毕。若它们就按P₁、P₂2、P₃的顺序执行，且不可剥夺，则三进程各自的周转时间分别为20、24和26个单位时间，平均周转时间是70/3个单位时间。这种非剥夺方式对短作业P₃而言是不公平的。非剥夺方式在批处理系统中常用。(2)剥夺调度方式(抢占方式)这是指进程正在运行时，系统可根据某种原则，剥夺已分配给它的处理机，并再分配给其他进程的一种调度方式。剥夺的原则有：③时间片原则一个时间片运行完后重新调度。下面我们仍以上述三个进程的情况为间分别为26、10、6个单位时间，而平均周转时间已由剥夺方式的70/3,降低为14P.PP₃PP₁PP₂PP₁PP₁P例如：有三个进程A、B、C,它们先后(但几乎又是同时)进入就绪队列。它们的CPU执行期分别是21、6和3个单位时间。按FCFS算法调度，它们的执行情况如下图所示。对于A,其周转时间为21,B的周转时间为27,C的周转时间为30,它们的平均周转时间为26。若它们按C、B、A次序到达，它们的执行情况如下图所示：30表面上也公平，但服务质量不佳，对短作业用户不公平，因而FIFO算法很少作为进程调度2.作业(进程)优先调度算法(SJ(P)F)短作业(进程)优先调度算法SJF或SPF是指对短作业或短进程优先调度的算法。它们3.由于作业(进程)的长短只是根据用户所提供的估计执行时间而定，而用户又可以会有意或无间地缩短其作业的估计执行时间，致使该程按FIFO规则排成一个环形队列，把CPU分配给队别为26、10、6个单位时间，平均周转时间为14个单位时间。P₂PP₃PP₁PP₂PP₁PP₁P而无法获得令用户满意的响应应时间。当时间片过定进程优先权的依据有：进程类型(通常系统进程的优先权高于用户进程的优先权)、进程对资源的要求(如估计的运行时间、内存需要量等)、用户要求的优先级(静态优在就绪队列中的进程，其优先权以速度a增加，若再令正在执行进程的优先权以速度该算法有利于短作业而不利于长作业，由于80%以上的作业都是短作业，故该算法能《计算机操作系统》教案该算法是将SJF算法与FCFS算法改进后加以折衷而得。它除了考虑作业要求的运行时响应比=(作业等待时间+作业要求的运行时间)/作业要求的运行时间4.优先权高者优先调度算法考虑如下三个基本目标：(1)尽量提高系统作业的吞吐量；(2)尽量使CPU和外部设备保持"忙",以提高资源的利用率；(3)对各种作业尽可能做到公平合理，使所有用户都满意。例如：假设有四道作业，它们的进入时间和运行时间由下表给出：作业号进入时间(时)运行时间(小时)12134在单道程序环境下，分别采用先来先服务和最短作业优先调度算法，试分别说明它们的调度顺序及平均周转时间和平均带权周转时间(不剥夺方式)。解：四道作业的运行时间表如下：作业号进入时间(时)运行时间(小时完成时间(时)周转时间(小时)完成时间(时)周转时间(小时)121314平均周转时间T=(0.4+1.3+1.8+1.9)/4=1.35(小时)平均带权周转时间w=(0.4/0.4+1.3/1+1.8/0.6+1SJF:调度顺序是1、4、3、2(2)链接。由链接程序(Linker)将编译后形成的目标模块以及(3)装入。由装入程序(Loader)将装入模块装入内存。的位置赋予它们实际物理地址(直接指定方式、绝对指定方式);第二种方法是使用静态分配方式(可重定位方式);第三种方法是使用动态分配方式(动态运行时装入方式)。亦即，1.绝对装入方式(直接指定方式)i《计算机操作系统》教案lhl,山L六词动有六词在用户的1000号单元处有一条指令LOAD1,2500,该指令的功能是将2500号单元中此，应将取数指令中的地址2500修改成12500,即把有效地址(相对地址)与本程序在内〈基地址寄存器>。该寄存器的值是由进程调度程序根据作业分配到的存储空间的起始地址来设定的。在具有这种地址变换机构的计算机系统中，当执行作业时，不是根据CPU给出的有效地址去访问主存而是将有效地址与基地址寄存器中的内容相加后得到的地址作为访问主存的地址。下图示出了地址变换过程。由于这种地址变换是在作业执行期间随着每条指令0有效地址处理机一侧存储器一侧0的数据访问自动地、连续地进行的，所以称为动态重定位。动态重定位示意图如下：动态地址重定位过程①设置基地址寄存器BR,虚地址寄存器VR;②将程序段装入内存，且将其占用的内存区首地址送BR中。例如，上图中(BR)=1K;③在程序执行过程中，将所要访问的虚地址送入VR中。如上图中执行LOADA500语句时，将所要访问的虚地址500放入VR中。④地址变换机构把VR和BR的内容相加，得到实际访问的物理地址。由此可以看出，采用动态重定位技术后，程序中所有指令和数据的实际地址是在运行过程中最后访问的时刻确定的。因此，设置这种地址变换机构的计算机系统允许我们采用动态存储分配策略。也就是说，在作业运行过程中临时申请分配附加的存储区域可释放占用的部连续分配存储管理为一个用户分配一个连续的内存空间。连续分配有以下两种形式：单一连续分配方式和分区式分配方式(固定分区、动态分区)。这是一种最简单的存储管理方式。但只能用于单用户、单任务的操作系统中。由于在8位和16位微机上，主要都是配置的单用户、单任务操作系统，如CP/M和MS-DOS,故在多种存储分配方式中，仍有它的一席之地。采用这种存储管理方式时，内存分为以下三个区：单一连续区主要是指内存只供一个用户进程使用。分配方式则主要采用静态分配方式，分区号大小分区号大小起址状态1已分配2已分配3已分配分为固定式分区、动态分区(可变式分区、可重定位分区及多重分区)。1.固定分区法(过时)成若干个区域(大小相等的或不等的);然后，把这些区域分配给每个用户作业。由于这些作业作业B作业C《计算机操作系统》教案二、动态分区法(可变式分区)为了减少存储区域的"内零头",进一步提高主存的利用率，使存储空间的划分更加适减少固定分区所造成的“内零头”(碎片),从而提高了内存的利用率。(1)分区分配中所用的数据结构；(2)分区的分配算法；(3)分区分配的操作。(1)空闲分区表用于为内存中每个尚未分配出去的分区设置一个表项，每个分区表项包含分区序号、分区始址及分区的大小等表目；分区号大小起址123可用表(2)自由链自由链则是利用每个内存空闲区的头几个单元存放本空闲区的大小及下个空查找时要较可用表困难，但由于自由链指针是利用的空闲区自身的单元，所以不必占用额外2.分区的分配与回收动态分区时的分配与回收主要解