【笔记】OS期末复习

2021年OS期末复习笔记

CH3 进程描述和控制

什么是进程

进程的定义：
- 一个正在执行的程序
- 一个正在计算机上执行的程序实例
- 能分配给处理器并由处理器执行的实体
- 由一组执行的指令，一个当前状态，和一组相关的系统资源表征的活动单元
进程控制块
- 进程控制块是存放进程表征元素的模块
- 它包括：标识符，状态，优先级，程序技术收起，内存指针，上下文，I/0状态信息，记账信息

进程状态

操作系统创建一个新进程的步骤

（1）为新进程分配一个唯一的进程标识符。此时，主进程表中会添加一个新表项，每个进程一个表项。
（2）为进程分配空间。 【根据进程的类型分配空间值，在作业创建时也可以基于用户请求设置，如果一个进程由另一个进程生成，则父进程可以把所需要的值作为进程创建请求的一部分传递给操作系统，若任何已有的地址空间将被这个新进程共享，则需要建立正确的链接】这包括进程映像中的所有元素。因此，操作系统必须知道私有用户地址空间（程序和数据）和用户栈需要多少空间。默认情况下会根据进程的类型分配这些值，但也可在作业创建时基于用户请求设置这些值。若一个进程由另一个进程生成，则父进程可把所需的值作为进程创建请求的一部分传递给操作系统。若任何已有的地址空间将被这个新进程共享，则需要建立正确的链接。最后，必须为进程控制块分配空间。
（3）初始化进程控制块。进程标识部分包括进程ID和其他相关的ID，如父进程的ID等；处理器状态信息部分的多数项目通常初始化为0，但程序计数器（置为程序入口点）和系统栈指针（定义进程栈边界）除外。进程控制信息部分根据标准的默认值和该进程请求的特性来初始化。例如，进程状态通常初始化为就绪或就绪/挂起。优先级默认情况下可设置为最低，除非显式请求了更高的优先级；进程最初不拥有任何资源（I/O设备、文件），除非显式地请求了这些资源，或继承了父进程的资源。
（4）设置正确的链接。例如，若操作系统将每个调度队列都维护为一个链表，则新进程必须放在就绪或就绪/挂起链表中。
（5）创建或扩充其他数据结构。例如，操作系统可因编制账单和/或评估性能，为每个进程维护一个记账文件。
两状态模型

非运行态，运行态
五状态模型
- 新建态，就绪态，运行态，阻塞态，退出态
- 运行——阻塞的原因：是因为需要有一些I/O请求，进程必须等待某些事件发生，因此进入阻塞态。
- 运行——就绪的原因：1.达到时间限制 2.被抢占了 3.进程资源释放对于处理器的控制【例如一个周期性进行记账的进程】
七状态模型
- 新建态，就绪态，就绪/挂起态，运行态，阻塞态，阻塞/挂起态，退出态
- 就绪态和阻塞态都在内存中，而就绪/挂起态和阻塞/挂起态都在外存中。
- 阻塞——阻塞挂起的原因：1.没有就绪进程，则至少换出一个阻塞进程 2.为了维护更多的性能所以释放空间，则会挂起一个阻塞的进程
- 运行态——就绪态的原因：1.超时 2.被抢占

进程描述

操作系统的控制结构
- 为了管理进程和资源，操作系统构造和维护其管理的每个实体的信息表，包括
  - 内存表
  - I/O表
  - 文件表
  - 进程表（进程控制表）
进程控制表
- 进程位置
- 进程映象（process image）
- 进程属性：进程控制属性、进程状态属性、进程标识属性

进程控制

执行模式
- 特权模式：系统模式，控制模式，内核模式
- 非特权模式：用户模式
进程创建
- 见前面
进程中断
- 时钟中断：操作系统确定当前正运行进程的执行时间是否已超过最大允许时间段【时间片（time slice），即进程中断前可以执行的最大时间段】。若超过，进程就切换到就绪态，并调入另一个进程。
  - I/O中断：操作系统确定是否已发生I/O活动。若I/O活动是一个或多个进程正在等待的事件，则操作系统就把所有处于阻塞态的进程转换为就绪态（阻塞/挂起态进程转换为就绪/挂起态）。操作系统必须决定是继续执行当前处于运行态的进程，还是让具有高优先级的就绪态进程抢占这个进程。
- 内存失效： 处理器遇到一个引用不在内存中的字的虚存地址时，操作系统就必须从外存中把包含这一引用的内存块（页或段）调入内存。发出调入内存块的I/O请求后，内存失效进程将进入阻塞态；操作系统然后切换进程，恢复另一个进程的执行。期望的块调入内存后，该进程置为就绪态。

操作系统的执行

无进程内核
- 在所有进程外部执行操作系统内核
在用户进程内执行
基于进程的操作系统
- 主要的内核功能被组织为独立的进程

进程挂起的特点

（1）该进程不能立即执行。
（2）该进程可能在也可能不在等待一个事件。若在等待一个事件，那么阻塞条件不依赖于挂起条件，阻塞事件的发生不会使进程立即执行。
（3）为阻止该进程执行，可通过代理使其置于挂起态，代理可以是进程本身，也可以是父进程或操作系统。
（4）除非代理显式地命令系统进行状态转换，否则该进程无法从这一状态转移。

SVR4 进程管理

九进程模型

CH 4 线程

进程和线程

请给出线程间的状态切换比进程间的状态切换开销更低的原因
- 在已有进程中创建一个新线程的时间，远少于创建一个全新进程的时间。【创建时间】
- 终止线程要比终止进程所花的时间少。【终止时间】
- 同一进程内线程间切换的时间，要少于进程间切换的时间。【切换时间】
- 线程提高了不同程序间通信的效率。在多数操作系统中，独立进程间的通信需要内核介入，以提供保护和通信所需的机制。但是，由于同一进程中的多个线程共享内存和文件，因此它们无需调用内核就可互相通信。【通信效率】
线程分类
- 用户级线程（User-Level Thread,ULT）
  - 所有的管理工作都由应用程序完成，内核意识不到线程的存在
  - 特点：默认情况下，应用程序从单个线程开始，并在该线程中开始运行。
- 内核级线程
  - 所有管理工作均有内核完成【Windows】
  - 特点：内核可以同时把同一个进程中的多个线程调度到多个处理器。若进程中的一个线程被阻塞时，内核可以调度同一个进程中的另一个线程
- UTL相较与KTL的优势
  - 所有线程管理数据结构都在一个进程的用户地址空间中，线程切换不需要内核模式特权，因此进程不需要为了管理线程而切换到内核模式，进而节省了两次状态转换（从用户模式到内核模式，以及从内核模式返回用户模式）的开销。
  - 调度因应用程序的不同而不同。一个应用程序可能更适合简单的轮转调度算法，而另一个应用程序可能更适合基于优先级的调度算法。为了不依赖底层的操作系统调度程序，可以做到为应用程序量身定做调度算法。
  - ULT可在任何操作系统中运行，不需要对底层内核进行修改以支持ULT。线程库是供所有应用程序共享的应用级函数。

线程状态（生命期）

线程的状态与进程相似，主要状态都有：运行态、就绪态和阻塞态

与进程状态改变相关的基本操作：

派生：在派生一个新进程时，同时也会为该进程派生一个线程，随后进程中的线程也可以在同一进程中派生另一线程。
阻塞：线程需要等待一个事件时会被阻塞，处理器转而执行另一个就绪线程、
解除阻塞：将该进程转移到就绪队列
结束：一个线程完成后，会释放其寄存器上下文和栈

线程同步
- 一个进程中的所有线程共享同一个地址空间和诸如打开的文件之类的其他资源，一个线程对资源的任何修改都会影响同一进程中其他线程的环境
- 因此需要同步各线程之间的活动使其互不干扰且不破坏数据结构

并发与并行/进程并发的实现（interleaving和overlapping）

并发与并行：并发性是指两个或多个事件在同一时间间隔内发生，并行是指两个或多个事件在同一时刻发生。
进程并发的实现在于，硬件中断一个正在运行的进程，把此时进程运行的所有状态保存下来，为此，操作系统维护一张表格，即进程表（process table），每个进程占用一个进程表项（这些表项也称为进程控制块）。该表存放了进程状态的重要信息：程序计数器、堆栈指针、内存分配状况、所有打开文件的状态、帐号和调度信息，以及其他在进程由运行态转为就绪态或阻塞态时，必须保存的信息，从而保证该进程在再次启动时，就像从未被中断过一样。

CH 5 并发性：互斥和同步

共享资源（Shared Resource）

允许两个或多个进程访问内存某一特定区域的资源

竞争条件（race condition）

多个线程或进程在读写一个共享数据时，结果依赖于它们执行的相对时间的情形

临界区（critical section/region）

一段代码，在这段代码中进程将访问共享资源，当另外一个进程以在这段代码中运行时，这个进程就不能再这段代码中执行

硬件解决方案：关中断、TSL和Exchange指令

关中断

单处理器机器中，并发过程不能重叠，只能交替，因此为保证互斥，只需要保证一个进程不被中断即可

```C
while (true)
{
/禁用中断/;
/临界区/;
/启用中断/;
/其余部分/;
}


  - 缺点：代价昂贵，且不适用于多处理器

- TSL指令

  - ![img](https://img2018.cnblogs.com/blog/1358881/201909/1358881-20190914121205379-1596519614.png)

- Exchage指令

  - ![、](https://img2018.cnblogs.com/blog/1358881/201909/1358881-20190914122555609-1998726413.png)

### 信号量（Semaphore，1965, Dijkstra ）

- 信号量定义
  - semWait：使得信号量-1，若值边为负数，则阻塞执行semWait的进程，否则进程就绪执行
  - semSignal：使得信号量+1，若值小于等于0，则被semWait操作阻塞的进程解除阻塞。
- 二元信号
  - 二元信号量的值只能是0或1
  - 非二元信号量也常称为**计数信号量**（counting semaphore）或**一般信号量**（general semaphore）
  - 互斥锁（mutex）：是一个编程标志位，用来获取或释放一个对象，其值为0时表示锁定，用于阻塞其他程序使用数据，为1时解锁。【为互斥锁加锁和解锁的进程必须是同一个进程，但二元信号量可以不用】

### 生产者-消费者问题（Producer-Consumer Problem）

### 原语（Primitive）

原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。

### 生产者-消费者问题中信号量解决方案中信号量的用途（同步、互斥）

### 管程（Monitor）

- 管程的定义
  - **管程是有一个或多个过程、一个初始化序列和局部数据组成的软件模块**
  - 管程中的数据变量每次只能被一个进程访问，因此可以把一个共享数据结构放在管程中，从而对他进行保护
  - 重点在于管程的过程，它可以操纵局部变量

- 管程的特点

（1）局部数据变量只能被管程的过程访问，任何外部过程都不能访问。
（2）**一个进程通过调用管程的一个过程进入管程**。
（3）**在任何时候，只能有一个进程在管程中执行**，调用管程的任何其他进程都被阻塞，以等待管程可用。

- 管程通过使用条件变量来支持同步，有以下两个函数可以操作条件变量
  - cwait(C)：调用进程的执行在条件c上阻塞，管程现在可以被另一个进程使用
  - csignal(c)：恢复被阻塞的进程

### 消息传递（Message Passing）

- 同步
  - send原语和recive原语
  - 阻塞send，阻塞receive：**发送者和接收者都被阻塞，直到完成信息的投递**。这种情况有时也称为会和（rendezvous），它考虑到了进程间的紧密同步。
  - 无阻塞send，阻塞receive：尽管发送者可以继续，但接收者会被阻塞直到请求的消息到达。这可能是最有用的一种组合，它允许一个进程给各个目标进程尽快地发送一条或多条消息。再继续工作前必须接收到消息的进程将被阻塞，知道该消息到达。例如，一个服务器进程给其他进程提供服务或资源。
  - 无阻塞send，无阻塞receive：不要求任何一方等待。
- 寻址
  - 确定目标或源进程
  - 分直接寻址(direct adressing)和简介寻址(indirect adressing)
  - 消息的发送者和接收者之间存在多种关系，信箱(mailbox)【用于隔离交互，避免其他程序的错误干扰】——变成端口。

### 读者-写者问题



## Charpter 6 并发：死锁和饥饿

###  6.1 死锁原理

##### 联合进程图

就是两个坐标，重叠区域角坐敏感区域（fatal region），创建了能够进入敏感区域的执行路径后，死锁必然发生

##### 可重用资源

一次仅供一个进程安全使用且不因为使用而耗尽的资源；对立的就是可消耗资源

##### 资源分配图【重点】（Resource Allocation Diagram）

画在本子上了

导致死锁的情况：存在进程和资源的环

##### 死锁的条件

1. 死锁的必要条件

   互斥、占有且等待、不可抢占

2. 死锁的可能性

   同必要条件

3. 死锁的存在性

   必要条件+循环等待

### 6.2 死锁预防

一种策略，试图设计一种系统来排除发生死锁的可能性。

从死锁的存在性出发：1.互斥 2.占有且等待 3.不可抢占 4.循环等待，在这之中，互斥不可能预防，占有且等待也很难【为了效率】

### 6.3 死锁避免

死锁避免允许三个必要条件，但通过明智的选择，可以确保永远不会到达死锁点，因此死锁避免与死锁预防可以允许更多的并发。

共有两种死锁避免的方法：

1. 若一个进程的请求会导致死锁，则不启动该进程。【进程启动拒绝策略】
2. 若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。【资源分配拒绝策略】【银行家算法属于这种策略】

### 银行家算法

1. ##### 安全序列

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

   **如果系统处于安全状态，就一定不会发生死锁，如果系统进入不安全状态，就可能发生思索死锁（处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态）**

2. 算法思路：可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。

![image-20210620162226017](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210620162226017.png)

	3.其他的写在纸上了

### 复习题：

#### 6.1 给出可重用资源和可消耗资源(consumable)的例子。

答：可重用资源的例子包括处理器、I/O通道、内存和外存、设备，以及文件、数据库和信号量之类的数据结构；可消耗资源的例子有中断、信号、消息和I/O缓冲区中的信息。

#### 6.2 产生死锁的三个必要条件是什么？

答：
（1）互斥。一次只有一个进程可以使用一个资源。其他进程不能访问已分配给其他进程的资源。
（2）占有且等待。当一个进程等待其他进程时，继续占有已分配的资源。
（3）不可抢占。不能强行抢占进程已占有的资源。

#### 6.3 产生死锁的4个条件是什么？

答：前三个条件都只是死锁的必要条件而非充分条件。要产生死锁，还需要第四个条件：
（4）循环等待。存在一个闭合的进程链，每个进程至少占有此链中下一个进程所需的一个资源。

#### 6.4 如何防止占有且等待条件？(How can the hold and wait condiion be prevented?)

答：可以要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足。

#### 6.5 给出防止不可抢占条件的两种方法。(List two ways in which the no-preemption condition can be prevented?)

答：首先，占有某些资源的一个进程进一步申请资源时若被拒绝，则该进程必须释放其最初占有的资源，必要时可再次申请这些资源和其他资源。其次，一个进程请求当前被另一个进程占有的一个资源时，操作系统可以抢占另一个进程，要求它释放资源。

#### 6.6 如何防止循环等待条件？(How can the circular wait condition be prevented?)

答：循环等待条件可通过定义资源类型的线性顺序来预防。

#### 6.7 死锁避免、检测和预防之间的区别是什么？(What is the difference among deadlock avoidance,detection,and prevention?)

答：死锁避免（预防）策略非常保守，它们通过限制访问资源和在进程上强加约束来解决死锁问题。死锁检测策略则相反，它不限制资源访问或约束进程行为。



### 单词

banker's algorithm 	银行家算法

deadlock prevention  死锁预防

pipe 管道

circular wait   循环等待

hold and wait  占有且等待

preemption  抢占

consumable resource   可消耗资源

joint progress diagram  联合进程图

resource allocationgraph  资源分配图

deadlock  死锁

memory barrier   内存屏障

reusable resource  可重用资源

deadlock avoidance   死锁避免

message   消息

spinlock  自旋锁

deadlock detection  死锁检测

mutual exclusion  互斥

starvation  饥饿



## Charpter7 内存管理

### 7.1 内存管理的需求

重定位、保护、共享、逻辑组织、物理组织

### 7.2 内存分区

内存管理的主要操作就是处理器把程序装入内存中执行

##### 7.2.1 固定分区

最简单的方法，但有两个问题（考虑放多少跟怎么少）

1. 程序可能因为太大了而放不下一个分区
2. 内存的利用率非常低——》由于装入的数据块小于分区大小而导致分区内部存在空间浪费的现象称为**内部碎片【internal fragmentation】**

放置算法

1. 把每个进程分配到能够容纳它的最小分区中，在这种情况下，每个分区需要维护一个调度队列【从单个分区的角度看这种方法是最优的】
2. 采用单个队列，可以优先选择换出被阻塞的进程而非就绪进程
3. 可考虑的算法有三种：最佳适配，首次适配，下次适配

##### 7.2.2 动态分区

随着时间的推移，内存中形成越来越多的碎片，内存的利用率下降，这种现象称为**外部碎片【external fragmentation】**。

外部碎片指的是**所有分区外的存储空间**【因为动态的话每一个进程就是一个分区】变成了越来越多的碎片，这与前面所讲的内部碎片正好对应。【这需要压缩，但压缩很费时间】

放置算法

下述三种算法都在内存中选择大于等于进程的空闲块，区别在于

1. 最佳适配：选择与要求大小最接近的块
2. 首次适配：从头开始扫描内存，选择大小足够的第一个可用快
3. 下次适配：从上次放置的位置开始扫描内存，选择下一个大小足够的可用块。

##### 7.2.3 伙伴系统

其实就是个二叉树，二分整个区间，若存储空间在子区间内，则分配，不满足，则继续分裂

##### 7.2.4 重定位

逻辑地址、相对地址、物理地址

### 7.3 分页

将内存分为大小固定、相等的块，且块相对比较小，**每个进程也被分成同样大小的块**，那么进程中称为页的块(page)可以分配到内存中称为页框(frame)的可用页

操作系统会为每个进程维护一个页表，页表给出了进程的每页对应页框的位置

**分页的寻址**：

考虑一个n+m位地址，最左边n位的是页号，最右边m位是偏移量

### 7.4 分段

把程序和与其相关的数据划分到几个段(segment)中

同分页，但是有点动态分区的味道

### 7.5 分段分页总结

分页：系统会维护一个空闲的页表，以说明每页对应的页框

分段：系统位每个进程维护一个段表，以说明每段中的加载地址和长度



### 复习题

#### 7.1 内存管理需要满足哪些需求？

答：重定位、保护、共享、逻辑组织、物理组织。

#### 7.2 为何需要重定位进程的能力？

答：在多道程序设计系统中，可用的内存空间通常被多个进程共享。通常情况下，程序员事先并不知道在某个程序执行期间会有其他哪些程序驻留在内存中。此外，我们还希望提供一个巨大的就绪进程池，以便把活动进程换入或换出内存，进而使处理器的利用率最大化。程序换出到磁盘中后，下次换入时要放到与换出前相同的内存区域会很困难。相反，我们需要把进程重定位（relocate） 到内存的不同区域。

#### 7.3 为何不可能在编译时实施内存保护？

答：程序在内存中的位置不可预测。

#### 7.4 允许两个或多个进程访问内存某一特定区域的原因是什么？

答：合作完成同一个任务的进程可能需要共享访问相同的数据结构。

#### 7.5 在固定分区方案中，使用大小不等的分区有何好处？

答：可缓解因程序太大而无法放到固定大小的分区和因程序太小产生大量内部碎片的问题。

#### 7.6 内部碎片和外部碎片有何区别？

答：固定分区中，由于装入的数据块小于分区大小，因而导致分区内存在空间浪费，这种现象称为内部碎片（internal fragmentation）；动态分区中，随着时间的推移，内存中形成越来越多的碎片，内存的利用率随之下降，这种现象称为外部碎片（external fragmentation），指在所有分区外的存储空间变成了越来越多的碎片。

#### 7.7 逻辑地址、相对地址和物理地址有何区别？

答：逻辑地址（logical address） 是指与**当前数据在内存中的物理分配地址无关的访问地址**，在执行对内存的访问之前必须把它转换为物理地址。相对地址（relative address） 是逻辑地址的一个特例，它是相对于某些已知点（通常是程序的开始处）的存储单元。物理地址（physical address） 或绝对地址是数据在内存中的实际位置。

#### 7.8 页和页框有何区别？

答：（个人理解）页是进程中的块，页框是内存中的块。

#### 7.9 页和段有何区别？

答：页大小相等，段可以大小不等；分页对程序员来说是透明的，而分段通常是可见的。



## Charpter 8 虚拟内存

#### 虚拟存储器的定义及实现

- 定义：
  - 基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存。另一方面，操作系统将内存中暂时不使用的内容换出到外存上。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。
- 实现方式：
  - 虚拟存储器有以下三种实现方式∶请求分页，请求分段，请求段页式

#### 8.1 硬件和控制结构

![image-20210620230957970](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210620230957970.png)



#### 8.1.2 分页

局部性原理——表明虚拟内存方案是可行的

局部性原理

**一个良好的计算机程序 常常具有良好的局部性，也就是说，它们倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用过的数据项本身**

1. **时间局部性**：如果程序中的某条指令一旦执行，不久之后该指令可能再次被执行。如果某数据彼访问过，不久之后该数据可能被再次访问
2. **空间局部性**：一旦程序访问了某个存储单元，不久之后其附近的存储单元也将被访问（程序在一段时间内访问同一范围内的地址）

分页：

转换检测缓冲区（Translation Lookaside Buffer TLB）——虚拟内存方案为页表像使用的一个特殊高速缓存

![image-20210620231438574](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210620231438574.png)

**TLB【重点】**

转换检测缓冲区（TLB）是一个**特殊的高速缓存**，包含有最近用过的页表项

![image-20210706194531023](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706194531023.png)

	给定一个虚拟地址，处理器首先检查TLB, 若需要的页表项在其中(TLB 命中），则**检索页框号并形成实地址**。若未找到需要的页表项(TLB 未命中），则**处理器用页号检索进程页表**，并检查相应的页表项。若“存在位”已置位，则该页在内存中，处理器从页表项中检索页框号以形成实地址。**处理器同时更新TLB, 使其包含这个新页表项**。最后，若“存在位”未置位，则表示需要的页不在内存中，这时会产生一次内存访问故障，称为**缺页( page fault )中断**。



![在这里插入图片描述](https://img-blog.csdnimg.cn/20201120144918135.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1RyYWN5Y29kZXI=,size_16,color_FFFFFF,t_70#pic_center)



#### 8.1.3 分段

![image-20210706200000705](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706200000705.png)

#### 段页式

在段页式系统中，用户的地址空间被程序员划分为许多段。每段依次划分为许多固定大小的页，页的长度等千内存中的页框大小。若某段的长度小于一页，则该段只占据一页。

![image-20210706201040355](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706201040355.png)

#### 读取策略

读取策略决定某页何时取入内存，常用的两种方法是请求分页( demand paging) 和预先分页（prepaging) 

- 请求分页
  - 只有当访问到某页中的一个单元时才将该页取入内存
- 预先分页
  - **读取的页并不是缺页中断请求的页**。预先分页利用了大多数辅存设备（如磁盘）的特性，这些设备有寻道时间和合理的延迟。若一个进程的页连续存储在辅存中，则一次读取许多连续的页要比隔一段时间读取一页有效。

#### 放置策略

第七章描述的最佳适配、首次适配、下次适配

#### 置换策略（Replacement Policy)

- 最佳(Optimal, OPT)
  - 置换下次访问距当前时间最长的那些页
- 最近最少使用(LeastRecently Used, LRU)
  - 置换内存中最长时间未被引用的页
- 先进先出(First In First Out, FIFO)
- 时钟(Clock)

#### 虚拟存储器的设计问题（Design Issues）

- 工作集（Working Set）：工作集的概念可用千指导有关驻留集大小的策略：

- 页面的大小（Page Size）：页越小，内部碎片越小，但需要的页的数量越多，意味着更大的页表。
  - 碎片（Fragmentation）：

- 装入页的时机（按需装入和预先装入， Demand Paging and Prepaging）

- 全局和局部（Global or Local Scope）：
  - 局部：仅在产生缺页的进程的驻留页中选择
  - 全局：把内存中所有未被锁定的页都作为置换的候选页

- 颠簸/抖动（Thrashing）：如果一块正好在将要用到之前换出，操作系统就不得不很快地把它取回。这类操作通常会导致一种称为系统抖动(thrashing )的情况：处理器的大部分时间都用于交换块而非执行指令。

- 页面替换算法：Optimal、Least Recently Used、FIFO、Clock

### 复习题

#### 8.1 简单分页与虚拟内存分页有何区别？

答：进程运行时，简单分页的所有页必须都在内存中，除非使用了覆盖技术，虚存分页并非所有页都须在内存页框中，仅在需要时才读入页，把一页读入内存可能需要把另一页写出到磁盘。

#### 8.2 什么是抖动？

答：处理器的大部分时间都用于交换块而非执行指令。

#### 8.3 为何在使用虚拟内存时，局部性原理至关重要？

答：局部性原理描述了一个进程中程序和数据引用的集簇倾向。因此，假设在很短的时间内仅需要进程的一部分块是合理的。同时，还可以对将来可能会访问的块进行猜测，从而避免系统抖动。局部性原理表明虚拟内存方案是可行的。

#### 8.4 哪些元素是页表项中能找到的典型元素？简单定义每个元素。

答：与内存中的页框相对应的页框号、表示它所对应的页是否在内存中的一位（P）、表示相应页的内容从上次装入内存到现在是否已改变的一位（M）。

#### 8.5 转换检测缓冲区的目的是什么？

答：为了克服简单的虚拟内存方案导致内存访问时间加倍的问题。原则上，每次虚存访问都可能会引起两次物理内存访问：一次取相应的页表项，另一次取需要的数据。

#### 8.6 简单定义两种可供选择的页面读取策略。

答：
请求分页（demand paging）：只有当访问到某页中的一个单元时才将该页取入内存。
预先分页（prepaging）：读取的页不是缺页中断请求的页。

#### 8.7 驻留集管理和页面置换策略有何区别？

答：驻留集管理的概念为：
（1）给每个活动进程分配多少页框。
（2）计划置换的页集是局限于那些缺页中断的进程，还是局限于所有页框都在内存中的进程。
置换策略的概念为：在计划置换的页集中，选择换出哪一页。

#### 8.8 FIFO和时钟页面置换策略有何区别？

答：始终策略需要给每个页框关联一个称为使用位的附加位，在时钟策略中会跳过使用位为1的页框。

#### 8.9 页缓冲实现什么功能？

答：被置换的页仍然留在内存中。

#### 8.10 为什么不能把全局置换策略和固定分配策略组合起来？

答：为保持驻留集的大小固定，从内存中移出的一页必须由同一个进程的另一页置换。

#### 8.11 驻留集和工作集有何区别？

答：驻留集表示进程在内存中的页集，工作集表示进程在过去的一段时间中被访问到的页集。

#### 8.12 请求式清除和预约式清除有何区别？

答：对于请求式清除（demand cleaning），只有当一页被选择用于置换时才被写回辅存；而预约式清除（precleaning） 策略则将这些已修改的多页在需要使用它们所占据的页框之前成批写回辅存。



## Charpter 9 单处理器调度

#### 调度类型

- 长程调度：决定加入待执行进程池。
- 中程调度：决定加入部分或全部位于内存中的进程集合。
- 短程调度：决定可用I/O设备处理哪个进程挂起的I/O请求。

#### 调度策略

略

#### 9.1 简要描述三种类型的处理器调度。

答：
长程调度：决定加入待执行进程池。
中程调度：决定加入部分或全部位于内存中的进程集合。
短程调度：决定可用I/O设备处理哪个进程挂起的I/O请求。

#### 9.2 在交互式操作系统中，通常最重要的性能要求是什么？

答：响应时间。

#### 9.3 周转时间和响应时间有何区别？

答：周转时间指一个进程从提交到完成之间的时间间隔，包括实际执行时间和等待资源（包括处理器资源）的时间；响应时间指从提交一个请求到开始接收响应之间的时间间隔。

#### 9.4 对于进程调度，较小的优先级值是表示较低的优先级还是表示较高的优先级？

答：对于UNIX和许多其他操作系统中，优先级数值越大，表示的进程优先级越低。某些系统如Windows的用法正好相反，即大数值表示高优先级。

#### 9.5 抢占式调度和非抢占式调度有何区别？

答：
非抢占：在这种情况下，一旦进程处于运行状态，就会不断执行直到终止，进程要么因为等待I/O，要么因为请求某些操作系统服务而阻塞自己。
抢占：当前正运行进程可能被操作系统中断，并转换为就绪态。一个新进程到达时，或中断发生后把一个阻塞态进程置为就绪态时，或出现周期性的时间中断时，需要进行抢占决策。

#### 9.6 简单定义FCFS调度。

答：每个进程就绪后，会加入就绪队列。当前正运行的进程停止执行时，选择就绪队列中存在时间最长的进程运行。

#### 9.7 简单定义轮转调度。

答：这种算法周期性地产生时钟中断，出现中断时，当前正运行的进程会放置到就绪队列中，然后基于FCFS策略选择下一个就绪作业运行。

#### 9.8 简单定义最短进程优先调度。

答：这是一个非抢占策略，其原则是下次选择预计处理时间最短的进程。

#### 9.9 简单定义最短剩余时间调度。

答：最短剩余时间是在SPN中增加了抢占机制的策略。在这种情况下，调度程序总是选择预期剩余时间最短的进程。

#### 9.10 简单定义最高响应比优先调度。

答：当前进程完成或被阻塞时，选择R值最大的就绪进程。

#### 9.11 简单定义反馈调度。

答：调度基于抢占原则并使用动态优先级机制。



## Charpter 11 I/0管理和磁盘调度

	I/O设备的特点

	I/O设备的分类

		块设备/字符设备（流设备）

	I/O软件的组织

	磁盘调度（Disk arm scheduling）

		磁盘I/O的过程（Seek time、Rotational Delay、Data Transfer Time）

	RAID

### 11.1 I/0设备

直接存储器访问（DMA）：一个DMA模块控制内存和I/0模块之间的数据交换。为传送一块数据，处理器给DMA模块发送请求，且只有在整个数据快传送结束后，它才被中断。

越来越多的I/0功能可以在没有中央处理器参与的情况下执行。——只有在传送开始和结束时才会用到处理器

**分类：**

- 面向块（ block-oriented ) 的设备**将信息保存在块中**，块的大小通常是固定的，**传送过程中一次传送一块**。通常可以通过块号访问数据。**磁盘和USB 智能卡**都是面向块的设备。

- 面向流( stream-oriented )的设备**以字节流的方式输入／输出数据**，它没有块结构。**终端、打印机、通信端口、鼠标**和其他指示设备及其他大多数非辅存设备，都属于面向流的设备。

**I/O软件的组织**

![image-20210706213408304](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706213408304.png)

### 11.4 I/O缓冲

为避免这些开销和低效操作，有时为了方便起见，在输入请求发出前就开始执行输入传送，并且在输出请求发出一段时间之后才开始执行输出传送，这项技术称为缓冲。

有单缓冲、双缓冲、环形缓冲

单缓冲方案：输入传送的数据被放到系统缓冲区内。当传送完成时，进程把该块移到用户空间，并立即请求另一块。这称为预读，或预先输入。这样做的原因是期望这块数据最终会被使用。

### 11.5 磁盘调度

磁盘性能参数：寻道时间、旋转延迟、传输时间、时序比较

##### 磁盘调度策略

写纸上了：		FIFO、SCAN、C-SCAN

##### RAID（独立磁盘冗余阵列）

1. RAID是一组物理磁盘驱动器，操作系统把它视为单个逻辑驱动器
2. 数据分布在物理驱动器阵列中
3. 使用冗余磁盘容量保存奇偶检验信息，保证在一个磁盘失效时，数据具有可恢复性

##### 磁盘I/O的过程（Seek time、Rotational Delay、Data Transfer Time）

- 寻道时间：寻道时间是将磁头臂移到指定磁道所需要的时间。寻道时间由两个重要部分组成：最初启动时间，以及访问臂达到一定的速度后，横跨那些其必须跨越的磁道所需要的时间。
- 旋转延迟：旋转延迟是指将磁盘的待访问地址区域旋转到读／写磁头可访问的位置所需要的时间
- 传输时间：![image-20210706213612886](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706213612886.png)



### 复习题

#### 11.1 列出并简单定义执行I/O的三种技术。

答：
程序控制I/O： 处理器代表一个进程给I/O模块发送一个I/O命令；该进程进入忙等待，直到操作完成才能继续执行。
中断驱动I/O： 处理器代表进程向I/O模块发出一个I/O命令。有两种可能性：若来自进程的I/O指令是非阻塞的，则处理器继续执行发出I/O命令的进程的后续指令。若I/O指令是阻塞的，则处理器执行的下一条指令来自操作系统，它将当前的进程设置为阻塞态并调度其他进程。
直接存储器访问（DMA）： 一个DMA模块控制内存和I/O模块之间的数据交换。为传送一块数据，处理器给DMA模块发请求，且只有在整个数据块传送结束后，它才被中断。

#### 11.2 逻辑I/O和设备I/O有何区别？

答：
逻辑I/O：逻辑I/O模块把设备当作一个逻辑资源来处理，它并不关心实际控制设备的细节。逻辑I/O模块代表用户进程管理的普通I/O功能，允许用户进程根据设备标识符及诸如打开、关闭、读、写之类的简单指令与设备打交道。
设备I/O：请求的操作和数据（缓冲的数据、记录等）被转换为适当的I/O指令序列、通道命令和控制器指令。可以使用缓冲技术来提高利用率。

#### 11.3 面向块的设备和面向流的设备有何区别？各举一些例子。

答：面向块（block-oriented）的设备将信息保存在块中，块的大小通常是固定的，传送过程中一次传送一块。通常可以通过块号访问数据。磁盘和USB智能卡都是面向块的设备。面向流（stream-oriented）的设备以字节流的方式输入/输出数据，它没有块结构。终端、打印机、通信端口、鼠标和其他指示设备以及其他大多数非辅存设备，都属于面向流的设备。

#### 11.4 为什么希望用双缓冲而非单缓冲来提高I/O的性能？

答：对于面向块的传送，我们可以粗略地估计执行时间为max[C,T]。因此，若C≤T，则有可能使面向块的设备全速运行；另一方面，若C＞T，则双缓冲能确保该进程不需要等待I/O。

#### 11.5 在磁盘读或写时有哪些延迟因素？

答：寻道时间（seek time）、旋转延迟（rotational delay）、存取时间（access time）、传输时间（transfer time）。

#### 11.6 简单定义图11.7中描述的磁盘调度策略。

答：
先进先出（FIFO）：按顺序处理队列中的项目。
最短服务时间优先（SSTF）：选择使磁头臂从当前位置开始移动最少的磁盘I/O请求。
SCAN：要求磁头臂仅沿一个方向移动，并在途中满足所有未完成的请求，直到它到达这个方向上的最后一个磁道。
C-SCAN：把扫描限定在一个方向上。因此，当访问到沿某个方向的最后一个磁道时，磁头臂返回到磁盘相反方向末端的磁道。

#### 11.7 简单定义7个RAID级别。

答：
RAID 0：条带化、非冗余。
RAID 1：镜像、被镜像。
RAID 2：并行访问、通过汉明码实现冗余。
RAID 3：并行访问、交错位奇偶校验。
RAID 4：独立访问、交错块奇偶校验。
RAID 5：独立访问、交错块分布奇偶校验。
RAID 6：独立访问、交错块双重分布奇偶校验。

#### 11.8 典型的磁盘扇区大小是多少？

答：512字节。

## CH 12

### 文件、文件系统

文件拥有的属性：

![image-20210706214338989](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706214338989.png)

文件系统不但提供存储数据（组织为文件）的手段，而且提供一系列对文件进行操作的功能接口。典型的操作如下：

- 创建：在文件结构中定义并定位一个新文件。
- 删除：从文件结构中删除并销毁一个文件。
- 打开：进程将一个已有文件声明为“打开”状态，以便允许该进程对这个文件进行操作。
- 关闭：相关进程关闭一个文件，以便不再能对该文件进行操作，直到该进程再次打开它。
- 读：进程读取文件中的所有或部分数据。
- 写：进程更新文件，要么通过添加新数据来扩大文件的尺寸，要么通过改变文件中已有数据项的值。

### 文件的分类

	正规文件（Regular file）、特殊文件（Device Special File）、目录（Directory）、管道（Pipe：Anonymous Pipe/Named Pipe）等

### 文件的常见操作

**树形结构**

![image-20210707010637386](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210707010637386.png)

		路径及分类

**根目录与当前目录（Root Directory and Current Directory/Working Directory）**

**绝对路径与相对路径（Absolute Path and Relative Path）**

**文件结构（字节流结构）**

**磁盘空间的分配方法及优缺点**

**磁盘块地址/编号**

**连续分配**

![image-20210706214908088](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706214908088.png)

**不连续分配（链式分配、索引分配）**

- 链式分配后局部性原理不再适用

  ![image-20210706214924113](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706214924113.png)

- 索引分配

![image-20210706215018887](C:\Users\10147\AppData\Roaming\Typora\typora-user-images\image-20210706215018887.png)

**空闲空间的记录**：

需要磁盘分配表(DiskAllocation Table, DAT) 

**基于i-node的Unix文件系统**

**文件的同时存取**

**文件的访问权限**

**i-node的结构**

**基于i-node的路径分析**





12.1 域和记录有何不同？
答：域（field）是基本的数据单元。一个域包含一个值，如雇员的名字、日期或传感器读取的值。域可通过其长度和数据类型（如ASCII字符串、二进制数等）来描述。域的长度可以是定长的或变长的，具体取决于文件的设计。对于后一种情况，域通常包含两个或三个子域：要保存的实际值、域名，以及某些情况下的域长度。在其他情况下，域之间特殊的分隔符暗示了域的长度。
记录（record）是一组相关域的集合，可视为应用程序的一个单元。例如，一条雇员记录可能包含以下域：名字、社会保险号、工作类型、雇用日期等。同样，记录的长度也可以是定长的或变长的，具体取决于设计。如果一条记录中的某些域是变长的，或记录中域的数量可变，则该记录是变长。对于后一种情况，每个域通常都有一个域名。对于这两种情况，整条记录通常都包含一个长度域。

12.2 文件和数据库有何不同？
答：文件是一组相似记录的集合，它被用户和应用程序视为一个实体，并可通过名字访问。文件有唯一的一个文件名，可被创建或删除。访问控制通常在文件级实施，也就是说，在共享系统中，用户和程序被允许或被拒绝访问整个文件。在有些更复杂的系统中，这类控制也可在记录级或域集实施。
数据库是一组相关的数据的集合，其本质特征是数据元素间存在着明确的关系，且可供不同的应用程序使用。数据库可能包含与一个组织或项目相关的所有信息，如一家商店或一项科学研究。数据库自身由一种或多种类型的文件组成。通常，数据库管理系统是独立于操作系统的，尽管它可能会使用某些文件管理程序。

12.3 什么是文件管理系统？
答：文件管理系统是一组系统软件，它为使用文件的用户和应用程序提供服务。典型情况下，文件管理系统是用户或应用程序访问文件的唯一方式，它可使得用户或程序员不需要为每个应用程序开发专用软件，并为系统提供控制最重要资源的方法。

12.4 选择文件组织时的重要原则是什么？
答：快速访问、易于修改、节约存储空间、维护简单、可靠性。

12.5 列出并简单定义5种文件组织。
答：
堆：是最简单的文件组织形式。数据按它们到达的顺序被收集，每条记录由一串数据组成。
顺序文件：是最常用的文件组织形式。在这类文件中，每条记录都使用一种固定的格式。所有记录有具有相同的长度，并由相同数量、长度固定的域按特定的顺序组成。
索引顺序文件：保留了顺序文件的关键特征：记录按照关键域的顺序组织。但它增加了两个特征：用于支持随机访问的文件索引和溢出文件。溢出文件类似于顺序文件中使用的日志文件，但溢出文件中的记录可根据它前面记录的指针进行定位。
索引文件：只能通过索引来访问记录。
直接文件或散列文件：开发直接访问磁盘中任何一个地址已知的块的能力。

12.6 为何在索引顺序文件中查找一条记录的平均时间小于在顺序文件中的平均时间？
答：索引提供了快速接近目标记录的查找能力。考虑一个包含100万条记录的顺序文件。要查找某个特定的关键域值，平均需要访问50万次记录。现在假设创建一个包含了1000项的索引，索引中的关键域均匀分布在主文件中。为找到这条记录，平均只需在索引文件中进行500次访问，接着在主文件中进行500次访问。查找的开销从500000降低到了1000。

12.7 对目录执行的典型操作有哪些？
答：查找、创建文件、删除文件、显示目录、修改目录。

12.8 路径名和工作目录有何关系？
答：一系列目录名和最后到达的文件名组成了该文件的路径名（pathname）。对交互用户或进程而言，总有一个当前路径与之相关联，通常称为工作目录（working directory）。

12.9 可以授予或拒绝的某个特定用户对某个特定文件的访问权限通常有哪些？
答：无、知道、执行、读、追加、更新、改变保护、删除。

12.10 列出并简单定义三种组块方法。
答：
定长组块（fixed blocking）： 使用定长的记录，且若干完整的记录保存在一个块中。在每个块的末尾可能会有一些未使用的空间，称为内部碎片。
变长跨越式组块（variable-length spanned blocking）： 使用变长的记录，并紧缩到块中，使得块中不存在未使用的空间。因此，某些记录可能会跨越两个块，两个块通过一个指向后续块的指针连接。
变长非跨越式组块（variable-length unspanned blocking）： 使用变长的记录，但并不采用跨越方式。若下一条记录比块中剩余的未使用空间大，则无法使用这一部分，因此在大多数块中都会有未使用的空间。

12.11 列出并简单定义三种文件分配方法。
答：
连续分配（continuous allocation）： 是指在创建文件时，给文件分配一组连续的块。
链式分配（chained allocation）： 基于单个块，链中的每块都包含指向下一块的指针。
索引分配（indexed allocation）： 每个文件在文件分配表中都有一个索引。分配给该文件的每个分区在索引中都有一个表项
	

## 预测题

### 填空

1. 产生死锁的必要条件
   - 互斥：只有对必须互斥使用的资源的争夺才会导致死锁
   - 不可抢占：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放
   - 占有且等待：当一个进程等待其他进程时，继续占有已分配的资源。
   - 循环等待：存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程请求。
2. 产生死锁的原因
   - 竞争临界资源：各个进程对不可剥夺的资源的竞争可能引起死锁
   - 进程推进顺序不当：进程推进顺序非法，请求和释放资源的顺序不当

### 简答

### 1.What is the kernel of an os?[1.2]

### 2.What is multiprogramming?[1.3]

### 3.Expalin the distination between a monolithic kernal and a microkernel.[1.9]

	单体内核（monolithic kernel）提供操作系统应提供的多数功能，包括调度、文件系统、网络、设备驱动器、存储管理等。典型情况下，这个大内核是作为一个进程来实现的，所有元素都共享相同的地址空间。微内核体系结构（microkernel architecture）只给内核分配一些最基本的功能，包括地址空间、进程间通信(Inter Process Communication, IPC)和基本的调度。

### 4.[2.2]

### 5.[2.5]

### 6.[2.12]

### 7.[3.2]

### 8.[3.6]

### 9.[8.2]

### 10.[9.2]

### 11.[9.6]

### 12.[9.8]

### 13.[5.3]

### 14.[6.1]

### 15.[6.8]

### 16.[6.9]

### 17.

**什么是死锁？什么是饥饿？两者之间的共同点和区别是什么**

- 死锁：指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待，导致各进程都阻塞，无法向前推进的现象。
- 饥饿：由于长期得不到想要的资源，某进程无法向前推进的现象
- 共同点：都是进程无法顺利向前推进的现象
- 不同点：如果有死锁现象，那么至少有两个或者两个以上的进程同时发生死锁，且发生死锁的进程一定处于阻塞态。但对于饥饿而言，可能只有一个进程发生饥饿，发生饥饿的进程既可以是阻塞态，也可以是就绪态。

**死锁的处理策略有哪些？**

- 预防死锁：破坏死锁产生的四个必要条件中的一个或几个
  - 互斥：很多时候无法破坏互斥条件
  - 不可抢占：
    - 当某个进程请求新的资源得不到满足时，必须立即释放保持的所有资源，待以后需要时再重新申请。
    - 当某个进程需要的资源被其他进程所占有的时候，可以有操作系统写出，将想要的资源强行抢占，这种方式需要考虑各个进程的优先级。
    - 缺点是实现起来比较复杂，且释放已经互动二资源可能会造成前一阶段工作的失效。
  - 占有且等待：可以要求进程一次性地请求所有需要的资源，并阻塞这个进程直到所有请求都同时满足
  - 循环等待：可以采用顺序资源分配法，首先给系统中的资源编号，规定每个进程必须按照编号递增的顺序请求资源，同类资源一次申请完。
  - ![img](https://img2018.cnblogs.com/blog/1358881/201909/1358881-20190927184318218-1388735870.png)
- 避免死锁：用某种方法组织系统进入不安全状态，从而避免死锁
  - 死锁避免需要直到未来几次资源请求的情况
  - 两种避免方法：1.若一个进程的请求会导致死锁，则不启动该进程 2.若一个进程增加的资源请求会导致死锁，则不允许这一资源分配【银行家算法】。
- 死锁的检测和接触：允许死锁的发生，不过OS会负责检测除死锁的发生，然后采取某种措施解除死锁。

### 大题

注:

构造parbegin(P1,P2,......,pn)的含义为：阻塞	主程序，初始化并行过程P1.P2,...,Pn过程全部终止之后，才恢复主程序的执行

##### **1.生产者消费者问题**

![img](https://img2018.cnblogs.com/blog/1358881/201909/1358881-20190916201239112-1683803912.png)

![img](https://img2018.cnblogs.com/blog/1358881/201909/1358881-20190915135612260-1362223675.png)

```C
semaphore mutex = 1;  //互斥信号量
semaphore empty = n;  //同步信号量。空闲缓冲区的数量
semaphore full = 0;   //同步信号量。产品的数量，非空缓冲区的数量
void producer(){
    while(1){
      produce()；//生成一个产品
      semWait(empty); //消耗一个空闲缓冲区
      semWait(mutex);
      append();	//把产品放入缓冲区
      semSignal(mutex);
      semSignal(full)   //增加一个产品
    }
}
void consumer(){
    while(1){
      semWait(full);   //消耗一个产品
      semWait(mutex);
      take();	//从缓冲区取出一个产品;
      semSignal(mutex);
      semSignal(empty);  //增加一个空闲缓冲区
      consume(); //使用产品;
    }
}
void main()
{
    parbegin(producer,consumer);
}

2.读者/写者问题

问题要求
- 任意数量的读进程可同时读这个文件
- 一次只有一个写进程可以写文件
- 若一个写进程正在写文件，则禁止任何读进程读文件

读者优先方案

数据结构及信号量：
- 信号量wsem：用于实施互斥。对于写进程
- 全局变量readcount：用于记录读进程的数量
- 信号量mutex：用于确保readcount被正确地更新。
思想：
- 对于写进程而言：只要有一个写进程正在访问共享数据去，其他进程（读，写）都不可以访问它。
- 对于读进程而言：也用信号量wsm实施互斥，当至少有一个读进程在读时，随后的进程无需等待，可以直接进入
算法代码

int readcount;
semaphore mutex=1,wsem=1;
void reader(){
    while(1){
        semWait(mutex);
        if(readcount == 0)
            semWait(wsem);
        readcount++;
        semSignal(mutex);
        读;
        sewWait(mutex);
        readcount--;	//不读了
        if (readcount == 0)
            semSignal(wsem);
        semSignal(mutex);
    }
}
void writer(){
    while(1){
        semWait(wsem);
        写;
        semSignal(wsem);
    }
}
void main(){
    readcount = 0;
    parbegin(writer,reader)
}

写者优先方案

不参考书上的解决方案了
新加入一个锁变量w，用于实现“写优先”
这里我们来分析一下读者1->写者1->读者2这种情况。第一个读者1在进行到读文件操作的时候，有一个写者1操作，由于第一个读者1执行了V(w)，所以写者1不会阻塞在P(w)，但由于第一个读者1执行了P(rw)但没有执行V(rw)，写者1将会被阻塞在P(rw)上，这时候再有一个读者2，由于前面的写者1进程执行了P(w)但没有执行V(w)，所以读者2将会被阻塞在P(w)上，这样写者1和读者2都将阻塞，只有当读者1结束时执行V(rw)，此时写者1才能够继续执行直到执行V(w)，读者2也将能够执行下去。

代码

int readcount;
semaphore mutex=1,wsem=1,w=1;
void reader(){
    while(1){
        semWait(w);
        semWait(mutex);
        if(readcount == 0)
            semWait(wsem);
        readcount++;
        semSignal(mutex);
        semSignal(w);
        读;
        sewWait(mutex);
        readcount--;	//不读了
        if (readcount == 0)
            semSignal(wsem);
        semSignal(mutex);
    }
}
void writer(){
    while(1){
        semWait(w);
        semWait(wsem);
        写;
        semSignal(wsem);
        semSignal(w);
    }
}
void main(){
    readcount = 0;
    parbegin(writer,reader)
}

3.哲学家就餐问题

解决方案思路：

增加一名服务员，他只允许四位哲学家同时进入餐厅，因为至少有一位哲学家可以拿到两把叉子

代码：

semaphore fork[5]={1};
semaphore room=4;
int i;
void philosopher (int i)
{
	while(true){
        think();
        wait(room);		//room锁p操作
        wait(fork[i]);	//拿起左边叉子
        wait(fork[(i+1) mod 5]);//拿起右边叉子
        eat();
        signal(fork[(i+1) mod 5]);//放下右边叉子
        signal(fork[i]);	//放下左边叉子
        signal(room);	//room锁v操作
    }
}
void main()
{
  	parbegin(philosopher(0),philosopher(1),philosopher(2),philosopher(3),philosopher(4))
}

4.资源分配拒绝策略【银行家算法banker algorithm】

安全序列
- 所谓安全序列，就是指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。安全系列可能有多个。
- 如果找不出任何一个安全序列，系统就进入了不安全状态，这意味着之后可能所有进程都无法顺利地执行下去，如果有进程提前归还了一些资源，那么系统也有可能重新回到安全状态。
- 出于安全状态一定不会发生死锁，进入不安全状态不一定会发生死锁。
算法实现
- 数据结构：
  
  Claim矩阵C【最大需求】
  
  Allocation矩阵A【当前已分配】
  
  Resource向量R【初始总的资源有多少】
  
  Available向量V【现在还有多少资源可以分配】
  
  C-A矩阵【最大需求-已经分配=还需要的资源矩阵】
- 算法步骤：
  - 先计算C-A
  - 找到满足（C-A）ij <= V ij 的对应资源，这就是本次分配的资源Pi
  - V矩阵+=本次分配的资源Pi的A矩阵【手头又有资源了】
  - 重复第一步，直到找到一个安全序列。
- 实战：
  - 资源分配拒绝策略的限制：
    - 必须事先声明每个进程请求的最大资源
    - 所讨论的进程必须是无关的，即它们的执行顺序必须没有任何同步要求的限制
    - 分配的资源数量必须是固定的
    - 在占有资源时，进程不退出【如果先退出，那么这个安全序列就没用了】

Wanjia Huang

【笔记】OS期末复习

CH3 进程描述和控制

什么是进程

进程状态

进程描述

进程控制

操作系统的执行

进程挂起的特点

SVR4 进程管理

CH 4 线程

进程和线程

线程状态（生命期）

并发与并行/进程并发的实现（interleaving和overlapping）

CH 5 并发性：互斥和同步

共享资源（Shared Resource）

竞争条件（race condition）

临界区（critical section/region）

硬件解决方案：关中断、TSL和Exchange指令

2.读者/写者问题

3.哲学家就餐问题

4.资源分配拒绝策略【银行家算法banker algorithm】

5.pro[2.2]

6.[8.2]

7.[9.7]

8.[4.2]

9.[5.5]

10.[6.12]

11.[6.13]

12.[7.4]

13.[7.15]

14.[10.12]

15.磁盘调度策略

16.进程调度策略