进程
进程的组成
进程由程序控制块（PCB）、程序段、数据段组成。
程序控制块（PCB）：包含操作系统对其进行管理所需的各种信息，如进程描述信息、进程控制和管理信息、资源分配清单和处理机相关信息。
程序段：程序代码存放的位置。
数据段： 程序运行时使用、产生的运算数据。如全局变量、局部变量、宏定义的常量就存放在数据段内。
进程的组织形式
进程的特征
- 动态性： 进程的最基本的特征， 进程是程序的一次执行过程， 是动态的产生、变化和消亡。
- 并发性：内存中由多个进程实体，各进程可并发执行。
- 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位。
- 异步性：各个进程按各自独立的、不可预知的速度向前推进，操作系统要提供进程同步机制来解决异步问题。
- 结构性：每个进程都会配置一个PCB。结构上看，进程有程序段、数据段和PCB组成。
线程
线程概念
让一个进程内可以并发处理多个任务（如QQ视频、文字聊天，发送文件）， 让进程并发成为了可能。
线程是一个最基本的CPU执行单元，是程序执行流的最小单位。
线程引入后的变化
进程是资源分配的基本单位，线程是调度的基本单位。
线程让进程内部也能并发执行，提高了并发度。
如果同一个进程内的线程切换，不需要切换进程环境，系统开销小。
线程属性
(1) 同一进程的不同线程间共享进程的资源。由于共享内存地址空间，同一进程中线程间通信甚至不 需系统干预。
(2) 每个线程都有一个线程ID，线程控制块（TCB）。
(3) 线程几乎不拥有系统资源。
(4) 多CPU计算机，各个线程可占用不同的CPU。
(5) 同一个进程的线程切换，不会引起线程切换。不同进程中的线程切换回引起线程切换。切换进程内的线程由于不需要切换进程环境，系统开销小。
线程实现方式
用户级线程
用户级线程由程序通过线程库实现， 线程管理工作都是由应用程序负责（包括线程切换）
用户线程对用户不透明，对操作系统透明。
注：在计算机中，从某个角度看不到的特性称该特性是透明的，操作系统看不到用户线程，所以 对操作系统是透明的。
内核级线程
内核级线程的管理工作是由操作系统内核完成， 线程调度、切换等工作都是由内核负责， 内核线程必须需要在核心态下才能完成。
组合方式
在同时支持用户线程和内核线程的系统中，可以采用二者组合的方式，将n个用户线程映射到m个内核线程上（n≥m）。
由于操作系统只看得见内核级线程，所以内核级线程才是处理机分配的单位。
所以对于上图，只有两个内核级线程，所以即使在4核处理机的计算机上运行，也最多只能被分配到 两个核，最多只能有两个用户线程并行执行，因为内核级线程才是处理机分配的单位。
处理机调度和进程调度
处理机调度
从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程的并发执行。
高级调度（作业调度）
高级调度是外存与内存之间的调度。
作业调入时会建立相应的 PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来 确定，但调出的时机必然是作业运行结束才调出。
中级调度（内存调度）
在引入虚拟存储技术之后，可以将暂时不能运行的进程调至外存等待，等它重新具备了运行条件且内存又稍有空间时，再重新调入内存。
这样做是为了提高内存利用率和系统吞吐量。
暂时调到外存等待的进程状态为挂起状态，但是进程的PCB不会一起调到外存，而是会常驻内存。 PCB中会记录进程数据在外存中的存放位置，进程状态等信息，操作系统通过内存的PCB来保持对各 个进程的监控、管理。被挂起的进程PCB会被放到挂起队列中。
中级调度（内存调度） 就是按照某种规则，从挂起队列中选择合适的进程将其数据重新调回内存
一个进程可能会被多次调出、调入内存。因此中级调度发生的频率比高级调度更高
挂起和阻塞的区别： 两种状态都是暂时不能获得CPU的执行权，但是挂起状态是将进程映像调到外存去，而阻塞态下 进程映像还在内存中。
低级调度(进程调度)
其主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。
进程调度
进程调度的时机
进程主动放弃处理机
- 进程正常终止
- 运行过程中发生异常而终止
- 进程主动请求阻塞（如等待I/O）
进程被动放弃处理机
- 进程时间片用完
- 有更紧急的任务需要处理
- 有更高优先级的进程进入就绪队列
不能进行调度与切换的情况：
- 在处理中断的过程
- 进程在操作系统的内核程序临界区，但是在普通临界区可进行调度、切换
- 在原子操作过程中
进程调度的方式
非剥夺调度方式，又称非抢占式。
剥夺调度方式，又称抢占式。
进程的切换与过程
(1) 对原来运行的进程各种数据的保存。 (2) 对新的进程各种数据的恢复（如程序计数器、程序状态字、各种数据寄存器等处理机线程信 息，这些信息都是保存在程序控制块PCB中）。
进程的切换是有代价的，因此如果进程切换调度过于频繁的话，必然会使整个系统的开销 过大，效率降低。因为系统大部分时间都花在进程切换上，真正用于执行进程的时间少。
调度算法的评价指标
CPU利用率
\[CPU利用率 = \frac{忙碌时间}{总时间}\]系统吞吐量
\[系统吞吐量 = \frac{总共完成了多少道作业}{总共花了多少时间}\]周转时间
\[作业周转时间 = 作业完成时间 - 作业提交时间\] \[平均周转时间 = \frac{各作业周转时间之和}{作业数}\] \[带权周转时间 = \frac{作业周转时间}{作业实际运行时间}\] \[平均带权周转时间 = \frac{各作业带权周转时间之和}{作业数}\]等待时间
等待时间：指进程或作业处于等待处理机状态时间之和。
平均等待时间：各个进程/作业等待时间的平均值。
响应时间
响应时间：指从用户提交请求到首次产生相应所用的时间。
进程调度算法
进程的调度方式有两种：非剥夺调度方式（非抢占式）和剥夺调度方式（抢占方式）。
先来先服务算法（FCFS,First Come First Service）
短作业优先算法（SJF,Shortest Job First）
非抢占式的短作业优先调度算法
短作业/进程优先调度算法：每次调度时选择当前已到达且运行时间最短的作业/进程。
抢占式的短作业优先调度算法——最短剩余时间优先算法(STRN,Shortest Remaining Time Next)
最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程的所需的运行时间比当前运行的进程剩余时间更短，则由新进程抢占处理机，当前运行进程重新回到就绪队列。 此外，当一个进程完成时也需要调度。
高响应比优先（HRRN,Highest Response Ratio Next）算法
非抢占式的调度算法
响应比 = （等待时间 + 运行时间）/ 运行时间
时间片轮转调度（RR，Round_Robin）
不会导致饥饿
由于进程不能在时间片内运行完，就会被强行剥夺处理机的使用权，因此时间片轮转算法属于抢占式 的算法。由时钟装置发出的时钟中断来通知CPU时间片已到。
优先级调度算法
会导致饥饿
非抢占式优先级调度算法
非抢占式优先级调度算法：当前进程主动放弃处理机时发生调度，每次调度时选择当前已到达且优先级最高的进程。
抢占式优先级调度算法
多级反馈队列调度算法
算法规则：
- 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
- 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若时间片用完进程还 没未结束，则进程进入下一级队列队尾。如果此时已经是最下级的队列，则重新放回最下级队列 队尾。
- 只有第k级队列为空时，才会为k+1级队头的进程分配时间片。
- 被抢占处理机的进程将重新放回原队列队尾。
0时刻，P1到达第一级队列，获取时间片后开始执行。
1时刻：P2进程进入第1级队列，同时P1时间片用完，P1进程没有结束，所以P1进入第2级队列 的队尾，P2开始上处理机运行。
2时刻：P2的时间片用完，P2也没有结束，所以P2进入第2级队列的队尾。
由于此时第1级队列是空的，所以第2级队列的队头获得时间片开始执行，级P1开始执行。
4时刻：P1的时间片用完，P1未结束，进入下一级队列，同时P2进程获取时间片开始执行。
5时刻：P3进程进入第1级队列，但是此时P2进程的时间片还没有用完。由于第1级队列的优先 级高，所以P3会抢占时间片，P2会进入同级队列即第2级队列的队尾等待。P3获取时间片开始 执行
6时刻：P3时间片用完，并且P3也运行结束退出。
此时第1级队列中又没有进程了，所以第2级队列中的队头即P2进程又获得了时间片开始执行。
8时刻：P2进程时间片用完，同时P2进程结束退出。
P2进程退出后，只有P1一个进程在第3级队列中，所以P1进程获取时间片运行，P1用完一个时 间片后，此时P1已经在最底层队列，所以它会被重新放到该级队列的队尾。
最后，P1再次获取时间片运行结束退出。
进程同步、互斥及实现方法
进程同步
回顾进程的特征： 动态性、并发性、异步性、独立性、结构性
由于并发性和异步性，需要进程同步机制。
进程互斥
临界资源：是指一个时间段内只允许一个进程使用的资源。
对临界资源的访问，必须互斥的进行。
临界区是进程访问临界资源的代码段。
进入区和退出区是负责实现互斥的代码段。
为了实现对临界资源的互斥访问，同时保证系统的整体性能，需要遵循以下原则：
- 空闲让进。当临界区空闲时，可以允许一个请求进入临界区的进程立即进入临界区。
- 忙则等待。已有进程进入临界区时，其他试图进入临界区的进程必须等待。
- 有限等待。对请求访问的进程，应保证能在有限的时间内进入临界区（保证不会饥饿）。
- 让权等待。当进程不能进入临界区时，应立即释放处理机，防止进程忙等待。
进程互斥的软件实现方法
单标志法
两个进程在访问完临界资源区后会把使用临界区的权限转交给另一个进程，即每个进程进 入临界区的权限只能被另一个进程赋予。
turn的初始值为0，则刚开始只允许0号进程进入临界区。
若P1先上处理机，则会一直循环，直到P1进程的时间片用完，发生调度，P0进程开始执行。
如果刚开始允许进入临界区的是P0进程， 但是P0进程一直不访问临界区，从而导致P1进程也一直无法访问临界区。所以单标志法存在的问题 就是：违背了空闲让进原则。
双标志先检查法
设置一个布尔类型的数组flag[]，数组中的各个元素用来标记各进程想进入临界区的意 愿，每个进程进入临界区之前先检查当前有没有别的进程想进入临界区，如果没有，则把自己对应的 标志flag[i]设为true，之后开始访问临界区。
程并发访问时，如果按照①⑤②⑥⑦…的顺序执行，P0和P1进程将会同时访问临界区。所以双标志先 检查法的主要问题是：违反了忙则等待的原则。
原因在于：进入区的检查和上锁两个处理不是一气呵成的。检查后和上锁前可能发生进程切换。
双标志后检查法
双标志先检查法的改版。前一个算法先检查后上锁，该算法先上锁后检查。
如按照①⑤②⑥…顺序执行，P0和P1进程都无法进入临界区。因此，双标志后检查法虽然解决了忙则 等待的问题，但是又违背了空闲让进和有限等待的原则，会因各进程长期无法访问临界资源而产生饥饿现象。
Peterson算法
对于双标志后检查法中，如果两个进程都争着进入临界区，那可以让进程尝试 “孔融让梨”，主动让对方先使用临界区。
Peterson算法可以很好的解决了前面3中算法的问题，无论何种顺序都可以保证同一个时刻只有一个 进程访问临界区。但是当一个进程访问临界区时，另一个进程不会释放处理机，会一直循环等待条件 满足访问临界区，违背了让权等待的原则。
进程互斥的硬件实现方法
中断屏蔽方法
利用“开/关中断指令”实现，与原语的实现思想相同
优点：简单、高效。
缺点：不适用于多处理机；只适用于操作系统内核进程，不适合用户进程（因为开/关中断指令只能 运行在内核态）。
TestAndSet（TS指令/TSL指令）
TSL指令是用硬件实现的，执行的过程中不允许被中断，只能一气呵成。下面是C语言描述的逻辑：
1
2
3
4
5
6
7
8
9
10
11
12
13
// 布尔型共享变量 lock 表示当前临界区是否加锁
// true 表示枷锁，false 表示未加锁
bool TestAndSet (bool *lock)
{
bool old; old = *lock; //old用于存放lock原来的值
*lock = true; // 无论之前是否加锁，都将lock设为true
return old; // 返回lock原来的值
}
// 以下是使用 TSL 指令实现互斥的算法逻辑
while(TestAndSet (&lock)); // 上锁并检查，
临界区代码...
lock = false; // "解锁"
剩余区代码...
相比于软件实现方法，TSL指令把上锁和检查操作用硬件的方式变成原子操作。
优点：实现简单，适用于多处理机环境。
缺点：违背让权等待的原则，暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致 忙等
Swap指令（XCHG指令）
Swap指令也是用硬件实现的，执行过程不能中断。以下是用C语言描述其逻辑：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//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; // "解锁"
剩余区代码...
逻辑上看，Swap指令和TSL没有多大的区别，都是先记录下临界区是否已经被上锁（记录在old变量 上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界 区上锁，则可跳出循环，进入临界区。
优点：实现简单，适用于多处理机环境。
缺点：违背让权等待的原则，暂时无法进入临界区的进程会占用CPU，从而导致忙等。
