2019考研计算机基础课程操作系统电子讲义槟果

第1章操作系统概 操作系统的概念、特征、功能和提供的服 操作系统的发展与分 操作系统的运行环 操作系统体系结 第2章进程管 进程与线 处理机调 同步与互 死 第3章内存管 内存管理基 虚拟内存管 第4章文件管 文件系统基 文件系统实 磁盘组织与管 第5章输入输出管 I/O管理概 I/O子系 第6章总 1章操作系统概操作系统的概念、特征、功能和提供的服务操作系统的概念操作系统是计算机系统中最重要、最基本的系统软件，操作系统位于硬件和用户程序之间。操作系统的目方便性（用户的观点有效性（系统管理人员的观点OS时，人们似乎更重视如何使用户能更为方便地使用计算机， 应采用层次化结构，以便于增加新的功能层次和模块，并能修改老的功能层次和块遵循，方便地实现互连，实现应用的可移植性和互操作性。开放性是指系统能遵循世界，特别是遵循开放系统互连(OSI)国际标准。凡遵循国际标准所开发的硬件20世纪90年代以后计算机技术的一个问题，也是一个新推出的系统或软件能否被广泛应用的至关重要的因素。操作系统的特征并发正是系统中的程序能并发执行这一特征，才使得OS能有效地提高系统中的资源利用率，并行与并I/O程序之间只能是顺行只在程执一才许/O之执行I/O操作时，计算程序也不能执行。为计算程序和/O程序分别建立一个进程(roces)后，这两个进可并发执行。若对内存中的多个程序都分别建立一个进程，就可以并发执行，极大地提高系统资源的利用率，增加吞吐量。共享一般情况下的共享与操作系统环境下的共享其含义并不完全相同。在操作系统环境下，所谓共享(Sharing)，是指系统中的资源可供内存中多个并发执行的进程(线程)共同使用，相应地，把这种资源共同使用称为资源共享，或称为资源复用。互斥共享方系统中的某些资源，如、磁带机等，虽然可以提供给多个进程(线程)使用，但应规定在一段时间内，只允许一个进程该资源。在系统中应建立一种机制，以保证多个进程对这类资源的互斥。同时方行的。典型的可供多个进程“同时”的资源是磁盘设备。一些用重入码编写的文件也可以虚拟操作系统中的所谓“虚拟”(irtual)，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物。物理实体(前者)是实的，即实际存在的，而后者是虚的，仅是用户感觉上的东西。相应地，用于实现虚拟的技术称为虚拟技术。在操作系统中利用了两种方式实现虚拟技术，即时分复用技术和空分复用技术。时分复用技虚拟处理机技术虚拟设备技术空分复用技20世纪初，电信业中就已使用频分复用技术来提高信道的利用率。它是指将一个频率范围比较宽的信道划分成多个频率范围较窄的信道(称为频带)，其中的任何一个频带都一展到成千上万条话路，每条话路供一对用户通话。在计算机中也把空分复用技术用于对空间的管理，用以提高空间的利用率。异步多道程序环境下，系统允许多个进程并发执行。单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。当正在执行的进程提出某种资源要求时，如打印请求，而此时正在为其它进程打印，由于属于临界资源，因此正在执行的进程必须等待，并释放出处理机，直到空闲，并再次获得处理机时，该进程方能继续执行。由于资源等因素的限制，使进程的执行通常都不可能“一气呵成”，而是以“停停走走”的方式运行。操作系统的功能引入OS不紊地、高效地运行，并能最大程度地提高系统中各种资源的利用率，方便用户的使用。传统的S中应具有处理机管理、器管理、设备管理和文件管理等基本功能。为了方便用户使用OS，还需向用户提供方便的用户接口。（1）处理机管理功调作业调度进程调度（2）器管理功内存分配的主要任务为每道程序分配内存空间，使它们“各得其所”提高器的利用率，尽量减少不可用的内存空间(碎片)允许正在运行的程序申请附加的内存空间，以适应程序和数据动态增长的需OS在实现内存分配时，可采取两种方式静态分配方式。每个作业的内存空间是在作业装入时确定的，在作业装入后的整个运行期间不允许该作业再申请新的内存空间，也不允许作业在内存中“移动”。动态分配方式。每个作业所要求的基本内存空间虽然也是在装入时确定的，但允许作业在运行过程中继续申请新的附加内存空间，以适应程序和数据的动态增长，也允许作业在内存保护的主要任务①确保每道用户程序都仅在自己的内存空间内运行，彼此互不干扰②绝不允许用户程序操作系统的程序和数据，也不允许用户程序转移到非共享的在多道程序环境下，由于每道程序经编译和后所形成的可装入程序其地址都是从0开始的，但不可能将它们从“0”地址(物理)开始装入内存，致使(各程序段的)地址空间内的逻辑地址与其在内存空间中的物理地址并不相一致。内存扩充并非是从物理上去扩大内存的容量，而是借助于虚 技术，从逻辑上扩使感存实容量便的能存扩充机制(包含少量的硬件)，用于实现下述各功能：请求调入功能置换功能设备管理功设备管理的主要任务如下完成用户进程I/O请求，为用户进程分配所需的I/O设备，并完成指定的文件管理功文件空间的管管文件的读/写管理和保文件的读/文件保护操作系统所能提供的服务 作为用户与计算机硬件系统之间的接OS处于用户与计算机硬件系统之间，用户通过OS来使用计算机系统。用户在OS帮 1-1OS的示意图1-1可看出，用户可通过以下三种方式使用计算机。1)命令方式。这是指由OS提供了一组联机应用程序。系统调用方式。OS提供了一组系统调用，用户可在自己的应用程序中通过相应的系OS作为计算机系统资源的管理硬件和软件资源分为四类：处理机、器、I/O设备和文件(数据和程序)。OS的主处理机管理是用于分配和控制处理机2）器管理主要负责内存的分配与回收I/O设备管理是负责I/O设备的分配(回收)与文件管理是用于实现对文件的存取、共享和保护。OS使用。为了方便用户使用I/O设备，人们在机上覆盖上一层I/O设备管理软件，由它来实现对I/O设备操作的细节，并向上将I/O设备抽象为一组数据结构以及一组I/O操作命令，readwrite命令，这样用户即可利用这些数据结构及操作命令来进行数据输入或输出，而无需关心I/O是如何具体实现的。1-2I/O软件隐藏了I/O操作实现的细操作系统的发展与分类操作系统的发展在20世纪50年代中期，出现了第一个简单的批处理60年代中期开发出多道程序批处理系统；不久又推出分时系统，与此同时，用于工业和控制的实时S也相继问世。207090VLSI和计算机体系结构大发展的年代，导致了微型机、多处理机和计算机网络的诞生和发展，与此相应地，也相继开发出了微机OS、多处理机OS和OS，并得到极为迅猛的发展。未配置操作系统的计算机系统人工操作方早期的操作方式是由程序员将事先已穿孔的纸带(或卡片)(或卡片输入机)，再启动它们将纸带(或卡片)上的程序和数据输入计算机，然后启动计算机运行。仅当程序运行完毕并取走计算结果后，才允许下一个用户上机。用户独占全机，即一台计算机的全部资源由上机用户所独占CPU等待人工操作。当用户进行装带(卡)、卸带(卡)等人工操作时，CPU及内存等资脱机输入/输出(Off-LineI/O)方脱机I/O技术。该技术是事先将装有用户程序和数据的纸带装入纸带输入机，在一 机的控制下速地调入内存。减少了CPU的空闲时间，提高I/O速度。1-3I/O单道批处理系统单道批处理系统(SimpleBatchProcessingSystem)为实现对作业的连续处理，需要先把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下，使这批作业能一个接一个地连续处理。其自动处理过程是：首先，由监督程序将磁带上的第一个作业装入内存，并把运行控制权交给该作业。当该作业处理完成时，又把控制权交还给监督程序，再由监督程序把磁带(盘)上的第二个作业调入内存。计算机系统就这样自动地一个作业一个作业地进行处理，直至磁带(盘)(SimpleachProcessngSysem)。1-4单道批处理系统的缺系统中的资源得不到充分的利用。因为在内存中仅有一道程序，每逢该程序在运行中CPU的利用率显著降低。如图1-5t2～t3、t6～t7CPU空闲。1-5多道批处理系统(MultiprogrammedBatchProcessing多道程序设计的基本为了进一步提高资源的利用率和系统吞吐量，在20世纪60年代中期引入了多道程序设计技术，由此形成了多道批处理系统。在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备个作业调入内存，使它们共享CPU和系统中的各种资源。1-6多道批处理系统的优多道批处理系统的优缺点如下内存中装入多道程序可提高内存的利用率；此外还可以提高I/O设备的利用率。系统吞吐量大 仅当作业完成时或运行不下去时才进行切换，系统开销小平均周转时间长。由于作业要排队依次进行处理，因而作业的周转时间较长，通常需几个小时，甚至几天。无交互能力。用户一旦把作业提交给系统后，直至作业完成，用户都不能与自己的作业进行交互，修改和调试程序极不方便。多道批处理系统需要解决的问处理机争用问题。既要能满足各道程序运行的需要，又要能提高处理机的利用率内存分配和保护问题。系统应能为每道程序分配必要的内存空间，使它们“各得其文件的组织和管理问题。系统应能有效地组织存放在系统中的大量的程序和数据，使它们既便于用户使用，又能保证数据的安全性。用户与系统的接口问题。为使用户能方便的使用操作系统 还应提供用户与之间的接为此，应在计算机系统中增加一组软件，用以对上述问题进行妥善、有效的处理。这组软件应包括：能控制和管理四大资源的软件，合理地对各类作业进行调度的软件，以及方便用户使用计算机的软件。正是这样一组软件构成了操作系统。据此，我们可把操作系统定义为：操作系统是一组控制和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。分时系统的引OS。用户的需求具体表现在以下几个方面： 免有些错误或不当之处需要修改，因而希望能像早期使用计算机时一样对它进行直接控制，并能以边运行边修改的方式，对程序中的错误进行修改，亦即，希望能进行人-机交互。共享主机2060年代计算机非常昂贵，不可能像现在这样每人独占一台微机，而只能是由多个用户共台计算机，但用户在使用机器时应能够像自己独占计算机一分时系统实现中的关键问在多道批处理系统中，用户无法与自己的作业进行交互的主要原因是：作业都先驻留在外行交互。及时接收 要及时接收用户键入令或数据并不，为此，只需在系统中配置一多卡。如当要主上连接8个终端时，须配置一个8用户的多路卡。多路卡的用是使主机能同时接收各用户从终端上输入的数据。此外，还须为每个终端配置一个缓冲区，用来暂存用户键入令(或数据)。及时处理 人机交互的关键，是使用户键入命令后地控制自己作业的运行，或修改自己的作业。为此，各个用户的作业都必须在内存中，且应能频繁地获得处理机而运行；轮转运行方式,引入时间片概念，每个作业每次只能运行一个时间片分时系统的特多路性。允许在一台主机上同时联接多台联机终端，系统按分时原则为每个用户服行一个时间片。多路性即同时性，它提高了资源利用率，降低了使用费用，从而促进了计算机更广泛的应用。独立性。每个用户各占一个终端，彼此独立操作，互不干扰。因此，用户所感觉到的，就像是他一人独占主机。及时性。用户的请求能在很短的时间内获得响应。此时间间隔是以人们所能接受的等待时间来确定的，通常仅为1～3秒钟。求系统提供多方面的服务，如文件编辑、数据处理和资源共享等实时系统(RealTime实时系统的类随着计算机应用的普及，实时系统的类型也相应增多，下面列出当前常见的几种工业()控制系统信息查询系统多系统嵌入式系统实时任务的类周期性实时任务和非周期性实时任务性，但都必须联系着一个截止时间(Deadline)。它又可分为开始截止时间(某任务在某时间以前必须开始执行)和完成截止时间(某任务在某时间以前必须完成)两部分。硬实时任务和软实时任务HRT：系统必须满足任务对截止时间的要SRT：若偶尔错过了任务的截止时间，对系统产生的影响也不会太实时系统与分时系统特征的比多路性。实时信息处理系统也按分时原则为多个终端用户服务。实时控制系统的多路性则主要表现在系统周期性地对多路现场信息进行，以及对多个对象或多个执行机构进行控制。而分时系统中的多路性则与用户情况有关，时多时少。独立性。实时信息处理系统中的每个终端用户在向实时系统提出服务请求时，是彼此独立地操作，互不干扰；而实时控制系统中，对信息和对对象的控制也都是彼此互不干扰。及时性。实时信息处理系统对实时性的要求与分时系统类似，都是以人所能接受的完成截止时间来确定的，一般为秒级到毫秒级，甚至有的要低于100微秒。交互性。实时信息处理系统虽然也具有交互性，但这里人与系统的交互仅限于系统中某些特定的服务程序。它不像分时系统那样能向终端用户提供数据处理和资源共享等服务可靠性。分时系统虽然也要求系统可靠，但相比之下，实时系统则要求系统具有高，所以实时系统中，往往都采取了多级容错措施来保障系统的安全性及数据的安全性。操作系统的分类单用户单任务操作系1974年第一代通用8位微处理机In8080出现后的第二年，DigitalResearch公司就开发出带有软盘系统的8位微机操作系统。1977年DigitalResearch公司对CP/M进行了重写，使其可配置在以In 、、Z80等8位为基础的多种微机上。1979年又推出带有硬盘管理功能的CP/M2.2版本。由于CP/M具有较好的体系结构，可适应性强，且具有可移植性以及易学易用等优点，使之在8位微机中占据了地位。MS-1981IBMIBM-PC个人计算机(16位微机)，在微机中采用了微软MS-DOS(DiskOperatingSystem)CP/M的基础上进行了较大的扩充，使其在功能上有很大的增强。1983年IBM推出PC/AT(配有In80286)，相应地，微软又开发出MS-DOS2.0版本，它不仅能支持硬盘设备，还采用了树形结构的文件系统。1987MS-DOS3.3MS-DOS1.03.3为DOS640KB19891993年又先后推出了多个MS-DOS版本，它们都可以配置在In、等32位微208090年代初，由于MS-DOS性能优越而受到当时用户的广泛欢迎，成为事实上的16位单用户单任务操作系统标单用户多任务操作系32位微机上配置的操作系统基本上都是单用户多任务操作系统，其中最有代表性的是由微软公司推出的Windows。年和1987年微软公司先后推出了Windows1.0和Windows2.0当时的硬件只是16位微机，对1.0和2.0版本不能很好的支持。1990年微软公Windows3.0Windows3.1版本，它们主要是针对386386486等微机的主流操作系统。1995Windows95Windows3.1有许多重大改进，采用了全32位的处理技术，并兼容以前的16位应用程序，在该系统中还集成了支持Internet的网络功能。1998Windows95Windows98，它已是最后一个仍然兼容以前的16位应用程序的Windows，其最主要的改进是把微软公司自己开发的Internet浏览器整合到系统中，大大方便了用户上网浏览，另一个特点是增加了对多的支持。2001年微软又发布了32位版本的WindowsXP，同时提供了家用和商业工作站两种版本，它是当前使用最广泛的个人操作系统。2001年还发布了64位版本的WindowsXP。多用户多任务操作系主机系统中的各种资源，而每个用户程序又可进一步分为几个任务，使它们能并发执行，从而可进一步提高资源利用率和系统吞吐量。在大、中和小型机中所配置的大多是多用户多任务操作系统，而在32位微机上，也有不少配置的是多用户多任务操作系统，其中最有代表性的是UNIXOS。SolarisOS：SUN公司于1982年推出的SUNOS1.0是一个运行在Motorola680x0UNIXOS1988SUNOS4.0Motorola680x0平台迁移到SPARC平台，并开始支持In公司的In80x86；1992年SUN发Solaris2.01998年开始，Sun64Solaris2.72.8，这LinuxOS：LinuxUNIXLinusTorvalds针对In80386开发的。1991年在Internet网上发布第一个Linux版本，由于源代码公开，InternetLinux的性能迅速提高，其应用范围也日益扩大。UNIXUNIX上运行的软件(包括1000多种实用工具软件和大量的网络软件)被移植到Linux上，而且可以在主要的微机上运行，如In80x86Pentium等。操作系统的运行环境内核态与用户态用户误用这些指令，称为指令，将故障中断。程序状态字寄存器的指令存取特殊寄存器(如用于内存保护的寄存器)其他系统状态和直接系统资源的指令等具有较高的级别，又称为态、系统态或管态；后者一般指用户程序运行时的状态，具有较低的级别，又称为普通态、目态。目态：程序执行时不可使用指令，I/O指令、时钟设置、中断机制、系统管理等，管态：程序执行时可以使用指令。执行系统管理程序，态、系统态、内核态、？CPU如何判断用户程序和系统程序程序状态字PSW记录CPU的运行模式和状态信一类是反映当前指令执行结果的各种状态信息，称为状态标志，如进位标志位(CF)标志位(OF)、结果正负标志位(SF)、结果是否为0标志位(Z)、奇偶标志位()等；一类存放控制信息，称为控制状态，如中断标志位(IF)、CPU的工作状态位(态还？状态如何转态到用户态--用户态到态--用户不能修改--系统调--访管指 通过中断实现从用户态到态的改变 在态下由操作系统代替用户完成其请求(指定的操作)③操作系统完成指定操作后再通过修改程序状态字(PSW)由态切换回用户态（用户态下执行的指令。当源程序中有需要操作系统服务的要求序行时处理若到了访指令就生个断，断装就会相的并返回到用户程序。值得注意的是，访管指令不是指令。指令是指用于操作系统或中断、异常中断是指程序执行过程中，当发生某个时，中止CPU上现行程序的运行，引出处理该的程序执行的过程。从中断的性质和激活的来说，可以分成两类：强迫性中断和自愿性中断。强迫性中断不是正在运行的程序所期待的，而是由于某种事故或外部请求信息所引起的，分为：机器故障中断。程序性中断。外部中断。愿行序。行对作统有某种需求，一旦机器执行到一条访管指令时，便自愿停止现行程序的执行而转入访管中断处理程序处理。按照中断信号的来源，可把中断分为外中断和内中断两类：外中断(又称中断)指来自处(又称异常)故障中断、时钟中断、控制台中断、它机中断和/O常是不能被的，一旦出现应立即响应并加以处理中断和异常的区别：中断是由与现行指令无关的中断信号触发的(异步的)，且中断的发生与CPU处在用户模式或内核模式无关，在两条机器指令之间才可响应中断，一般来说，出错和陷入的区别如下：它们发生时保存的返回指令地址不同，出错保存指向触发异常的中断和异常要通过硬件设施来产生中断请求，可看作硬中断。不必由硬件发信号而能的中断称软中断，软中断是利用硬件中断的概念，用软件方式进行模拟，实现宏观上的异步执之间用来模拟硬中断的一种信号通信方式。理断的序称中处理序它的要务处中断恢复常作。不同中断源对应不同中断处理程序，故快速找到中断处理程序的地址是一个关键问题。中断的原因。处理发生的中断。恢复正常操作。1-7如何来响应同时发生的中断呢?它按照预定顺序来响应，这个预定顺序称中断的优先级，首先响应优先级高的中断2、中断的：主机可允许或某类中断的响应，如允许或所有的I/O中断、外部中断、及某些程序性中断。有些中断是不能被的，例如，计算机中的自愿性访管中断就不能被。1）再发生中断：运行中断处理程序时，对任何新产生的中断不予理睬，这可以通过某些中断来实现。系统调用是中断或者异常处理，把控制流程转移到程序内的一些特定的位置。同时，处理器模式转变成模式。其次，由程序执行被请求的功能代码。这个功能代码代表着对一段标准程序段的执行，用以完成所请求的功能。第三，处理结束之后，程序恢复系统调用之系统调用与一般程序调用的不同运行在不同的系统状态。调用的程序是运行在用户态，被调用的程序运行在态进入的方式不同。过程调用语句直接跳转到被调用过程；而系统调用则必须通过运行系统调用命令。返回方式不同。过程调用直接返回；系统调用则不直接返回，有重新调度过代码层次不同。过程调用是用户级程序，而系统调用是系统级程序系统调用一般不能嵌套或递归图1- 运行环境示意1-9操作系统体系结构无结构操作系在早期开发操作系统时，设计者只是把他的注意力放在功能的实现和获得高的效率上，缺乏首尾一致的设计思想。OS是为数众多的一组过程的集合，每个过程可以任意地相用其它过程，致使操作系统内部既复杂又，因此，这种S是无结构的，也有人把它称为整体系统结构。模块化结构模块化程序设计技术的基本概模块化程序设计技术是20世纪60年代出现的一种结构化程序设计技术。该技术基于“分解”和“模块化”的原则来控制大型软件的复杂度。为使OS具有较清晰的结构，OS不再是由1-10模块独立在模块-接口法中，关键问题是模块的划分和规定好模块之间的接口。如果在划分模块时将模块划分得太小，虽然可以降低模块本身的复杂性，但会引起模块之间的联系过多，从而会造成系统比较；如果将模块划分得过大，又会增加模块内部的复杂性，使内部的联系加，因此在划分模块时，应在两者间进行权衡。利用模块-接口法开发的OS，较之无结构OS具有以下明显的优点提高OS设计的正确性、可理解性和可性增强OS的可适应性加速OS的开发过程模块化结构设计仍存在下述问题在 设计时，对各模块间的接口规定很难满足在模块设计完成后对接口的实际求在S设计阶段，设计者必须做出一系列的决定(决策)，每一个决定必须建立在上一个决定的基础上，但模块化结构设计中，各模块的设计齐头并进，无法寻找一个可靠的决定顺序，造成各种决定的“无序性”，这将使程序人员很难做到“设计中的每一步决定”都是建立在可靠的基础上，因此模块-分层式结构分层式结构的基本概为了将模块-接口法中“决定顺序”的无序性变为有序性，引入了有序分层法，分层法的设计任务是，在目标系统An和机系统(又称宿主系统)A0之间，铺设若干个层次的软件A1、A2、A3、…、An-1，使An通过An-1、An-2、…、A2、A1层，最终能在A0上运行。在操分层结构的优缺分层结构的主要优点易保证系统的正确性易扩充和易性分层结构的主要缺点是系统效率降低由于层次结构是分层单向依赖的，必须在每层之间都建立层次间的通信机制，S每执行一个功能，通常要自上而下地穿越多个层次，这无疑会增加系统的通信开销，从而导致系统效率的降低。4、微OS结足够小的内在微内核操作系统中，内核是指精心设计的、能实现现代OS最基本功能的小型内核，微内核并非是一个完整的OS与硬件处理紧密相关的部分OS最基本的部分只是为构建通用OS提供一个重要基础，可以确保把操作系统内核做基于客户/服务器模由于客户/服务器模式具有非常多的优点，故在单机微内核操作系统中几乎无一例外地都采用客户/服务器模式，将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放在微内核外面的一组服务器(进程)中实现，用于提供对进程(线程)进行管理的进程(线程)服务器、提供虚拟器管理功能的虚拟器服务器、提供I/O设备管理的/O微内核提供的消息传递机制来实现信息交互的。应用“机制与策略分离”原和算法来实现该功能的优化，或达到不同的功能目标采用面向对象技（2）.微内核应具有哪些功能，或者说哪些功能应放在微内核内，哪些应放在微内核外，目前尚的部分放入微内核中，微内核通常具有如下几方面的功能：进程(线程)管低级器管中断和陷入处（3）.OS结构是建立在模块化、层次化结构的基础上的，并采用了客户/服务器提高了系统的可扩展增强了系统的可靠性可移植性强提供了对分布式系统的支持融入了面向对象技术（4）应当，在微内核操作系统中，由于采用了非常小的内核，客户/服务器模式和消息传递机制虽给微内核操作系统带来了许多优点，但由此也使微内核OS存在着潜在缺点，其还会引起的上下文切换。例如，当某个服务器自身尚力完成客户请求而需要其它服务8次上下文的切换。2章进程管进程与线程进程的概念1、程序的顺序执一个应用程序由若干个程序段组成，每一个程序段完成特定的功能，它们在执行时，都需应先运行输入程序，用于输入用户的程序和数据；然后运行计算程序，对所输入的数据进行计算；最后是运行打印程序，打印计算结果。用结点(Node)代表各程序段的操作，其中I代表输入操作，C代表计算操作，P为打印操作，用箭头指示操作的先后次序。段S1:a=x+y；S2:b=a-5；S3:c2-1S2S1后(a被赋值)S3b被赋值后2.由上所述可以得知，在程序顺序执行时，具有这样三个特征 可再现性：指只要程序执行时的环境和初始条件相同，当程序重复执行时，不论是从头到尾不停顿地执行，还是“停停走走”地执行，都可获得相同的结果程序顺序执行时的这种特性，为程序员检测和校正程序的错误带来了很大的3、程序的并发执程序三者之间，存在着Ii→Ci→Pi这样的前趋关系，对一个作业的输入、计算和打印三个程序2-2由图可以看出，存趋关系Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1，而和Ci及Pi-1是的，即在Pi-1和Ci以及Ii+1之间，不存趋关系，可以并发执行。S1:a:=x+2S2:bS3:c:=a+bS4:d可画出图所示的前趋关系。S3ab被赋值后方能执行；S4S3之后执行；但S1和S2则可以并发执行，因为它们彼此互不依赖。2-34、程序并发执行时的特必将形成相互制约的关系，由此会给程序并发执行带来新的特征间断性。"走走停停"，一个程序可能走到中途停下来，失去原有的时序关系不可再现性。外界环境在程序的两次执行期间发生变化，失去原5、进程的定的运行也就失去了意义。为了能使程序并发执行，并且可以对并发执行的程序加以描述和控制，人们引入了“进程”的概念。对于进程的定义，从不同的角度可以有不同的定义，其中较典型的定义有进程是程序的一次执进程是一个程序及其数据在处理机上顺序执行时所发生的活动进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。6、进程的特PCB结构外，还具有，地址空间上包括：代码（指令CPU状态的改变）数据（变量的生成和赋值系统控制信息（进程控制块的建立和系统收回独立性。各进程的地址空间相互独立，除非采用进程间通信异步性。各进程按各自独立的、不可预知的速度向前进程的状态与转换所以进程在其生命周期内可能具有多种状态。每一个进程至少应处于三种基本状态之一：（Running（Blocked：就绪状态（Ready：进程已分配到除处理机以外的所有必要资源，具备了运行的条件，可能会有多个进程处于就绪状态，排成就绪队列。处理机之后便可执行，相应地，其状态就由就绪态转变为执行态；正在执行的进程(当前进程)如果因分配给它的时间片已完而被处理机暂停执行时，其状态便由执行转为就绪；如果因发生某，致使当前进程的执行受阻(例如进程某临界资源，而该资源正被其它进程访问时)，使之无法继续执行，则该进程状态将由执行转变为阻塞。运行状态到阻塞状态：正在运行的进程因需要等待某而无法运行，让出处理机。 塞状态到就绪状态：进程所等待的发生了，进程就从阻塞状态进入就绪状态。 图2-4进程的三种基本状态及其转进程是由创建而产生。创建一个进程是个很复杂的过程，基本步骤：如首先由进程申请一个空白PCB，并向PCB中填写用于控制和管理进程的信息；然后为该进程分配运行时所必于是把此时进程所处的状态称为创建状态。进程的终止也要通过两个步骤：首先，是等待操作系统进行善后处理，最后将其PCB，并将PCB空间返还系统。当一个进程到达了自然结束点，或是出现了无法克服的错作终被止进将止终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统即将其PCB，并将该空白PCB返还系统。4、挂起操作的引

图2-5进程的五种基本状态及转引入挂起操作的原因，是基于系统和用户的如下需要终端用户的需要父进程请求负荷调节的需要操作系统的需要5、引入挂起原语操作后三个进程状态的转活动就绪→静止就绪。当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya。当用挂起原语Supend将该进程挂起后，该进转变为静止就绪状态，表示为Readys，处于Readys状态的进程不再被调度执行。活动阻塞→静止阻塞。当进程处于未被挂起的阻塞状态时，称它是处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进转变为静止阻塞状态，表示为Blocked。处于该状态的进程在其所期待的出现后，将从静止阻塞变为静止就绪。ReadysActive激活后，该进程将转变为Readya状态。BlockedsActive激活后，该进程将转变为Blockeda状态。6、引入挂起操作后五个进程状态的转NULL→创创建→活动就绪创建→静止就绪执行→终止图2-6具有挂起状态的进程状态图2-7具有创建、终止和挂起状态的进程状态进程控制某而使其无法运行下去的进程，还可负责进程运行中的状态转换。如当一个正在执行的进程因等待某而暂时不能继续执行时，将其转换为阻塞状态，而当该进程所期待的出现时，又将该进程转换为就绪状态等等。进程控制一般是由S的内核中的原语来实现的。所谓原语即原子操作，要么全做，要么不做，一般是通过中断来完成的1）进程创建。creat2）进程撤销。halt3）进程阻塞。block4）进起。suspend6）进程的创进程的层次结在OS中，允许一个进程创建另一个进程，通常把创建进程的进程称为父进程，而把被创建的进程称为子进程。子进程可继续创建的孙进程，由此便形成了一个进程的层次结构。如在UNIX中，进程与其子孙进程共同组成一个进程(组)。为了形象地描述一个进程的关系而引入了进程图(rocessraph)。所谓进程图就是用于描述进程间关系的一棵有向树。2-8典型有四类：用户登录作业调度提供服务应用请求在系统中每当出现了创建新进程的请求后，OSCreat按下述步骤PCB。备和CPU时间等。初始化进程控制块(PCB)如果进程就绪队列能够接纳新进程，便将新进程插入就绪队列进程的终引起进程终止(TerminationofProcess)进程的终止过如果系统中发生了要求终止进程的某，S便调用进程终止原语，按下述过程去终止指定的进程：若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度；若该进程还有子孙进程，还应将其所有子孙进程也都予以终止，以防它们成为不可控的进程将被终止进程所拥有的全部资源或者归还给其父进程，或者归还给系统将被终止进程(PCB)从所在队列(或链表)进程的阻塞与唤引起进程阻塞和唤醒的有下述几类会引起进程阻塞或被唤醒向系统请求共享资源失败等待某种操作的完成新数据尚未到达进程阻塞过block过程后，由于该进程还处于执行状态，所以PCB插入阻塞即，保留被阻塞进程的处理机状态，按新进程的PCB中的处理机状态设置CPU的环境。进程唤醒过当被阻塞进程所期待的发生时，比如它所启动的I/O操作已完成，或其所期待的据已经到达，则由有关进程(比如提供数据的进程)调用唤醒原语wakeup，将等待该的进程唤醒。wakeup执行的过程是：首先把被阻塞的进程从等待该的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列中。进程的挂起与激supend()原语的执行过程：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。为了方便用户或父进程考查该进程的运行情况而把该进程的PCB到某指定的内存区域。若被挂起的进程正在执行，则转向调度程序重新调度进程的激活过当发生激活进程的时，系统将利用激活原语active()将指定进程激活active()原语执行过程：激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。若采用抢占调度策略，则每当有新进程（激活进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激立即当前进程的运行，把处理机分配给刚被激活的进程。进程组织程序：描述进程所要完成的功能，特指二进制的指令代码数据集合：程序运行所需要的数据结构。包括常数，变量，堆，数据栈等。进程控制块：进程控制块包含了进程的描述信息、控制信息和资源信息。在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，我们称之为资源信息表或进程信息表，包含了资源或进程的标识、描述、状态等信息以及一批成不同的队列，便于操作系统进行查找。OS管理的这些数据结构一般分为四类：内存表、设备表、文件表和用于进程管理的进程表，通常进程表又被称为进程控制块PCB。进程控制块PCB作为独立运行基本单位的标志能实现间断性运行方提供进程管理所需要的信息提供进程调度所需要的信息实现与其它进程的同步与通信在进程控制块中，主要包括四个方面信息进程标识进程标识符用于唯一地标识一个进程。一个进程通常有两种标识符外部标识符。它由创建者提供，通常是由字母、数字组成，往往是由用户(进程)在该进程时使用。为了描述进程的关系，还应设置父进程标识及子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。处理机状处理机状态信息主要是由处理机的各种寄存器中的内容组成的。处理机在运行时，许多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便在该进程重新执行时，能从断点继续执行。这些寄存器包括：①通用寄存器，又称为用户可视寄存器，它们是用户程序可以的，用于暂存信息 指令计数器，其中存放了要的下一条指令的地址 程序状态字PSW，其中含有状态信息，如条件码、执行方式、中断标志等进程调度信在 进行调度时，必须了解进程的状态及有关进程调度的信息，这些信息包括 进程状态，指明进程的当前状态，它是作为进程调度和对换时的依据 进程调度所需的其它信息，它们与所采用的进程调度算法有关，比如，进程已等待 的时间总和、进程已执行的时间总和 ，是指进程由执行状态转变为阻塞状态所等待发生的，即阻塞原因进程控制信是指用于进程控制所必须的信息，它包括(首)址，以便再调度到该进程执行时，能从PCB中找到其程序和数据；针、信号量等，它们可能全部或部分地放在PCB中； 指针，它给出了本进程(PCB)所在队列中的下一个进程的PCB的首地址进程控制块的组织方在一个系统中，通常可拥有数十个、数百个乃至数千个PCB。目前常用的组织方式有三种。(1)线性方式，即将系统中所有的PCB都组织在一张线性表中，将该表的首址存放在内存的一个区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适(2)方式，即把具有相同状态进程的PCB分别通过PCB中的字成一个队列。形成就绪队列、若干个阻塞队列和空白队列等。就绪队列而言，往往按进程的优先级将PCB从高到低进行排列，将优先级高的进程PCB排在队列的前面。把处于阻塞状态进程的PCB根据其阻塞原因的不同，排成多个阻塞队列，如等待I/O操作完成的队列和等待分配内存图2-11PCB队列示意PCBPCB表中的地址。进程通信进程通信是指进程之间的信息交换。由于进程的互斥与同步，需要在进程间交换一定的信来说明，它们之所以低级的原因在于：①效率低，生产者每次只能向缓冲池投放一个产品(消息)，消费者每次只能从缓冲区②通信对用户不透明，OS只为进程之间的通信提供了共享器在进程之间要传送大量数据时，应当利用OS提供的高级通信工具，该工具最主要的特使用方便。OS隐藏了实现进程通信的具体细节，向用户提供了一组用于实现高级通信令(原语)，用户可方便地直接利用它实现进程之间的通信。或者说，通信过程对用户是透明的。这样就大大减少了通信程序编制上的复杂性。(原语)高效地传送大量的数据。后续PV信方式。高级通信方式可分为三大类：共享内存、消息传递以及管道机制共享器系统(Shared-Memory基于共享数据结构的通信方式基于共享区的通信方式管道(pipe)通信又名pipe文件。向管道(共享文件)提供输入的发送进程(即写进程)以字符流形式将大量的数据送入管道；而接受管道输出的接收进程(即读进程)则从管道中接收(读)数据。由于发送进接收进程是利用管道进行通信的，故又称为管道通信。这种方式首创于UNIX系统，由于机制必须提供以下面的协调能力： 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待②同步，指当写(输入)进程把一定数量(如4KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后再把它唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程③确定对方是否存在，只有确定了对方已存在时才能进行通信息(mesage)为单位，将通信的数据封装在消息中，并利用操作系统提供的一组通信命令(原语)式的不同，可进一步分成两类：直接通信方式：基于OS的发送原间接通信方式：基于共享中间实4、消息传递通信的实现方（1）.OS所提供的发送命令(原直接通信原a对称寻址方式。一对一Send(Receiver，message)；发送一个消息给接收进程；Receive(Sender，message)；接收Sender发来的消息；bsend（，message；recee（d，esage；消息的格进接收进处于同一台器中，有相同的环，所消息的格比较简单，采用为户提供，进程发消息长是可的对于长息系无论处方面还是方面，都可能会付出的开销，但其优点在于方便了用户。进程的同步方在进程之间进行通信时，同样需要有进程同步机制，以使诸进程间能协调通信。不论是发(或接收)或者阻塞。为使在发送进接收进程之间能进行通信，必须在两者之间建立一条通信链路。有两种立链。是发程信显“立”(原语)请求系统为之建立一条通信链路，在链路使用完后拆除链路。用于计算机网络。第二种方式是发送进程无须明确提出建立链路的请求，只须利用系统提供的发送命令(原语)，系统会自动地为之建立一条链路。这种方式主要用于单机系统中。而根据通信方式的不同，则又可把链路分成两种 单向通信链路，只允许发送进程向接收进程发送消息，或者相反bABBA发（2）.信箱的结信箱定义为一种数据结构。在逻辑上，可以将其分为两个部分 2-13信箱通信原系统为邮箱通信提供了若干条原语abmessage)；从指定信箱中接收一个消息；信箱的类类 公用邮箱。由操作系统创建，并提供给系统中的所有核准进程使用5、直接消息传递系统实消息缓冲队列通信机制首先由的Hansan提出，并在RC4000系统上实现，后来被广泛应用于本地进程之间的通信中。在这种通信机制中，发送进程利用Send原语将消息直接发送给接收进程；接收进程则利用Receive原语接收消息。消息缓冲区PCB中有关通信的数据项mq消息队列指针,mutex互斥信号量2.发送进程在利用发送原语发送消息之前，应先在自己的内存空间设置一发送区a，把给目标(接收)进程，发送原语首先根据发送区a中所设置的消息长度a.size来申请一缓冲区i，接着，把发送区a中的信息到缓冲区i中。为了能将i挂在接收进程的消息队列mq上，应先获得接收进程的内部标识符j，然后将i挂在j.mq上。由于该队列属于临界资源，故在insert操作的前后都要执waitsignal操作。2-143.接收进程调用接收原语receive(b)，从自己的消息缓冲队列mq中摘下第一个消息缓冲区i，并将其中的数据到以b为首址的指定消息接收区内。线程概念与多线程模型线程的引入在OS中引入进程的目的是为了使多个程序能并发执行，以提高资源利用率和系统吞吐量，OS具有更好的并发性。首先让我们来回顾进程的两个基本属①进程是一个可拥有资源的独立单位，一个进程要能独立运行，它必须拥有一定的资源，包括用于存放程序正文、数据的磁盘和内存地址空间，以及它在运行时所需要的I/O设备、②进程同时又是一个可独立调度和分派的基本单位，一个进程要能独立运行，它还必须是一个可独立调度和分派的基本单位。每个进程在系统中有唯一的PCB，系统可根据其PCB感知进程的存在，也可以根据其PCB中的信息，对进程进行调度，还可将断点信息保存在其PCB中。反之，再利用进程PCB中的信息来恢复进程运行的现场。正是由于进程有这两个基本属性，才使进程成为一个能独立运行的基本单位，从而也就构成了进程并发执行的基础。程序并发执行所需付出的时空开为使程序能并发执行，系统必须进行以下的一系列操创建进程，系统在创建一个进程时，必须为它分配其所必需的、除处理机以外的所有资源，如内存空间、I/O设备，以及建立相应的PCB；撤消进程，系统在撤消进程时，又必须先对其所占有的资源执行回收操作，然后再撤消PCB；进程切换，对进程进行上下文切换时，需要保留当前进程的CPU环境，设置新选中进程的CPU环境，因而须花费不少的处理机时间。线程如何能使多个程序更好地并发执行，同时又尽量减少系统的开销，已成为近年来设计操作系统时所追求的重要目标。有不少研究操作系统的学者们想到，要设法将进程的上述两个属性分开，由S的指导下，形成了线程的概念。线程与进程的比较调度的基本单位进程内，切换代价在一个进的多个线程之间亦可并发执行，使得操作系统具有更好的并发性线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，线程控制块TCB。独立性,切换代价而言，进程也是远高于线程的。由于一个进的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易支持多处理机系 多线程多处理线程的状态和线程控制块执行状态，线程已获得处理机而正在运行就绪状态，已具备了各种执行条件，只须再获得CPU阻塞状态，在执行中因某受阻而处于暂停状态，例如，当一个线程执行从键盘读入数据的系统调用时，该线程就被阻塞。线程控制块TCB，将所有用于控制和管理线程的信息记录程控制块中。 线程运行状态，用于描述线程正处于何种运行状态④优先级，描述线程执行的优先程度 线程专有器，用于保存线程自己的局部变量拷贝⑥，即对某些信号加以多线程OS通常在多线程OS中的进程都包含了多个线程，并为它们提供资源。OS支持在一个进程是一个可拥有资源的基本单位多个线程可并发执行进程已不是可执行的实体线程的实现方式线程已在许多系统中实现，但各系统的实现方式并不完全相同。在有的系统中，特别是一些数据库管理系统，如nfomix所实现的是用户级线程；另一些系统(如Macinosh和OS/2操作系统)所实现的是内核支持线程；还有一些系统如Soaris操作系统，则同时实现了这两种类型的线程。KST(KernelSupportedOS的，是与内核紧密相关的。内核支持线程KST同样也是在内核的支持下运行的，它们的创建、阻塞、撤消和切换等，也都是在内核空间实现的。为了对内核线程进行控制和管理，在内核对其加以控制。当前大多数OS在多处理器系统中，内核能够同时调度同一进的多个线程并行执行如果进的一个线程被阻塞了，内核可以调度该进的其它线程占有处理器运行，也可以运行其它进的线程；内核支持线程具有很小的数据结构和堆栈，线程的切换比较快，切换开销小内核本身也可以采用多线程技术，可以提高系统的执行速度和效率ULT(UserLevel用户级线程是在用户空间中实现的。对线程的创建、撤消、同步与通信等功能，都无线程切换不需要转换到内核空间调度算法可以是进程的OS平台无关，因为对于线程管理的代码是属于用户程序而用户级线程方式的主要缺点则在于系统调用的阻塞问题。在基于进程机制的OS中，大多数系统调用将使进程阻塞，因此，当线程执行一个系统调用时，不仅该线程被阻塞，而且，进程内的所有线程会被阻塞。而在内核支持线程方式中，则进的其它线程仍然可以运行。在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点，内核每次分配给一个进程的仅有一个CPU，因此，进仅有一个线程能执行，在该线程放弃CPU之前，其它线程只能等待。有些S把用户级线内核支持线程两种方式进行组合，提供了组合方式UT/ST线程。在组合方式线程系统中，内核支持多个内核支持线程的建立、调度和管理，同时，也允许用户应用程序建立、调度和管理用户级线程。2-15线程的实现在仅设置了内核支持线程的OS中，一种可能的线程控制方法是，系统在创建一个新进程时，便为它分配一个任务数据区PTDA(PerTaskDataArea)，其中包括若干个线程控制块TCB空间2-16用户级线程的实运行时系统(Runtime(过程)的集合，其中包括用于创建和撤消线程的函数、线程同步和通信的函数，以及实现线程调度的函数等。正因为有这些函数，才能使用户级线程与内核无关。运行时系统中的所有函数都驻留在用户空间，并作为用户级线程与内核之间的接口。内核控制线这种线程又称为轻型进LWP(LightWeightProcess)。每一个进程都可拥有LWP，LWP都有自己的数据结构(TCB)，其中包括线程标识符、优先级、状态，另外还有栈和局部区等。LWP也可以共享进程所拥有的资源。LWP可通过LWP上，此时它便具有了内核支持线程的所有属性。这种线程实现方式就是组合方式。图2- 利用轻型进程作为中间系线程的创建和终线程的创应用程序在启动时，通常仅有一个线程在执行，人们把线程称为“初始化线程”，它主要功能是用于创建新线程。创建新线程时，需要利用一个线程创建函数(或系统调用)，并提供相应的参数，如指向线程主程序的指针、堆栈的大小，用于调度的优先级等。程的创建函数执行完后，将返回一个线程标识符供以后使用。线程的终由终止线程通过调用相应的函数(或系统调用)(主要是系统线程)，它们一旦被建立起来之后，便一直运行下去而不被终止。在大多数的S中，线程被中止后处理机调度调度的基本概念作业与作业调度的作业通过相应的输入设备输入到磁盘器，并保存在一个后备作业队列中。再由作业调度程序将其从外存调入内存。作业和作业作业(Job)作业步(JobStep)为了管理和调度作业，在多道批处理系统中，为每个作业设置了一个作业控制块JCB，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。JCB(CPU繁忙型、I/O端型)、作业状态、调度信息(优先级、作业运行时间)、资源需求(预计运行时间、要求内存大小等)、资源使用情况等。作业运行的三个阶段和三种状收容阶段运行阶段完成阶段作业调度的主要任务作业调度的主要任务是，根据JCB中的信息，检查系统中的资源能否满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为它们创纳调度(AdmissionScheduling)。在每次执行作业调度时，都需做出以下两个决定。接纳哪些作业调度三级调度高级调度(HighScheduling)，作业调度或长程调度（Long-ermScheduling，主要任务是按一定的原则对外存上处于后备状态的作业进行选择，给选中的作业分配内存、输入/输出设备等必要的资源，并建立相应的进程，放入就绪队列，以使该作业的进程获得竞争处理机的权利。也称为接纳调度（AdmissionScheduing。高级调度的时间尺度通常是分钟、小时或天。（Shor-ermScheduling，主要任务是按照某种策略和方法选取一个处于就绪状态的进程，将处理机分配给它，常见的低级调度有非抢占式和抢占式两高效。中级调度(Intermediate中级调度(Intermediate-LevelScheduling)，中程调度(Medium-TermScheduling)，引入目把阻塞状态进一步分成内存阻塞和外存阻塞两种状态。在调出操作的作用下，可使进程状态由为内存就绪。2-18调度的时机、切换和过程调度的时正在运行的进程运行完毕或发生某而不能再继续运行；在进程通信或同步过运行了某种原语操作，如 操作等在可抢先式调度中，有一个比当前进程优先级更高的进程进入就绪队列；在时间片轮转法中，时间片用完。进程调度的任进程调度的任务主要有三保存处理机的现场信按某种算法选取进程把处理器分配给进程进程调度的切换和过为了实现进程调度，在进程调度机制中，应具有如下三个基本部分上下文切换器调度的基本准则处理机调度算法的共同目平衡性。由于在系统中可能具有多种类型的进程，有的属于计算型作业，有的属于I/OCPU和各种外部设备都能经常处于忙碌状态，调度算法应尽可能保策略强制执行。对所制订的策略其中包括安全策略，只要需要，就必须予以准确地执行，即使会造成某些工作的延迟也要执行。批处理系统的目平均周转时间短平均周转时间：为了进一步反映调度的性能，更清晰地描述各进程在其周转时间中，等待和执行时间的具体分配状况，往往使用带权周转时间，即作业的周转时间T与系统为它提供服务的时间s之比，即W=T。平均带权周转时间：系统吞吐量高。由于吞吐量是指在单位时间内系统所完成的作业数，因而它与批处理处理机利用率高。对于大、中型计算机，CPU价格十分昂贵，致使处理机的利用率成为衡量系统性能的十分重要的指标；而调度方式和算法又对处理机的利用率起着十分重要的作着一定的。分时系统的目响应时间快实时系统的目截止时间的保证可预测性调度方式非抢占方式(Nonpreemptive在采用这种调度方式时，一旦把处理机分配给某进程后，就一直让它运行下去，决不会因件而被阻塞时，才把处理机分配给其它进程。抢占方式(Preemptive程的处理机重新分配给另一进程。在现代OS中广泛采用抢占方式，这是因为：对于批处方式能满足实时任务的需求，抢占方式比较复杂，所需付出的系统开销也较大典型调度算法1、先来先服务(FCFS)调度算照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。由于在实际情况中，短作业(进程)占有很大比例，为了能使它们能比长作业优先执行，而产生了短作业优先调度算法。短作业优先算SJFSJF优先将它们调入内存运行。短作业优先算法的缺必须预知作业的运行时间。在采用这种算法时，要先知道每个作业的运行时间。即使的运行，但此时作业并未完成，故一般都会偏长估计。对长作业非常不利，长作业的周转时间会明显地增长。更严重的是，该算法完全忽视作业的等待时间，可能使作业等待时间过长，出现饥饿现象。在采用FCFS算法时该调度算法完全未考虑作业的紧迫程度，故不能保证紧迫性作业能得到及时处理图2- 3、优先级调度算法(priority-scheduling优先级调度算法的类非抢占式优先级调度算法抢占式优先级调度算优先级的类静态优先范围内的一个整数来表示的，例如0～255中的某一整数，把该整数称为优先数。确定进程进程类型用户要求动态优先对于先来先服务调度算法，作业的等待时间就是作业的优先级，等待时间越长，其优先级其优先级越高,但上述两种优先级都作业的紧迫程度。FCFS算法所考虑的只是作业的等待时间，而忽视了作业的运行时间。SJF算法正好与之相反，只考虑作业的运行时间，而忽视了作业的等待时间。高响应比优先调度算法则是既考业的等待时间过长，从而改善了处理机调度的性能。高响应比优先算法是如何实现的呢?够的时间后，必然有机会获得处理机。该优先级的变化规律可描述RP如果作业的等待时间相同，则要求服务的时间愈短，其优先权愈高，因而该算法有利于短作业。当要求服务的时间相同时，作业的优先权决定于其等待时间，等待时间愈长，其优先权愈高，因而它实现的是先来先服务。对于长作业，作业的优先级可以随等待时间的增加而提高，当其等待时间足够长时，其优先级便可升到很高，从而也可获得处理机因此，该算法实现了一种较好的折衷。5、时间片轮转调度算法（RR（1）.在轮转(RR)法中，系统将所有的就绪进程按FCFS策略排成一个就绪队列。 系统可设置每隔一定时间(如30ms)便产生一次中断去激活进程调度程序进行调度把CPU分配给队首进程并令其执行一个时间片当它运行完毕后又把处理机分配给就绪队列中新的队首进程，也让它执行一个时间片。就可以保证就绪队列中的所有进程在确定的时间段内，都能获得一个时间片的处理机时间。（2）.在RR调度算法中，应在何时进行进程的切换，可分为两种情况 若一个时间片尚未用完，正在运行的 已经完成，就立即激活调度程序，将从就绪队列中删除，再调度就绪队列中队首的进程运行，并启动一个新的时间片（3）.时间片的大小对系统性能有很大的影2-216、多队列调度算7、多级反馈队列调度算（1）.设置多个就绪队列。为各个队列赋予不同的优先级。第一个最高，依次降低。各个队列中进程执行时间片的大小设置为：优先权越高，时间片越短。2-22每个队列都采用FCFS算法FCFS原则等待调度。当轮到片后仍未完成，再依次将它放入第三队列，……，依此类推。当进程最后被降到第n队列后，在第n队列中便采取按RR方式运行。按队列优先级调度。调度程序首先调度最高优先级队列中的诸进程运行，仅当第一队列空闲时才调度第二队列中的进程运行；换言之，仅当第1～(i-1)所有队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时又有新进程进入任一优先级较高的队列，此时须立即把正在运行的进程放回到第i队列的末尾，而把处理机分配给新到的高优先级进程。（2）.终端型用户。大多属于较小的交互性作业，只要能使作业在第一队列的时间片内完成，便可令用户满意。短批处理作业用户。周转时间仍然较短，至多在第二到三队列即可完成长批处理作业用户。将依次在1~n级队列中轮转执行，不必担心作业长期得不到理对于上述调度算法的比较，见表2-12-1否能能能能能能能否平均等待时间兼顾长短作有较好的响应型作业和短批不利于短作业，不利用I/O繁忙型估计时间不易计算响应比的平均等待时文切换浪费能能能否否能能能能能同步与互斥进程同步的基本概念间接相互制约关同处于一个系统中的进程必然共享某种资源，如CPU、I/O设备等，间接相互制约即源于资源共享。如A、B共享，若A申请打印时，已分配给B，则A只能阻塞，等B释放后再改为就绪，又称为"互斥"直接相互制约关这种制约源于进程之间的合作关系。如进程A向B提供数据，当输入缓冲空时，B不能得到数据而阻塞；反之当缓冲满时，A无法写入而阻塞，又称为"同步"临界资源(Critical许多硬件资源如、磁带机等，都属于临界资源，诸进程间应采取互斥方式，实生产者-消费者(producer-consumer具有n区中取走产品去消费。尽管所有的生产者进消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进一个已装满产品且尚未被取走的缓冲区中投放产品。来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针 用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出1。设缓冲池的组织是循环缓冲1in=(in+1)modn；(in+1)modn=out时表示缓冲；in=out则表示缓冲池空int …ITEM; ITEMbuffer［n］;//分配缓冲区intin=0,out=0;//定义指针intcounter=0;//定义计数器在生产者进设一局部变量nextp，用于暂时存放每次刚生产出来的产品；而在消费者进，则设一个局部变量nextc，用于存放每次要消费的产品voidproducer(void*生产者进程produceaniteminnextp; while(counter==n); }voidconsumer(void){ while(counter==0);nextc=buffer［out］;out=(out+1)%n;consumetheitemin}虽然上面的生产者程序和消费者程序，在分别看时都是正确的，而且两者在顺序执行其结果也会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述生产者 消费者 register1=register1+1;register2=register2- counter=register...counter5。如果生产者进程先执行左列的三条机器语言语句，然后counter5；值也还是5，但是，如果按下述顺序执行：register1:=counter；(register1=5)register1:=register1+1；(register1=6)register2:=counter；(register2=5)register2:=register2-1；(register2=4) 正确的counter5，4。读者可以自己试试，倘若再将两段程序中counter=6counter临界资源处理，亦即，令生产者进消费者进程互斥地变量counter。临界区(critical由前所述可知，不论是硬件临界资源还是软件临界资源，多个进程必须互斥地对它进行访问。人们把在每个进临界资源的那段代码称为临界区(criticalsection)每个进程进入临界区之前应先对欲的临界资源进行检查，看是否正在被。如果此刻该临资源未被，该进程可进入临界区，并设置它正在被的标志，在临界区之前执行的这段代码称为进入区（entrysection。在临界区之后也要加上一段代码，用于将临界区被的标志恢复为未被的标志，称为退出区（exitsection）同步机制应遵循的规空闲让进。当临界区空闲时，进程可以立即进入，以便有效地利用临界资源忙则等待。当已有进程进入其临界区时，其它进程必须等待，以保证互斥让权等待。对于等待的进程，它必须立即释放处理机，以避免进程忙等实现临界区互斥的基本方法用软件实现的同步互斥机while(turn!=i);criticalsection算法思想：使Pi进程轮流临界资源，设置一个变量，存放当前有权使用临界资源数据结构：整型变量当turn=i时，表示进程i可以或正在使用临界资源。当turn=j时，表示进程j可以或正在使用临界资源。算法分析：对Pj进程的描述。remaider算法分析：当Pi释放资源后，turn=1，若Pj总处于不临界资源的程序段运行（turn用于实现对的互斥而Pj总不进入打印功能）则turn总等于1，而Pi要再次访算法二：双标志检remainder若i，j两个进程共享某临界资源flag[i]=true，表示进程i正使用临界资源。flag[j]=true，表示进程j正使用临界资源。flag[i]=false，表示进程i没有使用临界资源。flag[j]=false，表示进程j没有使用临界资源。Pi，Pj同时Pi进程执while(flag[j])flag[j]false后，CPU又转Pjjflag[i]=false，也得以进入临界区，因PiPj检测到flag时还没来得及把flag标志改为True这样，出现了Pi，Pj同时进入临界区的情况。分析：实现了空闲临界资源的空闲让Pi，PjPi，Pj同时进注意：在理解这四个算法时，要时刻记住一个前题，PiPj是并发执行的进程。CPU，而只能执行一个小小的时间片。算法三：双标志法后Pi进程：while(flag[j]);criticalsectionremainderPj进程：whileflag[i]);criticalsectionremaindersection算法2是：同时想进，又都进了CS。Pi刚执行完flag[i]：=truePj又执行算法3是：同时想进，互相“挤”，结果谁也进不了CSpiPjflagtrue后，又都立即去检查对方的标志，因而都发现对方也要进入临界区，即对方的标志也为true，于是双方算法3可以有效防止两个进程同时进入临界区，但会造成两个进程都不能临界资源的while(flag[j]&&turn=j);criticalsection(i，j都想进时，进入者取决于若进程j想进入CS而且进程j正在使用CS则等待CS。 while(flag[j]&& flag[i&&turn==i为假进入CS忙则等待，空闲让进虽然可以利用软件方法解决诸进程互斥进入临界区的问题，但有一定难度，并且存在很大的局限性，因而现在已很少采用。目前许多计算机已提供了一些特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。可利用这些特殊的指令来解决临界区问题。上锁之后才能打开中断。进程在临界区执行期间，计算机系统不响应中断，从而不会调度，关中断的方法存在许多缺点①关中断权力可能导致严重 关中断时间过长，会影响系统效率，限制了处理器交叉执行程序的能利用Test-and-Set指令实现互这是一种借助一条硬件指令——“测试并建立”指令TS(Test-and-Set)以实现互斥的方法。在许多计算机中都提供了这种指令。booleanTS(Boolean booleanreturnwhileTS（&lock；criticalsectionlock=FALSE；remaindersection；}利用Swap指令实现进程互voidswap(Boolean*a,Boole