在学习操作系统时总结了笔记，并分享出来，特别是蓝色和红色字体。有问题请及时联系博主：Alliswell_WP，转载请注明出处。
参考书：《操作系统》谌卫军等，清华大学出版社，2012年5月
参考视频：清航全套计算机专业课视频
目录
第二章 进程管理
1.进程（Process）
2.线程（Thread）
3.进程间通信
4.经典的IPC问题
5.进程调度
第三章 死锁
第二章 进程管理（进程三种状态的转换？如何共享数据？低级通信？高级通信？互斥（引入的原因及如何解决）？PV原语、经典的三大IPC问题及解决方案、进程调度的优先级、死锁）
1.进程（Process）
为什么使用进程？Why processes？
为了提高计算机系统中各种资源的利用率，现代操作系统广泛采用多道程序技术（multi-programming），使多个程序同时在系统中存在并运行。
X86 CPU 寄存器
程序1 程序2
问题：硬件只有一份，如何使这两个程序同时运行？
为此，操作系统设计者提出了进程的概念。
什么是进程？A process = a program in execution
一个进程应该包括：
-程序的代码；
-程序的数据；
-CPU寄存器的值，如PC，用来指示下一条将运行的指令、通用寄存器等；
-堆、栈；
-一组系统资源（如地址空间、打开的文件）
总之，进程包含了正在运行的一个程序的所有状态信息。
扩展：栈的作用是什么？保存临时数据、函数调用时来分配栈针来存放形参和局部变量
进程和程序的区别？
程序是静态的，进程是动态的。
进程的特性
-动态性：程序的运行状态在变，PC、寄存器、堆和栈等；
-独立性：是一个独立的实体，是计算机系统资源的使用单位。每一个进程在一个“虚拟计算机”上运行，每个进程都有“自己”的PC和内部状态，运行时独立于其他的进程（虚拟PC和物理PC）；
如何实现逻辑PC？
在内存开辟一段空间，实现不同进程物理PC和逻辑PC轮流切换。
引起进程创建的三个主要事件？
-系统初始化时；
-在一个正在运行的进程当中，执行了创建进程的系统调用；
-用户请求创建一个新进程。
进程的三个基本状态
-运行状态（Running）：进程占有CPU，并在CPU上运行。处于此状态的进程数目小于等于CPU的数目。
-就绪状态（Ready）：进程已经具备运行条件，但由于CPU忙暂时不能运行，只要分得CPU即可运行；
（万事俱备只欠东风，只欠CPU）
-阻塞状态（Blocked/Waited）：指进程因等待某种事件的发生而暂时不能运行的状态（如I/O操作或进程同步），此时，即使CPU空闲，该进程也不能运行。
类比：修自行车……（运行——正在修；就绪——正在修别人的车，等空闲修；阻塞——坏零件，买回来才能修）
进程的状态及其转换
引起进程状态转换的具体原因如下：
运行态→等待态：等待使用资源；如等待外设传输；等待人工干预。
等待态→就绪态：资源得到满足；如外设传输结束；人工干预完成。
运行态→就绪态：运行时间片到；出现有更高优先权进程。
就绪态—→运行态：CPU 空闲时选择一个就绪进程。
问题：1）进程正常运行（未阻塞）时处于什么状态？运行态或就绪态
2）此页正在讲的PPT处于什么状态？阻塞态
3）是否有其他的状态转换？没有，这三种只有四种情况。
程序 = 数据结构 + 算法
描述进程的数据结构：进程控制块（Process Control Block，PCB）。
系统为每个进程都维护了一个PCB，用来保存与进程有关的各种状态信息。
PCB中的主要内容
系统用PCB来描述进程的基本情况以及运行变化的过程，PCB是进程存在的唯一标志。
进程的创建：为该进程生成一个PCB；
进程的终止：回收它的PCB；
进程的组织管理：通过对PCB的组织管理来实现；
状态队列
-由操作系统来维护一组队列，用来表示系统当中所有进程的当前状态；
-不同的状态分别用不同的队列来表示（运行队列、就绪队列、各种类型的阻塞队列）；
-每个进程的PCB都根据它的状态加入到相应的队列当中，当一个进程的状态发生变化时，它的PCB从一个状态队列中脱离出来，加入到另外一个队列。
如何实现队列？链表
2.线程（Thread）
为什么要引入线程？
【案例】编写一个MP3播放软件。核心功能模块有三个：1）从MP3音频文件当中读取数据；2）对数据进行解压缩；3）把解压缩后的音频数据播放出来。
单进程的实现方法
1 main() 2 { 3 while(TRUE) 4 { 5 Read();//I/O 6 Decompress();//CPU 7 Play();//I/O 8 } 9 } 10 Read(){……}//读数据 11 Decompress(){……}//解压缩 12 Play(){……}//播放
问题：1）播放出来的声音能否连贯？2）各个函数之间不是并发执行，影响资源的使用效率；
多进程的实现方法
问题：进程之间如何通信，共享数据？
怎么来解决这些问题？
需要提出一种新的实体，满足一下特性：1）实体之间可以并发地执行；2）实体之间共享相同的地址空间；
这种实体就是：线程
进程 = 线程 + 资源平台
优点：1）一个进程可以同时存在多个线程；2）各个线程之间可以并发地执行；3）各个线程之间可以共享地址空间。
理解：为什么CPU寄存器的值和栈的值不能共享？
3.进程间通信
需要讨论的问题：
-进程间如何通信呢，如何来相互传递信息呢?
-当两个或多个进程在访问共享资源时，如何确保它们不会相互妨碍——进程互斥问题；
-当进程之间存在着某种依存关系时，如何来调整它们运行的先后次序——进程同步问题。
生活中的例子：教室的座位——互斥、两同学相约看电影——同步
进程间通信方式
-低级通信：只能传递状态和整数值（控制信息）
-高级通信：能够传送任意数量的数据
如何实现通信？能否共享内存单元（全局变量或共享缓冲区）？
进程间互斥
产生的原因：1）进程宏观上并发执行，依靠时钟中断来实现微观上轮流执行；2）访问共享资源。
竞争状态（race condition)：两个或多个进程对同一共享数据同时进行读写操作，而最后的结果是不可预测的，它取决于各个进程具体运行情况。
解决之道：在同一时刻，只允许一个进程访问该共享数据，即如果当前已有一个进程正在使用该数据，那么其他进程暂时不能访问。这就是互斥的概念。
（备注：例子有点问题？进程之间不可以共享数据！此例子不严谨）
实现互斥访问的四个条件
1）任何两个进程都不能同时进入临界区；
2）不能事先假定CPU的个数和运行速度；
3）当一个进程运行在它的临界区外面时，不能妨碍其他的进程进入临界区；
4）任何一个进程进入临界区的要求应该在有限时间内得到满足。
基于繁忙等待的互斥实现
1 #define FALSE 0 2 #define TRUE 1 3 #define N 2//进程的个数 4 int turn;//轮到谁？ 5 int interested[N];//兴趣数组，初始值均为FALSE 6 void enter_region(int process)//process=0或1 7 { 8 int other;//另外一个进程的进程号 9 other=1-process; 10 interested[process]=TRUE；//表明本进程感兴趣 11 turn=process;//设置标志位 12 while( turn=process&& interested[other]=TRUE); 13 } 14 void leave_region(int process) 15 { 16 interested[process] = FALSE;//本进程已离开临界区 17 }
Peterson算法解决了互斥访问的问题，而且不会相互妨碍，可以完全正常地工作。
分析：
第一种情况：
P0在执行完other=1-process;后时钟中断；P1正常执行
全局变量：
turn： interested：[0]（0） [1]（0）
局部变量（栈）：
P0——process：0；other：1——>P0时钟中断
P1——process：1；other：0——interested：[0]（0） [1]（1）；turn：1——while循环条件不成立（interested[0]等于0，不等于1），卡不住，P1往下执行——>然后P0继续执行；interested：[0]（1） [1]（1）；turn：0——while循环条件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下执行
——>P1进入，P0卡住
第二种情况：
P0在执行interested[process]=TRUE;后时钟中断；P1正常执行
全局变量：
turn： interested：[0]（0） [1]（0）
局部变量（栈）：
P0——process：0；other：1；interested：[0]（1） [1]（0）——>P0时钟中断
P1——process：1；other：0——interested：[0]（1） [1]（1）；turn：1——while循环条件成立（turn等于process等于1；interested[0]等于1；），P1卡住，P1不能往下执行——>然后P0继续执行；turn：0——while循环条件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下执行——>然后P1继续执行（在while处）；——while循环条件不成立（turn（0），不等于process（1）），P1卡不住，P1往下执行——>然后P0继续执行——while循环条件成立（turn等于process等于0；interested[1]等于1；），P0卡住，P0不能往下执行
——>P1进入，P0卡住
核心：时钟中断；
解决方法：一步步执行
小结：以上的各种方法，都是基于繁忙等待（busy waiting)的策略，都可归纳为一种形式：当一个进程想要进入它的临界区时，首先检查一下是否允许它进入，若允许，就直接进入了；若不允许，就在那里循环地等待，一直等到允许它进入。
缺点：1）浪费CPU时间；2)可能导致预料之外的结果（如：一个低优先级进程位于临界区中，这时有一个高优先级的进程也试图进入临界区）
问题步骤描述：
-一个低优先级的进程正在临界区中；
-另一个高优先级的进程就绪了；
-调度器把CPU分配给高优先级的进程；
-该进程也想进入临界区；
-高优先级进程将会循环等待，等待低优先级进程退出临界区；
-低优先级进程无法获得CPU，无法离开临界区。
解决之道：
-当一个进程无法进入临界区时，应该被阻塞起来（sleep）；
-当一个进程离开临界区时，需要去唤醒（wake up)被阻塞的进程；
-克服了繁忙等待方法的两个缺点（浪费CPU时间、可能死锁）。
现有的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许一个进程进入临界区。
新的进程互斥问题形式：两个或多个进程都想进入各自的临界区，但在任何时刻，只允许N个进程同时进入临界区（N≥1）。
如何解决？信号量PV操作
-1965年由著名的荷兰计算机科学家Dijkstra提出，其基本思路是用一种新的变量类型（semaphore)来记录当前可用资源的数量。
-semaphore的取值可正可负，正数表示当前空闲资源的数量，负数的绝对值表示正在等待进入临界区的进程个数。
-信号量是由操作系统来维护的，用户进程只能通过初始化和两个标准原语（P、V原语）来访问。初始化可指定一个非负整数，即空闲资源总数。
备注：原语就是函数
-P、V原语包含有进程的阻塞和唤醒机制，因此在进程等待进入临界区时不会浪费CPU时间；
-P原语：申请一个空闲资源（把信号量减1），若成功，则退出；若失败，则该进程被阻塞；
-V原语：释放一个被占用的资源（把信号量加1），若发现有被阻塞的进程，则选择一个唤醒之。
信号量和P、V原语的实现
信号量结构体类型的定义：
1 typedef struct 2 { 3 int count；//计数变量 4 struct PCB*queue；//进程等待队列 5 }semaphore;
P原语：申请一个资源
1 P( semaphore S) 2 { 3 --S.count；//表示申请一个资源； 4 if(S.count<0)//表示没有空闲资源； 5 { 6 该进程进入等待队列S.queue末尾； 7 阻塞该进程； 8 调用进程调度器；//OSSched(） 9 } 10 }
V原语：释放一个资源
1 V( semaphore S) 2 { 3 ++S.count；//表示释放一个资源； 4 if(S.count<=0)//表示有进程被阻塞； 5 { 6 从等待队列S.queue中取出一个进程； 7 把该进程改为就绪状态，插入就绪队列 8 } 9 }
Windows 2000
-CreateSemaphore(创建信号量）
-WaitForSingleObject(P操作）
-ReleaseSemaphore(V操作）
μCOS-Ⅱ
-osSemCreate（创建信号量）
-osSemPend（P操作）
-osSemPost(V操作）
备注：互斥信号量初始化为1
分析：PV原语为什么可以实现进程互斥访问？
原理：PV原语不会中断
思考步骤：如果P1执行P(mutex);；--S.count后count为0，if判断不成立，继续往下执行，进入临界区，发生了中断（此时P1为就绪队列）——>P2执行P(mutex);；--S.count后count为-1，if判断成立，P2进入阻塞队列；——>P3执行P(mutex);；--S.count后count为-2，if判断成立，P3进入阻塞队列——（此时就绪队列：P1；阻塞队列：P2——P3）
——>P1继续执行，V(mutex);；++S.count；后count为-1，if判断成立（把P2取出，阻塞改为就绪，P1就绪）——>P2继续执行（接着上回P操作中if条件的最后），进入临界区，然后V(mutex);；++S.count；后count为0，if判断成立（把P3取出，阻塞改为就绪，P1，P2就绪） ——>P3继续执行（接着上回P操作中if条件的最后），进入临界区，然后V(mutex);；++S.count；后count为1，if判断不成立，然后P3进入非临界区——>P1、P2进入非临界区
进程间的同步是指多个进程中发生的事件存在某种时序关系，因此在各个进程之间必须协同合作，相互配合，使各个进程按一定的速度执行，以共同完成某一项任务。
同步：合作。互斥：竞争。
只考虑基于信号量的同步问题。
考虑：（S初值为0）若先进程P1（先A，然后V(S)），S=1——>然后P2，P(S)，S=0，执行B——先A后B可以
（S初值为0）若先进程P2，P(S)，S=-1，卡住，不执行，P2阻塞——>然后执行P1（先A，在调用V(S)），S=0，唤醒B，执行B——先A后B可以
4.经典的IPC问题
1）生产者一消费者问题
2）哲学家就餐问题
3）读者一写者问题
用信号量来解决，主要问题：如何选择信号量，如何安排P、V原语的顺序。
1）生产者一消费者问题
两个进程（生产者和消费者）共享一个公有的、固定大小的缓冲区，生产者不断地制造产品，并把它放入缓冲区，而消费者不断地把产品取出来，并且使用它。要求这两个进程相互协调，正确地完成各自的工作。
问题分析
对于生产者进程：制造一个产品，当要送入缓冲区时，要检查缓冲区是否有空位，若是，才可将产品送入缓冲区，并在必要时通知消费者；否则等待；
对于消费者进程：当它去取产品时，先要检查缓冲区中是否有产品可取，若有，则取走一个，并在必要时通知生产者；否则等待。
这种相互等待，并互通信息就是典型的进程同步。
同时，缓冲区是个临界资源，因此，各个进程在使用缓冲区的时候，还是个互斥问题。
信号量的定义
semaphore BufferNum;//空闲的缓冲区个数，初值为N
semaphore ProductNum;//缓冲区当中的产品个数，初值为0
semaphore Mutex;//用于互斥访问的信号量，初值为1
1 main() 2 { 3 cobegin 4 producer()； 5 consumer()； 6 coend 7 }
生产者进程
1 void producer(void) 2 { 3 int item； 4 while(TRUE) 5 { 6 item=produce_item()；//制造一个产品 7 P(BufferNum);//是否有空闲缓冲区 8 P(Mutex)；//进入临界区 9 insert_item(item);//产品放入缓冲区 10 V(Mutex);//离开临界区 11 V(ProductNum);//新增了一个产品 12 } 13 }
消费者进程
1 void consumer(void) 2 { 3 int item; 4 while(TRUE) 5 { 6 P(ProductNum);//缓冲区中有无产品 7 P(Mutex)；//进入临界区 8 item=remove_item()//从缓冲区取产品 9 V(Mutex)；//离开临界区 10 V(BufferNum);//新增一个空闲缓冲区 11 consume_item(item)；//使用该产品 12 } 13 }
2）哲学家就餐问题
1965年，由Dijkstra提出并解决，后来逐渐成为该领域的一个经典问题，或者说，是一块试金石，用来试验新的进程同步方法的优劣。
每个哲学家的动作只有两种：进餐和思考。当一个哲学家感到饥饿时，他试图去获得他左边和右边的两把叉子（一次取一把，顺序无关），然后才能开始进餐。吃完以后，他需要把两把叉子放回原处，然后继续思考。
问题是：如何保证哲学家们的动作有序进行?如：不出现相邻者同时要求进餐，也不出现有人永远拿不到叉子。
方案一
1 #define N 5 //哲学家个数 2 void philosopher(int i)//哲学家编号：0-4 3 { 4 while(TRUE) 5 { 6 think()；//哲学家在思考 7 take_fork(i);//去拿左边的叉子 8 take_fork((i+1)%N);//去拿右边的叉子 9 eat()；//吃面条中.… 10 put_fork(i)；//放下左边的叉子 11 put_fork((i+1)%N)；//放下右边的叉子 12 } 13 }
问题：不正确，可能导致死锁。
方案二
1 semaphore mutex //互斥信号量，初值 2 void philosopher(int i)//哲学家编号i：0-4 3 { 4 while(TRUE) 5 { 6 think()；//哲学家在思考 7 P(mutex)；//进入临界区 8 take_fork(i)；//去拿左边的叉子 9 take_fork((i+1)%N)；//去拿右边的叉子 10 eat()；//吃面条中… 11 put_fork(i);//放下左边的叉子 12 put_fork((i+1)%N)；//放下右边的叉子 13 V(mutex)；//退出临界区 14 } 15 }
问题：互斥访问。正确，但每次只允许一人进餐
方案2的缺点：它把就餐（而不是叉子)看成是必须互斥访问的临界资源，因此会造成（叉子)资源的浪费。从理论上说，如果有五把叉子，应允许两个不相邻的哲学家同时进餐。
哲学家就餐问题的解答
思路（1）哲学家自己怎么来解决这个问题?
指导原则：要么不拿，要么就拿两把叉子。
-S1思考中…
-S2进入饥饿状态；
-S3如果左邻居或右邻居正在进餐，等待；否则转S4
-S4拿起两把叉子；
-S5吃面条…
-S6放下左边的叉子；
-S7放下右边的叉子；
-S8新的一天又开始了，转S1
思路（2）计算机程序怎么来解决这个问题?
指导原则：不能浪费CPU时间；进程间相互通信。
-S1思考中…
-S2进入饥饿状态；
-S3如果左邻居或右邻居正在进餐，进入阻塞状态；否则转S4
-S4拿起两把叉子；
-S5吃面条..…
-S6放下左边的叉子，看看左邻居现在能否进餐（饥饿状态、两把叉子都在），若能则唤醒之；
-S7放下右边的叉子，看看右邻居现在能否进餐，若能，唤醒之；
-S8新的一天又开始了，转S1
思路（3）怎么样来编写程序?
1.必须有一个数据结构，来描述每个哲学家的当前状态；
2.该数据结构是一个临界资源，各个哲学家对它的访问应该互斥地进行——进程互斥；
一个哲学家吃饱后，可能要唤醒它的左邻右舍，两者之间存在着同步关系——进程同步；
数据结构的定义
1 #define N 5//哲学家个数 2 #define LEFT (G+N-1)%N//第个哲学家的左邻居 3 #define RIGHT (i+1)%N //第i个哲学家的右邻居 4 #define THINKING 0//思考状态 5 #define HUNGRY 1//饥饿状态 6 #define EATING 2//进餐状态 7 int state[N];//记录每个人的状态 8 semaphore mutex;//互斥信号量，初值1 9 semaphore s[N];//每人一个信号量，0
函数philosopher的定义
1 void philosopher(int i)//i的取值：0到N-1 2 { 3 while(TRUE)//封闭式开发，一直循环 4 { 5 think(）;//思考中… 6 take_forks(i)；//拿到两把叉子或被阻塞 7 eat()；//吃面条中… 8 put_forks(i)；//把两把叉子放回原处 9 } 10 }
函数take_forks的定义
1 //功能：要么拿到两把叉子，要么被阻塞起来。 2 void take_forks(inti)//i的取值：0到N-1 3 { 4 P(mutex)；//进入临界区 5 state[i]=HUNGRY;//我饿了! 6 test(i)；//试图拿两把叉子 7 V(mutex)；/退出临界区 8 P(s[i])；//没有叉子便阻塞 9 }
函数test的定义
1 void test(int i)//i的取值：0到N-1 2 { 3 if(stateli]=HUNGRY &&state[LEFT]!=EATING &&state[RIGHT]!=EATING) 4 { 5 state[i]=EATING；//两把叉子到手 6 V(s[i])；//第i人可以吃饭了 7 } 8 }
函数put_forks的定义
1 //功能：把两把叉子放回原处，并在需要的时候，去唤醒左邻右舍。 2 void put_ forks(int i)//i的取值：0到N-1 3 { 4 P(mutex)；//进入临界区 5 state[i]=THINKING；//交出两把叉子 6 test(LEFT)；//看左邻居能否进餐 7 test(RIGHT)；//看右邻居能否进餐 8 V(mutex)；//退出临界区 9 }
3）读者一写者问题
问题描述：在一个航空定票系统当中，有很多个竞争的进程想要访问（读、写）系统的数据库。
访问规则是：在任何时候，可以允许多个进程同时来读，但如果有一个进程想要更新（写）该数据库，则其他的任何进程都不能访问，包括读者和写者。问题是：怎么样来编程实现读者和写者。
问题分析
任何时候“写者”最多只允许一个，而“读者”可以有多个：
-“读一写”是互斥的；
-“写一写”是互斥的；
-“读一读”是允许的；
基于读者优先策略的方法
假设读者来：
1)若有其它读者在读，则不论是否有写者在等，新读者都可以读（读者优先）：
2)若无读者、笃者，则新读者也可以读：
3）若无读者，且有写者在写，则新读者等待：
假设写者来：
1)若有读者，则新写者等待：
2）若有其它写者，则新写者等待：
3）若无读者和写者，则新写者可以写；
-需要设置一个计数器rc，用来记录并发运行的读者个数；
-对于各个读者而言，该计数器是一个临界资源，对它的访问必须互斥进行，因此设置一个互斥信号量S_mutex；
-对于各个写者而言、写者与所有的读者而言，数据库是一个临界资源，对它的访问必须互斥地进行，因此设置一个互斥信号量S_db。
读者——写者问题的一个解答
int rc=0；//并发读者的个数 semaphore S_mutex;//对rc的互斥信号量，初值1 semaphore S_db;//对数据库的信号量，初值1 void writer(void) { think_up_data()；//生成数据，非临界区 P(S_db)；//希望访问数据库 write_data_base()；//更新数据库 V(S_db)；//退出临界区 }
1 void reader(void) 2 { 3 P(S_mutex)；//互斥地访问计数器rc 4 rc++；//新增了一个读者 5 if(rc=1) P(S_db)；//如果是第一个读者… 6 V(S_mutex)；//退出对rc的访问 7 read_data_base()；//读取数据库的内容 8 P(S_mutex)；//互斥地访问计数器rc 9 rc--；//减少一个读者 10 if(rc=0) V(S_db);//如果是最后一个读者 11 V(S_mutex);//退出对rc的访问 12 use_data_read()；//使用数据，非临界区 13 }
测试几个例子：
RRW——R1进入，R2进入，W1在writer中P(S_db)被挡住
RWR——R1进入，W1在writer中P(S_db)被挡住，R2进入（体现了读者优先）
WRR——W1进入，R1在reader中if后的P(S_db)被挡住，R2在reader中P(S_mutex)被挡住
5.进程调度
在多道系统当中，往往有多个进程同时在内存中运行。在任何时刻，一个进程只可能是以下三种状态之一：
-运行状态：该进程正在CPU上运行，每个CPU上最多只能有一个进程在运行；
-就绪状态：进程已经就绪，随时可以运行；
-阻塞状态：如在某个信号量上被阻塞，等待I/O
与此相对应，操作系统会维护相应的状态队列。
要解决的问题
WHEN:何时分配CPU一调度的时机
WHAT:按什么原则分配CPU一调度算法
HOW:如何分配CPU一进程的上下文切换
何时调度？
1）当一个新的进程被创建时，是执行新进程还是继续执行父进程?
2）当一个进程运行完毕时；
3）当一个进程由于I/O、信号量或其他的某个原因被阻塞时；
4）当一个I/O中断发生时，表明某个I/O操作已经完成，而等待该I/O操作的进程转入就绪状态；
5）在分时系统中，当一个时钟中断发生时。
两种调度方式
不可抢占调度方式：一个进程若被选中，就一直运行下去，直到它被阻塞（I/O，或正在等待其他的进程），或主动地交出CPU。以上的情形1一3均可发生调度；
可抢占调度方式：当一个进程在运行时，调度程序可以打断它。以上的情形1-5均可发生调度。
进程切换
进程切换时需要做哪些事情？
保存CPU寄存器中的值！
调度算法（自己看）
-优先级算法（Priority Scheduling)：给每个进程设置一个优先级，然后在所有就绪进程中选择优先级最高的那个进程去运行；
-SJF就是一个优先级算法，每个进程的优先级是它的CPU运行时间（时间越短，优先级越高）；
-分为可抢占和不可抢占两种方式；各进程优先级的确定方式可分为静态和动态两种。
优先级的确定
-静态优先级方式
基本思路：在创建进程时确定进程的优先级，并保持不变直到进程结束；
缺点：高优先级的进程一直占用CPU，低优先级的进程“饥饿”。
-I/O繁忙进程：让其进入最高优先级队列，以及时启动/O操作。通常只需一个小时间片，即可处理完一次I/O请求，然后转入到阻塞队列。
-CPU繁忙进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。
第三章 死锁
安全状态与不安全状态
我们的目标：判断系统的当前状态是否安全。
如何来做?
程序=算法+数据结构
数据结构：如何来表示系统的当前状态?什么叫安全的状态?
算法：如何来判断系统的当前状态是否安全?
系统状态的表示
系统中有n个进程（P1到Pn)，资源类型个数为m：
-向量E=（E1，E2，E3…，Em)称为总的资源向量，Ei：表示系统中第i种类型的资源个数。例如：若第一种类型的资源为打印机，则E1=2表示系统中共有2台打印机；
-向量A=（A1，A2,A3,…,Am)称为空闲资源向量，Ai:表示第i种类型的资源中，尚未被占用的个数；
-矩阵C=（Cij)n*m称为当前分配矩阵，Cij表示进程，Pi所占用的类型为j的资源个数；
-矩阵R=（Rij)n*m称为请求矩阵，Rij表示进程Pi还需要的类型为i的资源个数。
举个例子：
安全状态与不安全状态
一个状态被称为是“安全的”，如果它满足以下的两个条件：
1）它自身不存在着死锁问题；
2）存在着某种调度顺序，使得即使在最坏的情况下（所有的进程突然间同时请求它们最大数目的资源，即矩阵R中的数值），每一个进程都能够顺利地运行结束。
在学习操作系统时总结了笔记，并分享出来，特别是蓝色和红色字体。有问题请及时联系博主：Alliswell_WP，转载请注明出处。