操作系统上

1、操作系统的概念

操作系统(Operating System,OS)是指控制和管理整个计算机系统的硬件和软件资源，并合理地组织调度计算机的工作和资源的分配，以提供用户和其他软件方便的接口和环境(从下往上看)，他是计算机系统中最基本的系统软件(从上往下看)

从任务管理器可以看出操作系统对硬件和软件资源的分配

2、操作系统需要实现的功能

1. 操作系统作为系统资源的管理者需要实现的功能和目标

   补充：进程是一个程序的执行过程，执行前需要将该程序放到内存中，才能被CPU处理

   需要实现的功能和目标：

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

   目标：安全、高效

2. 操作系统作为用户和计算机硬件之间的接口(从下往上看)需要实现的功能

   用户接口：

   • 命令接口：允许用户直接使用

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

     

   • 程序接口：允许用户通过程序间接使用，由一组系统调用组成

   • GUI：图形用户接口

     • 用户可以通过使用形象的图形界面进行操作，不需要记忆复杂的指令 、参数。比如将文件拖拽到垃圾箱

   目标：方便用户使用

3. 操作系统作为最接近硬件的层次(从上往下看)需要实现的功能和目标

   功能和目标：实现对硬件机器的拓展

   没有任何软件支持的计算机称为裸机。在裸机上安装的操作系统可以提供资源管理功能和方便用户的服务功能，将裸机改造为功能更强、使用更方便的机器

   通常把覆盖了软件的机器称为扩充机器，又称为虚拟机

   

3、操作系统的四个特征

1. 四个特征：并发，共享，虚拟，异步。其中并发和共享是两个最基本的特征，二者互为存在的条件

2. 并发：指两个或多个事件在同一个时间间隔内发生。这些事件宏观上是同时发生的，但微观上是交替发生的。

   并行：指两个或多个事件在同一时刻同时发生

   操作系统的并发性：计算机系统中同时存在着多个运行着程序

   一个单核CPU同一时刻只能执行一个程序

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

   资源共享分为：互斥共享方式和同时共享方式

   • 互斥共享方式：系统中的某些资源，虽然可以提供给多个进程使用，但一个时间段内只允许一个进程访问该资源。比如：摄像头
   • 同时共享方式：系统中的某些资源，允许一个时间段内由多个进程同时对他们进行访问(此处的同时往往是宏观上的，微观上可能是交替访问，比如扬声器可以同时播放两个地方的)。比如：发送文件

4. 并发和共享的关系：互为存在的条件

   • 如果失去并发性，系统中只有一个程序正在执行，则共享性失去存在的意义
   • 如果失去共享性，如果提供vx和qq同时发送文件则不能实现，因为不能同时访问硬盘资源，也就无法并发

5. 虚拟：一个物理上的实体变为若干个逻辑上的对应物。物理实体是实际存在的，而逻辑上的对应物是用户感受到的(后续讲解)

   虚拟技术分为：空分复用技术(比如虚拟存储技术，一个电脑供4G运行内存，运行一个GTA需要4G内存，但我们能够同时运行GTA和其他软件)和时分复用技术(虚拟处理器，比如：我们同时运行多个程序)

   如果没有并发性，则一个时间段内只有一个程序运行，那么也就失去实现虚拟性的意义，没有并发性就谈不上虚拟性

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

   只有系统拥有并发性，才可能导致异步性

4、OS的运行机制和体系结构

1. 两种指令

   指令：就是让CPU能够识别、执行的最基本命令

   两种指令：

   • 特权指令：如内存清零指令，此指令不允许用户程序使用
   • 非特权指令：普通的运算指令

2. 两种处理器状态

   CPU如何判断当前是否可以执行特权指令？

   CPU有两种处理器状态(用程序状态字寄存器(PSW)中的某标志位来表示当前处理器处于什么状态，如0表示用户态，1表示核心态)

   • 用户态(目态)：此时CPU只能执行非特权指令
   • 核心态(管态)：特权指令和非特权指令都可执行

3. 两种程序

   • 内核程序：是系统的管理者，可以执行特权和非特权指令，运行在核心态
   • 应用程序：为了保证系统能够安全运行，普通应用程序只能执行非特权指令，运行在用户态

4. 操作系统的内核

   

   • 内核是计算机上配置的底层软件，是操作系统最基本、最核心的部分，实现操作系统的内核功能的程序就是内核程序

     

5. 操作系统的体系结构

   操作系统的体系结构分为大内核和微内核

   

小结：

5、中断

1. 当中断发生时，CPU立即进入核心态
2. 当中断发生后，当前运行的进程暂停运行，并由操作系统内核对中断进行处理
3. 对于不同的中断信号，会进行不同的处理

发生了中断，就意味着需要操作系统介入，开展管理工作。由于操作系统的管理工作(比如进程切换、分配I/O设备等)需要使用特权指令，因此CPU要从用户态转为核心态。中断可以使CPU从用户态切换为核心态，使操作系统获得计算机的控制权。有了中断才能实现多道程序并发执行

用户态 $\rightarrow$ 核心态：通过中断

核心态 $\rightarrow$ 用户态：执行一个特权指令，将程序状态字(PSW)的标志位设置为用户态

4. 中断的分类

   

5. 外中断的处理过程

   1. 执行完每个指令之后，CPU都要检查当前是否有外部中断的信号
   2. 如果检测到外部中断信号，则需要保护被中断进程的CPU环境(如程序状态字、程序计数器、通用寄存器)
   3. 根据中断信号类型转入相应的中断处理程序(此时进入核心态)
   4. 恢复原进程的CPU环境并退出中断，返回原进程继续往下执行

小结：

6、系统调用

1. 系统调用概念：系统调用是操作系统提供给应用程序使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务。
2. 应用程序通过系统调用请求操作系统的服务。系统中的各种共享资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作(如存储分配、I/O操作、文件管理等)，都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成，这样可以保证系统的稳定性和安全性，防止用户进行非法操作

3. 系统调用和库函数的区别

   

   库函数在应用程序和系统调用之间，在系统函数之上，内部有一些系统调用的封装

4. 系统调用的过程

   

小结：

7、进程

1. 进程的定义

   • 程序：就是一个指令序列

   • 进程实体：

     问题：在有了并发之后，在CPU中运行不止一个程序。在内存中放入多个程序，各个程序的代码、运算数据存放的位置不同，操作系统如何找到各个程序代码以及数据存储的位置？

     解决：系统为每个运行的程序配置一个数据结构，称为进程控制块 (PCB)，用来描述进程的各种信息(比如代码和数据存储的位置)

     为了方便操作系统管理、完成各程序并发执行，引入了进程、进程实体的概念

   • 进程实体(进程映像)的组成

     • PCB：操作系统通过PCB来管理进程，存储管理所需要的各种信息
     • 程序段：程序代码存放的位置
     • 数据段：程序运行时产生的数据存储的位置

     PCB的组成

     

   • 进程：是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。可以说进程是由PCB，程序段和数据段组成的。所谓创建进程就是创建PCB，撤销进程，就是撤销进程实体中的PCB。

   • 区别：进程实体是静态的，进程是动态的

   

2. 进程的组织

   • 一个系统中有很多个PCB，为了能够进行有效的管理，应该采取适当的方式将这些PCB组织起来

     

     • 链接方式

       

     • 索引方式

       

3. 进程特征

   • 动态性：进程是程序的一次执行过程，是动态的产生、变化和消亡的，是进程最基本的特征
   • 并发性：内存中有多个进程实体，各进程可以并发的执行
   • 独立性：进程是能够独立运行，独立获得资源、独立接收调度的基本单位
   • 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统需要提供进程同步机制来解决异步问题，进程是资源分配、接收调度的基本单位
   • 结构性：每个进程配置一个PCB。结构上看进程由PCB、程序段、数据段组成

小结：

8、进程的状态

1. 进程的基本状态

   进程是程序的一次执行，在这个执行过程中，有时进程正在被CPU处理，有时候等待CPU的服务，为了对各个进程进行管理，操作系统将进程划分为几种状态

   • 1、运行态(Running)：占有CPU，并在CPU运行(单核CP每次最多处理一个进程)
   • 2、就绪态(Ready)：已经具备运行条件，但由于没有空闲CPU，而暂时不能够运行(除了CPU以外，其他条件全部具备，比如获取打印机等)
   • 3、阻塞态(Waiting/Blocked)：因等待某一事件而暂时不能运行(比如：等待分配打印机、等待读取磁盘。CPU最昂贵的部件，为了提高CPU的利用率，需要先将其他资源分配到位，才能得到CPU的服务)
   • 4、创建态(New)：进程正在被创建，操作系统为进程分配资源、初始化PCB
   • 5、终止态(Terminate)：进程正在从系统中撤销，操作系统会回收进程拥有的资源、撤销PCB

   前三个是基本状态

2. 进程状态的转换

   

小结：

9、进程控制

1. 进程控制

   • 进程控制的主要功能就是对系统中的所有进程实施有效的管理，它具有创建新进程、撤销已有进程、实现进程状态转换

2. 如何实现进程控制

   

   问题：是否会发生从一个事件到另一个事件转换的时候出现中断，导致状态转移不完整？

   答：不会，进程控制是使用原语进行的

   • 用原语实现进程控制

     原语的特点是执行期间不允许中断，1只能一气呵成，这种不可被中断的操作就是原子操作

     原语使用"关中断指令"和"开中断指令"实现，开关中断权限非常大，所以只允许在核心态下执行特权指令

     

   • 进程控制相关的原语。无论哪个原语，要做的无非三类事情

     • 1、更新PCB中的信息(如修改进程状态标志、将运行环境保存到PCB、从PCB恢复运行环境)
       • a、修改进程状态标志
       • b、保存其运行环境
       • c、恢复运行环境
     • 2、将PCB插入合适的队列
     • 3、分配/回收资源

小结：

10、进程通信

1. 进程通信概念

   进程通信是指进程之间信息交换，进程是分配系统资源的单位，因此各进程拥有的内存地址空间相互独立

2. 进程通信方法

   为了保证安全，一个进程不能直接访问另一个进程的地址空间，但各个进程之间信息交换又是必须的，为了保证进程间的安全通信，操作系统提供了一些方法

   • 1、共享存储：操作系统在内存中开辟一个区域供进程间共同使用，两个进程对共享空间的访问必须是互斥的(一个操作时另一个不能够访问)。操作系统只负责提供共享空间和同步互斥工具(如P,V操作)。有两种共享存储的方式

     • 1、基于数据结构的共享：比如共享空间里只能放一个长度为10的数组。这种方式速度慢、限制多、是一种低级通信方式
     • 2、基于存储区的共享：在内存中划出一块共享存储区，数据的形式、存放的位置都由进程控制，而不是操作系统。这种方式速度更快，是一种高级通信的方式

   • 2、管道通信：

     

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

   • 3、消息传递：进程之间的数据交换以格式化消息为单位，进程通过操作系统提供的"发送消息/接收消息"两个原语进行数据交换

     

小结：

11、线程、多线程模型

1. 线程概念

   • 有的进程可能需要同时做很多事情，比如qq要发送文件、要视频，而传统的进程只能串行的执行一系列程序，为此引入线程来增加并发度。即将进程再细分为很多的线程。

   • 传统的进程是程序执行流的最小单位，引入线程后，线程是程序执行流的最小单位

   • 线程是一个基本的CPU执行单位，也是程序执行流的最小单位

   • 引入线程之后，不仅是进程之间可以并发，进程内各线程也可以并发，进一步提高了系统的并发度，使得一个进程内可以并发处理各种任务

   • 引入线程之后，进程只作为除CPU之外的系统资源的分配单元(比如打印机、内存地址空间是分配给进程的)

2. 引入线程之后的变化

   • 1、对于资源的分配、调度
     • 传统进程中、进程是资源分配和调度的基本单位
     • 引入线程之后，进程是资源分配的基本单位，线程是调度的基本单位
   • 2、对于并发性
     • 传统进程中，只能进程间并发
     • 引入线程之后，各线程间也能并发，提升了并发度
   • 3、对于系统开销
     • 传统进程间并发，需要切换进程的运行环境，系统开销大
     • 线程间并发，如果是同一进程内的线程切换，不需要切换进程环境，系统开销小
     • 引入线程后，系统的开销减小

3. 线程的属性

   • 1、线程是处理机调度的单位
   • 2、在多CPU的计算机中，各个线程可占用不同的CPU
   • 3、每个线程都有一个线程ID、线程控制块(TCB)
   • 4、线程也有就绪、阻塞、运行三种基本状态
   • 5、线程几乎不拥有系统资源，系统资源是分配给进程的
   • 6、同一进程的不同线程间可以共享进程的资源
   • 7、由于共享内存地址空间，同一进程中的线程间通信甚至无需系统干预
   • 8、同一进程中的线程切换，不会引起进程切换
   • 9、不同进程中的线程切换，会引起进程切换
   • 10、切换同进程内的线程，系统开销很小
   • 11、切换进程，系统开销大

4. 线程的实现方式

   • 1、用户级线程：由应用程序提供线程库实现

     • 所有的线程管理工作都是由应用程序负责(包括线程切换)

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

     • 在用户看来是有多个线程，在操作系统内核看来，并不意识到线程的存在(即用户级线程对用户不透明(不透明就是能看见)，对操作系统透明)

       

   • 2、内核级线程

     • 线程的管理工作是操作系统内核完成，因此线程调度、切换的工作都是由内核负责，所以内核级线程的切换必须要在核心态下完成

     • 对操作系统不透明

       

   • 3、支持用户级线程和内核级线程的系统中，可采用上述二者组合的方式：将n各用户及线程映射到m各内核级线程上(n > m)

     • 操作系统只看得见内核级线程，因此只有内核级线程才是处理机分配的单位

       

     • 由几个用户级线程映射到几个内核级线程可引出多线程模型

       • 1、多对一模型：多个用户级线程映射到一个内核级线程

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

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

       • 2、一对一模型：一个用户级线程映射到一个内核级线程

         优点：当一个线程被阻塞以后，别的线程还可以执行。多线程可以在多核处理机上执行

         缺点：一个用户进程会占用多个内核级线程，线程切换由操作系统内核完成，需要切换到核心态，因此线程管理成本高，开销大

       • 3、多对多模型：n个用户级线程映射到m个内核级线程(n > m)，每个用户进程对应m个内核级线程

         优点：集上面二者的优点，客服了他们的缺点

     小结：

     

12、处理机的调度

1. 处理机调度的概念：从就绪队列中按照一定的算法选中一个进程并将处理机分配给它运行，以实现进程的并发执行

2. 调度的三个层次：

   • 高级调度(作业调度)：按一定的原则从外存上处于后备队列的作业中选中一个或多个作业，给他们分配内存等必要资源，并建立相应的进程(建立PCB)，以使他们获得竞争处理机的权利。高级调度是外存和内存之间的调度，每个作业只调入一次，调出一次，作业调入时创建PCB，作业调出时撤销PCB。高级调度主要指的是调入问题，只有调入的时机是由操作系统来确定，调出必然是作业运行结束

   • 中级调度：

     挂起介绍：在引入虚拟存储技术以后，可以将暂时不能运行的进程调至外存等待，等它重新具备运行条件并且内存有空闲，再重新调入内存。这样做的目的是提高内存的利用率和系统吞吐量。暂时调到外存的进程状态为挂起状态，其中PCB不会被调到外存，而是会常驻内存，PCB记录进程数据。被挂起的进程PCB会被放到挂起队列中。

     中级调度就是决定将哪个处于挂起状态的进程重新调入内存，一个进程可能会多次调入，调出，所以中级调度发生的频率比高级调度高

     

   • 低级调度(进程调度)：按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，其频率很高，一般几十毫秒一次

   

小结：

13、进程调度的时机、切换与过程的调度方式

1. 进程调度的时机

   

2. 进程调度的方式

   • 非剥夺调度方式：又称非抢占方式。即，只允许进程主动放弃处理机。在允许过程中即便有更紧迫的任务到达，也不会放弃处理器

     特点：实现简单，系统开销小但是无法及时处理紧急任务，适合早期批处理系统

   • 剥夺调度方式，又称抢占方式。当一个进程正在CPU上执行的时候，如果有更加紧急的进程需要CPU，则立即暂停正在执行的，将CPU分给紧急的那个进程

     特点：可以优先处理紧急的，也可以让各进程按时间片轮流执行。适合分时操作系统、实时操作系统

3. 进程切换

   • 进程调度指的是从就绪队列中选中一个要执行的进程，这个进程可以是刚刚被暂停执行的进程，也可以是另一个进程，后一种情况就需要进程切换
   • 进程切换主要完成了：
     • 1、对原来运行进程各种数据的保存
     • 2、对新的进程各种数据的恢复(如：程序计数器、各种数据寄存器等，这些信息一般保存在进程控制块中)
   • 进程切换是有代价的，因此过于频繁的进行进程调度、切换，会使整个系统的效率降低

小结：

14、调度算法评价指标

1. CPU利用率：指CPU"忙碌" 的时间占总时间的比例
2. 系统吞吐量：单位时间内完成的作业的数量
3. 周转时间、平均周转时间、带权周转时间、平均带权周转时间
   • 周转时间：从作业被提交到系统开始，到作业完成为止的这段时间间隔。
     • 周转时间包括四个部分：高级调度时间、低级调度的时间、进程在CPU执行的时间、进程等待I/O操作完成的时间
     • 周转时间 = 作业完成时间 - 作业提交时间
   • 平均周转时间 = (各作业周转时间之和) / 作业数
   • 带权周转时间 = (作业周转时间 / 作业实际运行的时间) = (作业完成时间 - 作业提交时间) / 作业实际运行时间
     • 带权周转时间肯定是大于1的，带权周转时间与周转时间都是越小越好
   • 平均带权周转时间 = (各作业带权周转时间之和) / 作业数
4. 等待时间：指进程/作业处于等待处理机状态时间之和
   • 对于进程来说，等待时间就是进程建立以后等待被服务的时间之和，在等待IO完成期间进程也是在被服务的，所以不计入等待时间
   • 对于作业来说，等待时间为：建立进程后的等待时间 + 作业在外存后备队列中等待的时间
5. 响应时间：用户提交请求到首次产生响应所用时间

小结：

15、调度算法

1. 先来先服务算法(FCFS,First Come First Serve)

   • 算法规则：按照作业/进程到达的先后顺序进行服务
   • 用于作业/进程调度：
     • 作业调度：考虑哪个作业先到达后备队列
     • 进程调度：考虑哪个进程先达到就绪队列
   • 是否可抢占？非抢占式算法
   • 优缺点：
     • 优点：公平、算法实现简单
     • 缺点：排在长作业(进程)后面的短作业需要等待很长时间，带权周转时间很大，对短作业来说用户体验不好，即FCFS算法对长作业有利，对短作业不利
   • 是否会导致饥饿：不会

2. 短作业优先算法(SJF，Shortest Job First)

   • 算法思想：追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间
   • 算法规则：每次调度时选中最短的作业/进程优先得到服务(所谓最短，就是服务时间最短)
   • 用于作业/进程调度：可用于作业调度也可用于进程调度，用于进程调度时候称为"短进程优先(SPF，Shortest Process First)"
   • 是否可抢占？SJF和SPF都是非抢占式算法。但是也有抢占式的版本----最短剩余时间优先算法(SRTN，Shortest Remaining Time Next)，每当有进程加入的时候，就绪队列改变时就需要调度，如果新到达的进程剩余时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列
   • 优缺点
     • 优点：最短的平均等待时间、平均周转时间(SRNT)
     • 缺点：不公平。对短作业有利，对长作业不利。可能产生饥饿现象。另外，作业/进程的运行时间是由用户提供的，并不一定真实，不一定能做到真正的短作业优先
   • 是否会导致饥饿：会。如果源源不断的有短作业/进程到来，可能使长作业/进程长时间得不到服务，产生"饥饿"现象。如果一直得不到服务，就称为饿死

3. 高响应比优先(HRRN,Highest Response Ratio Next)

   • 算法思想：综合考虑作业/进程的等待时间和要求服务的时间
   • 算法规则：在每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程为其服务。响应比 = (等待时间 + 要求服务时间) / 要求服务时间
   • 用于作业/进程调度：可
   • 是否可抢占？非抢占式算法
   • 优缺点：综合考虑了等待时间和运行时间。等待时间相同时，要求服务时间短的优先(SJF优点)。要求服务时间相同时，等待时间长的邮箱(FCFS优点)。对于长作业来说，随着等待时间越来越长，其响应比也会越来越大，从而避免了长作业饥饿问题
   • 是否会导致饥饿：否

4. 上述算法一般适合用于早期的批处理系统

5. 时间片轮转算法(RR,Round - Robin)

   • 算法思想：公平的，轮流的为各个进程服务，让每一个进程在一定时间间隔内都可以得到响应
   • 算法规则：按照各个进程到达就绪队列的顺序，轮流的让各个进程执行一个时间片(如100ms)。若进程未在一个时间片内执行完毕，则剥夺处理机，将进程重新方法就绪队列队尾重新排队
   • 用于作业/进程调度：可用于进程调度
   • 是否可抢占：若进程未能在时间片内运行完，将被强行剥夺处理机使用权，因此时间片RR属于抢占式算法，由时钟装置发出时钟中断来通知CPU时间片已到
   • 优缺点：
     • 优点：公平；响应快，适用于分时操作系统
     • 缺点：由于高频率的进程切换，因此有一定的开销，不区分任务的紧急程度
   • 是否会导致饥饿：不会
   • 补充关于时间片的大小
     • 如果时间片太大，使得每个进程都可以在一个时间片内完成，则RR退化为FCFS调度算法，并且会增大进程的响应时间，因此时间片不能太大
     • 如果时间片太小，进程切换比较频繁，系统开销会增大

6. 优先级调度算法

   • 算法思想：随着分时操作系统的出现，越来越多的应用场景需要根据任务的紧急程度来决定处理的顺序
   • 算法规则：每个作业/进程有各自的优先级，调度时选择优先级最高的作业/进程
   • 用于作业/进程调度：都可
   • 是否可抢占：抢占式和非抢占式都有。对于非抢占式只需要在进程主动放弃处理机时进程调度即可，对于抢占式还需要在就绪队列变化时，检查是否会发生抢占
   • 优缺点：
     • 优点：用优先级区分紧急程度、重要程度，适用于分时操作系统，可灵活地的调整对各种作业/进程的偏好程度
     • 缺点：若源源不断的有高优先级进程到来，则可能会导致饥饿
   • 是否会导致饥饿：会
   • 补充
     • 根据优先级是否可以动态改变，可以将优先级分为静态优先级和动态优先级两种
       • 采用动态优先级，什么时候调整？
         • 如果进程在就绪队列中等待了很长时间，可以适当提升优先级
         • 如果进程占用处理机很长时间，可以适当降低其优先级
         • 如果一个进程频繁的进行I/O操作，可以适当提升其优先级
     • 如何合理的设置各类进程的优先级：
       • 系统进程优先级高于用于进程
       • 前台进程优先级高于后台进程
       • 操作系统更偏向I/O型进程(或称I/O繁忙型进程)，因为I/O设备可以和CPU并行工作。如果让I/O繁忙型进程优先运行，则I/O设备可以尽早投入使用

7. 多级反馈队列调度算法

   • 算法思想：对其他调度算法的折中权衡

   • 算法规则：

     • 1、设置多级就绪队列，各级队列优先级从高到低，时间片从小到大

     • 2、新进程到达时先进入第一级队列，按FCFS原则排队等待分配时间片，若用完时间片进程还没有结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾

     • 3、只有第k级队列为空时，才会为K + 1级队头的进程分配时间片

       

   • 用于作业/进程调度：用于进程调度

   • 是否可抢占式：抢占式算法。在k级队列的进程运行过程中，若更上级的队列中进入了一个新进程，则由于新进程处于优先级更高的队列中，因此新进程会抢占处理机，原来运行的进程放回k级队列队尾

   • 优缺点：上述算法优点的集合

   • 是否会导致饥饿：会，如果源源不断的有短进程到达，就会饥饿

8. 上面的三种更加适合于交互式系统

16、进程同步、进程互斥

1. 进程同步：

   • 同步也称为直接制约关系，它是指为完成某种任务而建立的两个或多个进程，这些进程为了完成某种任务，需要协调他们工作的次序。进程同步是为了结局进程异步的问题(进程异步是指：各并发执行的进程以各自独立的、不可预知的速度向前推进)。比如：管道通信中，写数据必须在读数据之前完成

2. 进程互斥

   • 临界资源：一个时间段内只允许一个进程使用的资源。比如摄像头，打印机、内存缓冲区等

     对于临界资源的访问，必须是互斥的进程。互斥，也称为间接制约关系

   • 进程互斥：当一个进程访问某临界资源的时候，另一个访问该临界资源的进程必须等待。等待当前访问临界资源的进程结束才可以访问

     对于临界资源的互斥访问可以分为四个部分

     • 1、进入区：负责检查是否可以进入临界区，如果可以进入，则设置正在访问临界资源的标志(上锁)，以阻止其他进程同时进入临界区
     • 2、临界区：访问临界资源的那段代码
     • 3、退出区：负责接触正在访问临界资源的标志(解锁)
     • 4、剩余区：做其他处理

   • 进程互斥需要遵循的原则：

     • 1、空闲让进。当临界区空闲的时候，可以允许一个请求进入临界区的进程立即进入临界区
     • 2、忙则等待。当已有进程进入临界区，其他试图进入临界区的进程必须等待
     • 3、有限等待。对请求访问的进程，应保证能在有限时间内进入临界区(保证不会饥饿)
     • 4、让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待

小结：

17、进程互斥的软件实现方法

1. 单标志法

   • 算法思想：当前有两个进程都要访问临界资源，在一个进程访问完临界资源以后会把使用临界区的权限转交给另一个进程。即：每个进程访问临界资源的权限只能被另一个进程赋予

   

   • turn表示当前允许进入临界区的进程号，也就是只有一个进程访问临界资源后，才会修改turn。这违背了空闲让进的原则，因为当P1进程想访问资源，需要P0进程先访问才行，而P0又不需要访问

2. 双标志先检查法

   • 算法思想：试着一个boolean类型的数组flag[],数组中的各个元素用来标志各进程想进入临界区的意愿，比如flag[0] = true，表示0号进程P0现在想要进入临界区。每个进程在进入临界区之前先检查当前有没有别的进程进入临界区，如果没有就把自身的标志位置为true，之后开始访问临界区

     

   • 按照152637....的顺序执行，P0和P1将会同时访问临界区，违背了忙则等待的原则。产生的原因：进入区的检查和上锁两个处理不是一气呵成的，检查后，上锁前可能会发生进程切换

3. 双标志后检查法

   • 算法思想：是双标志先检查法的改良版本，先上锁后检查

     

   • 按照152637顺序执行，P0和P1都无法进入临界区

   • 双标志发虽然解决了忙则等待的问题，但是又违背了空闲让进以及有限等待原则，因此会产生饥饿现象

4. Peterson算法

   • 算法思想：如果两个进程都想着进入临界区，可以让进程尝试让对方先使用临界区

     

   • 该算法解决了进程互斥问题，遵循了空闲让进，忙则等待，有限等待三个原则，但是没有遵循让权等待

18、进程互斥的硬件实现方法

1. 中断屏蔽方法

   • 利用"开/关中断指令"实现(与原语的实现思想相同，即在某进程开始访问临界区到结束访问为止都不允许被中断，也就不能发生进程切换，因此也就不会发生两个同时访问临界区的情况)
   • 优点：简单、高效
   • 缺点：不适用在多处理机，因为开关中断只是相对一个处理机来说的；只适用于操作系统内核进程，不适用于用户进程(开关中断权限比较大，需要在内核态)

2. TestAndSet指令

   • 简称TS或TSL指令，指令是用硬件实现的
   • 相比软件实现方法，TSL指令把上锁和检查操作用硬件的方式变成了一气呵成的原子操作
   • 优点：实现简单，适用于多处理机环境
   • 缺点：不满足让权等待

3. Swap指令

   • 也称为Exchange指令，或简称XCHG指令，也是用硬件实现，执行过程中不允许中断，只能一气呵成
   • 优点：实现简单，适用于多处理机环境
   • 缺点：不满足让权等待

4. Swap指令和Swap指令的区别

   在实现上，swap需要两个参数，不需要返回值，而test_and_set则是需要借助一个共享变量来实现互斥

进程互斥的实现方式：四种软件实现方式 + 三种硬件实现方式

19、信号量机制

1. 用户进程可以通过使用操作系统提供的一对原语来对信号量进行操作，从而很方便的实现了进程互斥、进程同步
2. 信号量就是一个变量(可以是一个整数，也可以是更复杂的记录型变量)，可以用一个信号量来表示当前系统中某种资源的数量。比如：系统中打印机的数量为1，可以设置一个初值为1的信号量
3. 原语：是一段特殊的程序段，使用开关中断实现，执行只能一气呵成，不可中断
4. 一对原语：wait(S)原语和signal(S)原语，这就是两个函数，信号量S就是传入的参数
5. wait、signal原语简称为P、V操作
6. 整型信号量
   • 用一个整数型变量作为信号量，用来表示系统中某种资源的数量。对信号量的操作只有三种：初始化、P操作、V操作
   • 
   • 问题：不满足让权等待
7. 记录型信号量
   • 是为了解决让权等待问题，用记录型数据结构表示信号量
   • 
   • 当资源已经分配完毕，进程会调用wait里面的block原语进行自我阻塞，由运行态到阻塞态，主动放弃处理机，因此该机制遵循了让权等待

小结：

20、用信号量机制实现进程互斥、同步、前驱关系

1. 信号量机制实现进程互斥

   • 设置互斥信号量，初值为1
   • 在临界区之前执行P，减少信号量的数目，并且小于0的时候需要阻塞
   • 在临界区之后执行V，释放资源

   对不同的临界资源需要设置不同的互斥信号量，并且P,V必须成对的出现

2. 信号量机制实现进程同步

   • 进程同步：即必须保证"一前一后"执行两个操作

   • 设置同步信号量S，初始值为0

   • 在前操作之后执行V(S)

   • 在后操作之前执行P(S)

     

3. 信号量机制实现前驱关系

   

   步骤：

   • 要为每一对前驱关系各设置一个同步变量
   • 在前操作之后对相应的同步变量执行V操作
   • 在后操作之前对相应的同步变量执行P操作

小结：

21、管程

1. 为什么要引入管程
   • 信号量机制存在的问题：编写程序困难、易出错
2. 管程的定义和基本特征
   • 管程作用：实现进程同步与互斥
   • 管程的组成：(类似类)
     • 共享的数据结构
     • 对数据结构操作的一组过程(函数)
     • 对共享数据设置初始值
     • 管程有一个名字
   • 管程的基本特征
     • 管程中定义的数据结构，只能被管程中定义的过程访问
     • 每次仅允许一个进程在管程内执行某个内部过程