第四章 操作系统基本原理
4.1 基本概念
计算机系统的层次结构：纯硬件->操作系统->软件/用户
操作系统(Operating System，OS)是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的成分，以提供给用户和其他软件方便的接口和环境，它是计算机系统中最基本的系统软件。
操作系统的功能和目标：
- 作为系统资源的管理者
- 向上层提供方便易用的服务
- 作为最接近硬件的层次
操作系统的特征：并发，共享，虚拟，异步
并发:同一时间间隔发生，宏观同时，微观交替
操作系统的发展和分类：
- 手工操作阶段
- 批处理阶段
- 单道批处理系统
- 多道批处理系统(操作系统开始出现)
- 分时操作系统：将CPU的工作划分为很多很短的时间片
- 实时操作系统：硬实时(导弹，银行等)和软实时()
- 网络操作系统
- 分布式操作系统
- 个人计算机操作系统
4.2 进程管理
4.2.1 状态管理图
- 进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB。
进程被创建时操作系统会为该进程分配一个唯一的不重复的PID，操作系统记录PID和进程所属的用户UID，还要记录给进程分配了哪些资源，例如内存、IO设备，记录进程运行的情况，占用CPU的时间，占用磁盘网络的情况，这些信息都被保存在一个叫PCB的数据结构里【进程 controller broker】 - 当进程创建完成后，便进入“就绪态”，处于就绪态的进程已经具备运行条件但由于没有空闲CPU，就暂时不能运行。
- 如果一个进程此时在CPU上运行，那么这个进程处于“运行态”，CPU会执行该进程对应的程序(执行指令序列)。
- 在进程运行的过程中，可能会请求等待某个事件的发生(如等待某种系统资源的分配，或者等待其他进程的响应)。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，并让它进入“阻塞态”，当CPU空闲时又会选择另一个“就绪态”进程上CPU运行。
- 一个进程可以执行exit系统调用，请求操作系统终止该进程。此时该进程会进“终止态”，操作系统会让该进程下CPU，并回收内存空间等资源，最后还要回入收该进程的PCB。当终止进程的工作完成之后，这个进程就彻底消失了。
4.2.2 前驱图
有向无环图
前驱后继
4.2.3 进程同步机制
进程具有异步性的特征。
异步性是指各并发执行的进程以各自独立的，不可预知的速度向前推进。
看一个例子：进程通信一管道通信
读进程和写进程并发地运行，由于并发必然导致异步性，因此“写数据”和“读数据”两个操作执行的先后顺序是不确定的。而实际应用中又必须按照“写数据->读数据”的顺序来执行的。
如何解决这种异步问题，就是进程同步机制所讨论的内容
同步亦称直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而产生的制约关系。进程间的直接制约关系就是源于它们之间的相互合作。
4.2.4 进程互斥机制
进程的“并发”需要“共享”的支持。各个并发执行的进程不可避免的需要共享一些系统资源(比如内存，又比如打印机、摄像头这样的I/0设备)
我们把一个时间段内只允许一个进程使用的资源称为临界资源。许多物理设备(比如摄像头、打印机)就属于临界资源。此外还有许多变量、数据、内存缓冲区等都属于临界资源。
对临界资源的访问，必须互斥地进行。互斥，亦称间接制约关系。进程互斥指当一个进程访问某临界资源时，另一个想要访问该临界资源的进程必须等待。当前访问临界资源的进程访问结束，释放该资源之后，另一个进程才能去访问临界资源。
对临界资源的互斥访问，可以在逻辑上分为如下四个部分：
do {entry section; //进入区：负责检查是否可进入临界区，若可进入，则设置正在访间临界资源的标志(可理解为“锁”)，以阻止其他进程同时进入临界区critical section; // 临界区：访问临界资源的那段代码exit section; //退出区：负贵解除正在访问临界资源的标志(可理解为'解锁")remainder section; //剩余区：做其他处理
}while(true)
注意：
临界区是进程中访问临界资源的代码段。进入区和退出区是负责实现互斥的代码段。
临界区也可称为“临界段”
如果一个进程暂时不能进入临界区，那么该进程是否应该一直占着处理机?该进程有没有可能一直进不了临界区?
为了实现对临界资源的互斥访问，同时保证系统整体性能，需要遵循以下原则:
- 空闲让进。临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区
- 忙则等待。当己有进程进入临界区时，其他试图进入临界区的进程必须等待,
- 有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)，
- 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待
4.2.5 信号量机制
用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步。
信号量其实就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示系统中某种资源的数量，比如系统中只有一台打印机，就可以设置一个初值为1的信号量。
原语是一种特殊的程序段，其执行只能一气呵成，不可被中断。原语是由关中断/开中断指令实现的。软件解决方案的主要问题是由“进入区的各种操作无法一气呵成”，因此如果能把进入区、退出区的操作都用“原语”实现，使这些操作能“一气呵成”就能避免问题。
一对原语: wait(S)原语和signal(S)原语，可以把原语理解为我们自己写的函数，函数名分别为wait和signal，括号里的信号量S其实就是函数调用时传入的一个参数。
wait、signal原语常简称为P、V操作(来自荷兰语proberen和verhogen)。因此，做题的时候常把wait(S)、signal(S)两个操作分别写为P(S)、V(S)。
信号量机制的作用：
- 实现进程互斥
- 实现进程同步
- 实现进程的前驱关系
不要一头钻到代码里，要注意理解信号量背后的含义：一个信号量对应一种资源信号量的值=这种资源的剩余数量(信号量的值如果小于0，说明此时有进程在等待这种资源)。
P(S)：申请一个资源S，如果资源不够就阻寒等待，即S-1。
V(S)：释放一个资源S，如果有进程在等待该资源，则唤醒一个进程，即S+1。
4.2.5 PV操作（6分左右）
4.2.5 PV操作实现前驱操作
4.2.6 死锁
死锁产生的必要条件：
产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生
- 互斥条件：只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷、子打印机设备)。像内存、扬声器这样可以同时让多个进程使用的资源是不会导致死锁的(因为进程不用阻塞等待这种资源)。
- 不剥夺条件：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放。
- 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放。
- 循环等待条件：存在一种进程资源的循环等待链，钱链中的每一个进程已获得的资源同时被下一个进程所请求。
死锁的处理策略：
- 预防死锁：破坏死锁产生的四个必要条件中的一个或几个。
- 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁(银行家算法)。
- 死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁。
某系统中有3个并发进程竞争资源R，每个进程都需要5个R，那么至少有___个R，才能保证系统不会发生死锁。
每个进程给4个，最后再加1个打破竞争，3*4+1=13
4.2.7 银行家算法
安全序列：指如果系统按照这种序列分配资源，则每个进程都能顺利完成。只要能找出一个安全序列，系统就是安全状态。当然，安全序列可能有多个。
如果分配了资源之后，系统中找不出任何一个安全序列，系统就进入了不安全状态。这就意味着之后，可能所有进程都无法顺利的执行下去。
如果系统处于安全状态，就一定不会发生死锁。如不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态。
因此可以在资源分配之前预先判断这次分配是否会导致系统进入不安全状态，以此决定是否答应资源分配请求。这也是“银行家算法”的核心思想。
