操作系统

(参照清华——操作系统课程)：

os：对硬件的管理和控制 本课程着重对kernel层的研究

Chapter1 概述

什么是OS？

CPU —–> 进程

磁盘 —–> 文件

内存 —–> 地址空间

用户角度：
  • 管理应用程序
  • 为应用程序提供服务
  • 杀死应用程序
资源角度：
  • 资源管理
  • 管理外设、分配资源

Kernel层内部组件：

  • CPU调度器
  • 物理内存管理
  • 虚拟内存管理
  • 文件系统管理
  • 中断处理与设备驱动

OS Kernel的特征：

  • 并发

    • 计算机系统中同时存在多个运行的程序，需要OS管理和调度

  • 共享

    • 互斥共享

  • 虚拟

    • 利用多道程序设计技术让每个用户都觉得有一个计算机专门为他服务。

  • 异步

    • 程序的执行不是一贯到底，而是走走停停，向前推进的速度不可预知
    • 只要运行环境相同，OS需要保证程序的运行结果也相同

Chapter2 操作系统基础操作

2.1 操作系统的启动

开机顺序：

​ 电脑开机后，将先执行bootstrap program程序(引导程序)，引导程序一般位于计算机的固件中，由它初始化系统的内核以及各个组件。

2.2 中断、异常和系统调用

中断(from 外设)

  • 来自不同的硬件设备的计时器和网络的中断

  • 异步

  • 对用户应用程序是透明的

中断的处理过程：
硬件：
  • 设置中断标记[CPU初始化]
    1. 将内部事件、外部事件设置中断标记
    1. CPU通过标记获得中断事件的ID(凭借中断向量表)

软件：
  • 保存当前处理状态
  • 中断服务程序处理
  • 清除中断标记
  • 恢复之前保存的处理状态

异常(from 不良的应用程序)

  • 应用程序产生，由于非法指令或者其他坏的处理状态

  • 同步

  • 杀死或重新执行意想不到的应用程序指令

异常的处理过程：
  • 保存现场
  • 异常处理
    • 杀死异常程序
    • 或者 重新执行异常命令
  • 恢复现场

系统调用(from 应用程序)

  • 应用程序主动向OS发送服务请求

  • 同步或异步

  • 等待后继续执行

系统调用的处理过程：

​ 调用系统函数 如printf()后，会触发系统调用，在屏幕上打印

将OS能提供的系统调用进行某种集成，形成各色各样的API供开发人员使用

  • Win32 API 用于Windows

  • POSIX API 用于 POSIX-based systems(such as: UNIX、LINUX、MAX OS X)

  • Java API 用于 JVM

    1. 通常情况下，每个系统调用有自己的序号，系统调用接口根据这些序号维护表的索引
    2. 系统调用接口 调用内核态中的系统调用，返回系统调用的状态和结果(其返回值)
    3. 用户不需要知道系统调用是如何实现的，只需要获取各个API的作用即可；操作系统接口的细节大部分隐藏在API中

🌟用户从系统调用的库中调用系统调用接口，在调用系统调用接口时，会触发一个从用户态->内核态的转换，执行内核态中的系统调用。

系统调用的开销会大于普通的函数调用，因为：

​ 系统调用会从用户态切换到内核态，需要两次建立函数空间，而函数调用只有自己唯一的栈空间

跨越操作系统边界的开销(中断、异常、系统调用)

在执行时间上开销超过应用程序

开销体现于：

  • 建立中断/异常/系统调用号 与 对应服务例程映射关系的初始化开销(因为你跨越了OS边界，不能把原本的状态带过去，所以需要一张映射表，由编号找到你需要做的事)
  • 建立内核堆栈(因为在内核态进行操作，需要在内核态建立变量存储空间)
  • 验证参数(内核态不信任用户态，需要进行验证)
  • 内核态映射到用户态的地址空间(内核态产生的数据需要拷贝回用户态)
  • 内核态独立地址空间(TLB)

这些开销都是值得的，它们保证了OS的操作安全、可靠！

Chapter3 连续式内存分配

计算机体系结构及内存分层体系

分层……计组里都学过

操作系统的内存管理方面的四个目标

  • 抽象
    • 逻辑地址空间
  • 保护
    • 独立地址空间
  • 共享
    • 访问相同内存
  • 虚拟化
    • 更多的地址空间

地址空间与地址生成

1.地址空间定义

​ 物理地址空间：硬件支持的地址空间

​ 逻辑地址空间：一个运行的程序所拥有的内存范围

2.地址生成

​ 逻辑地址生成：从变量的符号，通过一系列操作(编译、汇编、链接、载入)变为逻辑地址

​ 物理地址生成：已知逻辑地址，通过硬件MMU将逻辑地址映射到物理地址

3.地址安全检查

​ OS记录每一个程序能够访问的地址空间(开始位置和大小)

​ 这个表由OS维护，CPU要执行某个程序时，OS检查该程序的地址是否满足表中的限制(不与已占用空间冲突)，能满足则正常执行；否则CPU产生内存访问异常，让OS进行进一步处理。

连续内存分配：内存碎片与分区的动态分配

内存碎片问题

空闲内存不能被利用

  • 外部碎片

在**分配单元间**的未使用内存

  • 内部碎片

在**分配单元中**的未使用内存

分区的动态分配

常见分配策略
第一适配

​ 放在第一个能够满足需求的空闲块中

​ 简单实现：

  • 对空闲块列表按地址排序
  • 分配到第一个合适的分区
  • 回收时进行检查，看看自由分区能不能与相邻的空闲分区合并
    • 缺点：产生外部碎片、不确定性
最佳适配

​ 在能放下空闲块的分区中，寻找最小的分区（避免了分割大空闲块，为了最小化外部碎片产生的尺寸）

​ 简单实现：

  • 按尺寸排列空闲块列表
  • 分配时需要寻找最合适的分区
  • 回收时进行检查，看看自由分区能不能与相邻的空闲分区合并
    • 优势：当大部分分配是小尺寸时十分有效
    • 劣势：会产生外部碎片，重分配(回收)慢，容易产生很多很小的内部碎片

最差适配

​ 在能放下空闲块的分区中，寻找最大的分区（为了避免有太多微小的碎片）

​ 简单实现：

  • 按尺寸排列空闲块列表(从大到小)
  • 分配时需要寻找最合适的分区(找最大的，所以找非常快)
  • 回收时进行检查，看看自由分区能不能与相邻的空闲分区合并
    • 优势：分配中等大小的块效果最好
    • 劣势：重分配慢、外部碎片、每次都使用大空闲块可能导致大分区无法被分配

压缩式碎片整理

​ 在程序处于等待状态时，将其进行移动，从而消除外部碎片————目的是消除外部碎片

交换式碎片整理

​ 如果运行中的程序需要比较大的内存空间，那么可以让它抢占等待中的程序的内存空间(先将占用了内存空间的等待中的程序转存到硬盘中)

​ 问题：将哪个等待中的程序换出呢？什么时候执行换入、换出的操作呢？

Chapter4 非连续式内存分配

连续内存分配的缺点：

​ 分配给一个程序的物理内存是连续的、内存利用率较低、有外、内部碎片的问题

非连续内存分配的优点：

  • 更好的内存利用和管理
  • 允许共享代码与数据
  • 支持动态加载和动态链接

非连续内存分配的缺点：

  • 如何建立虚拟地址与物理地址之间的联系
    • 硬件方案
      • 分段 (分段和分页的区别：段的大小可以改变、页的大小是固定的)
      • 分页
    • 软件方案(开销大，不展开讨论)

分段

程序的分段地址空间

​ 有堆、栈、各种部分 逻辑空间是连续的，但实际上物理地址空间毫无关联(跟分配策略有关)

分段寻址方案

段访问机制：

​ s + addr （段号 + 段内偏移） 多地址空间

​ s与addr一起存 单地址空间

​ s通过 segment table(段表) 根据段号 查询 段所对应的物理地址，再加上偏移量就 = 物理地址 段表由OS建立

分页

  • 逻辑空间：页 物理页面：帧
  • 物理内存被分成大小相同的帧

一个程序的逻辑地址空间被划分为大小相等的页

​ 🌟(页内偏移大小=帧内偏移大小；页号大小 != 帧号大小{在页表中，通过页号得到帧号})

  • 页映射到帧
  • 页是连续的虚拟内存
  • 帧是非连续的物理内存
  • 不是所有的页都有对应的帧

分页地址空间

​ 帧的物理地址=帧号 + 帧内偏移

页寻址方案——页表

分页机制性能问题：
访问一个内存单元需要2次内存访问

​ 1.用于获取页表项

​ 2.根据获得的页表项访问数据

页表可能非常大
如何解决？
缓存

​ TLB：缓存近期访问的页-帧转换表项(TLB存于Cache中)

间接访问

​ 二级、多级页表：多次寻址速度降低，但是缩减了页表(时间换空间，但是可以通过TLB提速！)

反向页表(说实话没听明白，先挖个坑，回顾时填上)

​ 程序的地址空间很大时，逻辑地址空间会大于内存的物理地址空间

​ 这时 我们不是让页表与逻辑地址空间的大小相对应，而是让页表与物理地址空间的大小相对应

​ 利：

  • 转换表的大小相对于物理内存来说很小

  • 转换表的大小跟逻辑地址空间的大小无关

    弊：

  • 需要的信息对调了，即现在只能根据帧号找到页号

  • 如何转换回来？即如何根据页号找到帧号？

  • 需要在反向页表中搜索想要的页号

1
2
3
4
5
6
7
/*如何实现呢？
*		对页号做hash计算，为了在“帧表”中获取对应的帧号
*		页i被放置在“帧表”中f(i)的位置 #f为hash函数
*			为了查找页i，执行以下操作：
*				对于页i，计算f(i)并使用它作为页寄存器表的索引，获取对应的页寄存器
*				检查寄存器标签是否包含i，如果包含，则代表成功获取帧号，否则失败。
*/

Chapter5 虚拟内存

覆盖技术：

​ 为了在较小的内存中运行较大的程序，常用于多道程序系统，与分区存储管理配合使用

原理:

目标：把程序按照其自身逻辑结构，划分为若干个功能上相对独立的程序模块那些不会同时执行的模块共享同一块内存区域，按时间先后来运行。

  • 必要部分 (常用功能)的代码和数据常驻内存

  • 可选部分(不常用功能)在其他程序模块中实现,平时存放在外存中，在需要用到时才装入内存;

    • 不存在调用关系的模块不必同时装入到内存，从而可以相互覆盖,即这些模块共用一个分区。

缺点：

  • 程序的划分复杂，费时费力
  • 经常性的从外存读取数据，实际上是时间换空间
  • 需要程序员自己把整个程序划分为若干个小的功能模块，并确定各个模块之间的覆盖关系，增加了程序员的负担;

交换技术：

​ 多道程序在内存中时,让正在运行的程序或需要运行的程序获得更多的内存资源。

原理:

  • ​ 可将暂时不能运行的程序送到外存，从而获得空闲内存空间。
  • ​ 操作系统把一个进程的整个地址空间的内容保存到外存中(换出swap out)，而将外存中的某个进程的地址空间读入到内存中(换入swap in)。换入换出内容的大小为整个程序的地址空间。

问题：

  • 何时交换？
    • 只有当内存不够或者有不够的风险时进行交换
  • 交换区的大小
    • 必须足够存放用户进程中所有内存映像的拷贝
    • 必须能对这些内存映像进行直接存取
  • 交换技术:以进程作为交换的单位，需要把进程的整个地址空间都换进换出，增加了处理器的开销。

覆盖与交换的比较：

覆盖技术只能发生在那些相互之间没有调用关系的程序模块之间。因此程序员必须给出程序内的各个模块之间的逻辑覆盖结构。(移动的最小粒度为一个程序)

交换技术是以在内存中的程序大小为单位来进行的，它不需要程序员给出各个模块之间的逻辑覆盖结构。(移动的最小粒度为程序的一个子模块)

换言之，交换发生在内存中程序与管理程序或操作系统之间，而覆盖则发生在运行程序的内部。

虚存技术：

像覆盖技术那样，不是把程序的所有内容都放在内存中，因而能够运行比当前的空闲内存空间还要大的程序。但做得更好，由操作系统自动来完成，无须程序员的干涉;

像交换技术那样，能够实现进程在内存与外存之间的交换，因而获得更多的空闲内存空间。但做得更好，只对进程的部分内容在内存和外存之间进行交换。

程序的局部性原理(principle of locality):

​ 指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。这可以表现为:

  • 时间局部性:一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内;
  • 空间局部性:当前指令和邻近的几条指令，当前访问的数据和邻近的几个数据都集中在一个较小区域内。

程序的局部性原理表明，从理论上来说，虚拟存储技术是能够实现的，而且在实现了以后应该是能够取得一个满意的效果的。

基本概念：

​ 可以在页式或段式内存管理的基础上实现

  • 在装入程序时，不必将其全部装入到内存，而只需将当前需要执行的部分页面或段装入到内存，就可让程序开始执行；

  • 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；

  • 另一方面，操作系统将内存中暂时不使用的页面或段调出保存在外存上，从而腾出更多空闲空间存放将要装入的程序以及将要调入的页面或段。

基本特征：

  • 大的用户空间：通过把物理内存与外存相结合，提供给用户的虚拟内存空间通常大于实际的物理内存，即实现了这两者的分离。如32位的虚拟地址理论上可以访问4GB，而可能计算机上仅 有256M的物理内存，但硬盘容量大于4GB。

  • 部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虛拟地址空间进行的：

  • 不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续。

虚拟页式内存管理：

  • 大部分虚拟存储系统都采用虚拟页式存储管理技术，即在页式存储管理的基础上，增加请求调页和页面置换功能。

  • 基本思路：

    • 当一个用户程序要调入内存运行时，不是将该程序的所有页面都装入内存，而是只装入部分的页面，就可启动程序运行。
    • 在运行的过程中，如果发现要运行的程序或要访问数据不在内存，则向系统发出缺页中断请求，系统在处理这个中断时，将外存中相应的页面调入内存，使得该程序能够继续运行。
页表表项需要增加：
  1. 驻留位：1表示该页在内存中；0表示在外存中
  2. 保护位：表示允许对该页做何种类型的访问，如只读、可读写、可执行等
  3. 修改位：表明此页在内存中是否被修改过。若修改过，在回收此页时需要把这个页的内容同步到外存。
  4. 访问位：如果最近被访问过，置为1；用于页面置换算法
缺页中断处理过程：

  1. 如果在内存中有空闲的物理页面，则分配一物理页帧f，然后转第4步：否则转第2步：

  2. 采用某种页面置换算法，选择一个将被替换的物理页帧f，它所对应的逻辑页为q。如果该页在内存期间被修改过，则需把它写回外存；

  3. 对q所对应的页表项进行修改，把驻留位置为0；

  4. 将需要访问的页p裝入到物理页面f当中；

  5. 修改p所对应的页表项的内容，把驻留位置为1，把物理页帧号置为f

  6. 重新运行被中断的指令。

后备存储 Backing Store
概念：

  • 一个虚拟地址空间的页面可以被映射到一个文件（在二级存储中）中的某个位置

  • 代码段：映射到可执行二进制文件

  • 动态加载的共享库程序段：映射到动态调用的库文件

  • 其它段：可能被映射到交换文件(swap file)

​ 在何处保存未被映射的页？

  • 能够简单地识别在二级存储器中的页

  • 交换空间（磁盘或者文件）：特殊格式，用于存储末被映射的页面

Chapter6 页面置换算法

局部页面置换算法

功能与目标

功能：缺页，但主存满了，换谁出去？

目标：尽可能减少页面更换的次数，(通常在局部性原理指导下依据过去的统计数据进行预测)

<页面锁定>:有些页面必须常驻于内存中，不应参与页面置换算法。(通过在页表中添加 ‘锁定标志位,lock bit’ 判断)

6.1最优页面置换算法

​ 是一种理想情况下的页面置换算法, 该算法使用的前提是OS提前知道接下来要访问的页面，换出近期最不会被用到的页面。

无实际意义，但可以用于评价别的算法的性能，作为一个理想的标杆

6.2FIFO算法

系统维护一个页面的链表，每次淘汰驻留时间最长的页面(一个已经在链表中的页面再次被使用并不会刷新该页面的驻留时间，而是继续按原来的计时)

性能较差，调出的页面可能是经常被调用的页面，并且有**Belady现象**

6.3最近最久未使用算法(LRU)

当缺页中断发生时，选择淘汰最久未使用的页面（根据历史，推测未来，依据程序的访问具有局部性

​ LRU算法需要记录每个页面使用时间的先后顺序，开销比较大

两种可能的实现方法：

  • 维护一个链表，运行新页面：则放在链表头；运行链表中出现过的页面：将该结点移动到链表头部；若要淘汰页面，则删除队尾的页面。
  • 维护一个栈，刚使用的页面放在栈顶，如果栈中已经有该页面则还需要将栈中记录删去，若要淘汰页面，则删除栈底部的页面(ps:没啥区别啊)

6.4时钟页面置换算法

  • clock页面置换算法，LRU的近似，是对FIFO的一种改进：
基本思路：

  • 需要用到页表项当中的访问位，当一个页面被装入内存时，把该位初始化为0。然后如果这个页面被访问（读/写)，则把该位置为1;

  • 把各个页面组织成环形链表（类似钟表面），把指针指向最老的页面（最
    先进来）；

  • 当发生一个缺页中断时，考察指针所指向的最老页面，若它的访问位为0，立即淘汰：若访问位为1，则把该位置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

6.5二次机会法

添加脏位(用于标识有没有被写过)，如果被淘汰的页只被读过，则直接删除；如果该页面被修改过，就需要将更新的数据同步至硬盘。

用访问位、脏位两个位来判断被淘汰的页面，只有都为0的页面才会立即被淘汰，有1的页面会首先失去一个1，幸免于本轮循环。(脏位由1变0时，也需要写回硬盘)

给修改过的页面更多的机会留在主存中(其实只针对一种情况：访问位、脏位都为1时，页面被循环轮到后会先把访问位置为0，而不是改变脏位，这样就相当于给这个页面多一条命！)——通过减少写回硬盘的次数来降低开销

6.6最不常用法

Least frequency used LFU:

基本思路：

​ 当一个缺页中断产生时，选择被访问次数最少的页面淘汰

​ 给主存中的每个页都安排一个计数器，淘汰计数器值最小的页面

缺点：计数器开销大

6.7Belady现象

​ 在采用FIFO算法时，有时会出现分配的物理页面数增加，缺页率反而提高的现象；

image-20230605214433150 image-20230605214507498

6.8局部页面替换算法的问题、工作集模型

工作集：一个进程当前正在使用的逻辑页面集合，可以用一个二元函数w(t，∆)来表示

  • t是当前的执行时刻；

  • ∆称为工作集窗口 (working set window），即一个定长的页面访问的时同窗口：

  • w(t，∆)一在当前时刻 t 之前的 ∆时间窗口当中的所有页面所组成的集合(随着 t 的变化，该集合也在不断地变化）

  • |w(t，∆）|指工作集的大小，即页面数目。

常驻集：是指在当前时刻，进程实际驻留在内存当中的页面集合。

总结：

  1. 工作集是进程在运行过程中固有的性质，而常驻集取决于系统分配给进程的物理页面数日，以及所采用的页面置换算法；

  2. 如果一个进程的整个工作集都在内存当中，即常驻集>=工作集，那么进程将很顺利地运行，而不会造成太多的缺页中断（直到工作集发生剧烈变动，从而过渡到另一个状态）

  3. 当进程常驻集的大小达到某个数目之后，再给它分配更多的物理页面，缺页率也不会明显下降。

全局页面置换算法：

1.工作集页面置换算法

​ 如果页面不在工作集中，那么即使没有发生缺页中断，也会把该页面换出。

​ 每次都看看自己的常驻集和工作集，常驻集里有，但工作集中没有的页面都会被移除

2.缺页率页面置换算法

可变分配策路：

​ 常驻集大小可变，例如：每个进程在刚开始运行的时候，先根据程序大小给它分配一定数目的物理页面，然后在进程运行过程中，再动态地调整常驻集的大小。

  • 可采用全局页面置换的方式。当发生一个缺页中断时，被置换的页面可以是在其它进程当中，各个并发进程竞争地使用物理页面。
  • 优缺点：性能较好。但增加了系统开销。
  • 具体实现：可以使用缺页率算法 (PPF, page fault freguency)来动态调整常驻集的大小。

🌟如何动态地调整常驻集的大小？

​ 设置一个阈值k，将本次发生缺页的下标 - 上次发生缺页的下标 与 k 进行比较，

  • 如果k比较大，说明中断异常出现的太频繁了，直接将缺失页加入到工作集中(扩大工作集，降低缺页概率)

  • 如果k比较小，说明不怎么出现中断，那么执行下述操作：将工作集中不在[t_last, t_current]区间内出现的页面移除 (t_last, t_current指上一次、这次出现中断异常的时间下标)

抖动问题：

  • 如果分配给一个进程的物理页面太少，不能包含整个的工作集，即常驻集＜ 工作集，那么进程将会造成很多的缺页中断，需要频繁地在内存与外存之间替换页面，从而使进程的运行速度变得很慢，我们把这种狀态称为 “抖动”。
  • 产生抖动的原因：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，导致缺页率不断上升。所以os要选择一个适当的进程数目和进程需要的帧数，以便在并发水平和缺页率之间达到一个平衡。

抖动问题在一些情况下可以被本地的页面置换算法改善

Chapter7 进程和线程

7.1进程(process)的描述

进程定义：

​ 一个具有一定功能的程序在一个数据集合上的一次动态执行的过程

进程组成：

包含了一个正在运行的程序的所有状态信息

        1. 程序的代码
        1. 程序处理的数据
        1. 程序计数器的值，指示下一条即将运行的指令
        1. 一组通用的寄存器的当前值，堆、栈
        1. 一组系统资源(如打开的程序)
进程与程序的联系：
  • 程序是产生进程的基础
  • 程序的每次运行构成不同的进程
  • 进程是程序功能的体现
  • 通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。
进程与程序的区别：

  • 进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行，进程有核心态/用户态

  • 进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存

  • 进程与程序的组成不同：进程的组成包括**程序、数据和进程控制块**（即进程状态信息）

进程的特点：

  • 动态性：可动态地创建、结束进程；
  • 并发性：进程可以被独立调度并占用处理机运行；(并发->串、并行->并)
  • 独立性：不同进程的工作不相互影响：
  • 制约性：因访问共享数据/资源或进程间同步而产生制约。

进程控制结构：

​ 程序 = 算法 + 数据结构

​ 描述进程的数据结构：进程控制块(Process Control Block, PCB)

进程控制块：OS管理进程运行所用信息的集合，OS用PCB描述进程的基本情况及运行变化的过程，PCB是进程存在的唯一标志。

PCB中包含的内容：

  1. 进程标识信息。如本进程的标识，本进程的产生者标识(父进程标识)；用户标识。

  2. 处理机状态信息保存区。保存进程的运行现场信息：

    • 用户可见寄存器，用户程序可以使用的数据，地址等寄存器。

    • 控制和状态寄存器，如程序计数器(PC)，程序状态字 (PSW)。

    • 栈指针，过程调用/系统调用/中断处理和返回时需要用到它。

  3. 进程控制信息

  • 调度和状态信息，用于操作系统调度进程并占用处理机使用。

  • 进程间通信信息，为支持进程问的与通信相关的各种标识、信号、信件等，这些信息存在接收方的进程控制块中。

  • 存储管理信息，包含有指向本进程映像存储空间的数据结构。

  • 进程所用资源，说明由进程打开、使用的系统资源，如打开的文件等。

  • 有关数据结构连接信息，进程可以连接到一个进程队列中，或连接到相关的其他进程的PCB。

PCB的组织方式
  • 链表(常用)：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表

各状态的进程形成不同的链表：就绪链表、阻塞链表

  • 索引表：同一状态的进程归入一个index表（由index指向PCB)，多个状态对应多个不同的index表

各状态的进行形成不同的索引表：就绪索引表、阻塞索引表

7.2进程状态

进程生命周期管理

进程创建
引起进程创建的三个主要事件：
    1. 系统初始化时(创建init进程)	
    2. **用户请求**创建一个新进程
    3. 正在运行的**进程执行**了创建进程的系统调用
进程运行
内核选择一个就绪的进程，让它占用处理机并执行
进程等待
以下情况下，进程等待：
  1. 请求并等待系统服务，无法马上完成
  2. 启动某种操作，无法马上完成
  3. 需要的数据没有到达

进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生。

进程唤醒
唤醒进程的原因：
  1. 被阻塞进程需要的资源可被满足
  2. 被阻塞进程等待的事件到达
  3. 将该进程的PCB插入到就绪队列

进程只能被别的进程或操作系统唤醒。

进程结束
在以下四种情形下，进程结束：

  • 正常退出（自愿的）

  • 错误退出（自愿的）

  • 致命错误（强制性的）

  • 被其他进程所杀（强制性的）

进程状态变化模型

进程的三种基本状态：

​ 进程在生命结束前处于且仅处于三种基本状态之一

  • 运行状态(Running)：当一个进程正在处理机上运行时。

  • 就绪状态(Ready)：一个进程获得了除处理机之外的一切所需资源，一旦得到处理机即可运行。

  • 等待状态（又称阻塞状态Blocked)：一个进程正在等待某一事件而暂停运行时。如等待某资源，等待输入/输出完成。

进程其它的基本状态：

  • 创建状态(New)：一个进程正在被创建，还没被转到就绪状态之前的状态。

  • 结束状态(Exit)：一个进程正在从系统中消失时的状态，这是因为进程结束或由于其他原因所导致。

image-20230606110651191

进程挂起模型

进程挂起：进程不占用内存空间，处于挂起状态的进程映像在磁盘上。

挂起状态：
  • 阻塞挂起状态 (Blocked-suspend）：进程在外存并等待某事件的出现；
  • 就绪挂起状态 (Ready-suspend）：进程在外存，但只要进入内存，即可运行；
挂起 (Suspend）：把一个进程从内存转到外存；可能有以下几种情况：

  • 阻塞到阻塞挂起：没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程；

  • 就绪到就绪挂起：当有高优先级阻塞(系统认为会很快就绪的）进程和低优先就绪进程时，系统会选择挂起低优先级就绪进程；

  • 运行到就绪挂起：对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态；

在外存时的状态转换：
  • 阻塞挂起到就绪挂起：当有阻塞挂起进程因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。
解挂/激活 (Activate）：把一个进程从外存转到内存；可能有以下几种情况：
  • 就绪挂起到就绪：没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换；
  • 阻塞挂起到阻塞：当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程；
OS如何通过PCB完成进程的调度？
🌟状态队列

  • 由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；

  • 不同的状态分别用不同的队列来表示(就绪队列、各种类型的阻塞队列）；

  • 每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列。

7.3线程

为什么需要线程？

​ 处理并行操作时，如果使用多进程方式，会导致开销巨大(进程占用资源、进程切换占用时间、进程共享数据产生开销)

​ 因此，我们亟需提出一种实体，满足：1）实体之间可以并发运行；2）实体之间共享地址空间

​ 于是 线程 被提出！

什么是线程？

​ ＞进程当中的一条执行流程。

从两个方面来重新理解进程

  • 从资源组合的角度：进程把一组相关的资源组合起来，构成了一个资源平台（环境），包括地址空间（代码段、数据段）、打开的文件等各种资源；
  • 从运行的角度：代码在这个资源平台上的一条执行流程（线程）。
线程的优点：
  • 一个进程中可以同时存在多个线程；
  • 各个线程之间可以并发地执行；
  • 各个线程之间可以共享地址空间和文件等资源。
线程的缺点：
  • 一个线程崩溃，会导致其所属进程的所有线程崩溃。(因为线程间共享数据，因此一个线程的数据错误了，其他线程都要遭殃)
线程所需的资源：
image-20230606161910704
线程与进程的比较

  • 进程是资源分配单位，线程是CPU调度单位；

  • 进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈；

  • 线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系；

  • 线程能减少并发执行的时间和空间开销：

    • 线程的创建时间比进程短；(线程无需创建代码块、数据、文件的管理信息)

    • 线程的终止时间比进程短；(线程无需创建代码块、数据、文件的管理信息)

    • 同一进程内的线程切换时间比进程短；(在同一进程中的线程具有同一个页表，切换时无需切换页表)

    • 由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信；

线程的实现：

​ 三种主要的实现方式：

 1. 用户线程：在用户空间实现
 2. 内核线程：在内核中实现
 3. 轻量级线程：在内核中实现，支持用户线程
🌟用户线程：
image-20230606163157885

OS看不到TCB，只能看到PCB，只知道进程信息，进程中的线程信息由线程库管理。

在用户空间实现的线程机制，它不依赖于操作系统的内核，由一组用户级的线程库函数来完成线程的管理，包括进程的创建、终止、同步和调度等。

用户线程的优点：
  • 由于用户线程的维护由相应进程来完成 （通过线程库函数），不需要操作系统内核了解用户线程的存在，可用于不支持线程技术的多进程操作系统；
  • 每个进程都需要它自己私有的线程控制块（TCB）列表，用来跟踪记录它的各个线程的状态信息 (PC、栈指针、寄存器），TCB由线程库函数来维护；
  • 用户线程的切换也是由线程库函数来完成．无需用户态/ 核心态切换，所以速度特别快；
  • 允许每个进程拥有自定义的线程调度算法。
用户线程的缺点：
  • 阻塞性的系统调用如何实现？如果一个线程发起系统调用而阻塞，则整个进程在等待；(因为OS在内核态中只能管理进程，而不能单独地把进程中的某个线程阻塞)
  • 当一个线程开始运行后，除非它主动地交出CPU的使用权，否则它所在的进程当中的其他线程将无法运行；(同样，因为OS只能管理进程，因为只有OS有管理中断的权利，但是OS看不到线程)
  • 由于时间片分配给进程，故与其它进程比，在多线程执行时，每个线程得到的时间片较少，执行会较慢。
🌟内核线程：

​ image-20230606164400117

TCB也放在内核中

是指在操作系统的内核当中实现的一种线程机制，由操作系统的内核来完成线程的创建、终止和管理。

  • 在支持内核线程的操作系统中，**由内核来维护进程和线程的上下文信息 （PCB和TCB）**；
  • 线程的创建、终止和切换都是通过系统调用/内核函数的方式来进行，由内核来完成，因此系统开销较大；
  • 在一个进程当中，如果某个内核线程发起系统调用而被阳塞，井不会影响其他内核线程的运行：
  • 时间片分配给线程，多线程的进程获得更多CPU时间；
  • Windows NT和windows 2000/xP支持内核线程。
🌟轻量级进程(了解)
image-20230606164824053

7.4上下文切换

​ 停止当前运行进程(从运行状态改变成其他状态）并且调度其他进程（转变成运行状态）

  • 必须在切换之前存储许多部分的进程上下文
  • 必须能够在之后恢复他们，所以进程不能显示它曾经被暂停过
  • 必须快速（上下文转换时非常频繁的）

​ 需要存储什么上下文？

  • 寄存器(PC, SP， …)，CPU状态，……

  • 一些时候可能会费时，所以我们应该尽可能避免

7.5进程控制

创建进程

fork函数：fork函数用于从已经存在的进程中创建一个新的进程。新的进程称为子进程，而原来的进程是父进程。

返回值：子进程中返回0，父进程返回子进程id，出错返回-1

当一个进程调用fork之后，就有两个二进制代码相同的进程。而且它们都运行到相同的地方。但每个进程都将可以开始它们自己的旅程

fork()的简单实现

  • 对子进程分配内存
  • 复制父进程的内存和CPU寄存器到子进程
  • 开销昂贵

在99%的情况下,我们在调用fork()之后调用exec() —依据实际情况得出

  • 在fork()操作中内存复制是没有作用的（因为你fork完后立马去执行新的程序，会把你复制的东西都覆盖了
  • 子进程将可能关闭打开的文件和连接
  • 开销因此是最高的

vfork()

  1. vfork用于创建一个子进程，子进程和父进程共享地址空间。(fork的子进程有独立的地址空间)

  2. vfork保证子进程先运行，在子进程调用exec或exit之后父进程才可能被调度运行。

  • 一个创建进程的系统调用,不需要创建一个同样的内存映像
  • 一些时候称为轻量级fork()
  • 子进程应该几乎立即调用exec()
  • 现在不再使用如果我们使用 copy on write 技术(按需复制，不复制那些会被覆盖的部分，只复制进程创建必须的部分)

加载和执行进程

​ exec()函数：让当前进程执行新的程序

​ exec()调用允许一个进程”加载”一个不同的程序并且在main开始执行(事实上 _start)

​ 它允许一个进程指定参数的数量(argc)和它字符串参数数组(argv)

等待和终止进程

​ wait()系统调用 是被父进程用来等待子进程的结束

  • 一个子进程向父进程返回一个值，所以父进程必须接受这个值并处理

  • wait()系统调用担任这个要求

    • 它使父进程去睡眠来等待子进程的结果

    • 当一个子进程调用exit(的时候，操作系统解锁父进程，并且将通过exit()传递得到的返回值作为wait调用的一个结果(连同子进程的pid一起）如果这里没有子进程存活，wait()立刻返回

    • 当然，如果这里有为父进程的僵尸等待，wait(立即返回其中一个值(并且解除僵尸状态）

  • 进程结束执行之后，它调用exit()

  • 这个系统调用：

    • 将这程序的 “结果” 作为一个参数

    • 关闭所有打开的文件，连接等等

    • 释放内存

    • 释放大部分支持进程的操作系统结构

    • 检查是否父进程是存活着的：

      • 如果是的话。它保留结果的值直到父进程需要它：在这种情况里。进程没有真正
        死亡，但是它进入了僵尸 (zombie/ defunct)状态

      • 如果没有，子进程将被init进程接管，init代替其父进程，释放其所有的数据结构

    • 清理所有等待的僵尸进程

  • 进程终止是最终的垃圾收集（资源回收）

进程状态图：

image-20230606200728246

Chapter8 CPU调度

8.1背景

CPU调度

  • 从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个线程/进程
  • 调度程序：挑选进程/线程的内核函数(通过一些调度策略)
  • 什么时候执行调度？——线程、进程生命周期中状态的转化时，会进行调度

CPU调度时间

​ 满足一条即可：i): 一个进程从运行状态->等待状态; ii):一个进程被终结了

  • 不可抢占：
    • 调度程序必须等待事件结束
  • 可抢占：
    • 调度程序在中断被响应后执行
    • 当前的进程从运行切换到就绪，或者一个进程从等待切换到就绪
    • 当前运行的进程可以被换出

8.2调度准则

调度策略

程序执行模型

​ 程序在CPU突发和I/O中交替

  • 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU
  • 在时间分片机制下，线程可能在结束当前CPU突发前被迫放弃CPU

比较调度算法的准则

1.CPU使用率
  • CPU处于忙状态所占时间的百分比
2.吞吐量
  • 在单位时间内完成的进程数量
3.周转时间
  • 一个进程从初始化到结束，包括所有等待时间所花费的时间
4.等待时间
  • 进程在就绪队列中的总时间
5.响应时间
  • 从一个请求被提交到产生第一次响应所花费的总时间

​ 减少响应时间：及时处理用户的输出并且尽快将输出提供给用户

​ 减少平均响应时间波动：在交互系统中，可预测性比高低差异平均更重要

​ 增加吞吐量：i): 减少开销(操作系统开销，上下文切换) ii):系统资源的高效利用(CPU，I/O设备)、

​ 减少等待时间

​ 低延迟利于系统与用户的交互

​ 即使存在许多交互任务，我们也需要保证吞吐量不受影响

​

吞吐量vs延迟

吞吐量是OS的计算带宽，响应时间是OS的计算延迟

公平的目标

​ 保证每个进程占用相同的CPU时间——会增加平均响应时间(真的要设计成公平的吗？)

8.3调度算法

1.先来先服务(FCFS)

优点：
  • 简单
缺点：
  • 平均等待时间波动较大
  • 花费时间少的任务可能排在花费时间长的任务后面
  • 可能导致I/0和CPU之间的重叠处理
    • CPU密集型进程会导致I/0设备闲置时，I/0密集型进程也在等待

2.短进程优先/短剩余时间优先

有抢占式、非抢占式的两种方案

优点：
  • 最优的平均等待时间
缺点：
  • 可能导致饥饿
    • 连续的短任务流会使长任务饥饿
    • 短任务可用时，任何长任务的CPU时间都会增加平均等待时间
  • 需要预知未来
    • 我们怎么在运行进程之前就提前知道进程要运行多久？
      • 最简单的方法——询问用户，如果用户撒谎，就杀死进程
      • 如果用于不能给出时间，那么OS进行预估(根据之前的记录)

3.最高响应比优先

​ 在2的基础上进行了改进，考虑R ( R = (w + s) / s ) w:等待时间 s:执行时间

优点：
  • 不可抢占
  • 关注进程等待了多长时间
  • 防止无限期推迟
缺点：
  • 需要预知未来
    • 我们怎么在运行进程之前就提前知道进程要运行多久？
      • 最简单的方法——询问用户，如果用户撒谎，就杀死进程
      • 如果用于不能给出时间，那么OS进行预估(根据之前的记录)

4.轮询(RR)

  • RR 花销：额外的上下文切换开销
  • 时间量子太大
    • 等待时间过长
    • 极限情况退化成FCFS
  • 时间量子太小
    • 反应迅速但是切换频繁，开销大
    • 吞吐量由于大量的上下文切换开销受到影响
  • 目标：
    • 选择一个合适的时间量子
    • 经验规则：维持上下文切换开销处于1%以内

——RR的优化

  • 就绪队列被划分成独立的队列：
    • E.g. 前台（交互）, 后台（批处理）
  • 每个队列拥有自己的调度策略
    • E.g. 前台一RR，后台—FCFS
  • 调度必须在队列间进行
    • 固定优先级
    • 先处理前台，然后处理后台
    • 可能导致饥饿
    • 时间切片
      • 每个队列都得到一个确定的能够调度其进程的CPU总时间
      • E.g. 80%给使用RR的前台，20%给使用FCFS的后台

5.多级反馈队列

  • 一个进程可以在不同队列中移动
    • 时间量子大小随优先级级别的增加而增加
    • 如果任务在当前的时间量子中没有完成，则降到下一优先级
优点：
  • CPU密集型任务的优先级下降很快
  • I/O密集型任务停留在高优先级

6.公平共享队列

  • FFS控制用户对系统资源的访问
    • 一些用户组比其他用户组更重要
    • 保证不重要的组无法垄断资源
    • 未使用的资源按照每个组所分配的资源的比例来分配
    • 没有达到资源使用率目标的组获得更高的优先级

8.4实时调度

背景

​ 正确性依赖于时间与功能两方面

​ 需要保证及时性，速度和平均性能没那么重要

  • 强实时系统

    • 需要在保证的时间内完成重要的任务，必须完成

  • 弱实时系统

    • 要求重要的进程的优先级更高，尽量完成，并非必须

  • 硬时限

    • 如果错过了最后期限，可能会发生灾难性或非常严重的后果

    • 必须验证：在最坏的情况下也能够满足时限吗？

    • 保证确定性

  • 软时限

    • 理想情况下，时限应该被最大满足。如果有时限没有被满足，那么就相应地降低要求。

    • 尽最大努力去保证

调度准则

​ 静态、动态优先级调度(在程序执行之前就确定进程的优先级/在程序运行过程中，优先级会不断变化)

8.5多处理器调度

  • 多处理器的CPU调度更加复杂
    • 多个相同的单处理器组成一个多处理器
    • 优点：负载共享
  • 对称多处理器(SMP)
    • 每个处理器运行自己的调度程序
    • 需要在调度程序中同步

8.6优先级反转

​ 现有优先级 T1 < T2 < T3，

T3和T1都需要用到一块共享资源，T3先执行，锁定了共享资源，T1再执行(抢占了T3)，虽然T1优先于T3，但是T3把T1要用到的资源锁住了，所以T1无法执行完毕，因此让T3继续执行，此时让T2再执行，会抢占T3，这时候，T1需要等待T3，T3在等待T2，就出现了优先级反转问题！

解决方案：

  • (当出现资源抢占现象时)低优先级任务继承高优先级任务的优先级
  • 优先级天花板：
    • “资源” 的优先级和 “所有可以锁定该资源的任务中优先级最高的那个任务” 的优先级相同
    • 除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务尝试执行临界区的时候会被阻塞
    • 持有最高优先级上限信号量锁的任务，会继承被该锁所阳塞的任务的优先级

Chapter9 同步

背景：

  • 独立的线程：
    • 不和其他线程共享资源或状态
    • 确定性：一输入状态决定结果
    • 可重现：一 能够重现起始条件，I/0
    • 调度顺序不重要
  • 合作线程：
    • 在多个线程中共享状态
    • 不确定性
    • 不可重现
  • 不确定性和不可重现意味着bug可能是间歇性发生的

进程间合作工作的原因：

  • 进程/线程，计算机/设备需要合作
  • 优点1：共享资源
    • 一台电脑，多个用户
    • 一个银行存款余额，多台ATM机
    • 嵌入式系统（机器人控制：手臂和手的协调）
  • 优点2：加速
    • I/0操作和计算可以重叠
    • 多处理器 一 将程序分成多个部分井行执行
  • 优点3：模块化
    • 将大程序分解成小程序
  • 以编译为例，gcc会调用cpp, cc1, cc2. as, ld，使系统易于扩展

但是进程并发会带来一些问题，接下来我们要对其进行解决

一些概念：

原子操作：

  • 原子操作是指一次不存在任何中断或者失败的执行
    • 该执行成功结束
    • 或者根本没有执行
    • 并且不应该发现任何部分执行的状态
  • 实际上操作往往不是原子的
    • 有些看上去是原子操作，实际上不是
    • 连x++这样的简单语句，实际上是由3条指令构成的
    • 有时候甚至连单条机器指令都不是原子的

Critical section （临界区）

临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域

Mutual exclusion （互斥）

当一个进程处于临界区井访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源

Dead lock （死锁）

两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去

Starvation（饥饿）

一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行

Critical section (临界区）

临界区是指进程中的一段需要访问共享资源井且当另一个进程处于相应代码区域时便不会被执行的代码区域

  • 互斥：同一时间临界区中最多存在一个线程
  • Progress：如果一个线程想要进入临界区，那么它最终会成功
  • 有限等待：如果一个线程i处于入口区，那么在i的请求被接受之前，其他线程进入临界区的时间是有限制的
  • 无忙等待（可选)：如果一个进程在等待进入临界区，那么在它可以进入之前会被挂起

Mutual exclusion（互斥）

当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源

实现对临界区代码的保护

方案1——禁用硬件中断：

  • 没有中断，没有上下文切换，因此没有并发
    • 硬件将中断处理延迟到中断被启用之后
    • 大多数现代计算机体系结构都提供指令来完成
  • 进入临界区
    • 禁用中断
  • 离开临界区
    • 开启中断
缺点：
  • 一旦中断被禁用，线程就无法被停止
    • 整个系统都会为你停下来
    • 可能导致其他线程处于饥饿状态
  • 要是临界区可以任意长怎么办
    • 无法限制响应中断所需的时间(可能存在硬件影响）

​ 要小心使用

  • 一般只能禁止单CPU的中断，那么面对多CPU的情况就无法使 禁用硬件中断失效

方案2——基于软件的解决方案:

  • Dekker算法 (1965）：第一个针对双线程例子的正确解决方案
  • Bakery算法 ( Lamport 1979）：针对n线程的临界区问题解决方案
  • 复杂
    • 需要两个进程间的共享数据项
  • 需要忙等待
    • 浪费CPU时间
  • 没有硬件保证的情况下无真正的软件解决方案
    • Peterson算法需要原子的LOAD和STORE指令

方案3——更高级的抽象：

  • 大多数现代体系结构都提供特殊的原子操作指令
    • 通过特殊的内存访问电路，针对单处理器和多处理器
  • Test-and-Set 测试和置位
    • 从内存中读取值
    • 测试该值是否为1（然后返回真或假）
    • 内存值设置为1
  • 交换exchange
    • 交换内存中的两个值

我们可以通过Test-and-Set 或 exchange 来实现并发线程的管理

优点：
  • 适用于单处理器或者共享主存的多处理器中任意数量的迸程
  • 简单并且容易证明
  • 可以用于支持多临界区
缺点：
  • 忙等待消耗处理器时间
  • 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
  • 死锁
  • 如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并等待临界区

Chapter10 信号量和管程

背景：

  • 并发问题：竞争条件（竞态条件）
    • 多程序并发存在大的问题
  • 同步
    • 多线程共享公共数据的协调执行
    • 包括互斥与条件同步
    • 互斥：在同一时间只有一个线程可以执行临界区
  • 确保同步正确很难？
    • 需要高层次的编程抽象（如：锁）
    • 从底层硬件支持编译

信号量：

  • 是一个整形（sem），有两个原子操作

  • P () : sem 减1，如果sem<0， 等待，否则继续

  • V () ：sem 加1，如果 sem<=0，唤醒一个等待的P

  • 信号量是被保护的变量

    • 初始化完成后，唯一改变一个信号量的值的办法是通过P0和v0
    • 操作必须是原子

  • P () 能够阻塞，V () 不会阻塞

  • 我们假定信号量是 公平的

    • 没有线程被阻塞在P () if V () 被无限频繁调用（对于同一个信号量）
    • 在实践中，FIFO经常被使用

  • 两种类型信号量

    • 二进制信号量：可以是0或1
    • 一般/计数信号量：可取任何非负值
    • 两者相互表现(给定一个可以实现另一个)

  • 信号量可以用在2个方面

    • 互斥
    • 条件同步(调度约束一一一个线程等待另一个线程的事情发生）

信号量缺点：

  • 信号量的双用途
    • 互斥和条件同步
    • 但等待条件是独立的互斥
  • 读/开发代码比较困难
    • 程序员必须非常精通信号量
  • 容易出错
    • 使用的信号量己经被另一个线程占用
    • 忘记释放信号量
  • 不能够处理死锁问题

管程

  • 什么是管程

    • 一个锁：指定临界区
    • 0或者多个条件变量：等待/通知信号量用于管理并发访问共享数据

  • 一般方法

    • 收集在对象/模块中的相关共享数据
    • 定义方法来访问共享数据

  • Lock

    • Lock::Acquire（ 一 等待直到锁可用，然后抢占锁
    • Lock::Release （一释放锁，唤醒等待者如果有

  • Condition Variable

    • 允许等待状态进入临界区

      • 允许处于等待（睡眠）的线程进入临界区
      • 某个时刻原子释放锁进入睡眠

    • Wait () operation

      • 释放锁，睡眠，重新获得锁返回后

    • Signal () operation ( or broadcast () operation )

      • 唤醒等待者（或者所有等待者），如果有
IMG_C86C23D6FA1D-1

经典同步问题

读者—写者问题：

  • 动机

    • 共享数据的访问

  • 两种类型使用者

    • 读者：不需要修改数据
    • 写者：读取和修改数据

  • 问题的约束

    • 允许同一时间有多个读者，但在任何时候只有一个写者
    • 当没有写者是读者才能访问数据
    • 当没有读者和写者时写者才能访问数据
    • 在任何时候只能有一个线程可以操作共享变量

  • 多个并发进程的数据集共享

    • 读者一只读数据集；他们不执行任何更新
    • 写者-可以读取和写入

  • 共享数据

    • 数据集
    • 信号量CountMutex初始化为1
    • 信号量WriteMutex初始化为1
    • 整数 Rcount 初始化为0
读者优先实现(使用信号量方式)：
IMG_4D5569A45E16-1

哲学家就餐问题：

Chapter11 死锁

死锁问题：

​ 一组阻塞的进程持有一种资源 等待获取 另一个进程所占有的一个资源。

系统模型：

可重复使用的资源

  • 在一个时间只能一个进程使用且不能被删除

  • 进程获得资源，后来释放由其他进程重用

  • 处理器，I/O通道，主和副存储器，设备和数据结构，如文件，数据库和信号量

  • 如果每个进程拥有一个资源并请求其它资源，死锁可能发生

    使用资源

  • 创建和销毁

  • 在I/O缓冲区的中断，信号，消息，信息

  • 如果接收消息阳塞可能会发生死锁

  • 可能少见的组合事件会引起死锁

死锁特征：

死锁出现的必要条件：

1、 互斥：

进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。

2、占用并等待：

进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。

3、无抢占:

进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。

4、循环等待:

存在一种进程资源的循环等待链，链中每一个进程已获得的资源同时被 链中下一个进程所请求。即存在一个处于等待状态的进程集合{Pl, P2, …, pn}，其中Pi等 待的资源被P(i+1)占有（i=0, 1, …, n-1)，Pn等待的资源被P0占有；

死锁处理方法：

死锁预防：

破坏任意死锁出现的必要条件：

  • 互斥——共享资源不是必须的，必须占用非共享资源。

  • 占用并等待——必须保证当一个进程请求的资源，它不持有任何其他资源。

    • 需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源。
    • 资源利用率低;可能发生饥饿。

  • 无抢占

    • 如果进程占有某些资源，并请求其它不能被立即分配的资源，则释放当前正占有的资源
    • 被抢占资源添加到资源列表中
    • 只有当它能够获得旧的资源以及它请求新的资源，进程可以得到执行

  • 循环等待 —对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请。

死锁避免：

需要系统具有一些额外的先验信息提供。

  • 最简单和最有效的模式是要求每个进程声明它可能需要的每个类型资源的最大数目。

  • 资源的分配状态是通过限定提供与分配的资源数量，和进程的最大需求。

  • 死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待状态。

  • 当一个进程请求可用资源，系统必须判断立即分配是否能使系统处于安全状态。

  • 系统处于安全状态指：针对所有进程，存在安全序列。

  • 序列<P1，p2,……，PN>是安全的：针对每个Pi, Pi要求的资源能够由当前可用的资源+所有的 Pj 持有的资源来满足，其中j<i。

    • 如果 Pi 资源的需求不是立即可用，那么 Pi 可以等到所有 Pj 完成。
    • 当 Pi 完成后，P i + 1 可以得到所需要的资源，执行，返回所分配的资源，并终止。
    • 用同样的方法。Pi+2, Pi+3，和 Pn 能获得其所需的资源。
银行家算法(通过合理分配资源使得死锁避免)

死锁检测：

​ 就是银行家算法，看看能不能在现有资源下，让所有进程都跑通 (时间复杂度大、开销大)

死锁恢复：

  • 方法1：终止所有的死锁进程
  • 方法2：在一个时间内终止一个进程直到死锁消除
    • 终止进程的顺序应该是：
      • 进程的优先级
      • 进程运行了多久以及需要多少时间才能完成
      • 进程占用的资源
      • 进程完成需要的资源
      • 多少进程需要被终止
      • 迸程是交互还是批处理

Chapter12进程间通信(IPC——Inter Process Communication)

概述

通信模型

  • 进程通信的机制及同步

  • 不使用共享变量的迸程通信

  • IPC facility 提供2个操作：

    • send(message）一消息大小固定或者可变
    • receive (message)

  • 如果P和Q想通信，需要：

    • 在它们之间建立通信链路
    • 通过 send/receive交换消息

  • 通信链路的实现

    • 物理（例如，共享内存，硬件总线）

    • 逻辑（例如，逻辑属性）

直接与间接通信

直接通信:
  • 进程必须正确的命名对方：
    • send (P, message) 一 发送信息到进程P
    • receive (Q, messase） 一 从进程Q接受消息
  • 通信链路的属性:
    • 自动建立链路
    • 一条链路恰好对应一对通信进程
    • 每对进程之间只有一个链接存在
    • 链接可以是单向的，但通常为双向的
间接通信:
  • 定向从消息队列接收消息
    • 每个消息队列都有一个唯一的ID
    • 只有它们共享了一个消息队列，进程才能够通信
  • 通信链路的属性
    • 只有进程共享一个共同的消息队列，才建立链路
    • 链接可以与许多进程相关联
    • 每对进程可以共享多个通信链路
    • 连接可以是单向或双向
  • 操作
    • 创建一个新的消息队列
    • 通过消息队列发送和接收消息
    • 销毁消息队列
  • 原语的定义如下：
    • send （A, message）一 发送消息到队列A
    • receive (A,message）一 从队列 A接受消息

阻塞与非阻塞：

​ 阻塞：异步

​ 非阻塞：同步(发送方一定要等到接收方收到消息后再进行下一步操作)

通信链路缓冲：

  • 队列的消息被附加到链路；可以是以下3种方式之一：

  1. 0容量
    发送方必须等待接收方 (rendezvous)

  2. 有限容量 —— n messages的有限长度

    ​ 如果队列满，发送方必须等待

  3. 无限容量——无限长度
    发送方不需要等待

信号

  • 软件中断通知事件处理

  • Examples: SIGFPE, SIGKILL, SIGUSR1, SIGSTOP, SIGCONT

  • 接收到信号时会发生什么

    • Catch:指定信号处理函数被调用
    • Ignore：依靠操作系统的默认操作

  • Example: Abort, memory dump, suspend or resume process

    • Mask：闭塞信号因此不会传送
      • 可能是暂时的（当处理同样类型的信号）

  • 不足
    不能传输要交换的任何数据

管道

​ 主要是为了 实现使一个进程的输出作为另一个进程的输入 (这两个进程都是shell进程的子进程，shell进程为它们之间的通信创建通道)

消息队列

​ https://tangjiayang.github.io/2023/06/02/%E6%B6%88%E6%81%AF%E9%98%9F%E5%88%97/

​ 一种间接通信方式

共享内存

  • 进程

    • 每个进程都有私有地址空间
    • 在每个地址空间内，明确地设置了共享内存段

  • 优点

    • 快速、方便地共享数据

  • 不足

    • 必须同步数据访问

Chapter13 文件系统

基本概念

文件系统和文件

  • 文件系统：一种用于持久性存储的系统抽象

    • 在存储器上：组织、控制、导航、访问和检索数据
    • 大多数计算机系统包含文件系统
    • 个人电脑、服务器、笔记本电脑
    • iPod.Tivo /机顶盒、手机/掌上电脑
    • Google 可能是由一个文件系统构成的

  • 文件：文件系统中一个单元的相关数据在操作系统中的抽象

文件系统的功能：
  • 分配文件磁盘空间
    • 管理文件块（哪一块属于哪一个文件）
    • 管理空闲空间(哪一块是空闲的）
    • 分配算法（策略）
  • 管理文件集合
    • 定位文件及其内容
    • 命名：通过名字找到文件的接口
    • 最常见：分层文件系统
    • 文件系统类型（组织文件的不同方式）
  • 提供的便利及特征
    • 保护：分层来保护数据安全
    • 可靠性/持久性：保持文件的持久即使发生崩溃、媒体错误、攻击等
文件和块：
  • 文件属性：
    • 名称、类型、位置、大小，保护、创建者、创建时间、最近修改时间、…
  • 文件头：
    • 在存储元数据中保存了每个文件的信息
    • 保存文件的属性
    • 跟踪哪一块存储块属于逻辑上文件结构的哪个偏移

文件描述符

  • 需要元数据数据来管理打开文件：

    • 文件指针：指向最近的一次读写位置，每个打开了这个文件的进程都有这个指针
    • 文件打开计数：记录文件打开的次数——当最后一个进程关闭了文件时，允许将其从打开文件表中移除
    • 文件磁盘位置：缓存数据访问信息
    • 访问权限：每个程序访问模式信息

  • 用户怎么访问文件

    • 在系统层面需要知道用户的访问模式：
    • 顺序访问：按字节依次读取
      • 几乎所有的访问都是这种方式
    • 随机访问：从中间读写
      • 不常用，但是仍然重要．例如，虚拟内存支持文件：内存页存储在文件中
      • 更加快速 一 不希望获取文件中间的内容的时候也必须先获取块内所有字节。
    • 基于内容访问：通过特征
      • 许多系统不提供此种访问方式，相反，数据库是建立在索引内容的磁盘访问上（需要高效的随机访问)

  • 多用户系统中的文件共享：

    • 访问控制
      • 谁能够获得哪些文件的哪些访问权限
      • 访问模式：读、写、执行、删除、列举等
    • 文件访问控制列表 (ACL)
      • <文件实体，权限>
    • Unix 模式
      • 〈用户|组|所有人，读|写|可执行〉
      • 用户ID识别用户，表明每个用户所允许的权限及保护模式
      • 组ID允许用户组成组，并指定了组访问权限
    • 指定多用户/客户如何同时访问共享文件
      • 和过程同步算法相似
      • 因磁盘I/0和网络延迟而设计简单
    • Unix 文件系统(UFS) 语义
      • 对打开文件的写入内容立即对其他打开同一文件的其他用户可见
      • 共享文件指针允许多用户同时读取和写入文件
    • 会话语义
      • 写入内容只有当文件关闭时可见
    • 锁
      • 一些操作系统和文件系统提供该功能

目录

  • 文件以目录的方式组织起来

  • 目录是一类特殊的文件

    • 每个目录都包含了一张表<name, pointer to file header>

  • 目录和文件的树型结构

    • 早期的文件系统是扁平的 （只有一层目录）

  • 典型操作

    • 搜索文件
    • 创建文件
    • 删除文件
    • 枚举目录
    • 重命名文件
    • 在文件系统中遍历一个路径

  • 操作系统应该只允许内核模式修改目录

    • 确保映射的完整性
    • 应用程序能够读目录 （如1s)

  • 名字解析：逻辑名字转换成物理资源（如文件）的过程

    • 在文件系统中：到实际文件的文件名（路径）
    • 遍历文件目录直到找到目标文件

  • 举例：解析 “/bin/ls”

    • 读取root的文件头（在磁盘固定位置）
    • 读取root的数据块：搜索 “bin” 项
    • 读取bin的文件头
    • 读取bin的数据块：搜索 “ls” 项
    • 读取ls的文件头

  • 当前工作目录

    • 每个进程都会指向一个文件目录用于解析文件名
    • 允许用户指定相对路径来代替绝对路径

文件别名

基本概念

  • 两个或多个文件名关联同一个文件

  • 硬链接：多个文件项指向一个文件

  • 软链接：以“快捷方式”指向其他文件(**“快捷方式文件的内容是另一个文件的路径名**”)

  • 通过存储真实文件的逻辑名称来实现

文件系统种类

  • 磁盘文件系统

    • 文件存储在数据存储设备上，如磁盘。
    • 例如：FAT, NTFS, ext2/3， IS09660，等

  • 数据库文件系统

    • 文件根据其特征是可被寻址（辨识）的
    • 例如：winFS

  • 日志文件系统

    • 记录文件系统的修改/事件
    • 例如：journaling file system

  • 网络/分布式文件系统

    • 文件可以通过网络被共享

      • 文件位于远程服务器
      • 客户端远程挂载服务器文件系统
      • 标准系统文件访问被转换成远程访问
      • 标准文件共享协议：NFS for Unix, CIFS for windows

    • 分布式文件系统的问题

      • 客户端和客户端上的用户辨别起来很复杂
      • 例如，NFS是不安全的
      • 一致性问题
      • 错误处理模式

    • 例如：NFS, SMB, AFS, GFS

  • 特殊/虚拟文件系统

虚拟文件系统

  • 分层结构

    • 上层：虚拟(逻辑)文件系统
    • 底层：特定文件系统模块

  • 目的

    • 对所有不同文件系统的抽象(让上层使用统一的接口对不同的文件系统进行统一管理)

  • 功能

    • 提供相同的文件和文件系统接口
    • 管理所有文件和文件系统关联的数据结构
    • 高效查询例程，遍历文件系统
    • 与特定文件系统模块的交互

  • 实现

    • 卷控制块 (Unix: “superblock”）
      • 每个文件系统一个
      • 文件系统详细信息
      • 块、块大小，空余块、计数/指针等
    • 文件控制块 (Unix： ”vnode” or “inode”）
      • 每个文件一个
      • 文件详细信息
      • 许可、拥有者、大小、数据库位置等
    • 目录节点 (Linux: ”dentry”）
      • 每个目录项一个（目录和文件）
      • 将目录项数据结构及树型布局编码成树型数据结构
      • 指向文件控制块、父节点、项目列表等

  • 文件系统数据结构

    • 卷控制块（每个文件系统一个）
    • 文件控制块（每个文件一个）
    • 目录节点(每个目录项一个)

  • 持续存储在二级存储中

    • 分配在存储设备中的数据块中

  • 当需要时加载进内存

    • 卷控制模块 ：当文件系统挂载时进入内存
    • 文件控制块：当文件被访问时进入内存
    • 目录节点：在遍历一个文件路径时进入内存

数据块缓存

  • 数据块按需读入内存
    • 提供 read() 操作
    • 预读：预选读取后面的数据块
  • 数据块使用后被缓存
    • 假设数据将会再次被使用
    • 写操作可能被缓存和延迟写入
  • 两种数据块缓存方式
    • 普通缓冲区缓存
    • 页缓存：统一缓存数据块和内存页
      • 分页要求
        • 当需要一个页时才格其载入内存
      • 支持存储
        • 一个页（在虚拟地址空间中）可以被映射到一个本地文件中（在二级存储中）
      • 文件数据块的页缓存
        • 在虚拟内存中文件数据块被映射成页
        • 文件的读/写操作被转换成对内存的访问
        • 可能导致缺页和/或设置为脏页

打开文件的数据结构

  • 打开文件描述
    • 文件状态信息
    • 目录项、当前文件指针、文件操作设置等
  • 打开文件表
    • 一个进程一个
    • 系统级
    • 每个卷控制块也会保存一个列表
    • 所以如果有文件被打开将不能被卸载

文件分配

  • 大多数文件都很小

    • 需要对小文件提供强力的支持
    • 块空间不能太大

  • 一些文件非常大

    • 必须支持大文件 （64-bit 文件偏移）
    • 大文件访问需要相当高效

  • 如何为一个文件分配数据块

    • 分配方式
      • 连续分配
        • 优点：
          • 文件读取表现好
          • 高效的顺序和随机访问
        • 缺点：
          • 碎片
          • 如文件增大，则不好处理
      • 链式分配
        • 文件以数据块链表的方式存储
        • 文件头包含了从第一块到最后一块的指针
        • 优点：
          • 创建、增大、缩小容易
          • 没有碎片
        • 缺点：
          • 不可能进行真正的随机访问(链表，所以只能串型访问)
          • 可靠性(中途断电，导致链表被破坏)
      • 索引分配
        • 为每个文件创建一个名为索引数据块的非数据数据块
          • 到文件数据块的指针列表
        • 文件头包含了索引数据块
        • 优点：
          • 创建、增大、缩小很容易
          • 没有碎片
          • 支持直接访问
        • 缺点：
          • 当文件很小时，存储索引的开销
          • 如何处理大文件？
    • 指标
      • 高效：如存储利用 （外部碎片）
      • 表现：如访问速度

空闲空间列表

……

多磁盘管理 -RAID

磁盘阵列（Redundant Arrays of Independent Disks，RAID），”数块独立磁盘构成具有冗余能力的阵列”

磁盘阵列是由很多块独立的磁盘，组合成一个容量巨大的磁盘组，利用个别磁盘提供数据所产生加成效果提升整个磁盘系统效能。利用这项技术，将数据切割成许多区段，分别存放在各个硬盘上。

  • 分区：硬件磁盘的一种适合操作系统指定格式的划分

  • 卷：一个拥有一个文件系统实例的可访问的存储空间

    • 通常常驻在磁盘的单个分区上

  • 使用多个并行磁盘来增加

    • 吞吐量（通过并行)
    • 可靠性和可用性（通过冗余，多存几份，防备意外）

  • RAID 一 冗余磁盘阵列

    • 各种磁盘管理技术
    • RAID levels：不同RAID 分类（如，RATD-0， RAID-1, RATD-5)

  • 实现

    • 在操作系统内核：存储/卷管理
    • RAID硬件控制器 (I/0)

磁盘调度

  • 读取或写入时，磁头必须被定位在期望的磁道，并从所期望的扇区的开始
  • 寻道时间
    • 定位到期望的磁道所花费的时间
  • 旋转延迟
    • 从扇区的开始处到到达目的处花费的时间

SCAN

对于扫描算法，磁臂从磁盘的一端开始，向另一端移动；在移过每个柱面时，处理请求。当到达磁盘的另一端时，磁头移动方向反转，并继续处理。磁头连续来回扫描磁盘。SCAN 算法有时称为电梯算法，因为磁头的行为就像大楼里面的电梯，先处理所有向上的请求，然后再处理相反方向的请求。

C-LOOK

基于SCAN算法，C-LOOK移动磁头从磁盘一端到磁盘另一端（磁臂只需移到一个方向的最远请求为止），并且处理行程上的请求，然而，当磁头到达另一端时，它立即返回到磁盘另一端最远的请求，而并不处理任何回程上的请求，然后从该最远的请求开始，继续往同一方向移动磁盘处理请求。