操作系统读书笔记

PS:放在本地总是丢，传上来跟大家分享。看书做点笔记，我会不定时更新。写的不对或者有问题欢迎评论指正。

操作系统

并发：同一时间段多个事务执行。
「并行：同一时刻多个事务执行」
共享：资源被多个内存中并发执行的进线
程共同共同使用。
虚拟：通过时分复用和空分复用将一个物
理实体虚拟为多个。
异步：系统中的进程以走走停停的方式执
行，且以不可预知的速度推进。

中断异常和系统调用：

中断是由外设发出请求的，是异步执行，即发出请求后 不确定什么时候会执行。中断操作对用户是透明的，用户察觉不到中断的发生。
异常是由应用软件发生不可预知的错
误时发出的，是同步执行，即异常发生后会立即执行。异常的处理有两种第一种是发生了某些错误，这样操作系统会直接杀死该程序。第二种是由于操作系统未达成某些条件而发生异常，这样操作系统会在处理完成后重新执行这条异常指令。
系统调用是应用程序主动发出的请求，调用操作系统的函数完成作业。调用是同步过程，操作系统返回结果给应用程序是异步过程。也就是说操作系统处理完之后会以异步的形式通知应用程序我已经处理完了，至于应用程序什么时候响应该通知是未知的。
中断和异常都有表，称为中断表和异常表，表中代 和处理地址对应存储。在发生中断和异常时，会去查表然后调到处理地址。
中断在跳转之前先会添加中断标记，然后会保存当前状态，最后处理完中断会恢复现场，清除中断标记，继续执行。
系统调用，Win32API用于Windows，posix用于Linux。JAVA语言调用API不算系统调用，在虚拟机底层才系统调用。程序在用户态控制权很低，当转到内核态时控制权最高，可以执行任何指令。不同内核有自己的栈，当系统调用时，会有状态的切换和内核栈的建立和切换，所以系统调用的代价远高于函数调用，但是和其安全性相比，是值得的。

操作系统的开销：
①系统调用时会从用户线程切换到内核线程，调用完毕又要切换回用户线程，随之会有堆栈的保存和切换的开销。
②有时候还要传递处理，系统调用不能传递引用，只能进行拷贝。这样代价很高
③应用软件是被操作系统所不信任
的，因此每次调用都会验证参数以防止其恶意破坏。
④需要建立中断/异常/系统调用 与对应服务例程的映射关系的初始化开销。
⑤刷新TLB和cache的开销。

内存管理：

计算机的内存像金字塔，越靠近CPU的地方的内存速度越快，容量越小。
计算机地址空间分为逻辑地址和物理地址。通过编码产生编码地址，然后通过编译器变成逻辑地址，在内存调用时会去查操作系统的表，逻辑地址和物理地址对应表。得到物理地址取出指令然后执行。
外部碎片：程序之间的碎片存储空间。内部碎片：在程序单元中的未使用碎片空间。
连续内存分配：
首次分配，找到可以使用的就直接用。最优分配，找到最合适大小的在使用。最差分配，找到最大的去使用。
压缩式碎片整理：通过拷贝程序改变其地址去整理碎片地址。将中间留有碎片空间的程序通过拷贝放到一起。拷贝只能在程序未执行时发生，还有拷贝的开销也很大。
交换式内存整理：运行程序需要更多的内存，可以抢占等待的程序并且回收他们的内存。但换入换出开销很大。
非连续内存分配：
分段：将地址空间分成一个一个的内存块，分配给每个程序。每一个块的大小是不固定的。
分页：将地址空间分成一个一个页帧，以页帧为单位将每页存储到物理内存的一块中，块和页的大小相等。这样可以将页表放置在任一块中，实现了离散分配。
建立页表提供映射以方便查找。为了降低查询页表的开销，建立TLB快表，将近期常用的地址空间与物理空间的映射关系存放在快表中。当查询地址空间时先查询快表，如果快表中没有，则去访问页表，将查询到的结果存入快表。
由于虚拟内存的大小都很大，根据虚拟内存的大小建立的页表也是巨大的。为了减小页表的大小，可以使用多级页表。
反向页表也物理内存块编 为键，以虚拟内存编 为值，因为往往虚拟内存要大于物理内存。利用反向页表也可以节省空间开销。

虚拟内存：
覆盖技术：按自身逻辑把程序分成几个功能上相对独立的模块，不会同时执行的模块可以共享同一块内存区域，按时间先后运行（分时）。缺点： （1） 设计开销，程序员要划分模块和确定覆盖关系，编程复杂度增加了 （2） 覆盖模块从外存装入内存，实际是以时间来换空间。

描述进程的数据结构：进程控制块，PROCESS control block PCB 。OS给每个进程都维护了一个PCB，保存与之有关的所有状态信息。

PCB进程控制块：进程存在的唯一标识，操作系统管理控制进程运行所用的集合信息，描述进程的基本情况和运行变化的过程。用PCB的生成，回收，组织管理来实现进程的创建，管理和终止。

PCB的组织方式：
链表（便于插删，用于通用的OS）：同一状态的进程PCB为一链表，多个状态对应更多个不同的链表，就绪链表，阻塞链表
索引表（数组，不利于插删，使用于固定数目的进程，相对创建更快捷）：同一状态的归入一个index表（每一个index指向PCB），就绪/阻塞索引表。

5.进程状态：

进程的生命周期：创建，运行，等待，唤醒，结束。

创建：①系统初始化时，创建INIT进程，INIT进程再负责创建其他进程。

②用户请求创建一个新进程。

③正在运行的进程执行了创建进程的系统调用。

运行：OS内核选择一个就绪的进程，让其占用CPU并执行。

等待（阻塞）：①请求并等待系统服务，无法马上开始。

②启动某种操作（和其它进程协调工作），无法马上完成。

③需要的数据没有达到（控制台输入）。

唤醒：需要的资源被满足，等待的事件到达，都意味着可将该进程的PCB插入到就绪队列。因为自身没有占用CPU，所以只能等待OS或者其他进程唤醒。

结束：自愿结束（正常退出，错误退出），强制性退出（致命错误，如访问了不该访问的内存。被操作系统或其他进程杀死）。

6.进程状态变化：

运行态(running)：正在占用CPU并执行。

就绪态(ready)：一切准备工作都已经做好，等待CPU执行。

阻塞态(blocked)：等待资源。

创建态(new)：已创建还没就绪。

结束态(exit)：正在从OS中消失，PCB还在。

线程：

1.线程定义：进程中的一条执行流程。

进程=线程+资源管理

资源管理：包括地址空间（代码段，数据段），打开的文件等的资源平台（环境）等 。

一个进程所拥有的线程共用进程的资源。

2.多线程：在进程空间内有多个控制流且执行流程不一样，有各自独立的寄存器和堆栈，但共享代码段，数据段，资源。

3.线程与进程的比较：

①进程是资源分配单元（内存，打开的文件，访问的 络等），线程是CPU调度单位。

②进程拥有一个完整的资源平台，而线程只独享必不可少的资源（寄存器，栈）

③线程同样具有就绪，阻塞和执行三种基本状态和转换关系。

④线程能减少并发执行的时空开销：
线程的创建时间、终止时间、同一进程内线程的切换时间都更短，因为进程要创建一些对内存和打开的文件的管理信息，而线程可以直接用所属的进程的信息，因为同一进程内的线程有同一个地址空间，同一个页表，所有信息可以重用，无失效处理。而进程要切页表，开销大，访问的地址空间不一样，cache，TLB等硬件信息的访问开销大。另外线程的数据传递不用通过内核，直接通过内存地址可以访问到，效率很高。

4.线程的三种实现方式：

①用户线程:在用户空间实现，OS看不到，由应用程序的用户线程库来管理。用户线程和内核线程间，可以是一对一，一对多，多对多的关系。

优点：开销小，调度灵活，便于管理。

缺点：一个线程挂了，整个进程都会停。

②内核线程，OS内核来完成线程的创建终止和管理。OS的调度单位不再是进程而是线程。进程主要完成资源的管理。缺点：开销太大，每次切换都要完成一次用户态到内核态的变化。

③轻量级进程：内核支持的用户线程。一个进程有一个或多个轻量级进程，每个轻量级进程由一个单独的内核线程来支持。

CPU调度**：

1.批处理系统调度算法：

重要指标(吞吐量， 周转时间， CPU利用率， 公平平衡)

①**非抢占式的先来先服务(FCFS)：**按照进程就绪的先后顺序使用CPU。

特点：公平，实现简单，但是长进程后边的短进程需要等很长时间，这样总体的周转时间会很大。不利于用户体验。

②非抢占式的最短作业优先(SJF)：具有最短完成时间的进程优先执行。

③最短剩余时间优先(SRTN)：SJF抢占式版，即当一个新就绪的进程比当前运行进程具有更短的完成时间，系统抢占当前进程，将当前正在运行的进程挂到就绪态，选择新就绪的进程执行。

特点：改善短作业的周转时间，如果源源不断有短任务到来，可能使长的 任务长时间得不到运行，产生饥饿现象。

④非抢占式的最高响应比优先(HRRN)：计算出每个进程的响应比R，之后总是选择R最高的进程执行。

响应比R = （等待时间+ 执行时间） / 执行时间(预估)

2.交互系统中采用的调度算法：

重要指标（响应时间， 公平平衡）

①时间片轮转调度算法：每个进程被分配一个时间片，允许该进程在该时间段运行。如果在时间片结束时该进程还在运行，则挂到就绪态并将CPU分配给另一个进程。如果该进程在时间时间片结束前阻塞或结束，则CPU立即进行切换。

• 当时间片太长时，其降级为FCFS算法，引起对短的交互请求响应时间长。

• 当时间片太短时，会导致频繁切换进程，浪费CPU时间。

• 通常选择为20ms~50ms。

  ②虚拟轮转法：

• 主要基于时间片轮转法进行改进，解决在CPU调度中对于I/O密集型进程的不友好。

• 其设置了一个辅助队列，对于I/O密集型进程执行完一个时间片后，则放进辅助队列，CPU调度时总是先检查辅助队列中是否村在完成I/O操作的进程。

• 如果不为空总是优先调度辅助队列里的进程，直到为空，才调度就绪队列的进程。

③**最高优先级调度算法:**选择优先级最高的进程优先执行。

• 优先级可以静态不变，也可以动态调整。
• 优先数决定优先级
• 就绪队列可按照优先级组织
• 实现简单，但不公平，可能导致优先级低的进程产生饥饿现象
• 可能产生优先级反转问题(基于优先级的抢占式算法)，即一个低优先级进程持有一个高优先级进程所需要的资源，使得高优先级进程等待低优先级进程运行。

④多级反馈队列调度算法：

• 设置多个就绪队列，并为各队列赋予不同的优先级。
• 第一个队列的优先级最高，依次递减。对于各个队列进程执行时间片的大小也不同，优先级越高的队列，分配到的时间片越少。
• 当第一级队列为空时，再第二级队列进行调度，依次类推，各级队列按照时间片轮转方式进行调度。
• 当一个进程创建后，首先把它放入第一队列的队尾。按照FCFS原则排队等待调度。当轮到该进程执行时，如果它在该时间片完成，便可准备撤离系统，如果第一个时间片结束时尚未完成，则将该进程转入第二队列的队尾，再同样的按照FCFS等待调度执行。

⑤**公平共享调度算法(FFS)：**多用户共享一台计算机，每个用户的进程是不同的，在用户级别公平调度。

例如：linux的CFS：定义了一种新的模型，它给cfs_rq（cfs的run queue）中的每一个进程安排一个虚拟时钟，vruntime。如果一个进程得以执行，随着时间的增长（也就是一个个tick的到来），其vruntime将不断增大。没有得到执行的进程vruntime不变。
而调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同[优先级]的进程，优先级高的进程vruntime增长得慢，以至于它可能得到更多的运行机会。

linux内核分析——CFS（完全公平调度算法）

3.实时系统调度算法：

正确性依赖于其时间和功能两方面的一种操作系统。

性能指标(时间约束的及时性， 速度和平均性能相对不重要)

1.强实时系统：需要在保证的时间内完成重要的任务，必须完成

2.软实时系统：要求重要的进程的优先级更高，尽量完成，并非必须

①速率单调调度(RM)：

• 最佳静态优先级调度
• 通过周期安排优先级
• 周期越短优先级越高
• 执行周期最短的任务

②最早期限调度(EDF)：

• 最佳的动态优先级调度
• Deadline越早优先级越高
• 执行Deadline最早的任务

同步的一些概念：

原子操作(atomic operation)：只一次不存在任何中断或失败的执行，要么成功要么没执行。实际操作往往不是原子操作，甚至单个机器指令都不一定是原子的。

临界区(critical section)：进程中访问共享资源的代码区域，当另一个进程处于相应代码区时便不会执行。

互斥(mutual exclusion) ： 任意时刻只能有一个进程进入临界区访问。当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区，并访问任何相同的共享资源。

死锁(Dead lock): 多个进程互相等待完成特定任务而导致均无法完成自身任务。

饥饿(starvation)： 一个可执行的进程长期等待执行，被调度器持续忽略。

临界区的特点：

• 互斥：同一时间临界区中最多存在一个进程。

• progress：如果一个线程想要进入临界区，那么它最终会成功。

• 有限等待：如果一个线程i处于入口区，那么在i的请求被接受之前，其他进程进入临界区的时间是有限制的。

• 无忙等待(可选)：如果一个进程在等待进入临界区，那么在它可以进入之前可以被挂起。

  **三种满足性能的方法：**禁用硬件中断，基于软件，更高级的抽象。

  1. 禁用硬件中断：没有中断，就没有进程上下文切换，没有并发。减少不确定性，进入临界区禁用中断，退出后再开启。

     问题: ①一旦禁用中断，线程将无法停止。整个系统都会为你停下来，可能导致其他线程处于饥饿。

     ②要是临界区太长，无法限制响应中断所需的时间，可能有硬件影响。一般都用于短的临界区。

     ③多CPU下存在问题。一个CPU只能屏蔽自身，其余CPU任然可以产生中断。

     2.基于软件：共享数据项。

     Peterson算法：

     Bakery算法：N个进程的临界区。

     • 进入临界区之前，进程接受一个数字
     • 得到的数字最小的进入临界区
     • 如果进程Pi和Pj收到相同的数字，那么如果i < j，Pi先进入临界区，否则Pj先进入临界区
     • 编 方案总是按照枚举的增加顺序生成数字

     **问题：**复杂：需要共享数据。

     耗资源：需要忙等，浪费CPU。

     没有硬件保证的情况下，没有真正的软件解决方案。

  3.基于硬件原子操作的高层抽象实现：

  硬件提供了一些原语，像中断禁用，原子操作指令等。

  操作系统提供更高级的编程抽象来简化并行编程，例如：锁，信 量。

锁是一个抽象的数据结构。是一个二进制状态(锁定/解锁)。

Lock::Acquire() – 锁被释放前一直等待，然后得到锁。

Lock::Release() – 释放锁，唤醒任何等待的进程。

被封装的原子操作：

①Test-and-Set 测试和置位

• 从内存中读取值

• 测试该值是否为1(然后返回真或假)

• 内存值设为1

  实现机理：

  举例子：

  ②exchange 交换

交换内存中的两个值。

实现机理：

举例子：

实现简单，易扩展到多临界区，开销小，适用于单处理器或共享主存的多处理器中任意数量的进程。广泛使用。

包含了一系列的共享变量，以及针对这些变量的操作的函数的组合/模块

• 一个锁：指定临界区，确保互斥性；

• 0或者多个条件变量：等待/通知信 量用于管理并发访问共享数据

由于信 量的操作分散，难以控制，读写和维护都很困难。因此就提出了一种集中式同步进程——管程。管程将共享变量和对他们的操作都集中在一个模块中，操作系统或并发程序就是由这样的模块构成。

特征：

1. 模块化。管程是一个基本程序单位，可以单独编译。
2. 抽象数据类型。管程中不仅有数据，还有对数据的操作。
3. 信息掩蔽。管程外可以调用管程内定义的一些函数，但函数的具体实现对外不可见。

同一时刻只能有一个线程访问管程，因此需要锁机制保证其互斥性。获取锁后进入执行。管程中有许多共享变量和资源，执行过程中某个条件得不到满足，就将该线程挂起到该共享变量维持的队列中等待，并且将锁释放掉。别的线程得到锁继续访问，当条件满足之后被唤醒继续执行。

死锁

死锁：一组阻塞的进程（两个或多个），持有一种资源，等待获取另一个进程所占有的资源，而导致谁都无法执行。

**死锁的特征：**四个的必要条件

• 互斥
• 持有并等待
• 无抢占，资源只能被进程自愿释放
• 循环等待，形成闭环

死锁处理办法：

• Deadlock Prevention （死锁预防）

  打破死锁出现的条件：

  1. 互斥：占用非共享资源 会增加不确定性 不推荐
  2. 占用并等待：保证当一个进程请求资源时，不持有任何其他的资源 all or nothing 需要进程请求并分配其所有资源，资源利用率低，可能饥饿
  3. 无抢占：允许抢占占有某些资源的进程
  4. 循环等待：对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请，会出现资源利用不够

• Deadlock Avoidance （死锁避免）

  当进程运行过程中，根据申请资源的情况判断会不会死锁，如果会就不给资源

  银行家算法：

  进程数量n，资源类型数量m

  Max 总需求量 n*m矩阵 Max[i, j] = k表示进程Pi最多需要资源类型Rj的数量为k

  Available 剩余空闲量 长度为m的向量，如果available[j]=k 则有k个类型Rj的资源实例可用
  Allocation 已分配量 n*m矩阵 allocation[I, j]=k 进程Pi已经分配了资源类型Rj的k个实例

  Need 未来需要量 n*m矩阵 need[i, j]=k 进程Pi可能需要资源类型Rj的k个实例

  Max[i, j]=need[I,j]+allocation[i,j]

  

  寻找Need比Available 小的线程，执行完之后释放其Allocation 。

• Deadlock Detection （死锁检测）

• Recovery from Deadlock （死锁恢复）

  通过杀死所有死锁进程，在一个时间内终止一个进程直到死锁消除等方式完成，都干扰了进程的正常运行，都有强制性。
  多数情况下，就是重启

进程间通信IPC(Inter Process Communication)

直接通信：

1. 进程必须正确的命名对方
   • send( P, message) – 发送信息到进程P
   • receive(Q, message)-从进程Q接收消息
2. 通信链路的属性
   • 自动建立链路
   • 一条链路恰好对应一对通信进程
   • 每对进程之间只有一个链接存在
   • 链接可以是单向的，但通常为双向的

间接通信：为了实现间接通信，要发送到共享区，发送方和接收方都不关注具体的另一方是谁

1. 定向从消息队列接收消息：
   • 每个消息队列都有一个唯一的ID
   • 只有他们共享了一个消息队列，进程才能通信
2. 通信链路的属性：
   • 只有进程共享一个共同的消息队列，才建立链路
   • 链接可以与许多进程相关联
   • 每对进程可以共享多个通信链路
   • 连接可以是单向或者双向
3. 操作：
   • 建立一个新的消息队列
   • 通过消息队列发送和接收消息
   • 销毁消息队列
4. 原语的定义如下：
   • send(A, message) – 发送消息到队列A
   • receive(A, message) – 从队列A接受消息

IPC的常用手段：信 ，管道，消息队列，共享内存

1. 信 ：

   • 硬件中断interrupt，信 是软件中断，通知有事件要处理 ，应用程序会catch，默认停下来处理信 ，特殊处理函数

   • examples: SIGFPE, SIGKILL, SIGUSRI, SIGSTOP, SIGCONT

2. 接收到信 时会发生什么

   • catch : 指定信 处理函数被调用
   • ignore: 依靠操作系统的默认操作 ， 如abort, memory dump, suspend or resume process
   • mask: 闭塞信 因此不会传送（可能是暂时的，当处理同样类型的信 ）

3. 不足：不能传输要交换的任何数据

4. 效率很高，异步。一般处理完后会回到被打断的进程

管道：用于数据交换，与信 不同。理解为内存中的一个buffer

消息队列： 管道必须有父进程，数据是字节流，没有数据结构。消息队列可以多个不相干的进程来传递数据，而且message作为一个字节序列存储，message queues是消息数组。是一个有意义的结构化

共享内存： 直接的方式。不用系统调用send&receive，数据量最大，最快。