王道操作系统第一二章

前言·

看到南大jyy OS的课，内存等等，当时感觉新鲜有挑战，现在暑假有时间了，却感觉头大，没拼劲了

总之，还是从简单的入手，建立好相关的概念再说

共18个小时，预计7月份9-16号，也就是一周即可刷完

呵呵，flag要倒了，因为这几天只是在看小说

参考：《王道操作系统》学习笔记总目录+思维导图_王道操作系统思维导图_BitHachi的博客-CSDN博客

感觉第一章和概念部分给了自己一种比较简单的错觉（早知道，还是王道），后面的调度、互斥很难的，只是粗浅地看视频很难学会；和计组也有一些互通的内容

第一章操作系统概述·

1.1 OS概念功能特征·

首先举了MAC、WINDOWS、Linux的例子

然后通过计算机系统的层次结构：裸机（纯硬件）- 操作系统 - 应用程序（软件）- 用户（用户也有部分和操作系统接触）

操作系统的概念：

操作系统（Operating System，OS）是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配；以提供给用户和其他软件方便的接口和环境；它是计算机系统中最基本的、最接近系统硬件的系统软件。(向)

是系统最基本最核心的软件，属于系统软件
合理的组织、调度计算机的工作与资源的分配
为用户和其它软件提供方便的接口和环境

通过打开QQ视频聊天的例子引出了OS作为系统资源的管理者，提供的功能：

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

命令接口用户可直接使用，包含：

联机/交互式命令接口
脱机/批处理命令接口

程序接口：允许用户通过程序间接使用，可以在程序中进行系统调用来使用程序接口。普通用户不能直接使用程序接口，只能通过程序代码间接使用。

除此以外，还有GUI，当然也是属于用户可直接使用,也有认为用户接口不包括GUI的教材

操作系统的四个特征：·

并发
共享
虚拟
异步

并发：两个或多个事件在同一时间间隔内发生，这些事件在宏观上是同时发生的，在微观上是交替发生的，操作系统的并发性指系统中同时存在着多个运行的程序

并行：两个或多个事件在同一时刻发生（真的同时发生）

一个单核(CPU)同一时刻只能执行一个程序，因此操作系统会协调多个程序使他们交替进行（这些程序在宏观上是同时发生的，在微观上是交替进行的）

操作系统是伴随着“多道程序技术出现的”，因此操作系统和并发是一同诞生的

共享：资源共享，是指系统中的资源可以供内存中多个并发执行的进程共同使用

互斥共享：某个资源在一段时间内只能允许一个进程访问；例如：摄像头
同时共享：某个资源在在一段时间内可以同时允许多个进程访问；例如：硬盘

并发性和共享性互为存在条件（如果无法并发，那么共享没有意义，因为只能有一个程序在运行）

虚拟：是把一个物理上的实体变为若干逻辑上的对应物。物理实体实际存在，逻辑对应物是用户感受到的

虚拟处理器（CPU）：通过多道程序设计技术，采用让多道程序并发执行的方法，分时来使用一个CPU，实际物理上只有一个CPU，但是用户感觉到有多个CPU 时分复用技术
虚拟存储器：从逻辑上扩充存储器容量，用户感觉到的但实际不存在的存储器空间复用技术

技术有：空分复用技术和时分复用技术

*没有并发性，就没有必要有虚拟性，（因为，只有一个程序嘛）

异步：多道程序环境允许多个程序并发执行，但由于资源有限，如cpu只有一个，进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进。

由于并发运行的程序会争抢着使用系统资源，而系统中的资源有限，因此进程的执行不是一贯到底的，而是走走停停的，以不可预知的速度向前推进（看这句话好理解）可以理解成排队买饭，但拿到饭不一定是完全按排队顺序，因为有些饭做的时间长，另外，做饭做饭是一批批相同的饭做的

1.2 OS的发展与分类·

1.2 操作系统的发展和分类（手工、单道/多道批处理、分时、实时、网络、分布式、嵌入式、个人计算机）_BitHachi的博客-CSDN博客

手工操作阶段：人机速度不匹配（手工装/取纸带慢，机器相对来说更快：速度差）

批处理阶段：

单道批处理系统(引入脱机输入输出技术：外围机+磁带)；取消了手工装/取纸带，缓解人机速度矛盾，资源利用率依然低
多道批处理系统（例如计算机输入输出时同时可以计算）；多道程序并发执行；不提供人机交互功能（OS诞生）

分时操作系统：提供人机交互功能；无法优先处理紧急任务

实时操作系统：

硬实时：必须在绝对严格的规定时间内完成处理
软实时：能接受偶尔违法时间约定
能优先处理紧急任务，可靠性强

除此以外，还有网络OS、分布式OS、PC OS

*甘特图：甘特图是一种项目管理工具，用于展示项目任务在时间轴上的安排。（多项目进度横轴）

1.3 OS的运行机制–中断和异常–系统调用·

高级语言代码-编译->机器指令程序运行的过程就是CPU执行指令的过程

内核程序和应用程序

内核程序必须是特权指令（例如内存清零），且在内核态（核心态、管态）下执行

反之，应用程序是非特权指令，在用户态/目态下执行

CPU处于内核态，说明运行的是内核程序，可以执行特权指令（拓展：CPU中有一个寄存器叫程序状态字寄存器PSW；二进制位1表示内核态，0表示用户态）

内核(Kernel)是OS中最重要的部分，有很多内核程序构成

内核态–>用户态：一条修改PSW（程序状态字寄存器）的特权指令

用户态–>内核态：由中断引起，硬件自动完成

中断和异常：

中断：会使CPU由用户态变为内核态，使OS重新夺回对CPU的控制权（中断是唯一途径）

中断类型：

*下面内中断中终止和故障可能有标注错误

内中断：与当前执行的指令有关，中断信号来源于CPU内部
1. 试图在用户态执行特权指令终止ABORT
2. 指令非法e.g.执行除法指令，除数为0 终止ABORT
3. 请求使用系统内核的服务，此时会执行一条特殊的指令–陷入指令，该指令会引发一个内部中断信号陷入TRAP
4. 故障FAULT 缺页故障
外中断：与当前执行的指令无关，中断信号来源于CPU外部
- 时钟中断：由中断部件发来的中断信号
- I/O中断：由I/O设备发来的中断信号

也有：内中断称为异常，外中断称为（狭义的）中断

找到相应的中断处理程序：通过中断向量表实现

系统调用：

其实如果你多练算法多敲代码多打比赛，时间长了，你就会有一种类似英语语感的这种东西，你看着这些就不再抽象，很好理解 ——某弹幕

*操作系统作为用户和计算机硬件之间的接口，需要向上提供一些简单易用的服务，主要包括命令接口和程序接口，程序接口由一组系统调用组成

系统调用：操作系统对应用程序/程序员提供的接口；可理解为可供应用程序调用的特殊函数，使处理器由用户态切换到核心态

打印机的例子：用户想要使用打印机的互斥共享资源，只能通过系统调用操作系统内核发出请求，内核会对各个请求协调处理

什么功能需要系统调用实现（凡是与共享资源相关的操作，会直接影响到其他进程的操作，需要操作系统的介入，就需要系统调用；保证系统稳定安全，防止非法操作）：

设备管理
文件管理
进程管理
进程通信
内存管理

系统调用和库函数：系统调用处于底层；有的库函数是对系统调用的进一步封装；应用程序通过高级语言间接实现系统调用

系统调用的过程：

传递系统调用参数，陷入指令/Trap/访管
由操作系统内核程序处理系统调用请求
返回应用程序

1.4 操作系统的体系结构·

操作系统分为内核和非内核（例如：GUI不属于内核部分）

名称	大内核	微内核
内核态	进程管理、存储管理、设备管理 + 时钟管理、中断处理、原语	时钟管理、中断处理、原语
用户态		进程管理、存储管理、设备管理
特点	将OS的主要模块都作为系统内核，运行在核心态	只保留最基本的功能在内核
优点	高性能	内核功能少，结构清晰，易于维护
缺点	内核代码庞大，结构混乱，难以维护	需要频繁地在核心态用户态之间切换，性能低（消息传递）

名称	分层结构	模块化	外核
特点	每层可单向调用更低一层提供的接口	将OS按功能划分为多个模块（主模块+可加载）	分配未经抽象的硬件资源
优点	便于调试验证	动态加载、适用性强；可直接调用，效率高	使用灵活；减少虚拟资源的映射层，提升效率
缺点	效率低，无法跨层调用；难以合理定义各层的边界	模块接口定义未必合理；难以调试	降低一致性；系统复杂

1.5 操作系统引导BOOT·

这一节解释：开机–> 让OS运行起来

磁盘的开头：主引导记录MBR：包含磁盘引导程序和分区表

C盘：活动分区，安装了OS

C盘的开头：引导记录PBR（负责找到“启动管理器”）和根目录

主存：RAM和ROM（BIOS）：包含ROM引导程序，即自举程序

1.6 虚拟机·

虚拟机：使用虚拟化技术，将一台物理机虚拟化为多台虚拟机器（virtual machine VM/Hypervisor），每个虚拟机器都可以独立运行一个操作系统

直接运行在硬件上：
- 只有虚拟机管理程序运行在内核空间；其他OS运行在用户空间
- 使用特权指令时被VMM截获
- 第一类VMM运行在最高特权级（Ring 0）
运行在宿主操作系统上：
- 例如：VMware或VirtualBox
- 分配的是虚拟内存和虚拟磁盘
- 可迁移性更好 .iso
- 第二类VMM部分在用户态，部分在内核态

第二章进程管理·

2.1_1 进程的概念、组成、特征·

程序：静态的，存放在磁盘里的可执行文件，一系列的指令集合

进程process：动态的，是程序的一次执行过程

*同一程序多次执行对应多个进程

区分进程：当进程被创建时，OS为进程分配唯一的、不重复的process ID进程ID、进程所属用户UID、分配的I/O设备、内存文件等

进程描述信息，进程控制管理信息，资源分配信息，处理机相关信息都被保存在一个数据结构：进程控制块PCB（Process Control Block）

进程实体（映像）的组成：PCB、程序段（程序代码/指令序列）、数据段（运行中产生的各种数据，例如变量）||进程是进程实体的运行过程，系统资源调度分配的独立单位

进程的特征：动态性、并发性、独立性、异步性、结构性

2.1_2 进程的状态与转换·

状态：

创建态：进程正在创建时，OS为进程分配资源、初始化PCB
就绪态：进程创建完成后，已经具备运行条件，由于没有空闲CPU，暂时无法运行
运行态：一个进程正在CPU上运行，CPU会执行该进程对应的程序（执行指令序列）
阻塞态：在事件发生前，进程无法继续向下执行，进程从CPU下去，进入阻塞态
终止态：一个进程可以执行exit系统调用，请求OS终止该进程，进程下CPU，回收内存空间等资源和PCB

进程的整个生命周期大部分处于三个基本状态：运行态、就绪态、阻塞态

运行–>阻塞主动行为 || 阻塞–>运行被动（不是进程能控制的）

PCB有一个变量state表示进程当前状态

进程的组织：

链接方式：根据状态的不同创建队列（指针指向处于XX状态的进程，队列形式）
索引方式：根据状态的不同创建索引表

2.1_3 进程控制·

进程控制：对系统的所有进程实施有效的管理，具有功能：实现创建新进程、撤销已有进程、进程的状态转换等

进程控制通过原语实现，原子性，执行过程中一气呵成，不允许被中断

例如：需要执行两步操作：PCB2的state设为1，将PCB2从阻塞状态队列放到就绪状态（若是此时有中断信号打断，不能一气呵成，那么就会导致OS的某些关键数据结构信息不一致）

通过关中断指令和开中断指令实现原语：执行了关中断指令后，不再例行检查（每执行一条指令检查|一条程序包含多条指令）中断信号

讲述了各种进程状态转换的原语（既流程）和切换事件（常见例子）

*作业调度：从外存中挑选一个程序，放入内存开始运行

进程切换时，先在PCB中保存这个进程的运行环境，即必要的CPU的寄存器，例如：PSW PC IR 通用寄存器

进程控制原语，通用操作：更新PCB信息，将PCB插入合适队列，分配/回收资源

2.1_4 进程间通信IPC·

进程间通信(Inter-Process Communication)：指两个进程之间产生数据交互

各进程的内存地址空间独立，为保证安全，不能直接访问其他进程的地址空间

进程通信三种方式：

共享存储：设置共享存储区（避免出错，各个进程对共享空间的访问互斥，PV操作实现）
消息传递：进程间数据交换以格式化的消息为单位，进程通过"发送消息/接受消息"原语进行数据交换；通信方式：（直接，A直接发给B，间接：类似公共存储"信箱"）
管道通信：pipe文件，开辟大小固定的内存缓冲区，FIFO单向，类似队列，限制写入读取位置，只能头或尾
- 互斥，即当一个进程正在对pipe执行读/写操作时，其它(另一)进程必须等待。
- 同步，指当写(输入)进程把一定数量(如4KB)的数据写入pipe，便去睡眠等待，直到读(输出)进程取走数据后，再把他唤醒。当读进程读一空pipe时，也应睡眠等待，直至写进程将数据写入管道后，才将之唤醒。
- linux进程的管道通信- 博客园刚在想：管道通信为什么要互斥访问，自己想反正一个头读数据，一个尾部写数据，直接边读边写呗，上面即为解答

发现前面的章节也可能用到后面的知识，重听一遍还是很有必要的

2.1_5 线程的概念·

啊，从这开始当时啥笔记也没做，现在就得花时间了

本来想，线程不如直接把进程下划分为多个子进程，不过看到这么多线程和进程间的差异，感觉创造”线程“这个概念有必要的（QQ程序/进程，有视频聊天和文件传输两个功能/线程）感觉写的不好：子进程和线程的区别-CSDN博客进程与子进程及线程 - 苦心明 - 博客园 (cnblogs.com)

线程是一个基本的CPU执行单元，也是程序执行流/调度的最小单位（如QQ的视频聊天和文件传输功能）

进程只作为除CPU外的系统资源的分配单位（如打印机、内存地址空间分配给进程）

线程间并发：如果同一进程内的线程切换，则不需要切换进程环境，系统开销小

2.1_6 线程的实现方式和多线程模型·

用户级线程User-Level Thread ULT

早期OS只支持进程，线程通过应用程序内（处于用户态）的线程库（调度管理线程）实现

线程库：例如 while 视频聊天，文字聊天，文件传输

用户级线程切换不需切换到核心态，系统开销小；若一个用户级线程被阻塞，整个进程阻塞

内核级线程Kernel-Level Thread KLT

管理在操作系统内核；切换线程发生变态，开销大

多线程模型

一对一：一个用户级线程映射到一个内核级线程
多对一：多个用户级线程映射到一个内核级线程
多对多：需用户级线程数更多（自己想的是利用同一类资源或捆绑类的，放在一起）克服了并发度不高和开销大的缺点

2.1_7 线程的状态与转换·

就绪、运行、阻塞态的转换和进程方式一致

组织控制：TCB线程控制块，和PCB类似

2.2_1 调度的概念、层次·

当有一堆任务要处理，但由于资源有限，无法同时处理这些事物，就需要确定某种规则来决定处理任务的顺序

高级调度：作业：一个具体的任务

低级调度：进程/处理机：就绪队列选取一个进程，并分配处理机

中级调度：内存：内存不足时，可将某些进程的数据从队列中调出到外存，等内存空闲或进程需要运行时再重新调入，暂时调出的进程状态称为挂起状态，举了<手机杀后台的例子>

挂起态（suspend）可细分为就绪挂起、阻塞挂起（这两个和之前的5个进程状态合并为七状态模型）

*阻塞态的程序映像还在内存，挂起态调到外存

2.2_2进程调度的时机、切换与过程、方式·

一些需要进程调度的情况：

主动放弃：

进程正常终止
运行过程中发生异常而终止
进程主动请求阻塞（如等待IO）

被动放弃：

分给进程的时间片用完
有更紧急的事需要处理（IO中断）
有更高优先级的进程进入就绪队列

不能进程切换时机：处理中断，原语，进程在操作系统内核程序临界区中

临界资源：一个时间段只允许一个进程使用的资源，各进程需要互斥地访问临界资源

临界区：访问临界资源地那段代码

进程调度的方式：

非剥夺调度方式：非抢占方式，只允许进程主动放弃处理机

剥夺调度方式：抢占方式，有更重要紧迫进程，会暂停当前执行进程

2.2_3调度器和闲逛进程·

调度器scheduler

I/O中断原理 - 博客园 (cnblogs.com)当外部设备的I/O模块准备好时，它会发送给CPU一个中断信号，CPU则会“立即”做出响应，暂停当前程序的处理去服务该I/O设备的程序。

idle闲逛进程：没有其他就绪进程时，运行闲逛进程（能耗低，指令周期末尾例行检查中断）

2.2_4调度算法的评价指标·

CPU利用率：CPU忙碌时间/总时间

系统吞吐量：单位时间内完成作业的数量

周转时间：从作业被提交给系统开始，到作业完成为止的时间间隔；平均周转时间，周转时间和/作业数；带权周转时间：作业周转时间/作业实际运行时间

等待时间：进程/作业等待进入服务的时间

响应时间：从用户提出请求到首次产生响应所用的时间

2.2_5–2.2_7调度算法·

学习思路或关心问题：算法思想、算法规则、适用于作业调度还是进程调度、（非）抢占式、优缺点、是否导致饥饿

周转时间=完成时间-到达时间；带权周转时间=周转时间/运行时间；等待时间=周转时间-运行时间-(IO时间)

先来先服务FCFS:

非抢占式

短作业优先SJF：（J指Job，P指Process）

非抢占式：每次调度时选择当前已到达且运行时间最短的进程

抢占式的SJF，最短剩余时间优先算法SRTN：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间更短比当前运行的时间更短，就由新进程抢占，当然，进程完成时也需要调度

在所有进程同时可运行/几乎同时到达，那么，SJF调度算法的平均等待时间、平均周转时间最少

长作业长时间无法得到服务，可能产生饥饿

高响应比优先HRRN：

每次调度时先计算每个作业的响应比，选出最高的；响应比=（等待时间+要求服务时间）/要求服务时间（如果是抢占式，要求服务时间会变化吗）

好吧，这是非抢占式的算法

*上面三种算法，没有区分任务紧急程度，交互性差，只适用早期的批处理系统

时间片轮转调度算法RR(Round-Robin)：

按照各进程到达就绪队列的顺序，轮流让各个进程执行

常用于分时操作系统，更注重响应时间，因而不计算周转时间

默认新到达的进程先进入就绪队列，刚才下处理机的排在队尾

时间片太大，时间片轮转调度算法会退化为先来先服务，增大进程响应时间（例如10个进程，用完时间片后的响应时间=单个时间片*9，因此时间片大，响应时间长）；时间片太小，进程切换频繁（切换进程开销占1% is OK）

优先级调度算法：

每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程

非抢占式只需在进程主动放弃处理机时调度即可，而抢占式需在每次有新来进程时检查调度

通常，系统进程、前台进程、I/O繁忙型（相比计算型）进程更优先

动态优先级：等待时间长，适当提升优先级；运行时间长，适当降低优先级

不断有高优先级进程可能导致饥饿

多级反馈队列调度算法：

设置多个就绪队列，队列的优先级逐个降低，时间片递增。该队列的进程时间片结束后，进入下一时间片队列的队尾

第二章 2.3 2.4部分·

2.3_1进程同步、进程互斥·

同步：并发性带了异步性（不确定那个进程先运行）；但有时要求进程的工作顺序

互斥：对临界资源的访问，需要互斥进行，即一段时间只能允许一个进程访问资源

实现互斥的代码：

进入区：检查是否可以进入临界区，需要“上锁”
临界区：访问临界资源的实际操作代码
退出区：负责“解锁”
剩余区：其他代码

四个原则：

空闲让进：临界区空闲时，应允许一个进程访问
忙则等待：临界区正被访问时，其他试图访问的进程需要等待
有限等待：要在有限时间进入临界区，保证不会饥饿
让权等待：进入不了临界区的进程，要释放处理机，防止忙等

感觉操作系统调度、互斥的处理策略和生活中也很类似

2.3_2进程互斥的软件实现方法·

单标志法：两个进程在访问完临界区后会把使用临界区的权限交给另一个进程，即每个进程进入临界区的权限只能被另一个进程赋予

双标志先检查：设置一个布尔型数组flag[]，数组中每个元素用来标记各进程想进入临界区的意愿，即检查其他的flag数组若全为false，则自己的flag[i]设为true，然后访问临界区【如果能解决检查和上锁一气呵成就OK了】

双标志后检查：先上锁后检查（避免忙则等待实现不了的意外情况，但违背了空闲让进和有限等待，产生饥饿）

Peterson算法：

flag[0]=true;//0号进程表达想用的意愿
turn=1;//表达愿意让对方先用
while(flag[1]&&turn=1) ;//如果对方要用且自己愿意让对方用，就一直等待
critical section;//临界区段
flag[0]= false;//0号进程表达不想用了
reminder section;//剩余区

依然没能解决让权等待问题

2.3_3进程互斥的硬件实现方法·

中断屏蔽方法：

关中断、临界区、开中断；与原语类似，先禁止中断操作

简单高效

不适用多处理机、只适用于操作系统内核进程

TestAndSetLock指令

只是加锁操作，不区分进程，进程记录上一次锁状态为old，加锁lock=true，相当于也锁上自己和未来的下一个人，返回old；如果old是true，则有人再用，等待完毕后，自己使用，使用后，将lock锁状态修改为false，即下一个个人的返回结果old为false可用；但自己还没用完，则下一个人的old为true，下一个人无法使用

实现简单，无需像软件一样检查逻辑漏洞，使用于多处理机环境

不满足“让权等待”，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，造成忙等

Swap指令

while(old==true) Swap(&lock,&old);

也称Exchange或XCHG指令

优缺点与TSL一致

2.3_4 互斥锁·

spin lock自旋锁：需要连续循环忙等的互斥锁

需忙等，时间片用完下处理机，违反“让全等待”

优点：等待期间不用切换进程上下文，多处理机（多核）系统，若上锁时间短，等待代价低

acquire(){
	while(!available) ;//锁为1，其他忙等待
	;
	available = false;//使用上锁/获得锁
}

release(){
	available = true;//释放锁
}

2.3_5 信号量机制·

解决了让权等待问题

整型信号量

一对原语：wait（s）和signal（s）{括号里的S是函数调用时传入的一个参数}通常简写为P、V操作（荷兰语）

用一个整数型的变量作为信号量，用来表示系统中某种资源的数量（只有三种操作：初始化、P操作、V操作）

感觉让权等待和下处理机恢复是需要平衡的问题| 忙等确实太拉了，应该让进程睡眠等待，其他进程退出后唤醒睡眠进程才对合理

记录型信号量：

相比之下增加了block和wakeup原语，感觉记录型信号量这个名字起的不好

typedef struct{//记录型信号量的定义
    int value;//剩余资源数
    struct process *L;//等待队列
}
//某进程需要使用资源时，通过wait原语申请
void wait (semaphore S){
    S.value--;
    if(S.value<0){
        block(S.L);//block原语使进程进入阻塞态，并挂到信号量S的等待队列（实现让权等待）
    }
}
//进程使用完资源后，通过signal原语释放
void signal (semaphore S){
    S.value++;
    if(S.value<=0){//如果有至少一个资源无需分配，说明等待队列已经为空
        wakeup(S.L);//变为就绪态
    }
}

2.3_6 信号量实现进程互斥、同步、前驱关系·

信号量对应资源；P(S)：申请一个资源

互斥：

分析并发进程的关键活动，划定临界区
设置互斥信号量mutex初始值为1
进入区 P（）申请资源
退出区 V（）释放资源

/*记录型信号量的定义*/
typedef struct {
    int value;//剩余资源数
    struct process *L;//等待队列
} semaphore;

semaphore mutex = 1;//初始化信号量

同步：让本来并发的进程相互配合、有序推进

semaphore=0;//初始化同步信号量，初始值为0

P1(){code1,code2,V(S),code3}; P2(){P(S),code4,code5,code6};

由于P2要执行的code4前必须要P(S)，而S初始值为0，资源只能由P1()执行完code2后释放，借此实现了进程同步；V(S)放到code2后来释放资源/作为code4运行的条件。

在“前操作”之后执行V(S) code2–>V(S)

在“后操作”之前执行P(S) P(S)–>code4

前驱：就是多级同步问题

前驱图的代码逻辑：//相较于数据结构的图简单得多
Px(){ 
    其余代码
	V(需要的资源/上一个节点释放的资源) 
	CODEx //A实现实现同步顺序的代码段
	V(使用后可释放的资源/下一个节点需要的资源)
}

2.3_7-8 (多)生产者-(多)消费者问题·

进程和进程之间发生的等待被对方唤醒的情况称为：死锁

先互斥后同步会死锁；先互斥，那么自己也无法访问（但是感觉是条件没有配置好：问题类似于i–>0和–i>=0 运算顺序变了，修改好临界值依然可用）

多生成消费者问题：指的是产品种类

举了一个盘子，放/吃苹果、橘子的问题（当只有一个盘子资源时，不需设置mutex互斥；但例如两个盘子，可能造成两个进程写入缓冲区的数据互相覆盖的情况）

不需要分别设置4个（2乘2）唤醒，而可以通过设置单个信号量（盘子）来考虑【盘子变空的事件角度】

2.3_9 吸烟者问题·

一个生产者，生产多种产品的问题

2.3_10 读写者问题·

允许多个读者同时读操作（允许同时读和多生产者多消费者产生了差异；读者进程不会改变数据），但允许一个写者写文件，且写的时候不允许其他读写操作

P(W)可以理解为为请求服务的进程创建阻塞队列

semaphore rw = 1;//实现共享文件的互斥
int count = 0;//记录当前有几个读进程
semaphore mutex = 1;//保证对count变量的互斥访问 避免两个写进程同时
semaphore w = 1;//实现“写优先”
writer (){
    P(w);
    P(rw);
    写文件操作;
    V(rw);
    V(w);
}
reader (){
    while(1){
        P(w);
        P(mutex);
        if(count==0) P(rw);//对于第一个读，上锁；但第二个由于count!=0，会跳过if执行语句，避免阻塞
        count++;
        V(mutex);
        V(w);
        读文件操作;
        P(mutex);
        count--;
        if(count==0) V(rw);
        V(mutex);
    }
}

读读不互斥、写与其他互斥：核心思想：设置了一个计数器count记录当前访问共享文件的读进程数；第一个/最后一个会引发写操作的禁止或允许，而其他的则是默认允许读操作并行；

count的检查和赋值无法一气呵成，用到互斥信号量

解决写进程饥饿，是通过 P（w）w新变量，来阻塞新的源源不断的读进程，来保证一定能使count降为0，释放rw，使得可以写进程操作

2.3_11 哲学家进餐问题·

避免死锁：最多允许四名哲学家进餐，这样可以有一个哲学家可以进餐，不会死锁

要求奇数号哲学家先拿左，偶数号先拿右，相邻的会直接产生冲突，避免占有一只筷子再等待另一只的情况

设置编号：奇号先使用

semaphore chopstick[5]={1,1,1,1,1};
semaphore mutex = 1;//互斥地取筷子
Pi (){ //i号哲学家的进程
	while(1){
		P(mutex);
        P(chopstick[i]);//拿左
        P(chopstick[(i+1)%5]);//拿右
        V(mutex);
        吃饭
        V(chopstick[i]);//放左
        V(chopstick[(i+1)]%5);//放右
        思考
}
}

可以再找博客看看

2.3_12 管程·

为什么要引入管程：信号量机制：编写程序困难，易出错

组成：

共享数据结构
对数据机构初始化的语句
一组来访问数据结构的过程/函数

特征：

各外部进程/线程只能通过管程提供的特定入口才能访问共享数据
每次仅允许一个进程在管程内执行某个内部过程

管程和面向对象的“类”类似，“封装”思想

由编译器负责实现各进程互斥地进入管程中的过程；管程中设置条件变量和等待/唤醒操作，以解决同步问题

Java：关键字synchronized来描述函数：使得函数一段时间内只能被一个线程调用

static class monitor{
    private Item buffer[] = new Item[N];
    private int count = 0;
    
    public synchronized void insert (Item item){
        ...
    }
}

2.4 死锁预防避免检测和解除·

死锁的概念

各进程因竞争资源造成的一种互相等待对方资源，导致各进程都阻塞，都无法向前推进的现象

饥饿：由于长时间得不到想要的资源，某进程无法向前推进的现象

死循环：某进程执行过程中一直挑不出某个循环的现象。程序逻辑bug或故意设计

死锁产生的必要条件：

互斥条件
不剥夺条件：进程获得的资源未使用完之前，不能强行夺走，只能主动释放
请求和保持条件：进程已经保持了一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时进程被阻塞，但又对自己持有的资源保持不放
循环等待条件：存在一种资源的循环等待链，链中的每一个进程已获得的资源同时被下一个进程所请求

实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁

死锁的预防：

针对互斥条件：提出将互斥使用的资源（逻辑上）改造为允许共享使用，如：SPOOLing技术（缺点：系统安全）
不剥夺条件：设置主动释放条件；设置进程间优先级（缺点：实现复杂、可能造成之前工作失效，只适用于易保存和恢复的资源、反复申请释放资源会增大开销，降低系统吞吐量、一直放弃的话会造成饥饿）
请求和保持条件：设置运行前必须申请到全部资源才能获得（有些资源只需使用很短时间，但运行期间一直保持的话，会造成资源利用率低，甚至进程饥饿）
循环等待条件：每个进程必须按编号递增请求资源，避免申请之前进程已申请|正在占用的资源（不便于添加新设备，资源浪费，用户编程麻烦）

避免死锁：

安全序列：系统按照某序列分配资源，每个进程都能顺利完成。

若能找到一个安全序列，则系统是安全状态；当然，安全序列有多个

不安全状态只是可能发送死锁，安全状态则一定不会发生死锁

对于n个进程，m钟资源

最大需求矩阵Max；分配矩阵Allocation；最多还需求Need矩阵；长度为m的一维数组Available表示可用资源；进程Pi用一个长度为m的一维数组Request_i表示本次申请的资源数

如果Request_i[j]<=Need[i,j] (0<=j<=m);

则检查Request_i[j]<=Available[j] (0<=j<=m)，则尝试分配，大于则，资源不足不分配

假设分配后，更新矩阵，检查回收后是否依然有能继续分配满足的进程/处于安全状态

多种类型资源采用多维向量（a，b，c）

检测和解除：

考虑实现死锁检测算法的数据结构

为了对死锁检测：

用某种数据结构来保存资源的请求和分配信息
提供一种算法，利用上述信息来检测系统是否进入死锁状态

如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁

R1有3个资源 R2有2个资源；P1申请R2两个，占用R1两个；P2占有R1,R2各一个，申请R1一个；死锁

解除：

资源剥夺法：挂起(暂时放到外存上)，并抢占其资源，分配给其他死锁进程
撤销回退法（进程终止法）：强制撤销部分或全部死锁进程，并剥夺资源；实现简单，代价大，需重头再来
进程回退法：让一个或多个死锁进程回退到足以避免死锁的地步，要求系统记录进程的历史信息，设置还原点

结束谁：进程优先级、已执行多久、还要多久、进程使用多少资源、交互式还是批处理式

第二章终于结束！1W字