操作系统

一、引论

计算机系统由硬件和软件组成

操作系统是配置在计算机硬件上的第一层软件（这一层里实际上又是多层系统软件，一层一层抽象，隐藏对硬件的操作细节），是对硬件系统的首次扩充

1.1 目标和作用

根据应用环境确定目标

查询系统：响应时间
实时系统、武器控制：实时性和可靠性

配置操作系统的目标

有效性
- 提高资源利用率
- 提高系统吞吐量
方便性：易学易用，图形界面
可扩充性：微内核结构、客户服务器模式
开放性：遵守接口规范

操作系统的作用 OS 作为接口的示意图

作为用户与计算机硬件系统之间的接口：OS 处于用户与计算机硬件系统之间，用户通过 OS 来使用计算机系统
- 命令方式
- 系统调用方式
- 图形、窗口方式
作为计算机系统资源的管理者
- 处理器
- 存储器
- I/O设备
- 信息（数据文件和程序）
实现对计算机资源的抽象

1.2 发展过程

作业：即系统中各种应用程序的任务，有计算型、I/O型等等

无操作系统（纸带打孔，卡片输入）
- 人工操作
  - 单用户独占全机
  - CPU等待用户操作
- 脱机输入/输出方式
  - 减少了CPU等待时间
  - 提高了I/O速度（直接从高速的磁带、磁盘上读取）
单道批处理系统 a. 最早的一种操作系统
b. 批处理系统旨在提高系统资源的利用率和系统吞吐量
c. 把一批作业以脱机方式输入到磁带上，并在系统中配上监督程序(Monitor)，在它的控制下使这批作业能一个接一个地连续处理
- 自动性
- 顺序性
- 单道性
多道批处理系统所有作业都存放在外存，通过调度算法调入内存，共享CPU和系统资源
- 提高CPU的利用率（一个等待I/O时，交替运行其他作业)
- 提高内存和I/O设备利用率（大部分作业属于中小型）
- 增加系统吞吐量优缺点
- 资源利用率高
- 系统吞吐量大
- 平均周转时间长：要排队依次处理
- 无交互能力：交给系统后，用户无法控制
分时系统满足人机交互、共享主机、便于上机。作业应直接进入内存，引入时间片，每个时间片转换作业任务
- 多路性
- 独立性
- 及时性
- 交互性
实时系统系统能够及时响应外部事件的请求，并在规定的时间内完成处理，控制所有实时任务协调
实时任务分类
- 硬实时：必须满足任务截止时间的要求，否则后果难以预料
- 软实时：错过截止时间影响也不大

1.3 基本特性

并发、共享、虚拟、异步，后三个都是以并发为基础

并发性两个或多个时间在同一时间间隔内发生（一段时间内），在一段事件内宏观上同时运行，但微观上每一时刻只有一个程序在运行（并行系统除外）
- 并行性：两个或多个事件在同一时刻发生（时间点）
- 进程和线程：
  - 进程：是分类资源的基本单位
  - 线程：独立运行和独立调度的基本单位。引入的原因是进程调度的开销很大，提高多个程序间并发执行的程度
共享性资源可供内存中多个并发执行的进程（线程）共同使用
- 互斥共享：打印机等物理设备、临界资源
- 同时访问：磁盘、可同时写入的文件
虚拟技术将一个物理实体变为若干个逻辑上的对应物
- 时分复用技术：分时使用
  - 虚拟处理机技术：多道程序技术，为每道程序建立一个进程，并发执行
  - 虚拟设备技术：将一台物理设备变为多台逻辑设备，“同时”操作 -空分复用技术：
  - 虚拟磁盘：磁盘分盘
  - 虚拟存储器：内存可同时存放多个程序
异步性进程以用户不可预知的方式推进，很可能每一次执行的顺序都不相同

1.4 主要功能

处理机管理进程和线程管理
- 进程控制：分配资源、回收资源、控制进程（线程）状态的转换
- 进程同步：为多个进程（线程）的运行进行协调
  - 进程互斥
  - 进程同步
- 进程通信：交换信息
- 调度
  - 作业调度：从后备队列选出作业，分配资源，建立进程
  - 进程调度：从进程就绪队列中，选出进程，分配处理机
存储器管理
- 内存分配：动态、静态分配
- 内存保护：只能访问自己的内存空间
- 地址映射：逻辑地址到物理地址
- 内存扩充：虚拟内存技术
  - 请求调入
  - 置换
设备管理主要是I/O相关的管理
- 缓冲管理
- 设备分配
- 设备处理
文件管理
- 文件存储空间管理
- 目录管理
- 文件的读写管理和保护
操作系统与用户之间的接口
- 用户接口：用户直接取得系统服务
- 程序接口：程序员编程时使用的接口，用于程序取得系统服务

1.5 微内核操作系统

缺点：

效率降低：一次服务请求至少四次上下文切换。
- 第一次是发生在客户发送请求消息给内核，以请求取得某服务器特定的服务时；
- 第二次是发生在由内核把客户的请求消息发往服务器时；
- 第三次是当服务器完成客户请求后，把响应消息发送到内核时；
- 第四次是在内核将响应消息发送给客户时

二、进程管理

传统操作系统中，程序不能独立运行，进程是资源分配和独立运行的基本单位。

操作系统的四大特性也是基于进程而形成的

2.1 进程的基本概念

顺序执行和并发执行

顺序执行的特征
- 顺序性
- 封闭性
- 可再现性
并发执行的特征
- 间断性
- 失去封闭性
- 不可再现性

进程的特征和定义

引入进程的目的：为了使程序能并发执行，对并发执行的程序加以描述和控制

结构特征
- 程序段
- 相关的数据段
- PCB（进程控制块）创建进程即创建PCB，撤销进程即撤销PCB
动态性由创建而产生，有调度而执行，由撤销而消亡
并发性多个进程在一段时间内同时存在与内存中，同时运行
独立性进程实体是一个能独立运行、独立分配资源、独立接受调度的基本单位
异步性进程按各自独立、不可预知的速度向前推进

进程的一些典型定义：

程序的一次执行
一个程序及其数据在处理机上顺序执行时所发生的活动
程序在一个数据集合上运行的过程，是系统进行资源分配和调度的独立单位
进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

进程的三种基本状态

进程基本状态的转换

就绪获得了除处理机外的所有资源
执行正在执行
阻塞正在执行的进程由于某事件暂时无法执行，放弃处理机。如请求I/O、申请缓冲空间
创建只分配了PCB，没有其他资源
终止当一个进程到达了自然结束点，或是出现了无法克服的错误，或是被操作系统所终结，或是被其他有终止权的进程所终结，它将进入终止状态
终止后的进程不能再被执行，当对终止状态进程信息统计后，将会被删除

另外：在引入挂起状态后，又将增加从挂起状态(又称为静止状态)到非挂起状态(又称为活动状态)的转换引入挂起的状态转换

进程控制块PCB

PCB是进程存在的唯一标志，操作系统根据PCB感知进程的存在
PCB 中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。
进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。
OS 根据 PCB 来对并发执行的进程进行控制和管理。
PCB 经常被系统访问，尤其是被运行频率很高的进程及分派程序访问，故 PCB 应常驻内存

进程控制块中的信息

进程标识符
- 内部标识符：操作系统赋予的进程序号
- 外部标识符：创建者提供，用户在访问进程时使用
处理机状态处理机中各种寄存器的内容
进程调度信息
- 进程状态
- 进程优先级
- 其他信息：比如已执行时间、已等待时间
- 事件：比如阻塞原因
进程控制信息
- 程序和数据的地址
- 进程同步和通信机制
- 资源清单：除处理机外的全部资源和已分配资源清单
- 链接指针：指向进程队列的下一个PCB

2.2 进程控制

进程创建

申请空白 PCB
为新进程分配资源
初始化进程控制块
- 初始化标识信息，将系统分配的标识符和父进程标识符填入新 PCB 中
- 初始化处理机状态信息，使程序计数器指向程序的入口地址，使栈指针指向栈顶
- 初始化处理机控制信息，将进程的状态设置为就绪状态或静止就绪状态
- 优先级，通常是将它设置为最低优先级，除非用户以显式方式提出高优先级要求
将新进程插入就绪队列

进程终止

引起终止的事件
- 正常结束
- 异常结束
- 外界干预
终止过程
- 根据被终止进程的标识符，从 PCB 集合中检索出该进程的 PCB，从中读出该进程的状态
- 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度
- 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防成为不可控的进程
- 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统
- 将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息

进程的阻塞

引起进程阻塞和唤醒的事件
- 请求系统服务，操作系统不能立即满足例如，请求使用正在使用中的打印机
- 启动某种操作例如，进程启动了某 I/O 设备，如果只有在 I/O 设备完成了指定的 I/O 操作任务后进程才能继续执行
- 新数据尚未到达
- 无新工作可做
进程的阻塞是进程自身的一种主动行为，通过调用阻塞原语 block 把自己阻塞。
当被阻塞进程所期待的事件出现时，则由有关进程调用唤醒原语 wakeup( )
- wakeup的执行过程：
  - 被阻塞的进程从等待该事件的阻塞队列中移出
  - 将其 PCB 中的现行状态由阻塞改为就绪
  - 再将该 PCB 插入到就绪队列中

进程的挂起与激活

进程的挂起当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起，系统将利用挂起原语 suspend( )将指定进程或处于阻塞状态的进程挂起
- 挂起原语的执行过程
  - 检查被挂起进程的状态
    - 若处于活动就绪状态，改为静止就绪
    - 对于活动阻塞状态的进程，改为静止阻塞
    - 若被挂起的进程正在执行，则转向调度程序重新调度
进程的激活过程当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的该进程换入内存。利用激活原语 active( )将指定进程激活。
- 将进程从外存调入内存，检查该进程的现行状态
  - 若是静止就绪，便将之改为活动就绪
  - 若为静止阻塞，便将之改为活动阻塞
- 假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度
  - 由调度程序将被激活进程与当前进程进行优先级的比较
  - 如果被激活进程的优先级更低，就不必重新调度
  - 否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程

2.3 进程同步

进程之间可能存在直接制约和间接制约关系

同步机制应遵循的规则：

空闲让进
忙则等待
有限等待：应保证在有限时间内能进入，防止死等
让权等待：不能得到临界资源时，放弃处理机

进程同步机制

信号量
- 整型信号量：为满足让权等待原则，如果信号量$\leq0$会不断测试
- 记录型信号量：增加了等待进程链表
- AND型信号量：多个临界资源
- 信号量集：AND型的扩充
管程定义了一种新的数据结果对资源进行描述

2.4 经典同步问题

生产者消费者问题
五哲学家进餐问题
读者写者问题

2.5 进程通信

进程之间的信息交换

共享存储器系统
- 基于共享数据结构的通信方式：少量数据
- 基于共享存储区的通信方式：大量数据
消息传递系统：数据交换是格式化的消息(message)为单位，如计算机网络的报文
管道通信系统：用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，又名 pipe 文件，管道机制必须提供三方面的协调能力：
- 互斥，即当一个进程正在对 pipe 执行读/写操作时，其它(另一)进程必须等待
- 同步，指当写(输入)进程把一定数量(如 4 KB)的数据写入 pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把它唤醒。当读进程读一空 pipe 时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
- 确定对方是否存在，只有确定了对方已存在时，才能进行通信。

消息传递通信的实现方法

直接通信
间接通信：通过信箱等暂存

2.6 线程

引入线程，是为了减少程序在并发执行时(切换)所付出的时空开销，使 OS 具有更好的并发性。

在引入线程的操作系统中，线程是调度和分派的基本单位，而进程是资源拥有的基本单位，不对进程进行频繁的切换

把传统进程的两个属性分开，使线程基本上不拥有资源，这样线程便能轻装前进，从而可显著地提高系统的并发程度。在同一进程中，线程的切换不会引起进程的切换，但从一个进程中的线程切换到另一个进程中的线程时，将会引起进程的切换。

一般而言，线程自己不拥有系统资源(也有一点必不可少的资源)，但它可以访问其隶属进程的资源，即一个进程的代码段、数据段及所拥有的系统资源，如已打开的文件、I/O 设备等，可以供该进程中的所有线程所共享。

用户级线程与内核支持线程

对用户级线程，调度仍然以进程为单位（对进程而言公平，线程多的进程中的线程不公平）对内核支持线程，调度以线程为单位（对线程公平，进程不公平）

用户级线程的优点

线程切换不需要转换到内核空间
调度算法可以是进程专用的
用户级线程的实现与操作系统平台无关

用户级线程的主要缺点

系统调用的阻塞问题。在基于进程机制的操作系统中，大多数系统调用将阻塞进程，因此，当线程执行一个系统调用时，不仅该线程被阻塞，而且进程内的所有线程都会被阻塞。而在内核支持线程方式中，则进程中的其它线程仍然可以运行。
在单纯的用户级线程实现方式中，多线程应用不能利用多处理机进行多重处理的优点。内核每次分配给一个进程的仅有一个 CPU，因此进程中仅有一个线程能执行，在该线程放弃 CPU 之前，其它线程只能等待。

操作系统复习