操作系统引论

操作系统的定义

从资源管理的观点：操作系统是控制和管理计算机的软、硬件资源，合理组织计算机的工作流程，以方便用户的程序集合
从用户的观点：操作系统是配置计算机硬件上的第一层软件，是对硬件系统的第一次扩充
操作系统的目标：
1. 有效性：提高系统资源利用率、提高系统吞吐量
2. 方便性：方便用户通过OS操纵计算机系统
3. 可扩充性：适应计算机硬件、体系结构以及应用的发展
4. 开放性：遵循世界标准规范
操作系统的作用
1. 作为用户与计算机硬件系统之间的接口
  - 用户可通过三种方式使用计算机：命令方式、系统调用方式、图形窗口方式
2. 作为计算机系统资源的管理者
  - 四类资源：处理机管理、存储器管理、I/O设备管理、文件管理
  - 处理机可执行的指令分为：特权指令（只能由操作系统使用）、非特权指令
  - 处理机状态划分为：管态、目态
  - 处理机状态保证了特权指令的正确使用，把OS与用户程序区分开来
3. 实现了计算机资源的抽象
  - 裸机上覆盖上一层I/O设备管理软件，隐藏I/O设备操作的细节
操作系统发展的主要动力：
1. 不断提高计算机资源的利用率
2. 方便用户
3. 器件的不断更新迭代
4. 计算机体系结构的不断发展

操作系统的发展过程

无操作系统的计算机系统
1. 人工操作方式：打孔纸带
  
  缺点：用户独占全机、CPU等待人工操作
2. 脱机输入输出：解决人机矛盾及CPU和I/O设备速度不匹配的矛盾。将装有用户程序和数据的纸带(或卡片)装入纸带输入机(或卡片机)，在一台外围机的控制下，把纸带(卡片)上的数据(程序)输入到磁带上。当CPU需要这些程序和数据时，再从磁带上将其高速地调入内存。
  
  减少了CPU空闲时间，提高了I/O速度。
单道批处理系统
- 把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下使这批作业能一个接一个地连续处理。
- 特征：自动性、顺序性、单道性
多道批处理系统
- 在该系统中，用户所提交的作业都先存放在外存上并排成一个队列，称为“后备队列”；然后，由作业调度程序按一定的算法从后备队列中选择若干个作业调入内存，使它们共享CPU和系统中的各种资源。
- 优点：提高CPU利用率、提高内存和I/O设备利用率、增加系统吞吐量
- 特点：资源利用率高、系统吞吐量大、平均周转时间长、五交互能力
- 需要解决的问题：处理机管理问题、内存管理问题、I/O管理问题、文件管理问题、作业管理问题
分时系统
1. 概念
  1. 分时：CPU时间分段处理
  2. 时间片：CPU的时间段
  3. 响应时间：从终端发出请求到系统给予回答所经历的时间
2. 分时系统的产生：分时系统(Time Sharing System)与多道批处理系统之间有着截然不同的性能差别，它能很好地将一台计算机提供给多个用户同时使用，提高计算机的利用率。用户的需求具体表现在以下几个方面：
  1. 人机交互
  2. 共享主机
  3. 便于用户上机
3. 分时系统实现中的关键问题
  1. 及时接收：配备多路卡，用于主机同时接受各用户从终端输入的数据。配置缓冲区缓存用户键入指令
  2. 及时处理：人机交互关键，使用户键入命令后能及时控制自己作业运行。所以各个用户作业都必须在内存中。
4. 分时系统特征：多路性、独立性、及时性、交互性
实时系统

实时系统是指系统能及时(或即时)响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。
1. 实时任务
  1. 按任务执行时是否呈现周期性来划分：周期性实时任务、非周期性实时任务
  2. 根据对截止时间的要求来划分：硬实时任务、软实时任务
2. 实时系统与分时系统特征比较
  1. 多路性：实时控制系统的多路性则主要表现在系统周期性地对多路现场信息进行采集，以及对多个对象或多个执行机构进行控制。而分时系统中的多路性则与用户情况有关，时多时少。
  2. 独立性
  3. 交互性：实时信息处理系统虽然也具有交互性，但这里人与系统的交互仅限于访问系统中某些特定的专用服务程序。它不像分时系统那样能向终端用户提供数据处理和资源共享等服务
  4. 及时性
  5. 可靠性：实时系统要求较高

操作系统的基本特性

并发性、共享性、虚拟性、异步性。并发和共享是操作系统两个最基本的特征。

并发性
1. 并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。
2. 多道程序环境下，并发性指在一段时间内，宏观上多个程序同时执行，但微观上每一时刻只有一个程序执行
3. 进程：是指在系统中能独立运行并作为资源分配的基本单位。引入进程的目的：使多个程序能够并发执行
4. 线程：在一个进程中可以包含若干个线程，可以利用进程拥有的资源。
5. OS中，将进程作为资源分配的基本单位，将线程作为独立运行、调度的基本单位。
共享性
1. 互斥共享方式：一段时间只允许一个进程（线程）访问资源，如打印机。
2. 同时访问方式：进程可以交替对该资源进行访问，如磁盘设备。
虚拟性
1. 时间复用技术
  1. 虚拟处理机技术：利用多道程序设计技术，为每道程序建立一个进程，多道程序并发执行，以此分时使用一台处理机。
  2. 虚拟设备技术：将一台I/O设备虚拟为多台逻辑上的I/O设备，允许每个用户占用一台逻辑上的I/O设备。
2. 空分复用技术：将一个频率范围非常宽的信道，划分成多个频率范围较窄的信道，其中的任何一个频带都只供一对用户通话。在计算机中也使用了空分复用技术来提高存储空间的利用率。
  1. 虚拟磁盘技术：一台磁盘虚拟为多台虚拟磁盘
  2. 虚拟存储器技术：空分复用可以利用存储器的空闲空间来存放其它的程序，以提高内存的利用率。虚拟存储技术本质上是内存分时使用，通过时分复用方式，在远小于程序的内存空间中运行。
异步性：在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。由于资源等因素的限制，使进程的执行通常都不是“一气呵成”，而是以“停停走走”的方式运行。

操作系统的主要功能

处理机管理功能：进程控制、进程同步（互斥、同步）、进程通信、进程与作业调度
存储器管理功能：内存分配、内存保护、地址映射、内存扩充（虚拟技术）
设备管理功能：缓冲管理、设备分配、设备处理、I/O控制、磁盘调度
文件管理：文件存储空间的管理、目录管理、文件读写管理和保护
操作系统与用户之间的接口：命令接口（联机命令接口、脱机命令接口、图形用户界面）、程序接口（也称系统调用）

操作系统设计

传统操作系统结构
1. 无结构操作系统
2. 模块化结构OS：将OS按其功能精心地划分为若干个具有一定独立性和大小的模块；每个模块具有某方面的管理功能。仔细地规定好各模块间的接口，使各模块之间能通过该接口实现交互；进一步将各模块细分为若干个具有一定功能的子模块。
  
  优点：提高OS设计的正确性、可理解性和可维护性；增强OS适应性、加速OS开发过程
  
  缺点：模块间接口难满足实际需求；开发无序。
3. 分层式结构OS：为了将模块-接口法中“决定顺序”的无序性变为有序性，引入了有序分层法。
  
  在目标系统An和裸机系统A0之间铺设若干层次软件，最终能在A0上运行。常采用自底向上法铺设。
  
  优点：易证明正确性、易扩充和维护；缺点：系统效率降低。
客户/服务器模式（C/S模式）
1. 组成：客户机（在一个LAN网络上连接多台网络工作站）、服务器（规模较大的机器）、网络系统（用于连接所有客户机和服务器）
2. C/S模式优点：数据的分布处理和存储；便于集中管理；灵活性和可扩充性；易于改编应用软件
面向对象的程序设计
微内核OS结构
1. 足够小的内核：微内核并非是一个完整的OS，而只是操作系统中最基本的部分，它通常用于：① 实现与硬件紧密相关的处理；② 实现一些较基本的功能；③ 负责客户和服务器之间的通信。它们只是为构建通用OS提供一个重要基础，这样就可以确保把操作系统内核做得很小。
2. 基于客户/服务器模式
3. 应用机制与策略分离原理
4. 采用面向对象技术
微内核的基本功能：进程管理、低级存储器管理、中断和陷入处理

习题

在计算机系统中配置操作系统的主要目的是(A)，操作系统的主要功能是管理计算机系统中的(B)，包括©和(D)，以及文件和设备。这里©的管理主要是对进程进行管理。

A (1) 增强计算机系统的功能 (2) 提高系统资源的利用率 (3) 提高系统运行速度 (4) 合理组织系统的工作流程以提高吞吐量

B (1) 程序和数据 (2) 进程 (3) 资源 (4) 作业 (5) 软件 (6) 硬件

C, D (1) 存储器 (2) 虚拟存储器 (3) 运算器 (4) 处理机 (5) 控制器
操作系统是一种系统软件，它负责为用户和用户程序完成(A)的工作。

A (1) 与硬件无关并与应用无关 (2) 与硬件相关而与应用无关 (3) 与硬件无关而与应用相关 (4) 与硬件相关并与应用相关
在多道批处理系统中，为了充分利用各种资源，系统总是优先选择(A)多个作业投入运行；为了提高吞吐量，系统总是想方设法缩短用户作业的(B)

A (1) 适应于内存容量的 (2) 计算量大的 (3) I/O量大的 (4) 计算型和I/O型均衡的

B (1) 周转时间 (2) 运行时间 (3) 提交时间 (4) 阻塞时间
分时系统响应时间（及时性）主要是根据(A)确定的，而实时系统的响应时间则是由(B)确定的。

A, B (1) 时间片大小 (2) 用户数目 (3) 计算机运行速度 (4) 用户所能接受的等待时间 (5) 控制对象所能接受的时延 (6) 实时调度
分时系统和实时系统都有交互性，实时系统的交互性允许用户访问(A)，分时系统的交互性允许用户请求系统提供(B)。

A (1) 文字编辑程序 (2) 专用服务程序 (3) 专用硬件 (4) 数据处理程序

B (1) 数据处理服务 (2) 资源共享服务 (3) 数据通信服务 (4) 多方面的服务

答案：1. A(2) B(3) C(4) D(1) 2. A(2) 3. A(4) B(1) 4. A(4) B(5) 5. A(2) B(4)

进程管理

进程的基本概念

程序的顺序执行：在各程序段之间，必须按照某种先后次序顺序执行

程序顺序执行的特征：顺序性、封闭性（程序一旦开始，执行结果不受外界影响）、可再现性
程序的并发执行
1. 并发程序：是指两道或两道以上程序同时装入内存中运行，这些程序的执行在时间上互相有重叠，即在一个程序执行结束之前，另一个程序已经开始执行。
2. 特征：间断性、失去封闭性、不可再现性
进程的特征和定义

在多道程序环境下，程序的执行属于并发执行，此时它们将失去其封闭性，并具有间断性及不可再现性的特征。为使程序能并发执行，且为了对并发执行的程序加以描述和控制，人们引入了“进程”的概念。
1. 进程的定义
  - 进程是程序的一次执行
  - 进程是一个程序及其数据在处理机上顺序执行所发生的活动
  - 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位
2. 进程的特征：
  - 结构性：通常程序无法并行执行，为使程序能独立运行，应配置一个进程控制块（PCB）；由程序段、相关数据和PCB构成了进程实体。创建进程：创建进程实体中的PCB。撤销便是撤销进程的PCB。
  - 动态性
  - 并发性
  - 独立性
  - 异步性
3. 进程的基本状态：就绪、执行（单处理机系统只有一个进程处于执行状态）、阻塞
4. 挂起状态：某进程在计算机操作系统中暂时被调离出内存的状况。
  1. 引入挂起状态的原因：终端用户的请求；父进程请求；负荷调节的需要；操作系统的需要
5. 创建状态和终止状态
  1. 创建状态：创建一个进程一般要通过两个步骤：首先，为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列之中。
    
    当一个新进程被创建时，系统已为其分配了PCB，填写了进程标识等信息，但由于该进程所必需的资源或其它信息，如主存资源尚未分配等，一般而言，此时的进程已拥有了自己的PCB，但进程自身还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。
  2. 终止状态：当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态。
    
    进程的终止也要通过两个步骤：首先等待操作系统进行善后处理，然后将其PCB清零，并将PCB空间返还系统。
    
    进入终止态的进程以后不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集。一旦其它进程完成了对终止状态进程的信息提取之后，操作系统将删除该进程。
    
    当系统资源足够时，进程创建后便给其分配资源，进入活动就绪状态；当系统资源和性能不足时，并不分配给新建进程所需资源（特别是主存），进程状态为静止就绪状态，换到外存，不参与调度。
6. 进程控制块PCB
  1. 作用：为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块PCB，它是进程实体的一部分，是操作系统中最重要的记录型数据结构。作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。
  2. 系统总是通过PCB对进程进行控制：
    - OS调度某进程执行时，要从该进程PCB中查出先行状态及优先级
    - 调度到某进程后，要根据其PCB中所保存的处理及状态信息，设置该进程恢复运行的现场，根据PCB中程序和数据的内存始址，找出其程序和数据
    - 进程执行过程中，需要和与之合作的进程同步、通信或访问文件时，也需要访问PCB
    - 进程由于某种原因暂停执行时，需将断点的处理机环境保存在PCB中
  3. 进程常驻内存，放在OS专门开辟的PCB区内。
  4. 进程控制块中的信息
    1. 进程标识信息：内部标识符（PID）、外部标识符
    2. 处理机状态信息：通用寄存器、PC、PSW、用户栈指针
    3. 进程调度信息：进程状态、优先级、调度所需其他信息
    4. 进程控制信息：程序和数据地址、进程同步和通信机制、资源清单、链接指针
  5. PCB的组织方式
    1. 链接方式：把具有同一状态的PCB，用其中的链接字链接成一个队列。这样，可以形成就绪队列、若干个阻塞队列和空白队列等。
    2. 索引方式：系统根据所有进程的状态建立几张索引表，并把各索引表在内存的首地址记录在内存的一些专用单元中。

进程控制

进程控制是进程管理中最基本的功能。它用于创建一个新进程，终止一个已完成的进程，或终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。

原语：机器语言编写、常驻内存、不可中断（下图为四个控制原语）
进程控制
1. 进程图：用于描述一个进程的家族关系的有向树
2. 引起创建进程的事件：用户登录、作业调度（批处理系统，调度到某作业时，装入内存、分配资源、创建线程、插入到就绪队列）、提高服务（用户程序提出某种请求）、应用请求
  
  进程创建原语：Create():申请空白PCB、为新进程分配资源、初始化PCB、插入到就绪队列
3. 引起进程终止的事件：正常结束、异常结束（越界错误、保护错-访问不允许访问或不适当方式访问、非法指令等）、外界干预
  
  进程终止原语：termination():根据被终止进程的标识符，取出PCB读出状态、若处于执行态立刻终止、终止子孙进程、归还被终止进程资源、将被终止进程PCB从队列移除
4. 引起进程阻塞或唤醒事件：请求系统服务（阻塞）、启动某种操作（阻塞）、新数据尚未到达（阻塞）、无新工作可做（阻塞）
  
  进程阻塞原语：Block() 进程唤醒原语：Wakeup()
  - Block(): 1. 进程停止执行 2. PCB现行状态执行变为阻塞 3. PCB插入阻塞队列 4. 调用调度程序重新调度
  - Wakeup(): 1. 将被阻塞进程从阻塞队列移除 2. PCB现行状态变为就绪 3. PCB插入就绪队列
  - Suspend() 1. 检查被挂起进程状态，若处于活动就绪则改为静止就绪；若处于活动阻塞则改为静止阻塞 2. PCB复制到内存区域 3. 若被挂起进程正在执行则重新调度

进程同步

进程同步基本概念
1. 并发进程之间的制约关系：间接制约关系（共享某种资源）、直接制约关系（进程间合作）
2. 临界资源：一次只允许一个进程使用的资源
3. 临界区：包含临界资源的程序段。每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问。必须在临界区前面增加一段用于进行上述检查的代码，把这段代码称为进入区(entry section)。相应地，在临界区后面也要加上一段称为退出区(exit section)的代码，用于将临界区正被访问的标志恢复为未被访问的标志。
4. 同步机制遵循原则（临界区调度原则）
  1. 空闲让进
  2. 忙则等待
  3. 有限等待：对要求访问临界资源的进程应保证在有限时间内进入
  4. 让权等待：不能进入自己临界区时应立即释放
5. 信号量机制
  1. 整形信号量：一个用于表示资源数目的整型量S，仅能通过原语Wait(s)和signal(s)操作。
    
    wait操作当S≤0时会一直测试，不遵循让权等待。
  2. 记录形信号量：增加进程链表L，链接所有等待进程。
    
    S.value初值表示系统中某类资源的数目。每次Wait操作都意味着进程请求一个单位的该类资源，当S.value＜0时，表示该类资源已分配完毕，应调用block()自我阻塞。
    
    每次signal代表释放一个，当释放以后S.value仍然≤0，应该wakeup唤醒S.L第一个等待的进程。
    
    当初值为1代表互斥信号量。
  3. AND型信号量：将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源也不分配给它。
    
    Swait(Dmutex, Emutex)和Ssignal(Dmutex, Emutex)
  4. 信号量集：Swait(S1，t1，d1，…，Sn，tn，dn)操作可描述如下，其中S为信号量，d为需求值，而t为下限值。
    - Swait(S，d，d)。此时，在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。
    - Swait(S，1，1)。此时的信号量集已蜕化为一般的记录型信号量(S>1时)或互斥信号量(S=1时)。
    - Swait(S，1，0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。
6. 管程：代表共享资源的数据结构，以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序，共同构成了一个操作系统的资源管理模块。
  1. 管程的组成：管程名称、局部于管程内部的共享数据结构说明、对该数据结构进行操作的一组过
    程、对局部于管程内部的共享数据设置初始值的语句。
  2. 管程特性：模块化、抽象数据类型、信息掩蔽
  3. 管程和进程的区别
    - 进程定义的是私有数据结构PCB，管程定义公有数据结构
    - 进程是由顺序程序执行有关操作，管程主要进行进程同步和初始化操作
    - 设置进程目的：实现系统并发行；设置管程目的：解决共享资源互斥使用
    - 管程：被动工作；进程：主动工作
    - 进程之间并发执行；管程不可与调用者并发
    - 进程具有动态性，创建、撤销；管程是OS中资源管理模块，供进程使用。
  4. 条件变量：
    1. x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。
    2. x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，唤醒一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。（这与信号量机制中的signal操作不同，因为后者总是要执行s:=s+1操作，因而总会改变信号量的状态。）

经典进程同步问题

生产者消费者、读者写者、哲学家吃饭

进程通信

进程之间有两种信息需要交换：低级通信（传递控制信息）、高级信息（传递数据）

目前，高级通信机制归结为三大类：共享存储器系统、信息传递系统和管道通信系统

共享存储器系统：相互通信的进程共享某些数据结构或共享存储区，进程便可以通过这些空间通信。
1. 基于共享数据结构的通信方式：要求进程公用某些数据结构，借以实现诸进程间的信息交换。如在生产者—消费者问题中，就是用有界缓冲区这种数据结构来实现通信的。低效、只适合传递少量数据。
2. 基于共享存储区的通信方式。为了传输大量数据，在存储器中划出了一块共享存储区，进程可通过对共享存储区中数据的读写来实现通信。需要程序员自己设置同步和互斥措施才能保证实现正确的通信。
消息传递系统：进程间的数据交换是以格式化的消息为单位的；程序员直接利用操作系统提供的一组通信命令(原语)。
1. 直接通信方式：原语——Send(Receiver, message), Receive(Sender, message)
2. 间接通信方式：利用邮箱通信方式，可实现实时和非实时通信。提供若干原语：
  1. 创建、撤销邮箱
  2. 发送、接受消息 Send(mailbox, message), Receive(mailbox, message)
  3. 三种信箱：私用信箱（单向）、公用信箱（双向，操作系统创建）、共享信箱（创建时期指明共享，同时指出共享进程）
管道通信
1. 所谓“管道”，是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名pipe文件。
2. 写进程以字符流形式将大量数据送入管道，读数据读走。
3. 管道机制必须提供以下三方面协调能力：
  1. 互斥：一个进程对管道读写，另一进程须等待
  2. 同步：写进程写入pipe后去睡眠等待，直至读进程取走在唤醒；读进程读空pipe后也应等待，写进程写入管道后再唤醒。
  3. 确定对方是否存在：确定已存在才能进行通信。
信息传递的实现
1. 通信链路：
  1. 两种方式建立：显式建立（建立连接原语请求建立，需要显示拆除）、自动建立（利用系统发送原语，系统自动建立，主要用于单机）
  2. 根据连接方式分为两类：点对点、多点连接链路
  3. 根据通信方式分为两类：单向、双向链路
  4. 根据链路容量分为两类：无容量（没有缓冲区）、有容量链路
2. 消息格式
  1. 可以分为消息头+消息正文。
  2. 定长消息格式、变长消息格式
3. 进程同步方式
  1. 发送进程阻塞，接收进程阻塞
  2. 发送进程不阻塞，接受进程阻塞（常用）
  3. 发送和接收进程均不阻塞（较常见）
消息缓冲队列通信机制
1. 消息缓冲区
2. PCB中有关通信的数据项：增加消息队列首指针，用于对消息队列进行操作
3. 发送、接受原语
线程

线程的基本概念：
1. 调度：引入线程的OS中，把线程作为调度和分派的基本单位，把进程作为资源拥有的基本单位。
2. 并发性：引入线程的OS中，不仅进程之间可以并发执行，一个进程内的多个线程之间也可以并发执行
3. 拥有资源：线程自己不拥有系统资源，但它可以访问其隶属进程的资源
4. 系统开销：线程切换的代价远低于进程
5. 此外，一个进程中的多个线程具有相同的地址空间，在同步和通信的实现方面线程也比进程容易。
线程的属性
1. 轻型实体：不拥有系统资源，只有必不可少、能保证其独立运行的资源（如TCB）
2. 独立调度和分配的基本单位
3. 可并发执行
4. 共享进程资源
线程的状态
1. 状态参数：寄存器状态、堆栈、线程运行状态、优先级、线程专有存储器、信号屏蔽
2. 运行状态：执行、就绪、阻塞状态
线程的创建和终止
1. 应用程序在启动时，通常仅有一个线程在执行，该线程被人们称为“初始化线程”。它可根据需要再去创建若干个线程。
多线程OS中的进程
1. 作为系统资源分配的基本单位
2. 可包含多个线程
3. 进程不是一个可执行的实体
线程实现方式
1. 内核支持线程：不论什么进程，都是在操作系统内核支持下运行的，与内核紧密相关。内核支持线程中，无论是系统还是用户进程中的线程，创建、撤销、切换均由内核完成。
  
  优点：内核能够同时调度同一进程的多个线程并行执行；进程中一个线程被阻塞了，内核可以调度当前进程或其他进程的线程执行；线程切换快；可采用多线程技术。
  
  缺点：用户的线程切换开销较大。（需要在管态和目态切换）
2. 用户级线程：对于这种线程的创建、撤消、线程之间的同步与通信等功能，都无须利用系统调用来实现。
  
  优点：线程切换不需要转到内核空间；调度算法可以是进程专用的；用户级线程的实现与操作系统无关。
  
  缺点：系统调用的阻塞问题（线程执行一个系统调用后，该线程所属进程的全部线程均被阻塞）；多线程应用不能利用多处理机进行多重处理。
3. 组合方式：内核支持KST线程建立、调度和管理，也允许用户应用程序建立、调度和管理用户级线程；同一个进程内的多个线程可以同时在多处理器上并行执行，而且在阻塞一个线程时，并不需要将整个进程阻塞。
4. 用户级线程与内核控制线程的连接
  1. 一对一模型：为每一个用户线程都设置一个内核控制线程与之连接，当一个线程阻塞时，允许调度另一个线程运行。在多处理机系统中，则有多个线程并行执行。
  2. 多对一模型：将多个用户线程映射到一个内核控制线程，为了管理方便，这些用户线程一般属于一个进程，运行在该进程的用户空间，对这些线程的调度和管理也是在该进程的用户空间中完成。当用户线程需要访问内核时，才将其映射到一个内核控制线程上，但每次只允许一个线程进行映射。
    
    线程管理开销小、效率高，但一个线程访问内核阻塞，整个进程都阻塞。同时在多处理机系统中，一个进程的多个线程无法实现并行。
  3. 多对多模型：该模型结合上述两种模型的优点，将多个用户线程映射到多个内核控制线程，内核控制线程的数目可以根据应用进程和系统的不同而变化，可以比用户线程少，也可以与之相同。

习题

若进程正处于执行状态时，因终端请求而停下来以便研究其运行状况，此时进程应转变为(A)状态。
批处理系统中，导致进程创建的典型事件是(A)

A (1) 作业录入 (2) 作业调度 (3) 进程调度 (4) 中级调度

答案：1. 静止就绪 2. A(1) B(3) C(5) D 中断 3. A(2) 4. A.(4) B. (3) C.(2) D.(5) E.(5)

处理机调度与死锁

处理机调度的层次

调度分为三个层次：高级调度（作业调度）、中级调度（交换调度）、低级调度（进程调度）

高级调度
1. 作业：比程序更广泛的概念，作业 = JCB + 作业说明书 + 程序 + 数据。批处理系统中以作业为基本单位从外存调入内存。
  
  作业步：每个作业在运行期间都会经过若干独立的加工步骤，我们将每一个加工步骤成为作业步。
  
  典型的作业分为三个作业步：编译作业步、连结装配作业步、运行作业步
2. 作业控制块PCB：多道批处理系统中为每个作业设置了一个作业控制块，它是作业在系统中存在的标志，其中保存了系统对作业进行管理和调度所需的全部信息。
  
  每个作业进入系统时，系统为每个作业建立一个JCB，根据作业类型将它插入相应的后备队列中。
  
  作业调度程序依据一定的调度算法来调度它们，被调度到的作业将会装入内存。在作业运行期间，系统就按照JCB中的信息对作业进行控制。当一个作业执行结束进入完成状态时，系统负责回收分配给它的资源，撤消它的作业控制块。
3. 作业状态
  - 作业提交：作业的输入（从输入设备到外存）；
  - 作业收容（就绪）：作业输入（到外存）完成，系统为其建立JCB，等待调度运行；
  - 作业执行：分配资源，送入内存，被调度运行；
  - 作业完成：释放资源，完成作业输出；
4. 作业调度
  1. 作业调度的主要功能：根据作业控制块中的信息，审查系统能否满足用户作业的资源需求，以及按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。
  2. 周转时间 = 完成时间 - 提交时间 = 等待时间 + 运行时间
  3. 四种调度模型：FIFO、短作业优先、响应比高优先、基于作业优先级
低级调度

通常也把低级调度(Low Level Scheduling)称为进程调度或短程调度，它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度，在多道批处理、分时和实时三种类型的OS中，都必须配置这级调度。
1. 低级调度的功能：保存处理机现场信息、按某种算法选取进程、把处理机分配给进程
2. 低级调度三个基本机制：排队器、分派器、上下文切换机制（切换的主要开销）
3. 进程调度方式：
  1. 非抢占式方式：实时要求比较严格的实时系统中，不宜采用这种调度方式。
  2. 抢占方式：优先权原则、短作业优先原则、时间片原则
中级调度

选择在外存上的那些具备运行条件的就绪进程，将它们重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待进程调度。
1. 中级调度实际上就是存储器管理中的对换功能。
2. 引入目的：提高内存利用率和吞吐量。

调度队列模型和调度准则

调度队列模型
1. 仅有进程调度的调度队列模型：时间片
2. 具有高级和低级调度的调度队列模型
  - 作业调度按一定的作业调度算法，从外存的后备队列中选择一批作业调入内存，并为它们建立进程，送入就绪队列，然后才由进程调度按照一定的进程调度算法选择一个进程，把处理机分配给该进程。
  - 就绪队列的形式。在批处理系统中，最常用的是最高优先权优先调度算法，相应地，最常用的就绪队列形式是优先权队列。
3. 具有三级调度的调度队列模型
面向用户的准则：周转时间短、响应时间快、截止时间保证、优先权准则
- 平均周转时间 $T=\dfrac{1}{n}[\sum_{i=1}^nT_i]$
- 带权周转时间 $W=\dfrac{T}{T_s}$
- 平均带权周转时间 $W=\dfrac{1}{n}[\sum_{i=1}^n\dfrac{T_i}{T_s}]$
面向系统的准则：系统吞吐量高、处理机利用率好、各类资源的平衡利用

调度算法

先来先服务：适合作业调度和进程调度。有利于长作业，不适合短作业。
短作业优先调度：可以用于作业调度和进程调度。对长作业不利，无法保证紧迫性作业。服务时间由用户估计，无法保证真正的短作业优先。
高优先权优先调度算法
1. 优先权调度算法类型：非抢占式优先权算法（用于批处理系统、对实时性要求不高的系统）、抢占式优先权调度算法（常用于比较严格的实时系统中，以及对性能要求较高的批处理和分时处理系统中）
2. 优先权类型：静态优先权、动态优先权
3. 高响应比优先调度算法：
  
  $\mbox{优先权}=\dfrac{\mbox{等待时间}+\mbox{要求服务时间}}{\mbox{要求服务时间}}=\dfrac{\mbox{响应时间}}{\mbox{要求服务时间}}$
基于时间片的轮转调度算法
1. 时间片轮转法（分时系统）
  
  每个时刻，先把到来的任务插入队尾，然后再把这一时刻执行完的任务放到队尾。
2. 多级反馈队列调度算法
  
  设置多个就绪队列，每次时间片到没执行完就放入优先级低的队列（时间片更长）。
  
  仅当前一个队列空闲时，调度程序才调度下一队列的进程运行。

实时调度

实时系统中调度提出某些特殊的要求，前面的算法不能很好满足。

实现实时调度的基本条件
1. 系统提供必要信息：就绪时间；开始和完成的截止时间；处理时间；资源要求；优先级。
2. 系统处理能力强： $\sum_{i=1}^m\dfrac{C_i}{P_i}\le N$ ，其中 $C_i$ 为处理时间， $P_i$ 为周期时间， $N$ 为处理机数。
3. 采取抢占式调度机制
4. 具有快速切换机制：对外部中断快速响应、快速的任务分派能力
非抢占式调度算法：非抢占式轮转/优先调度算法
抢占式调度算法：基于时钟中断的抢占式优先权调度算法（抢占需等待时钟到来）、立即抢占的优先权调度算法

产生死锁的原因和必要条件

产生死锁的原因：竞争资源、进程间推进顺序非法
产生死锁的必要条件
- 互斥条件：某资源只能由一个进程占用，其他进程请求该资源只能等待，直至占有该资源的进程释放
- 请求和保持条件：进程已经保持了至少一个资源，又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程阻塞但对占有资源不放。
- 不剥夺条件：进程已获得的资源，在未使用完前不能被剥夺。
- 环路等待条件：发生死锁时，必然存在一个进程-资源的环形链。
处理死锁的基本方法
1. 预防死锁：设置限制条件去防止，但是可能会导致系统资源利用率和系统吞吐量降低。
2. 避免死锁：资源动态分配过程中，用某种方法防止系统进入不安全状态。实现上有一定难度。
3. 检测死锁：不采用任何措施，在运行过程中发现死锁。
4. 解除死锁：与检测死锁相配套。实施方法：撤销或挂起一些进程回收资源。

预防死锁的方法

预防死锁
1. 摒弃”请求和保持“条件：必须一次性申请整个运行过程中的全部资源。缺点：资源严重浪费、进程延迟运行。
2. 摒弃”不剥夺“条件：当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。实现起来比较复杂，且要付出很大的代价。
3. 摒弃”环路等待“条件：资源有序分配。
系统安全状态：安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

不安全不一定死锁，死锁必定不安全。
银行家算法：略

死锁的检测与解除

死锁的检测：允许死锁发生；保存有关资源的请求和分配信息；提供检测算法。检测时机也很重要。
资源分配图：

r1已经将资源分配给P1、P2各一个，P2想要一个r1但尚未满足；P1想要一个r2尚未满足；r2已经将资源分配给P2一个。
死锁定理：把资源分配图加以简化的方法，检测系统处于S状态时是否处于死锁状态。
1. 找出一个既不阻塞又非孤立的进程结点Pi，释放所占有的全部资源
2. 重复释放，最后若能消去所有的边，则说明没有死锁；否则说明存在死锁。
死锁的解除：
1. 剥夺资源：从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
2. 撤销进程：最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。
  
  同样可以采用策略撤销，如撤销进程付出代价最小等。