进程

进程实体

代码段

PCB

进程标识符

外部标识符：
为方便用户对进程的访问，为每个进程设置一个外部标识符，通常由字母和数字组成
内部标识符：
为方便系统对进程的使用，在OS中又为进程设置了内部标识符，赋予每个进程唯一一个数字标识符，通常是一个进程序号

处理机状态

通用寄存器
PC
PSW
堆栈指针寄存器SP：指向用户自己堆栈的指针和指向内核栈的指针

进程调度信息

进程状态：指明进程当前的状态（阻塞、就绪、运行），作为进程调度、对换的依据
进程优先级：描述进程使用处理机的优先级别（用一个整数表示），优先级高的优先获得处理机
进程调度所需的其他信息：部分进程调度算法需要知道进程已等待CPU时间总和、进程已执行时间总和等
事件：进程由执行转态转换为阻塞状态所等待发生的事件（阻塞的原因）

进程控制信息

程序和数据的地址
即程序和数据的内存或外存起始地址，便于该进程执行时能从PCB中快速找到程序和数据
页表的起始地址（最后放在寄存器一定是物理地址）

进程同步和通信机制
比如消息队列指针、信号量等，它们可能会全部或部分放在PCB中

资源清单
列出了该进程在运行期间所需的全部资源（除CPU外）

链接指针
给出本进程所在队列中的下一个进程的PCB起始地址

进程映像

（建立在虚拟存储的基础上）

操作系统内核区

将操作系统内核映射到这个区域
区域内容对进程不可见

共享库的存储映射区

将共享库（如动态链接库DLL）映射到进程的虚拟地址空间部分，使多个进程能共享同一个物理内存副本的库，节省了内存资源
映射区域允许进程执行库中的代码，并访问库中的数据，就像这些代码和数据时进程自己的一部分一样

代码段

程序的二进制代码
代码段是只读的，可被多个进程共享

数据段

包括全局变量和静态变量

PCB

放在内核区

堆

用来存放动态分配的变量，通过调用malloc函数动态的向高地址分配空间

栈

用来实现函数调用，从用户空间的最大地址向低地址方向增长

为每个进程创建巨大的、私有的虚拟内存的假象，这种地址空间的抽象让每个程序好像拥有自己的内存，而实际上操作系统秘密地让多个地址空间复用物理内存

进程状态

就绪态：资源充分，只差CPU
阻塞态：主动阻塞，等待输入，将CPU让出
执行态

进程的控制

创建

过程：
分配进程标识符，申请PCB，为进程分配资源，为程序和数据分配必要的内存，初始化PCB，若就绪队列未满则插入
父进程创建子进程，子进程可以继承父进程所拥有的资源（打开的文件，分配的缓冲区）

执行：
父进程与子进程并发执行
父进程等待，直到其某个或全部子进程执行完毕

内存映像：
子进程是父进程的复制品（子进程与父进程具有相同的程序、数据、堆栈）
子进程加载另一个新程序

终止

当子进程被撤销时，应将从父进程那里获得的资源归还父进程
在撤销父进程时，也必须同时撤销所有的子进程

阻塞

进程调用阻塞原语block将自己阻塞，是一种主动行为
OS介入，停止执行该进程，将PCB中改为阻塞态，将PCB中改为阻塞态，将PCB插入阻塞队列，执行调度程序重新调度CPU

唤醒

将阻塞进程所期待的事件发生时，使用唤醒原语wakeup将等待该事件的进程唤醒
OS将被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态改为就绪，将该PCB插入就绪队列

进程通信

共享存储

通信进程之间有一块用于通信的共享空间

消息传递

以格式化的消息为单位，将通信的数据封装在消息中

管道通信

“管道”指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件，也叫pipe文件
管道不可以同时读写
管道同一时刻只能有一个方向的传输
管道满时写进程被阻塞，管道空时读进程被阻塞

线程

基本概念

每个线程类似于独立的进程，只有一点区别：它们共享进程的地址空间，从而能够访问相同的数据
线程只是作为独立调度和分派的单位，但是它们没有独立的地址空间，也没有掌握资源，完全依附于进程
每个线程都有自己独立的栈和栈指针，并且线程之间没有做保护措施，每个线程的堆栈可以被其他线程读写甚至清除，由一个线程打开的文件也可以被其他线程读写

实现方式

ULT

把整个线程实现部分放在用户空间中，内核看到的就是一个单线程进程

线程切换在用户空间实现，无需模式切换
每个进程可以选择自己专用的调度算法，对自己内部的线程进行调度和管理
ULT的实现与OS无关，因为ULT管理的代码会显式地出现在用户程序中，因此ULT甚至可以在不支持线程机制的OS平台上实现

内核只识别到一个进程，因此调度的对象是整个用户进程，每次只能给整个进程分配CPU，进程中只有一个线程能执行，无法发挥多处理器系统优势
进程中的某个线程发起IO系统调用，会导致进程中的所有线程全部被阻塞

KST

内核可识别到内核级线程，因此调度的对象是内核级线程，在多处理机系统中，每次可以给不同的内核级线程分配CPU，提高并行度
如果用户进程中的一个线程被阻塞，内核可以调度该进程内的其他线程上处理机，或者调度其他进程的线程

每次线程切换都需要CPU改变状态，开销较大
TCB存放在内核空间中，内存占用较大

CPU调度

进程调度

原理

进程调度是CPU在内核态下完成的
进程调度基于中断机制

方式

非抢占调度方式
正在执行的进程执行完毕或无法继续执行
正在执行的进程因提出IO请求而暂停执行
进程通信或同步过程中执行了某种原语操作（block原语）

抢占调度方式
优先级高可抢占处理机
短进程优先原则
时间片原则，各进程按照时间片运行，正在执行的进程的一个时间片用完后，停止该进程执行并重新放回就绪队列的末尾，然后将处理机分配给就绪队列中的下一个进程

调度时机

主动放弃

运行完毕，正常终止
运行过程中发生异常
发生事件，请求阻塞

被动放弃

进程时间片用完
有更高优先级进程进入就绪队列（抢占）
有更加紧急的事情需要处理

不可进程切换的情况

处理中断时
进程处于内核临界区时
执行原子操作时

调度目标

调度算法

先来先服务FCFS

按照作业/进程到达的先后次序进行调度
只能是非抢占式
对长作业有利，对短作业不利
有利于CPU繁忙型作业/进程，不利于IO繁忙型作业/进程

短作业优先SJF

(未说明就是非抢占式)

作业/进程越短，优先级越高，越先被调度
如果是抢占式SJF，作业/进程的剩余时间越短，优先级越高，越先被调度
平均等待时间和平均周转时间最优
对短作业有利，对长作业不利，甚至导致长作业饥饿
默认在估计运行时间相等时按照先后顺序服务

高响应比优先

响应比=（等待时间+要求服务时间）/要求服务时间
每次调度时选择响应比最高的作业投入运行
克服了长作业饥饿问题

优先级调度

按优先级调度

时间片轮转

所有就绪进程排成就绪队列，OS每隔一段时间就产生一次时钟中断，调度进程，将CPU分配给就绪队列首进程，令其执行一个时间片

多级队列调度

设置多个队列，将不同类型的进程分配到不同的就绪队列，每个队列实行不同的调度算法

多级反馈队列调度

结合了时间片调度和优先级调度算法，设置多个就绪队列，为每个队列赋予不同优先级
赋予了各个队列的进程运行时间片不同，优先级越高的队列里进程的时间片越小
每个队列采用FCFS算法
仅当1~i-1级队列为空，才调度i级，若CPU正在执行第i级队列中的某个进程时，有新进程进入优先级更高的队列，立即将正在执行的进程放回本级队列队尾，将CPU分配给新到的进程