操作系统—— 精髓与设计原理--期末复习

一、计算机系统概述

1、基本构成

计算机有四个主要的结构化部件：

①处理器（Processor）：控制计算机的操作，执行数据处理功能。当只有一个处理器时，它通常指中央处理器（CPU）

②内存（Main memory）：存储数据和程序

③输入/输出模块（I/O modules）：在计算机和外部环境之间移动数据

④系统总线（System bus）：在处理器、内存和输入/输出模块间提供通信的设施

2、部件补充

①存储器地址寄存器（MAR）：确定下一次读/写的存储器地址

②存储器缓存寄存器（MBR）：存放要写入存储器的数据或从存储器读取的数据

③程序计数器（PC）：保存下一次要取的指令地址

④指令寄存器（IR）：存放取到的指令

3、中断

中断最初是用于提高处理器效率的手段。

利用中断功能，处理器可以在I/O操作的执行过程中执行其他指令。

4、重要习题

1.列出简要定义计算机的四个主要组成部分

2.一般而言，一条机器指令能指定的四种不同操作是什么

3.什么是中断

4.多处理器系统和多核系统区别是什么

5.空间局部性和时间局部性的区别是什么

6.开发空间局部性和时间局部性的策略是什么

二、操作系统概述

1、操作系统的目标

操作系统是控制应用程序执行的程序，是应用程序和计算机硬件之间的接口。它有三个目标：

①方便：操作系统使计算机更易于使用

②有效：操作系统允许以更有效的方式使用计算机资源

③扩展能力：在构造操作系统时，应允许在不妨碍服务的前提下，有效的开发、测试和引入新的系统功能。

2、操作系统的概念

操作系统是指控制和管理整个计算机系统的硬件和软件资源，并且合理地自主调度计算机的工作和资源的分配，提供给用户和其他软件比较方便的接口和环境，是计算机系统中最基本的系统软件。

3、操作系统的基本特征

①并发：指两个或多个事件在同一时间间隔内发生，宏观上看是同时发生，微观上看是交替发生的

并行：是指系统具有同时进行运算或操作的特性，在同一时刻能完成两种或以上的工作

PS：单核CPU的程序只能并发执行，多核CPU的程序可以并行执行

②共享：系统中的资源可供内存中多个并发执行的进程共同使用

互斥共享：资源在特定一段时间内只允许一个进程访问该资源

同时共享：一个时间段内允许多个进程同时对某些资源进行访问

③虚拟

④异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底。而是走走停停的，以不可预知的速度向前推进。

4、操作系统的功能和接口

操作系统作为系统资源的管理者对资源进行管理：处理机管理、存储器管理、文件管理、设备管理

①处理机管理

在多道程序环境下，处理机的分配和运行都以进程为基本单位，因而对处理机的管理可归纳为对进程的管理

进程管理的主要功能包括：进程控制、进程同步、进程通信、死锁处理、处理机调度

②存储器管理

主要包括：内存分配与回收、地址映射、内存保护与共享和内存扩充

③文件管理

主要包括：文件存储空间的管理、目录管理以及文件读写管理和保护

④设备管理

主要包括：缓冲管理、设备分配、设备处理和虚拟设备

操作系统作为用户与计算机硬件系统之间的接口提供了用户接口：

①命令接口

联机命令接口（交互式命令接口）适用于分时或实时系统的接口

脱机命令接口（批处理命令接口）适用于批处理系统

向上层提供服务：给软件或程序员提供程序接口（系统调用）

②程序接口

程序接口由一组系统调用组成。用户通过在程序中使用这些系如调用来请求操作系统为其提供服务

5、操作系统的发展过程

（1）单道批处理系统

特点：单路性、独占性、自动性、封闭性、顺序性

缺点：系统的资源得不到充分利用

（2）多道批处理系统

特点：多路性、共享性、自动性、封闭性、无序性、调度性

好处：提高CPU利用率，提高内存和I/O设备的利用率，增加系统吞吐量

缺点：平均周转时间长，无交互能力

PS：引入多道程序设计的前提之一是系统具有中断功能

（3）分时系统

允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源

采用“时间片轮转”的处理机调度策略

PS：分时系统的主要目的是比较快速地响应用户

（4）实时系统

系统能及时响应外部事件的请求，在规定时间内完成对该事件的处理，并控制素有实时任务协调一致的运行。

6、操作系统的运行环境

1.CPU执行两种不同性质的程序：操作系统内核程序、应用程序

操作系统划分为用户态和核心态，严格区分两类程序

用户自编的程序在用户态，操作系统内核程序在核心态

2.内核

是计算机最低层的软件，是计算机功能的延申。包含四个方面内容：

①时钟管理：操作系统需要通过时钟管理向用户提供准确时间，通过时钟中断的管理，可实现进程的切换

②中断机制：引入中断机制的初衷是提高多道程序环境中CPU的利用率

③原语：原语是底层的一些可被调用的公用小程序，他们各自完成一个规定的操作，是不可划分的单位

④系统控制及其数据结构处理

3.中断和异常

本质：发生中断就意味着需要操作系统介入开展管理工作

中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。

“核心态”→“用户态”的切换是通过执行一个特权指令，将程序状态字(PSW)的标志位设置为“用户态”

4.中断的分类

①内中断（异常）：a、资源中断-指令中断（trap指令）；b、强迫中断（缺页）

②外中断：a、外设请求（中断信号）；b、人工干预（用户强制）

三、进程控制与描述

1、进程的概念

1、定义：进程是程序的一次执行

2、组成：进程由程序控制块（PCB）、程序段、数据段组成

操作系统通过PCB来管理进程，PCB中应该包含操作系统对其进行管理所需的各种信息。

3、组织方式

①链式方式：按照进程状态将PCB分为多个队列，操作系统持有指向各个队列的指针

②索引方式：依据进程的状态不同，建立索引表，操作系统持有指向各个索引表的指针

4、进程的特征

①动态性：进程是程序的一次执行过程，是动态的产生、变化和消亡

②并发性：内存中有多个进程实体，各进程可并发执行

③独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位

④异步性：各个进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程同步机制来解决异步问题

⑤结构性：每个进程都会配置一个PCB

PS：进程和程序本质区别在于：前者可以并发执行，后者不能并发执行

2、进程的状态和切换

1、进程有五个状态：就绪状态、运行状态、阻塞状态、创建状态、终止状态。

创建态：进程在创建时，需要申请一个空白的PCB，向其中填写控制和管理进程的信息完成资源分配，如果创建工作无法完成，此时进程所处的状态称为创建态

运行态：进程占用CPU，并在CPU上运行

就绪态：进程已具备运行条件，但由于未分配CPU无法运行

阻塞态：进程因等待某个事件发生而暂时不能运行

终止态：进程结束或出现错误或被系统终止

2、状态的转换

 

 3、进程通信

1.进程通信是指进程之间的信息交换

PV操作是最低级的通信

高级通信方法主要有三类：

①共享存储（生产者消费者）

②消息传递

③管道通信（pipe文件）

4、线程

1、引入线程的目的正是为了简化进程间的通信，以小的开销来提高进程内的并发程度

线程是进程中执行运算的最小单位，是进程中的一个实体，是被系统独立调度和分派的基本单位。线程不拥有系统资源，但可与同属一个进程的其他线程共享进程拥有的全部资源

一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行

2.线程表示进程的一个控制点。

进程是系统资源分配的单位，线程是处理机调度的单位

3、比较

四、处理机调度

1、基本概念

1、不同的调度算法具有不同的特性，主要的评价准则：

①CPU利用率

②系统吞吐量：单位时间内CPU完成的作业数

③周转时间：从作业提交到作业完成所经历的时间

④等待时间：进程处于等处理机状态的时间之和

⑤响应时间

 2、进程调度方式

①非剥夺调度：当一个进程正在处理机上执行，即使有更为重要的进程进入就绪队列，仍然让正在执行的进程继续执行，直到该进程完成或进入阻塞态，才把处理机分配给更为重要的进程

②剥夺调度：抢占方式，遵循一定的原则。

2、先来先服务算法

FCFS：按照作业到达的先后顺序进行调度

适用情况：作业调度、进程调度

优点：算法实现简单

缺点：对长作业有利，对短作业不利

3、短作业优先算法

SJF：以作业的长短来计算优先级

适用情况：作业调度、进程调度

优点：最短的平均等待时间及平均周转时间

缺点：①必须先知道作业的运行时间

②对长作业不利，会出现饥饿现象

③没有考虑作业的紧迫程度

4、优先级算法

基于进程的紧迫程度，由外部赋予进程相应的优先级，进行调度

适用情况：作业调度、进程调度、I/O调度

优点：用优先级区分紧急程度，运用于实时OS

缺点：可能导致低优先级进程的饥饿

优先级类型：

①静态优先级：在创建进程时确定，其在进程的整个运行期间不变

②动态优先级：在创建进程之初，先赋予一个优先级，然后动态调整

5、时间片轮转算法

RR：公平地、轮流地为各个进程服务，让每个进程在一定时间间隔内都可以得到响应

算法规则：按照各进程到达就绪队列的顺序，轮流让各个进程执行一个时间片，若进程未到一个时间片内执行完，则剥夺处理机，将进程重新放到就绪队列队尾重新排队

适用情况：进程调度

属于抢占式算法

优点：公平、响应快、适用于分时OS

缺点：不能区分任务的紧急程度，需要进程切换，消耗较大

6、高相应比优先算法

HRRN：综合考虑作业的等待时间和要求服务的时间

算法规则：在每次调度前，计算各个作业的响应比，选择响应比最高的作业为其服务

适用情况：作业调度、进程调度

优点：综合考虑了等待时间和运行时间

缺点：每次调度前都要计算响应比，增加系统的开销

PS：不会导致饥饿

7、多级反馈队列调度算法

算法规则：设置多个就绪队列，各级队列优先级从高到低，时间片从大到小

每个队列采用FCFS算法

按队列优先级调度

适用情况：进程调度

优点：用优先级区分紧急程度，运用于实时OS

缺点：可能导致低优先级进程的饥饿

五、并发：死锁与饥饿

1、死锁的概念

1.死锁的定义：各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

注意区分：

 2.产生死锁的必要条件

①互斥条件：只有对互斥使用的资源才会导致死锁（哲学家的筷子）

②请求和保持条件：进程至少已经保持了一个资源，但是又提出了新的资源请求，而还资源又被其他进程占有，此时请求进程被阻塞，但又对自己的资源保持不放

③循环等待条件：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程请求

④不剥夺条件：进程获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

2、死锁的预防

死锁的处理就是不允许死锁的发生，分为静态策略（预防死锁）和动态策略（避免死锁）

1.预防死锁：破坏死锁产生的必要条件

2.避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）

3.死锁的检测和解除：允许死锁的发生，不过操作系统会检测出死锁的发生，然后采取某种措施解除死锁

①破坏互斥条件

如果把互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。例如：SPOOLing技术

②破坏不剥夺条件

当某个进程请求新的资源得不到满足时。它必须立即释放保持的所有资源，待以后需要时再重新申请。

③破坏请求和保持条件

可以采用静态分配的方法，即进程在运行请按一次申请完它所需要的全部资源，在它的资源未满足前，不让它投入运行。一旦投入运行后，这些资源就一直归他所有，该进程就不会再请求别的资源了

④破坏循环等待条件

对所有资源类型进行先行排序（顺序资源分配法）。首先给系统中的资源编号，规定每个进程必须按编号递增的顺序情求资源，同类资源一次申请完

PS：产生死锁的原因可能是：①时间上：调度时机不合适；②空间上：独占资源分配不当

 3、死锁的避免--银行家算法

1.系统安全状态

在避免死锁方法中，把系统的状态分为安全和不安全。当系统处于安全状态时可避免发生死锁。

2.安全序列

如果系统按照这种序列分配资源，则么各进程都能顺利完成，只要找出一个安全序列，系统就是安全状态

3.银行家算法

核心思想：在资源分配之前预先判断这次分配是否导致系统进入不安全状态，依此决定是否应答资源分配请求，让该进程先阻塞等待

（1）数据结构

①可利用资源向量Available。长度为m的一维数组，表示还有多少可用资源

②最大需求矩阵Max。表示各进程对资源的最大需求数，n×m矩阵

③分配矩阵Allocation。表示已经给各进程分配了多少资源，n×m矩阵

④需求矩阵Need。表示各进程最多还需要多少资源，Max-Allocation=Need

⑤进程P的请求向量。长度为m的一维数组，表示进程此次申请的各种资源数

（2）算法步骤

 ④系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。

（3）安全性算法

 例：

（1）由题：已占有资源 ：A：1+1，B：3+6，C：1+5+3+1，D：2+4+2+4

用资源拥有量减去相应已占有资源，再相加：1+5+2+0=8

（2）

（3）

 4、死锁的检测与解除

如果系统中既不采用预防死锁也不采用避免死锁的措施，系统应当提供两个算法：

1.死锁检测算法

2.死锁解除算法

 六、并发性：互斥与同步