十天玩转操作系统，做一个热爱学习的程序猿，重点讲解，每天进步一点点

       操作系统(OS)这门学科在计算机领域有着很重要的作用，作为计算机硬件和软件的临界者，对计算机发展有着很重要的意义，随着时代的不断发展，越来越多的操作系统进入大众视野，无论是大家耳熟能详的Windows、MAC，抑或是程序员口中经常念叨的Linux。除了电脑操作系统，手机中的鸿蒙、苹果、安卓也是大家关注的热点，因此要想在计算机领域有所造诣，操作系统是必须要了解掌握的一门学科，因此在这里借助平台，跟大家分享一下我学习操作系统的经验和笔记，用十天的时间来和大家梳理和整理这门学科，让我们一起探索其中的奥秘，享受知识带给我们的快乐吧！！！

调度

当有一堆进程任务要进行处理时，由于资源有限，就需要遵循某种规则来决定处理这些任务的顺序

• 高级调度（外存与内存之间的调度）面向作业
  按一定原则挑选作业分配内存等必要资源，建立相应进程，以使它们获得竞争处理机的权利
• 中级调度（外存与内存之间的调度）面向进程
  引入虚拟存储技术之后，暂时将不能运行的进程调至外存等待，提高内存利用率和系统吞吐量
  暂时调到外存等待的进程状态称为挂起状态（PCB不会一起调出，常驻内存，存放在挂起队列中）
  决定将哪个处于挂起状态的进程重新调入内存

挂起状态：就绪挂起、阻塞挂起
                                                                七状态模型

• 低级调度（内存与CPU之间的，又称“进程调度”）
  通过某种算法和策略从就绪队列中选取一个进程，分配其处理机

进程调度

需要进程调度的情况：

• 主动放弃
  进程正常终止
  运行过程中发生异常而终止
  进程主动请求阻塞（等待I/O）

• 被动放弃
  分给进程的时间片用完
  有更紧急的事需要处理
  有更高优先级的进程进入就绪队列

不能进程调度的情况：

• 处理中断的过程
• 操作系统内核临界区中的进程（如果是普通临界区是可以进行进程调度的）
• 原子操作过程中（原语）

进程调度方式

（1）非剥夺调度方式（非抢占式）
只允许主动放弃处理机，无法及时处理紧急的任务
（2）剥夺调度方式（抢占式）
优先处理更紧急的进程，也可实现让各进程按时间片轮流执行的功能（时钟中断）

进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程
1、对原来运行进程各种数据的保存
2、对新的进程各种数据的恢复
（如：程序计数器、程序状态字、各种数据寄存器等处理现场信息，一半保存到进程控制块）

进程调度、切换是有代价的

调度算法指标

1、CPU利用率：CPU“忙碌”的时间占总时间的比例
利用率=忙碌的时间/总时间
2、系统吞吐量：单位时间内完成作业的数量
系统吞吐量=总共完成了多少道作业/总共花费的时间
3、周转时间：作业被提交系统开始到作业完成为止的时间间断
周转时间=作业完成时间—作业提交时间
平均周转时间 = 各作业周转时间之和/作业数
带权周转时间 = 作业周转时间/作业实际运行的时间 =（作业完成时间 - 作业提交时间）/ 作业实际运行时间
平均带权周转时间 = 各个作业带权周转时间之和/作业数
4、等待时间：进程/作业处于等地啊处理机状态时间之和，时间越长，客户满意度越低
5、响应时间：从用户从提出请求到首次响应时间间隔

---

调度作为进程中很重要的一个环节，除了了解调度的含义之外，还需要对不同情况的进程采取不同调度方案，也就是我们常说的调度算法，也是进程环节很重要的一趴，要充分了解每种算法的思想和意义！

---

调度算法

（1）FCFS（先来先服务）
算法规则                              按照作业/进程到达的先后顺序进行服务
是否可抢占                          非抢占式
优缺点                                 对长作业有利，短作业不利
是否会导致饥饿                  不会

（2）SJF（非抢占式）
算法规则                              当前已到达且运行时间最短的进程优先得到服务
是否可抢占                          非抢占式
优缺点                                  “最短的”平均等待时间、平均周转时间
是否会导致饥饿                   会

（3）SJF（抢占式）
算法规则                              最短剩余时间优先算法（SRTF），改变就绪队列顺序。
是否可抢占                          抢占式
优缺点                                 最短的平均等待时间、平均周转时间
是否会导致饥饿                  会

---

抢占式的短作业/进程优先调度算法（最短剩余-时间优先，SRNT算法）的平均等待时间、平均周转时间最少。

---

（4）HRRN（高响应优先比）
算法规则                              计算各个作业/进程的响应比，响应比最高的作业/进程为其服务
                                            响应比=（等待时间+要求服务时间）/要求服务时间（>=1）
是否可抢占                          非抢占式
优缺点                                 综合考虑等待时间和运行时间（要求服务时间）
是否会导致饥饿                  不会

（5）RR（时间片轮转）
算法规则                              按照进程到达就绪队列顺序，轮流执行一个时间片（自行设定）。用于进程调度
是否可抢占                          抢占式（时钟中断控制）
优缺点                                 综合考虑等待时间和运行时间（要求服务时间）适合分时操作系统
是否会导致饥饿                  不会

---

时间片设置较大会自动退化成FCFS算法
时间片设置较小进程切换过于频繁，系统花大量时间来处理进程切换

---

（6）优先级调度算法
算法规则                             每个作业/进程有各自的优先级，调度时选择优先级最高的
是否可抢占                          抢占式、非抢占式
优缺点                                 优先级区分紧急程度、重要程度，适合实时操作系统。可以灵活调整对各种作业/进程偏好程度
是否会导致饥饿                  会

---

就绪队列按照不同的优先级组织，优先级高的进程在队头位置

• 静态优先级：创建进程时确定，之后一直不变
• 动态优先级：创建进程时有一个初始值，之后会根据情况动态调整

如何设置进程优先级？

• 系统进程优先级高于用户进程
• 前台进程优先级高于后台进程
• 操作系统更偏好I/O型进程（I/O繁忙型进程）

如何动态改变优先级？

• 等待时间过久，则适当提升其优先级
• 占用处理机运行时间长，适当降低优先级
• 进程频繁进程I/O操作，可适当提升优先级

---

（7）多级反馈队列调度算法
算法规则
1、设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
2、新进程到达时先进入第1级队列，按FCFS原则分配时间片，用完时间片未结束，则进程进入下一级队列队尾，若是最后一级队列，未执行完重新放回当前队列
3、只有K级队列为空时，才会为K+1级队头的进程分配时间片
是否可抢占                         抢占式
优缺点                                集合多个算法的优点
是否会导致饥饿                  会

---

被抢占处理机进程重新放回原队列队尾

---

同步与互斥

进程同步

直接制约关系
两个或多个进程在有时相互合作完成，但是需要规定一定的次序执行。

进程互斥软件

间接制约关系

do{entry section           //进入区            负责检查是否可进入临界区，若可进入，设置正在访问临界资源的标志（“上锁”），阻止其他进程进入临界区critical section         //临界区            访问临界资源exit section              //退出区            解除正在访问临界资源标志（“解锁”）remainder section   //剩余区            其他处理
}while(true)

临界区是进程中访问临界资源的代码段
进入区和退出区时负责实现互斥的代码段

1、空闲让进 临界区空闲可以允许请求进入临界区
2、忙则等待 已有进程占用，必须等待使用完进入
3、有限等待 有限等待时间内进程都可进入临界区
4、让权等待 进程不能进入临界区需要释放处理机

同步互斥的实现

（1）单标志法
int turn = 0; //turn表示当前允许进入临界区的进程号

如果P0进程一直不访问临界区，但是P1进程也无法访问，会造成临界区空闲
单标志法的主要问题：违背“空闲让进”原则

（2）双标志先检查法
bool flag[2]; //数组长度为进程个数
flag[0] = false;
flag[1] = false;

双标志先检查法主要问题是 ：违反“忙则等待”原则

（3）双标志后检查法
bool flag[2]; //数组长度为进程个数
flag[0] = false;
flag[1] = false;

双标志后检查法主要问题是：违背了“空闲让进”和“有限等待”原则，导致进程“饥饿”现象

（4）Peterson算法
bool flag[2];
int turn = 0;

1、主动争取
2、主动谦让
3、检查对方是否想用临界资源，且自己是否属于最后“谦让”

双标志后检查法主要问题是：未遵循“让权等待”原则

进程互斥硬件

（1）中断屏方法
利用“开/关中断指令”实现（与原语思想相同）
优点：简单、高效
缺点：不适用与多处理机；只适用于操作系统内核进程；

（2）TestAndSet指令（TSL指令）
硬件实现，C语言描述逻辑如下：

//布尔型共享变量lock表示当前临界区是否被加锁
//true表示已加锁，FALSE表示未加锁
bool TestAndSet(bool *lock){bool old;old=*lock;        *lock=true;return old;
}//以下是使用TSL指令实现互斥的算法逻辑
while(TestAndSet(&lock));//“上锁”并“检查”
临界区代码……
lock=false;//“解锁”
剩余区域代码……

缺点：不满足“让权等待”

（3）Swap指令（Exchange指令，XCHG指令）
硬件实现，C语言逻辑：

//Swap指令的作用是交换两个变量的值
Swap (bool *a,bool *b){bool temp;temp=*a;*a=*b;*b=temp;
}//以下是用Swap指令实现互斥的算法逻辑
//lock表示当前临界是否被加锁
bool old=true;
while(old==true)Swap(&lock,&old);
临界区代码……
lock=false；
剩余区代码……

缺点：不满足“让权等待”

---

      第三天的学习到这里就结束了，不知道小伙伴们收获如何呢？欢迎评论区交流学习，也恳请各位批评指正！！

      操作系统其实就是计算机中的一个大管家，这个大管家有着很多很厉害的角色（就像谍战片里面的大府中的老管家一样），因此学习操作系统这门课，就像是在欣赏一部谍战片，要想理解角色内涵，你就必须站在其角度去思考，思考其可能会遇到的危险以及应对策略（bug与bug的修复），这样你才能在凶险的代码江湖生存下来，成为一代英雄，留下你的印记，期待与各位在江湖的相遇，也希望大家能给作品一个三连！！

---

本文参考教材：王道考研——操作系统（配套PDF文件，点赞留言后私信我发你）
教材配套讲解视频：b站链接

---