操作系统复习

第一章

并发、并行、系统调用、用户态、核心态等概念的含义及理解

1、基本特征

并发：两个或多个活动在同一给定的时间间隔中进行。（并行：两个和多个活动在同一时刻发生）
共享：计算机系统中的资源被多个进程所共用。
异步：进程以不可预知的速度向前推进。
虚拟：把一个物理的实体变为若干个逻辑上的对应物。

2、主要功能

处理机管理
存储器管理
文件管理
设备管理

3、重要概念

两种指令

特权指令
非特权指令

两种程序

内核程序
应用程序

处理机状态

用户态（目态）
核心态（管态）
用户态到核心态：通过中段
核心态到用户态：特权指令PSW的标志为0用户态1核心态。

系统调用

系统给程序员提供的唯一接口，可获得OS的服务。在用户态发生，核心态处理。

第二章

1、进程概念的理解，进程基本状态转换图及转换原因

进程的定义

进程是计算机中程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位。

进程的组成

PCB：进程存在的唯一标志
程序段：能被进程调度到CPU的代码
数据段

进程的状态

1、状态的种类

运行态
就绪态
阻塞态
创建状态
结束状态

2、状态的转换

3、转换原因

就绪态->运行态：处于就绪态的进程被调度后，获得处理机资源
运行态->就绪态：时间片用完或在可剥夺系统中有更高级的进程进入
运行态->阻塞态：进程需要的某一资源没有准备好
阻塞态->就绪态：进程等待的事件到来

2、进程并发运行的实质

并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。

3、常见调度算法的运行原则

先来先服务
短作业优先
最短剩余时间优先
高响应比优先
静态优先级
时间片轮转

第三章

1、进程同步或互斥的解决方案

1、基本概念

互斥：是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步：是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。在大多数情况下，同步已经实现了互斥，特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源

临界资源：一次仅允许一个进程使用的资源

临界区：在每个进程中访问临界资源的那段程序。

2、解决互斥问题应遵循的四个准则和基本方法

空闲让进：如果有多个进程要求进入空闲的临界区，一次只允许一个进程进入
忙则等待：任何时候，进入临界区的进程不可多余一个。如已有进程进入自己的临界区，则其它所有试图进入自己临界区的进程必须等待
有限等待：进入临界区的进程要在有限的时间内退出，以便其它进程能及时的进入自己的临界区。
让权等待：如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象

3、用信号量解决基本的进程同步或互斥问题

暂时留空

4、死锁

1、死锁的含义

多个进程因竞争资源而造成的一种僵局，如果没有外力，这些进程将无法推进

2、死锁的产生原因

非剥夺资源的竞争和进程的不恰当推进顺序

3、死锁产生的必要条件

互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链。

4、死锁的具体解决方案

1、预防死锁

破坏互斥条件
破坏不可剥夺条件
破坏请求和保持条件
破换循环等待条件

2、避免死锁

安全状态：系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。
银行家算法：首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况。因此，状态包含两个向量Resource（系统中每种资源的总量）和Available（未分配给进程的每种资源的总量）及两个矩阵Claim（表示进程对资源的需求）和Allocation（表示当前分配给进程的资源）。安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。

3、检测死锁

利用死锁原理：

首先为每个进程和每个资源指定一个唯一的号码；
然后建立资源分配表和进程等待表。

4、解除死锁

资源剥夺法
撤销进程法
进程回退法

第四章

1、各种存储管理方案的基本原理及特点

1、连续分配管理方式

单一连续分配：分配到内存的固定区域
固定分区分配：分配到内存不同的固定区域、分区可以相等可以不等。
动态分区分配:按照程序的需要进行动态的划分。首次适应算法、最佳适应算法、最坏适应算法、邻近适应算法。

2、非连续分配管理方式

基本分页式存储管理
基本分段式存储管理
段页式

2、不同存储管理方案的地址变换，逻辑地址到物理地址的转换

3、虚拟存储器的定义理解和特征

定义理解

虚拟存储器是用户能作为可编址内存对待的虚拟存储空间，它使用户逻辑存储器与物理存储器分离，是操作系统给用户提供的一个比真实内存空间大得多的地址空间。就是说，虚拟存储器并不是实际的内存，它的大小比内存空间大得多；用户感觉所能使用的“内存”非常大，这是操作系统对逻辑内存的扩充。

特征

虚拟扩充:虚拟存储器不是扩大物理内存空间，而是扩充逻辑内存容量。
部分装入:每个进程不是全部一次性地装入内存，而是分成若干部分。当进程要执行时，只需将当前运行需要用到的那部分程序和数据装入内存。以后在运行过程中用到其他部分时，再分别把那些部分从外存调入内存。
离散分配:一个进程分成多个部分，它们没有被全部装入内存。即使装入内存的那部分也不必占用连续的内存空间。
多次对换:在一个进程运行期间，它所需的全部程序和数据分成多次调入内存。

4 、常见页面置换算法的置换原则和缺页率的计算

页面置换算法（OPT、FIFO、LRU、CLOCK、改进的时钟置换算法）

1、最佳置换算法（OPT）

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

2、先进先出置换算法（FIFO）

每次选择淘汰的页面是最早进入内存的页面

3、最近最久未使用置换算法（LRU）

每次淘汰的页面是最近最久未使用的页面

4、时钟置换算法（CLOCK）

5、改进的时钟置换算法

第五章

1、设备控制方式

设备控制方式

1、程序直接控制方式

2、中断控制方式

3、DMA控制方式

4、IO通道控制方式

2、缓冲区的作用

1、缓和CPU与外设间速度不匹配的矛盾

2、提高CPU与外设之间的并行性

3、减少对CPU的中断次数

3、缓冲区的类型

1、单缓冲：当数据到达率与离去率相差很大时，可采用单缓冲方式

2、双缓冲：当信息输入和输出率相同，可利用双缓冲区，实现两者的并行

3、多缓冲：对于阵发性的输入、输出，为了解决速度不匹配的问题，可以设立多个缓冲区

4、磁盘访问时间的组成

寻道时间
旋转延迟时间
传输时间

5、常见的磁盘调度算法

1、先到先服务算法（FCFS）

2、最短查找时间优先算法（SSTF）

3、扫描算法（SCAN）

4、循环扫描算法（CSCAN）

第六章

1、文件的目录结构

2、文件的物理结构

1、连续文件结构（连续分配方式）

2、串联文件结构（链接分配方式）

3、索引文件结构（索引分配方式）

3、文件的逻辑结构

1、无结构文件

2、有结构文件

顺序文件
索引文件
索引顺序文件