知识体系

自己回答：

1、为什么要引入进程？

并发性要求程序被切割成一小块一小块，在肉眼无法分辨的间隔中执行，以达到看似同时执行的效果。

2、什么是进程？进程由什么组成？

进程是一次执行的独立单位，是资源分配的最小单元，由程序段、相关数据段和PCB三部分组成。

3、进程是如何解决问题的？

首先申请一个空白的PCB，并向PCB中填写一些控制和管理进程的信息；然后由系统为该进程分配运行时所必需的资源，最后把该进程转入就绪态。

 

基本概念

进程状态

前三种是进程的基本状态。

运行态：在单处理机环境下，每个时刻最多只有一个进程处于运行态。.

就绪态：进程获得了除处理机外的一切所需资源，一旦得到处理机，便可立即运行。系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列， 称为就绪队列。

阻塞态：又称等待态。进程正在等待某一事件而暂停运行，如等待某资源为可用或等待输入/输出完成。即使处理机空闲，该进程也不能运行。

若资源不足(如内存空间)，则并不是创建失败，而是处于阻塞态，等待内存资源。创建态可以直接转为阻塞态！

进程通信

1、共享存储

在通信的进程之间存在一块可直接访问的共享空间，通过对这片共享空间进行写/读操作实现进程之间的信息交换。

2、消息传递

在消息传递系统中，进程间的数据交换是以格式化的消息为单位的。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。有直接和间接的方式。

3、管道

管道是指用于连接一个读进程和一个写进程以实现它们之间的通信的一个共享文件。以字符流方式进行读写。

处理机调度

1、高级调度/作业调度

按一定的原则从外存上处于后备状态的作业中挑选一个作业，给它们分配资源，属于内存与辅存之间的调度。对于每个作业只调入一次、调出一次。

2、中级调度/内存调度

其作用是提高内存利用率和系统吞吐量。为此，应将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起态。当它们已具备运行条件且内存又稍有空闲时，由中级调度来决定把外存上的那些已具备运行条件的就绪进程再重新调入内存，并修改其状态为就绪态，挂在就绪队列上等待。 

3、低级调度/进程调度

其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度。进程调度的频率很高，一般几十毫秒一次。

注：调度是指决定资源分配给哪个进程的行为，是一种决策行为；切换是指实际分配的行为，是执行行为。一般来说，先有资源的调度，然后才有进程的切换。

作业调度从外存的后备队列中选择一批作业进入内存， 为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒。

线程

引入进程的目的是为了更好地使多道程序并发执行，提高资源利用率和系统吞吐量；引入线程的目的是为了减小程序在并发执行时所付出的时空开销，提高操作系统的并发性能。

（由于有了线程，线程切换时，有可能会发生进程切换，也有可能不发生进程切换，平均而言每次切换所需的开销就变小了，因此能够让更多的线程参与并发，而不会影响到响应时间等问题。）

线程是最小的执行单元，与进程结构类似。线程自己不拥有系统资源，只拥有一点儿在运行中必不可少的资源，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。一个线程可以创建和撤销另一个线程，同一进程中的多个线程之间可以并发执行。由于一个进程内部有多个线程，若线程的切换发生在同一个进程内部，则只需要很少的时空开销。

分为用户级线程和内核级线程。

 

调度算法

调度准则（详情见王道课程）

1、CPU利用率

2、系统吞吐率：单位时间完成任务量

3、周转时间：从作业提交到作业完成所经历的时间

周转时间 = 作业完成时间 - 作业提交时间

带权周转时间：作业周转时间与作业实际运行时间的比值

4、等待时间：进程处于等处理机状态的时间之和

5、响应时间：从用户提交请求到系统首次产生响应所用的时间

先来先服务

短作业优先

优先级调度

自己设定的优先级。分为非剥夺式和剥夺式，静态和动态（可调整）。

一般情况下，系统＞用户，交互＞非交互，I/O＞计算。

高响应比优先调度

响应比 = （等待时间 + 要求服务时间）/ 要求服务时间

1、作业的等待时间相同时，要求服务时间越短，响应比越高，有利于短作业。

2、要求服务时间相同时，作业的响应比由其等待时间决定，等待时间越长，其响应比越高，因而它实现的是先来先服务。

3、对于长作业，作业的响应比可以随等待时间的增加而提高，等待时间足够长时，其响应比便可升到很高，从而也可获得处理机。因此，克服了饥饿状态，兼顾了长作业。

时间片轮转调度（适用于分时系统）

时间片轮转调度算法主要适用于分时系统。在这种算法中，系统将所有就绪进程按到达时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务的原则，但仅能运行一个时间片， 如100ms。在使用完-一个时间片后，即使进程并未完成其运行，它也必须释放出处理机给下一个就绪的进程，而被剥夺的进程返回到就绪队列的末尾重新排队，等候再次运行。

适当选择时间片大小非常重要。

多级反馈队列调度

1、设置多个就绪队列，并为各个队列赋予不同的优先级，第1级队列的优先级最高，第2级队列次之，其余队列的优先级逐次降低。

2、赋予各个队列中进程执行时间片的大小各不相同。在优先级越高的队列中，每个进程的运行时间片越小。例如，第2级队列的时间片要比第1级队列的时间片长1倍....第i+1级队列的时间片要比第i级队列的时间片长1倍。

3、一个新进程进入内存后，首先将它放入第1级队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；若它在一个时间片结束时尚未完成，调度程序便将该进程转入第2级队列的末尾，再同样按FCFS原则等待调度执行；若它在第2级队列中运行一个时间片后仍未完成，再以同样的方法放入第3级队列....如此下去，当一个长进程从第1级队列依次降到第n级队列后，在第n级队列中便采用时间片轮转的方式运行。

4、仅当第1级队列为空时，调度程序才调度第2级队列中的进程运行;仅当第1~(i-1)级队列均为空时，才会调度第i级队列中的进程运行。若处理机正在执行第i级队列中的某进程，这时又有新进程进入优先级较高的队列[第1~(i-1)中的任何一个队列]，则此时新进程将抢占正在运行进程的处理机,即由调度程序把正在运行的进程放回第i级队列的末尾，把处理机分配给新到的更高优先级的进程。

 

进程同步

临界资源：一次仅允许一个进程使用的资源

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

访问临界资源总共有四个步骤，依次是进入区、临界区、退出去、剩余区。

同步：直接制约关系，是指为完成某种任务而建立的两个或多个进程，这些进程因为需要在某些位置上协调它们的工作次序而等待、传递信息所产生的制约关系。

互斥：间接制约关系。当一个进程进入临界区使用临界资源时，另一个进程必须等待，当占用临界资源的进程退出临界区后，另一进程才允许去访问此临界资源。

四个重要的原则（后续设计中需要）：空闲让进，忙则等待，有限等待，让权等待。