操作系统教案
第一部分：操作系统引论(1)
一、操作系统基本常识
1.计算机是由硬件和软件两部分组成的，而操作系统（Operating System）是配置在计算机硬件之
上的第一层软件，是对计算机硬件的第一次扩充。操作系统是系统软件的基础，其他的系统软件，例如编译程序、汇编程序、数据库管理系统、诊断程序等，都是在操作系统的支持下工作的，都要依赖于操作系统，取得操作系统提供的各类服务。
2.操作系统的目标是什么？
1）方便性：计算机硬件只能识别0或1，即只能识别机器代码，因此没有配置操作系统的计算机是难以使用的；如果配置了操作系统，则可以使用OS提供的各种命令来使用计算机
系统，从而方便了用户，也使计算机变得易学易用。
2）有效性：操作系统可以管理CPU、I/O设备等系统资源，从而避免各种资源使用无需而引起的资源浪费现象。配置了OS的计算机可有效改善系统的资源利用率和提高系统吞吐量。
3）可扩充性：OS采用模块化设计，可适应计算机硬件和体系结构的迅速发展，可方便增加新的功能模块和修改旧的功能模块。
4）开放性：为了适应不同的硬件系统和软件系统，实现硬件设备正确、有效地协同工作，以及实现应用程序地可移植性和互操作性，要求OS具有开放性。
说明：方便性和有效性是OS最重要的两个目标。当前更重视OS使用上的方便性。
3.操作系统的作用有哪些？
1）从一般用户的观点看，OS是用户和计算机硬件系统之间的接口；用户可以通过命令方式或者系统调用方式来使用计算机。
2）从资源管理的观点看，OS是计算机资源的管理者。计算机的资源分为四类：处理器、存储器、I/O设备和信息（数据和程序），相应地，OS系统的主要功能也是对这四类资源的管理，即：处理机管理、存储器管理、I/O设备的管理、文件管理。这也是本课程要介绍的主要内
容。
3）OS可用作扩充机器。没有任何软件支持的计算机，称为裸机，覆盖了软件的机器称为虚拟机（Virtual machine）；每多覆盖一层软件，则虚拟机的功能就越强。
4.操作系统可以用一种层次结构模型描述：底层是OS对象，中间层是对对象进行的操作和管理
的软件的集合；最高层是OS提供给用户的用户接口。
二、操作系统发展历程
1.无操作系统时代：
1）人工操作方式：主要发生在第一代计算机到上世纪50年代中期，此时的程序员通过人工操作方式直接操作计算机硬件系统；用户独占全机和CPU等待人工操作是这种方式的主要缺点。
人工操作方式严重影响了计算机资源的利用率，引起了所谓的“人机矛盾”。后来出现了“通道技术”和“缓冲技术”，用于缓和此矛盾，但是效果不好，再后来引入了“脱机输入输出方式”，获得了良好的效果。
2）脱机输入输出方式：该方式最突出的方式是增加了外围机。外围机的作用在于脱机控制输入设备和输出设备。因为输入和输出都是在脱机状态下进行的，因此可有效减少CPU的空
闲时间，从而缓和了人机矛盾。该中方式的优点是：减少了CPU的空闲时间；提高了I/O
的速度。
2．操作系统时代
1）单道批处理系统（Simple Batch System）：是为提高系统资源利用率和系统吞吐量而提出的，配有监督程序(Monitor)。首先将一批作业以脱机输入输出方式（Off-Line I/O）输入道磁带上，然后在监督程序的监督之下顺序执行。此种方式可保证系统对作业的处理是成批进行的，且内存中总保持一道作业。其效果并不好，目前已经很少使用。其特点是：自动性（无需人工干预）、顺序性、单道性。可以认为SBS是OS的前身。
说明：系统吞吐量是指系统在单位时间内完成的总工作量。
2）多道批处理系统：为进一步提高系统资源的利用率和系统吞吐量，引入了多道程序设计技术，增加了作业调度程序。用户提交的作业都存放在外存上，排成一个队列（后备队列）；然后，由专门的作业调度程序按照一定的算法（？）从后备队列中选择若干个作业调入内存，这些作业共享内存和处理机等资源，可并发运行。优点：提高CPU的利用率（有效避免I/O等待）；提高内存和I/O设备的利用率；增加系统吞吐量。缺点：平均周转时间长；无交互能力。特征：多道性、无序性（作业完成顺序同进入顺序无关）、调度性（作业调度和进程调度）。
说明：作业调度是将作业从外存调入内存，但是不一定占有处理机；进程调度是从已在内存中的作业选择一个作业，将处理机分配给它，使其运行。
平均周转时间：从作业进入系统开始，指导其完成并退出系统所经历的时间。
3）分时系统（Time-Sharing System）：是一台主机+ 多个终端的系统。推动分时系统形成和发展的动力是用户的需要。用户使用计算机时，希望实现“人机交互”，以便能对错误进行
修改，并且希望能独占主机；但是在19世纪60年底，计算机非常昂贵，又不可能每个用
户独占一台主机，所以“共享主机”是一个不错的选择；同时，如果每个用户各自占用一
台终端设备，则可以方便地将自己的作业通过终端设备传输到计算机上处理。
分时系统的定义：是指一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户共享主机的资源，每个用户都可以通过自己的终端以交互的方式使用计算机。
分时系统需要解决的问题：
a. 及时接收：指的是主机要及时接收用户输入的命令和数据
b. 及时处理：指用户通过终端键入命令后能及时控制自己的作业运行或修改自己的作
业。在分时系统中，所有用户的作业都直接进入内存，且在较短短时间内（例如3
秒之内）保证每个作业都运行一次（一个时间片）。
说明：
时间片：指的是一段很短的时间，例如0.1秒，用于进程调度时的时间段表示。
分时系统的实现方法：
a. 单道分时系统：系统内存中只驻留一道程序（作业），其余作业都在外存上。当内
存中的一个作业运行一个时间片后，便被调至致外存（称为调出），再从外存上选
一个作业装入内存（称为调入）并运行一个时间片，如此往返。特点：每个用户的
作业都可以轮流调入内存接受CPU的服务，但是由于每道作业都是频繁的调入调
出多次，开销大，CPU空闲较多，系统性能较差。
b. 具有“前台”和“后台”的分时系统：为充分利用CPU，将内存分为前台区和后台
区，前台区存放按时间片“调入”和“调出”的作业流，后台区存放批处理作业。
只有前台在调入/调出过程中，或者前台已经无作业可运行时，方才可运行后台区
的作业。该类型分时系统能在一定程度提高了系统的性能。
c. 多道分时系统：内存中可同时存放多道作业（程序），每道程序在内存中没有固定
的位置。系统将具备运行条件的作业排成一个队列，这些作业可以轮流获得时间片
来运行。该类系统的特点是：切换作业是在内存中进行，不要花费调入、调出开销，具有较好的性能。现代的分时系统多属于多道分时系统。
分时系统的特点：
(1) 多路性：一台主机上连接多台终端，系统按照分时原则轮流为每个用户服务。多
路性也称为同时性。
（2）独立性：是从用户的角度考虑的，每个用户独占一个终端，各自独立操作，互补干扰，因此，用户感到是他一个人占用主机。
（3）及时性：用户的请求能在很短短时间内获得响应。人所能接受的等待时间是2~3秒，因此，分时系统中让用户等待的时间也限定在该范围内。
（4）交互性：用户通过终端可以同主机进行广泛的对话，以实现人机交互。
. 4) 实时系统（Real-Time System）：多道批处理系统和分时系统虽然已经获得了较好的资源利用率和响应时间，但是无法解决“实时控制”和“实时信息处理”两个领域的应用。
计算机作为控制系统的中心设备，用于生产过程的控制，能保证实时采集现场数据，并对数据进行及时处理和自动控制，例如高炉温度控制、武器控制、自动驾驶系统等。“实时”是“及时”或“即时”的意思，而“实时系统”是指能及时响应外部时间的请求，在规定的时间内完成对该时间的处理，并控制所有实时任务协调一致地运行。
实时任务：控制系统中要求在规定时间内完成的任务称为实时任务，它们都带有某种
程度的紧迫性。分类如下：
（1）按照是否呈现周期性划分
●周期性实时任务：任务按照制定的周期循环执行；
●非周期性实时任务：任务的执行无明显得周期性，但是都同一个截止时间相
联系。截止时间（deadline）分为开始截止时间和完成截止时间。所谓开始
截止时间，是指任务在某时间之前，必须开始执行；所谓完成截止时间，是
指某任务必须在某时间之前完成。
（2）按照对截止时间的要求严格程度划分
●硬实时任务：系统必须满足对截止时间的要求，否则可能出现难以预料的后
果；
●软实时任务：系统也有也一个截止时间，但是对截止时间的要求不严格。若
错过了截止时间，对系统产生的影响也不会很大。
说明：实时系统和分时系统的比较
（1）多路性：都具有多路性。分时系统的多路性指的是系统按照分时原则为多个用户服务，实时系统的多路性是指系统经常对现场的多路信息进行采集及对多个对象
进行控制。
（2）独立性：都具有独立性。分时系统的独立性体现在每个终端用户向系统提出服务时是独立的操作，彼此不相干，实时系统的独立性体现在系统对多路信息采集和
控制时，也是彼此独立的。
（3）及时性：实时信息系统的实时性通分时系统类似，都是以人所能接受的时间来确定，而实时控制系统是以控制对象所要求的开始截止时间和完成截止时间来确定
的，时间要求比较严格。
（4）交互性：实时信息系统中的交互是为了访问系统内的特定资源，分时系统中是系统向终端用户提供各种数据处理服务、资源贡献服务等。
（5）可靠性：分时系统要求系统较为可靠，但实时系统要求系统严格可靠。
三、操作系统定义、特征、服务及功能
1．操作系统的定义：是一组控制和管理计算机硬件和软件资源，合理对各类作业进行调度，以及方便用户的程序的集合。
批处理系统、分时系统和实时系统是三种基本的操作系统类型。一个实际的操作系统，可能兼有三者或者其中两者的功能。
2．操作系统的四大基本特征
1) 并发性（Concurrence）
并发：两个或多个事件在同一个时间间隔内发生。
并行：两个或多个时间在统一时刻发生。
程序是不能并发进行的，是静态实体；为使得程序能并发执行，系统必须为每个程序建
立进程。进程，也称任务，是系统中能独立运行且作为资源分配的基本单位，是一个活动实体。进程之间可以并发执行和交换信息。
2) 共享性（Sharing）：系统中的资源可供内存中的多个并发执行的进程共同使用。有两种共享资
源的方式：互斥共享方式和同时访问方式。
互斥共享方式：有的资源可以供多个进程使用，但是在一个特定的时间段内只能由一个进程占用，这样的资源称为临界资源；其它希望使用该资源的进程必须等待当前进程释放该
资源。
同时访问方式：有的资源（如磁盘）可以允许多个进程同时访问。注意这里的“同时”是一个宏观的概念，在微观上往往是这些进程交替对资源进行访问。
3) 虚拟性（Virtual）：通过某种技术把一个物理实体变成若干个逻辑上的对应物。物理实体实实
在存在的，而后者是虚拟的，是用户感觉到的东西。例如多道分时系统中中只有一个CPU，但是每个终端用户都认为有一个CPU在专门为他服务，此即为利用多道程序技术把一台物理上的CPU变成多台逻辑的CPU。
4) 异步性(A synchronism)：多道环境中，多个进程并发执行，但是由于资源有限，通常进程的执
行并非“一气呵成”，而是以“走走停停”的方式进行，即进程是以异步方式进行的。
说明：并发和共享是操作系统的两个最基本的特征，且互为依存。
3．操作系统提供的服务：操作系统提供了其他程序执行的环境，也为程序和用户提供了一些操作系统的服务。操作系统可以提供诸如程序执行、I/O操作、文件系统操纵、通信以及差错检测等服务，还可以提供系统调用（System Call）服务。
4．操作系统的五大功能
1) 存储器管理功能：为多道程序的运行提供良好的环境。这里的“存储器”指的是内存。主要
有以下功能：内存分配（静态分配、动态分配）、内存保护（每道程序在自己的内存范围内，不能越界）、地址映射和内存扩充（借助虚拟存储技术）
2) 处理机管理功能：实际是对进程的管理。在多道程序环境下，对处理机的管理是以进程为基
本单位的，因此处理机的管理可以归结为对进程的管理。主要有以下功能：进程控制、进程同步、进程通信和调度（作业调度和进程调度）等。
3) 设备管理功能：主要任务是完成用户提出的各种I/O请求，为用户分配I/O设备，提高CPU
和I/O设备的利用率，提高I/O速度，以及方便用户使用I/O设备。主要功能有：缓冲管理（CPU 和I/O设备之间速度不匹配）、设备分配（包括回收）、设备处理（设备驱动）、保证设备的独立性和虚拟性。
4) 文件管理功能：主要是对用户文件和系统文件进行管理，以方便用户使用，并保证文件的安
全性。主要功能包括：文件存储空间的管理、目录管理、文件的读写管理以及文件的贡献与保护等。
5) 用户接口功能：是操作系统为了方便用户使用而向用户提供的“用户与操作系统的接口”，通
常以命令和系统调用的形式呈现出来，有命令接口、程序接口（系统调用）和图形接口几种形式。
5．常见操作系统：有以下几类操作系统
1) 微机操作系统：
（1）单用户单任务操作系统：只允许一个用户使用计算机，且只允许用户程序作为一个任务运行，是一种最简单的操作系统。例如：CP/M和MS-DOS。
（2）单用户多任务操作系统：只允许一个用户使用计算机，但允许将一个用户程序分为若干个任务，使它们并发执行，可有效改善系统的性能。例如OS/2和Windows系列。
（3）多用户多任务操作系统：允许多个用户通过各自的终端，使用同一台主机，共享主机系统中的各类资源，而每个用户程序又可进一步分为几个任务，使它们并发执行，从而进一步
提高了资源利用率和增加系统吞吐量。例如UNIX OS 。
2) 多处理机操作系统MPS（MultiProcessor System）：多台处理机协调工作，可增加系统吞吐量、
节省开支、提高系统的可靠性。
3) 网络操作系统：主要有两种模式C/S模式和对等模式（peer-to-peer）
4) 分布式操作系统：通集中式操作系统不同。处理和控制都集中在一台主机上，所有的任务都由
主机来处理，这样的系统称为集中式操作系统。而分布式操作系统的处理和控制，都是分散在系统的各个处理单元上。
第二部分：进程原理(2~4)
程序是不能独立运行的，而只有将程序调入进程，由系统为程序创建一个或多个进程，程序才可以运行。因此，进程才是资源分配和独立运行的基本单位。
进程是操作系统中极为重要的概念，要深刻理解。
一、程序执行
1. 程序执行
程序顺序执行的特征：1) 顺序性（保证前驱、后继关系）；2) 封闭性（程序不间断执行，占有本机所有资源，资源状态只有本程序可改变，执行结果不受外界影响）；3) 可再现性（只要条件相同，不管何时、何地执行，结果均相同）。
程序并发执行，其特征是为了提高系统运行效率，特征为：
1) 间断性（并发程序之间相互制约，例如互为输入、输出，程序具有“执行――暂停执行――
再次执行”的活动规律）；
2) 失去封闭性（系统资源由多个程序共享，其状态也受多个程序控制；某程序运行时，受到
其他程序的影响）；
3) 不可再现性（失去了封闭性，也将导致失去可再现性）
说明：当多个程序共享一个资源时，由于对资源的访问时刻不定，因此执行结果不定。例如：假设有一软件变量资源N，设当前N＝5，现有两个程序A和B共享该变量，程序A对N
的操作为：N:= N +1 ; 程序B对N的操作为：先利用Print（N）打印N，然后执行N：＝0；由于A和B可以按照不同的速度执行，则语句N:= N +1 ; Print(N) ; N:=0 ; 有可能出现以下几种执行顺序：
（1）N:=N+1; Print(N) ; N=0 ; N的取值分别是6 ，6 ，0
（2）Print(N) ; N:=N+1; N=0 ; N的取值分别是5 ，6 ，0
（3）Print(N) ; N=0 ; N:=N+1; N的取值分别是5 ，0 ，1
以上结果说明，程序A中变量N的值可能是6,也可能是1,结果是可变的；同样情况，程序B 中打印N时其值有可能是6,也可能是5,结果也是可变的。
程序并发执行，虽然能显著提高系统效率，但是出现了“不可再现性”，这显然是不允许的。既要保证系统的效率，又要保证程序执行的“可再现性”，必须采取适当的措施。这些措施的根本就是要保证并发执行的程序对临界资源的独占性访问。
2. 程序并发执行的条件――Bernstein条件
设程序Pi可对多个变量进行操作（资源），操作分为“读操作”和“写操作”，亦即程序Pi在执行过程中作为参考的所有变量的集合称为“读集”，在执行过程中需要修改的所有变量的集合称为“写集”，如下定义：
R(Pi) = {a1, a2 , …,am} ；R(Pi)是Pi的读集
W(Pi) = {b1 , b2 ,…,bn} ；W(Pi)是Pi的写集
若两个程序Pi和Pi能满足如下条件，它们便能够并发执行，并具有可再现性：R(Pi)∩W(Pj) W(Pi) ∩R(Pj) W(Pi) ∩W(Pj) = { }
以上条件是由Bernstein提出的，因此称为Bernstein条件。
理解：只有保证程序Pi的读集和Pj的写集不相交、Pi的写集和Pj的读集不相交、Pi的写集和Pj的写集不相交，才能保证Pi和Pj并发执行，且保证程序的正确执行（可再现性）。
说明：两个程序可以同时对某变量执行“读操作”，但只要有一个“写操作”，则另一个程序就不能再执行“读操作”，也不能再执行“写操作”了，即“写操作”是独占临界资源的。
二、进程基本概念
1．进程：是可执行程序在一个数据集合上的运行过程，是系统资源分配和独立运行的基本单位。其基本特征为：
1) 动态性：进程是进程实体的执行过程，它“由创建而产生，由调度而执行、因得不到资源而
暂停执行，以及由撤消而消亡”。动态性是进程最基本的特征，是同程序不同的。
【程序：是一组指令的集合，存放在某种介质上，无运动含义，是一个静态实体】
2) 并发性：是多个进程实体同时运行表现出来的特征。并发性说明的是“同一段时间”，同并行
性不同。
3) 独立性：指的是进程实体是一个能独立运行和获得资源的基本单位。如果某程序没有建立进
程，则不能作为一个独立的单位参与运行。
4) 异步性：多个进程各自独立运行，其运行速度是不可预知的。该特种导致了程序执行的不可
再现性，因此操作系统必须采取有效措施保证各程序（进程）之间能协调运行。
5）结构特征：进程实体是由程序段、数据段以及进程控制块（PCB）三部分组成的。
2．进程基本状态
有五个基本状态：
1) 新状态（New）：进程刚刚建立，还未送入就绪队列的状态。
2) 就绪状态（Ready）：进程获得了除处理机（CPU）之外的所有资源，一旦获得了处理机，便
可立即执行。一个系统中可有多个进程同时处于就绪状态，这些进程可排成一个或多个队列，这样的队列称为就绪队列。
3) 执行状态（Execute）：进程已经获得处理机，其对应的程序正在执行。单处理机系统中，系统
中只有一个进程处于执行状态，而在多处理机系统中，可能有多个进程同时处于执行状态。
4) 阻塞状态（Block）：某进程正在执行重，但是因为某些原因（例如等待I/O）暂时停止了执行，
此时进程转入阻塞状态，处理机被剥夺。注意阻塞状态一定是由执行状态转过来的。阻塞状态也称为“睡眠”状态或“等待”状态。同就绪队列近似，系统中处于阻塞状态的进程也排成一个队列，或者根据阻塞原因排成多个队列，这些队列称为阻塞队列。
处于阻塞状态的队列，只有其I/O完成，或者需要的资源得到了，则从阻塞队列重转出，排到就绪队列的尾部，等待接收系统的重新调度。
5) 终止状态（Terminated）：进程结束（不管正常结束，还是异常结束），操作系统将它从就绪队
列中移出，但是还没有撤销时的状态。
说明：如果当前进程正在执行，则它仍处于就绪队列中，仅是其PCB中有关进程状态的字段要修改为“正在执行”状态。之所以如此，是因为在进程并发时，进程不可能总占有处理机，操作系统会根据各种不同策略为进程分配处理机，所以进程的执行过程是“走走停停”式的，是在“就绪”――“执行”――“就绪”的状态中来回切换的。
3．进程五大基本状态的切换
一个进程只有一次新状态和终止状态，但可有多次就绪状态、阻塞状态和执行状态。有以下几种状态转换的情况。
1) 新状态→就绪状态：系统的就绪队列允许接收新的就绪队列时，操作系统就将处于新
状态的进程移入就绪队列，此时完成了进程的“新状态”到“就绪状态”的转变。
2) 就绪状态→执行状态：进程调度程序为就绪队列中优先（如何判断优先？）的进程分
配处理机，则该进程由就绪状态变成了执行状态，该进程称为当前进程。
3) 执行状态→阻塞状态：当正处于执行状态的进程需要访问临界资源，而临界资源正在
被其它资源访问时，或者进程需要等待I/O时，进程将由执行状态变为阻塞状态，进
程也将进入阻塞队列。
4) 执行状态→就绪状态：当前进程时间片用完，或者有更高优先级的进程出现时，当前
进程的处理机被剥夺，执行状态就变为就绪状态。注意：仅处理机被剥夺，而其他所
有资源还占据的状态是就绪状态，如果资源不完备，或者进程需要I/O，则进入阻塞状
态。
5) 阻塞状态→就绪状态：阻塞进程获得了所需的全部资源(除了处理机)，并且I/O也已经
完成，则可由阻塞状态转为就绪状态，等待进程处理程序的调度而重新获得处理机。
6) 执行状态→终止状态：进程完成，不管是正常完成，还是异常结束，都将执行状态变
为终止状态，等待系统撤消。
4. 进程的挂起状态（Suspend）
是一种新引入的状态，是一种静止状态。处于此状态的进程，得不到处理机调度。处于挂起状态的进程被调出内存，进入外存暂时存放。其原因可能基于：
1) 终端用户的需要；2) 父进程的要求；3) 操作系统的需要；4) 对换的需要；5) 负荷调节
的需要。
【所谓对换，指的是为了缓和内存紧张的情况，将内存中处于阻塞状态的进程换至外存上，此时进程将处于一种有别于阻塞状态的另一种状态，称为静止阻塞状态。该状态的进程即处于挂起状态，确切地说，该进程处于静止阻塞状态，因为即使该进程获得了所有资源，或者其预想的事情（例如I/0）已经发生能够，其仍不具备运行条件，仍不能进入就绪队列】
引入挂起状态的进程，又增加了从挂起状态（静止状态）到非挂起状态(活动状态)的转换，或者相反。为同原有的就绪、阻塞状态相区别，原有的非挂起状态下的就绪、阻塞状态分别称为活动就绪状态、活动阻塞状态，而挂起状态下的就绪、阻塞状态称为静止就绪状态、静止阻塞状态。状态转换图如下所示。
（1）活动就绪→静止就绪（ReadyA→ReadyS）：
（2）静止就绪→活动就绪(ReadyS→ReadyA)：如果利用激活原语Active将进程激活后，静止就绪状态的进程变为活动就绪状态，此时进程可以再调度执行。
（3）活动阻塞→静止阻塞(BlockA→BlockS)：利用挂起原语Suspend将进程挂起时，活动阻塞状态的进程变为静止阻塞状态。即使该进程所期待的事件发生了（例如I/O完成），也不能进入活动就绪队列，而只能进入静止就绪队列。
（4）静止阻塞→活动阻塞(BlockS→BlockA)：如果利用激活原语Active将进程激活后，静止阻塞状态的进程变为活动阻塞状态。
5．进程控制块PCB
进程控制块是进程实体的一部分，是操作系统中最重要的记录型数据结构，PCB中记录了操作系统所需要的，用于描述进程情况及控制进程运行所需的全部信息。
PCB的特征：1) 常驻内存；2) 是进程存在的唯一标识；3) 一个进程对应一个PCB；4) 可以被多个系统模块访问；5) OS中有专门的PCB区。
PCB中包含的信息：
（1）进程标识符信息：例如外部标识符（字母，用户访问进程时使用）、内部标识符（整数，系统使用）、父进程标识符、子进程标识符以及用户标识符（谁拥有该进程）等。
（2) 处理机状态信息：现场保护、现场恢复，例如通用寄存器、PC、PSW、SP等的信息。
（3) 进程调度信息：进程当前状态、优先级、进程调度所需的信息以及阻塞原因（事件）等。
（4) 进程控制信息：例如程序和数据的地址、进程同步和通信机制、资源清单以及链接指针等。
PCB的组织方式：
（1）链接方式：把具有相同状态的PCB用其中的链接字，链接成一个队列。
（2）索引方式：系统根据所有进程的状态，建立几张索引表，索引表的每一个表项指向一个PCB的物理块。
三、进程控制
1．处理机的执行状态：系统态和用户态。
1) 系统态又称为核心态，具有较高的特权，能访问所有寄存器和存储区，能执行一切执令。
2) 用户态具有较低特权的执行状态，只能执行规定的指令，访问指定的寄存器和存储区。
通常情况下，用户程序运行在用户态，OS内核通常运行在系统态。进程控制就是由OS内核实现的。
2．操作系统内核
操作系统内核是计算机硬件的第一次扩充，内核执行OS与硬件关系密切，执行频率高的模块，它们是常驻内存的。多数OS包括下述功能：
1) 支撑功能：包括中断处理功能、时钟管理功能、原语操作等。
2) 资源管理功能：包括进程管理、存储器管理、设备管理等。
中断：计算机在执行程序的过程中，当出现异常情况或特殊请求时，计算机停止现行程序的运行，转向对这些异常情况或特殊请求的处理，处理结束后再返回到现行程序的间断处。这就是“中断”。
3．进程的创建及终止
1) 进程图：是用于描述进程家族关系的有向树，表现进程之间的父子关系。父进程和子进程关系为：（1）父进程创建子进程；（2）子进程继承父进程的资源，文件以及缓冲区；（3）子进程随父进程的撤消而撤消；（4）子进程撤消时，其从父进程获得的资源全部归还父进程。
2) 什么时候创建进程？（引起创建进程的事件）
（1）用户登录；（2）作业调度；（3）提供服务；（4）应用请求。
3) 什么时候终止进程？（引起终止进程的事件）
（1）正常结束；（2）异常结束（出现错误或故障）；（3）外界干预（例如操作系统干预、父进程干预、父进程终止等）。
4) 进程创建步骤：
（1）申请空白PCB（为进程分配唯一数字标识符，从PCB集合中索取空白PCB块）；（2）为新进程分配资源（为进程的程序和数据，以及用户栈分配内存资源）；（3）初始化进程控制块（包括初始化标识符信息、处理机状态信息以及处理机控制信息）；（4）将新进程插入就绪队列（如就绪队列能够接纳新进程，则插入）。
5) 进程的终止步骤：
OS调用进程终止原语，按下述过程终止指定进程：
（1）从PCB集合中检索当前进程PCB，并从中读出进程状态；（2）终止进程的执行（修改其调度标志为真，以保证终止后应重新调度）；（3）终止子孙进程；（4）释放资源（或归还给其父进程，或归还给系统）；（5）将被终止进程的PCB从它所处的队列中移出。
4．进程阻塞及唤醒
1) 引起进程阻塞和唤醒的事件
（1）请求系统服务，如：打印服务；
（2）启动某种操作，如：启动I/O或启动打印机；
（3）新数据尚未到达；
（4）无新工作可做，发送一消息之后等待的时候。
2) 进程阻塞过程
(1)终止进程的执行，将进程的状态改为阻塞态；
(2)将进程插入相应的阻塞队列；
(3)转进程调度例程，重新进行进程调度，以将CPU分配给其它进程。
3) 进程唤醒过程
(1)将进程从阻塞队列中移出；
(2)将进程状态由阻塞改为就绪；
(3)将进程插入就绪队列。(有可能立即得到调度，也有可能在就绪队列中等待)
【说明：进程阻塞用Block原语，进程激活用Active原语。需要说明，这是两个作用相反的原语。】
5．进程挂起与激活
1) 进程的挂起过程：调用挂起原语suspend( )。suspend的执行过程：（1）检查被挂起的进程的状态，如正处于活动就绪状态或执行状态，则将其修改为静止就绪状态；如正处于活动阻塞状态，则将其修改为静止阻塞状态；（2）复制改进程的PCB到指定的内存区域，以方便用户或父进程检查其运行情况；（3）如果被挂起的进程正在执行，则转调度程序重新调度新的进程。
2) 进程的激活过程：调用激活原语Active（）。执行过程：（1）将进程后外存换入内存；（2）检查现行状态，若是静止就绪（阻塞）状态，则修改为活动就绪（阻塞）状态；（3）如采用抢占调度策略，且有新进程进入就绪队列，则还可能转入进程调度程序：如当前进程优先级较低，则立即剥夺其执行，将处理机分配给刚被激活的进程，否则就不必重新调度，继续原先进程的执行即可。
四、线程
1．线程的引入（减少时空开销，提高系统的并发性）
上个世纪60年代，进程的概念被提出，在OS中进程一直作为资源分配合独立运行的基本单位。直到80年代中期，人们又提出了比进程更小的能独立运行的基本单位――线程。
提出线程的目的是为了进一步提高系统内程序并发执行的程度，进一步提高系统吞吐量。目前新近推出的OS和DBMS中都引入了线程的概念。
引入线程的目的：为了减少程序并发执行时所付出的时空开销，保证OS具有更好的并发性。为保证程序能并发运行，系统必须进行以下操作：创建进程、撤消进程和进程切换，而这一切，系统都必须付出较大的时空开销。
多个进程进入内存，可保证良好的并发性，但是进程越多，切换的频率越大，系统为之付出的时空开销就越大，实际上系统的性能将有所降低。如果既要保证并发性，又要减少系统时空开销，则必须采取新的措施。由此，线程被提出了。
线程：线程是进程的一个实体，是被系统独立调度和分派的基本单位。线程有进程生成，本身基本上不拥有资源，仅有一点自己的运行过程中必不可少的资源（例如程序计数器、堆栈等），但是它可以利用创建它的进程的所有资源。一个进程可以创建多个线程，线程也可以创建或撤消另一个线程，这些线程共享进程的资源。同一个进程的线程之间可以并发执行，线程之间相互制约，也呈现间断性（异步性），因此，线程也同样拥有就绪、阻塞和执行三种基本状态，有的系统中还有终止状态。
2．线程和进程的比较
线程：轻型进程（Light-Weight Process），也称为进程元；
进程：重型进程（Heavy-Weight Process）
一个进程都有若干个线程，至少有一个线程。线程和进程有一些相似之处，下面我们从调度、
并发性、拥有资源、系统开销等方面对它们进行比较。
调度：传统OS中，进程是资源分配和独立执行的基本单位，而在引入线程的OS中，进程仅是资源拥有的基本单位，线程称为调度和分派的基本单位。进程的两个属性（资源分配，独立执行）被分开，从而线程可轻装上阵，可提高系统并发程度。
同一进程的线程切换不会引起进程的切换，不同进程的线程的切换将会引起进程切换。
并发性：在引入线程的OS中，不仅进程之间可以并发，同一进程之间的线程也可以并发，从而有效提高了并发程度。
拥有资源：进程是拥有资源的，而线程基本上不拥有资源，但是同一个进程的线程可以共享进程的资源。
系统开销：进程的创建和撤销，系统都需要为之分配和撤销资源（如内存空间、I/O设备等），而系统创建线程实，没有资源分配合撤销的问题，因此系统开销远远小于进程；同时，进程切换时，系统需要保护旧进程的线程、设置新进程的初始环境，也需要很大的系统开销，而线程切换时，除了保护几个优先的寄存器之外，不涉及有关存储器管理的有关方面，因此系统开销非常小。另外，由于同一进程的线程占有相同的地址空间，线程同步和通讯的开销也非常小。
线程分为用户级线程和内核支持线程。
五、进程同步
OS系统引入进程，提高了系统效率和吞吐量，但是进程运行的异步性，导致了结果的不可再现性和差错，因此必须采取措施保证进程执行结果的可再现性和正确性。这就是进程同步提出的原因。
进程同步的主要任务：使并发执行的进程之间能有效利用资源和相互合作，从而使程序的执行具有可再现性。
1．多道程序环境下进程之间的关系
资源共享：进程之间彼此无关，互不知道对方的存在。但是处在一个环境之下，运行时需资源共享（如共享CPU和I/O设备）。进程同步的主要任务是保证进程能互斥地访问临界资源。系统中的资源不是由用户进程直接使用的，而是由系统（操作系统）统一分配的。亦即：用户进程要使用某资源，必须首先咨询系统：资源被其他进程占有吗？如果占有，则当前进程或等待，或进入阻塞状态；如果资源处于空闲状态，则当前进程占有该资源，继续执行，执行完毕后，释放资源，其他进程方可再次占有该资源。
相互合作：如果进程之间具有某种合作关系，例如进程A的输出作为进程B的输入。则进程同步的目的是保证进程A和进程B在执行次序上协调一致，不会出现与时间有关的差错。后面介绍到的“生产者－消费者”问题就是一个典型的具有合作关系的进程同步问题。
2．临界资源和临界区
临界资源：一段时间内只允许一个进程访问的资源。临界资源要求“独占”，即要被“互斥”地被访问。
临界区：每个进程中访问临界资源的代码。如下:
说明：如果每个进程都能保证互斥地进入自己的临界区，则能保证互斥访问临界资源。
entry section，进入区：其作用时保证进程进入临界区之前先对欲访问的临界资源的当前状态进程检查，看它是否正在被访问。如此时临界资源未被访问，则进程可以进入临界区，对资源进行访问，并设置临界资源的访问标志为“占用”状态；如果此时临界资源处于占用状态，则说明其他进程正在访问它，为避免混乱，本进程不能进入临界区。
exit section，退出区：是临界区后面的一段代码，用于恢复刚才在临界区中访问的临界资源的标志为“未被占用”状态，以便于其他的进程可进入自己的临界区。
remainder section，剩余区：进入区、临界区、退出区之外的其它代码。
3．同步四原则
1) 空闲让进：当临界资源空闲时，允许进程访问，以有效利用临界资源；
2) 忙则等待：当临界资源忙时，进程将不能进入临界区对临界资源进行访问，只能等待，以保
证进程互斥访问临界资源；
3) 有限等待：不要“死等”，要保证进程能在有限时间（可以忍受的时间）内进入临界区访问临
界资源；
4) 让权等待：如果进程不能进入临界区，即当前无法访问临界资源，则应立即释放处理机，让
其他符合运行条件的进程有机会获得处理机，以免当前进程陷入“忙等”状态。
4．互斥问题的解决
可以采用软件方法解决进程互斥问题，也可以用硬件方法解决进程互斥问题。目前用软件方法解决进程互斥的方法已经很少使用，但是从理解的角度出发，利用软件方法解决，还是有些意义的。
经典进程同步问题
生产者－－消费者问题
1．利用记录型信号量解决生产者一消费者问题
mutex：使诸进程互斥地访问缓冲区（n个缓冲区）
empty、full：空、满缓冲区数量。
Var mutex,empty,full:semaphore:=1,n,0; buffer:array[0,1,…,n-1] of item;
in, out: integer: =0,0;
begin
parbegin
producer: begin
repeat
…
Produce an item in nextp;
…
wait(empty);
wait(mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
signal(mutex);
signal(full);
Until false;
End
consumer:begin
repeat
wait(full);
wait(mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
signal(mutex);
signal(empty);
Consumer the item in nextc;
Until false;
end
parend
end
2．利用AND信号量解决生产者——消费者问题var mutex, empty, full: semaphore:=1,n,0;
buffer:array[0,…,n-1] of item;
in out: integer :=0,0;
begin
parbegin
producer: begin
repeat
…
produce an item in nextp;
…
swait(empty, mutex);
buffer(in):=nextp;
in:=(in+1) mod n;
ssingal(mutex, full);
Until false;
End
Consumer: begin
repeat
swait(full, mutex);
nextc:=buffer(out);
out:=(out+1) mod n;
ssignal(mutex, empty);
consumer the item in nextc;
until false;
end
parend
end
六、信号量机制
1.整型信号量机制
wait和Signal操作(PV操作)：
Wait(s)：while s≤0 do no-op
s：=s-1.
Signal(s)：s：=s+1
注：wait(s)和Signal(s)都是原子操作。
使用整型信号量的缺点：“忙等”不停检测，直到本次时间片用完，并未遵循“让权等待”的准则。
2.记录型信号量机制
特点：可以实现让权等待。
procedure wait(s)
var s：semaphore
begin
s value：=s.value-1;
if s.value<0，then block(S.L)
end
procedure Signal(s)
var s：semaphore
begin
s value：=s.value+1;
if s.value<=0 then wakeup(S.L)
end
s.value>=0时，s.value的值表示资源数量；s.value<0时，|s.value|的值表示某资源的等待队列中进程的数量。
每次的wait(s)操作，意味着进程请求一个单位的资源，因此描述为s.value：=s.value-1;当s.value<0时，表示资源已分配完毕，因而进程调用block原语，进行自我阻塞，放弃处理机，并插入到信号链表S.L中。
每次的Signal(s)操作，意味着进程释放一个资源，故s.value：=s.value+1操作表示资源数目加1。若加1后仍是S.value<=0，则表示在该信号链表中，仍有等待该资源的进程被阻塞，故还应该调用wakeup原语，将S.L链表中的第一个等待进程唤醒。
如果S.value的初值为1，表示只允许一个进程访问临界资源，此时的信号量转化为互斥信号量。
3.AND型信号量机制
AND型信号量集机制的目的在于解决进程共享多个临界资源的互斥问题。
AND同步机制的基本思想是：将进程在整个运行过程中所需要的所有临界资源，一次性地全部分配给进程，待该进程使用完后再一起释放，只要还有一个资源不能分配给该进程，其它所有可能为之分配的资源，也不分配给它。
实现：
Swait(S1，S2，……S n)
if S1≥1 and …and S n≥1 then
for i：=1 to n do
end for
else
place the process in the waiting queue with the first S i found with S i<1, and set the program count of this process to the beginning of Swait operation
end if
SSignal.(S1，s2，……s n)
for i：=1 to n do
S i=S i +1;
remove all the process waiting in the queue associated with S i into the ready queue
endfor
4.信号量集机制
1）当信号量必须大于一个给定值(不一定是1)而且每次分配的资源数为给定值(不一是1个单位)的信号量集机制。
实现：
Swait(S1，t1，d1，……S n，t n，d n).
if S1≥t1 and …and s n≥t n then
for i：=1 to n do
S i：=S i-d i
end for
else
Place the executing process in the waiting queue of the first S i with S i＜ti and set its program counter to the beginning of the Swait Operation.
end if
Signal(S i，d i，……;s n，d n)
for i：=1 to n do
S i：= Si+d i
Remove all the process waiting in the queue associated with S i into the ready queue
end for
2）一般“信号量集”的几种特殊情况。
（1）Swait(S,d,d)：允许每次申请d个资源。
当资源数少于d时，不予分配。
（2）Swait (S,1,1)：S>1，记录型信号量。
S=1时，互斥型信号量。
（3）Swait(S,1,0)，可控开关，当时，允许进入，S<1时，不能进入。
信号量的应用
1.利用信号量实现互斥
var mutex: semaphore:=1
begin
parbegin
process1:begin
repeat
wait(mutex);
critical setion
signal(mutex);
remainder section
until false;
end