《操作系统》课程提纲，王道考研b站视频提纲，更新中，欢迎补充

写在前面：

1. 该笔记为王道考研b站《操作系统》正版视频提纲，笔记内容为个人归纳
2. 笔记未更新完，欢迎同路人到GitHub上下载完整md文件，更新细节后重新建立提交分支到我的笔记项目下面，我会合并大家的提交，方便更多人学习
   GitHub链接：https://github.com/Ulrich2003/OS-Notes
   笔记名：操作系统.md
3. 特别提醒：GitHub上的版本永远是最新版本，CSDN版本只能不定时更新，不能保证是最新笔记版本
   笔记内容过多
4. 笔记内容过多，推荐使用浏览器内置「页内搜索功能」查找相关知识点，Mac系统快捷键为 + F ，Windows下应该是ctrl + F
   

   进程的状态

   进程控制

   简单理解为：进程控制为要实现进程状态的转换

   进程控制无非要做3类事情：

   • 更新PCB中的信息
   • 将PCB插入合适的队列
   • 分配/回收资源

   进程的创建

   无 -> 创建态 -> 就绪态

   进程的阻塞和唤醒

   进程通讯

   进程是分配系统资源的单位，因此各个进程拥有的内存地址空间相互独立

   为了保证安全，一个进程是不能直接访问另一个进程的地址空间

   共享存储

   1. 管道只能采用半双工通讯，某一段时间内只能实现单向的传输 如果要实现双向同时通讯，则需要设置两个管道
   2. 各进程要互斥地访问管道
   3. 数据以字符流的形式写入管道，当管道写满时，写进程write()系统调用将被阻塞，等待读进程将数据取走。当读进程将数据全部取走后，管道变空，此时读进程read()系统调用将被阻塞。
   4. 如果没有写满，是不允许读的。如果没有读空，是不允许写的。
   5. 数据一旦被读出，就从管道中抛弃，这就意味着读进程最多只能有一个，否则可能会有读错数据的情况

   消息传递

   进程间的数据交换以**格式化的消息 **为单位。进程通过操作系统提供的“发送消息/接收消息”两个原语进行数据交换。

   2. 间接通信方式

   消息要先发送到中间实体（信箱）中，因此也称为“信箱通信方式”

   线程的属性：

   用户级线程（从用户视角看到的进程）

   用户级进程由应用程序通过线程库实现。所有线程管理工作都由应用程序负责

   用户级线程中，线程切换可以在用户态下即可完成，无须操作系统干预

   在用户看来，是由多个线程，但在操作系统内核看来，并意识不到线程的存在（用户级线程对用户不透明，对操作系统透明）

   内核级线程

   内核级线程就是「从操作系统内核视角看到能看到的线程」

   内核级线程的管理工作由操作系统内核完成。线程调度，切换等工作都由内核负责，因此内核级线程的切换必然需要在核心态下才能完成

   多线程模型

   多对一模型

   每个用户级线程映射到一个内核级线程。每个用户进程只对应一个内核级线程。

   优点：用户级线程的切换在用户空间即可完成，不需要切换到核心态，线程管理的系统开销小，效率高

   缺点：当一个用户级线程被阻塞后，整个进程都会被阻塞，并发度不高。多个线程不可在多核处理机上并行运行

   多对多模型

   克服了多对一模型并发度不高的缺点，又克服了一对一模型中一个用户进程占用太多内核级线程，开销太大的缺点。

   高级调度是辅存（外存）与内存之间的调度。每个作业只调入一次，调出一次。 作业调入时会建立相应的PCB，作业调出时才会撤销PCB。高级调度主要是入问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。

   中级调度（内存调度）

   引入虚拟存储技术之后，可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时，再重新调入内存。

   这么做的目的是为了提高内存利用率和系统吞吐量。

   暂时调到外存等待的进程状态为挂起状态，值得注意的是，PCB并不会一起调到外存，而是会常驻在内存中。PCB中会记录进程数据在外存中存放到位置，进程状态等信息，操作系统通过内存中的PCB来保持对各个进程的监控、管理。被挂起的进程会被放到挂起队列中。

   进程的挂起态和七状态模型

   暂时调到外存等待的进程状态称为挂起状态

   挂起态又可以进一步细分为就绪挂起，阻塞挂起两种状态

   进程调度的时机、切换的过程

   进程调度（低级调度），就是按照某种算法重就绪队列中选择一个进程为其分配处理机

   等待时间

   FCFS（First Come First Serve）

   算法思想：公平角度考虑

   算法规则：先来先服务

   用于作业调度时：考虑的是哪个作业先到达后备队列

   用于进程调度时：考虑的是哪个进程先到达就绪队列

   是否占 F

   优点：公平，算法实现简单

   缺点：排在长作业后面的短作业需要等待很长的时间，带权周转时间很大，对短作业来说作业体验非常不好。

   是否会导致饥饿 F

   SJF（Shortest Job First）

   算法思想：追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间

   算法规则：短作业优先

   于作业调度，也可进程调度。用于进程调度时称为“短进程优先”（Shortest Process First）算法

   是否占 SJF是非抢占式算法，但是也有抢占式版本 – 最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）

   优缺点：

   优点：“最短的” （不严谨） 平均等待时间，平均周转时间

   缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定真正做到短作业优先

   长作业/进程如果因为有源源不断的短作业/进程到来，可能会产生“饿死”现象

   做题细节

   1. 如果题目没有特别说明，所提到的“短作业/进程优先算法”默认是非抢占式的

   HRRN（Highest Response Ratio Next）

   算法思想：综合考虑作业/进程的等待时间和要求服务的时间

   算法规则：每次调度时先计算各个进程的响应比，选择响应比高的作业/进程为其服务。

   优缺点： 对各类进程相对公平，每个新到达的进程都可以很快就得到响应

   是否会导致饥饿：

   进程同步，进程互斥

   互斥共享方式

   系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源

   我们把一个时间段内只允许一个进程使用的资源称为临界资源，如摄像头，打印机，此外还有许多变量，数据，内存缓冲区等都属于临界资源

   对临界资源的互斥访问，可以在逻辑上分为四部分

   标志先检查法：

   Peterson算法：

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

   整型信 量示意图：

   • S.value表示某种资源数量，S.L指向等待该资源的队列
   • P操作中，一定是先S.value–，之后可能需要执行block原语
   • V操作中，一定是先S.value++，之后可能需要执行wakeup原语
   • 可以用记录型信 量实现系统资源的“申请”和“释放”
   • 可以用记录型信 量实现进程互斥，进程同步

   注意：题目中出现P(S) , V(S)的操作，除非特殊声明，否则默认S为记录型信 量

   用信 量实现进程互斥，同步，前驱关系

   视频链接https://www.bilibili.com/video/BV1YE411D7nH=22

   生产者-消费者问题

   装入的三种方式：

   绝对装入：在编译时，如果知道程序将放在内存中的哪个位置，编译程序将产生绝对地址的目标代码装入程序按照装入模块中的地址，将程序和数据装入内存。

   绝对装入只适用于单道程序程序环境

   静态重定位：又称可重定位装入。编译，链接后的地址都是从0开始的，指令中使用的地址，数据存放的地址都是相对于起始地址而言的逻辑地址。装入时进行“重定位”，将逻辑地址变换为物理地址（地址变换是在装入时一次完成的

   静态重定位的特点是在一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存空间，就不能装入该作业。作业一旦装入内存后，在运行期间就不能再移动，也不能再申请内存空间。

   动态重定位（常用）：又称动态运行时装入。编译，链接后的装入模块的地址都是从0开始的，装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而上把地址转换推迟到程序真正要执行时才进行。因此装入内存后所有的地址依然是逻辑地址，这种方式需要一个重定位寄存器的支持。

   特点可以将程序分配到不连续的存储区中，在程序运行前只需要装入它的部分代码即可投入运行，然后在程序运行期间，根据需要动态申请分配内存：便于程序段的分享，可以向用户提供一个比存储空间大得多的地址空间。

   采用动态重定位时允许程序在内存中发生移动

   链接的三种方式

   1. 静态链接：在程序运行之前，先将各目标模块以及他们所需的库函数连接成一个完整的可执行文件（装入模块）。之后不再拆开。
   3. 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享

   内存覆盖技术

   覆盖思想：将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。

   内存中分为一个“固定区”和若干个“覆盖区”

   需要常驻的内存的段存放在“固定区”中，调入后就不再调出（除非运行结束）

   具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。

   1文件区主要用于存放文件，追求存储空间的利用率，对文件空间的管理采用离散分配方式

   2对换区空间只占磁盘空间的小部分，被换出的进程数据存放于对换区，主要追求换入换出速度，采用连续分配方式

   固定分区分配

   将用户空间划分为若干个固定大小的分区 ，在每个分区中只装入一道作业

   目的：为了解决多道程序系统中装入多道程序，且这些程序之间又不会互相干扰。

   • 分区大小相等分配法：缺乏灵活性，但是多适合一台计算机控制多个相同对象的场合
   • 分区大小不等分配法：增加灵活性，可以满足不同大小的进程

   动态分区分配没有内部碎片 ，但是有外部碎片

   内部碎片：分配给某进程中的内存区域中，如果有些部分没有用上

   外部碎片：是指内存中某些空闲分区由于太小而难以利用（过紧凑技术来解决外部碎片）

   相关计算：

   什么是页表 /h5>

   为了知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

   1一个进程对应一张页表

   2进程的每一页对应一个页表项

   3每个页表项由「页 」和「块 」组成

   4页表记录进程页面和实际存放的内存块之间的对应关系

   段 的位数决定了每个进程最多可以分为几个段

   段内地址位数决定了每个段最大长度是多少

   分段，分页管理的对比

   页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。

   段是信息的逻辑单位，分段的主要目的是为了更好的满足用户需要。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名

   页的大小固定且由系统决定，段的长度却不固定，决定于用户编写的程序。

   分页的用户进程地址空间是维的，程序员只需给出一个记忆符即可表示一个地址

   分段的用户进程地址空间是二维的，程序员在标识一个地址 时，既要给出段名，也要给出段内地址