进程定义
程序段、数据段、PCB组成进程实体，即进程，创建进程即创建PCB，撤销即撤销PCB（进程存在的唯一标志）
定义：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
进程组成：
| 存放 | 性质 | |
|---|---|---|
| PCB | 进程管理者（操作系统）所需数据 | 进程存在的唯一标志 |
| 程序段 | 要执行的程序代码 | |
| 数据段 | 执行过程中的各种数据 |
进程的状态与转化
基本状态：运行态，就绪态，阻塞态
进程转化的实质就是PCB的修改以及相关环境的改变（如某些寄存器的值的改变）
进程通信
三种方式：共享存储，消息传递（消息队列），管道通信
共享储存：基于数据结构的共享（低级）与基于存储区的共享（高级）
管道通信：半双工通信，同一时间段内只能实现单向的传输（双向通信需要设置两个
管道）
当管道满时，写进程的write（）被阻塞；
当管道空时，读进程的read（）被阻塞。
即没写满不能读，没空不能写
由于数据被读出后就被抛弃，所以读进程最多只有一个
消息传递：格式化的消息为单位通过“发送消息/接收消息”两个原语进行数据交换
//中间的调度内容被吃掉了，以后吐出来//
进程调度的时机
主动放弃与被动放弃进程
不能进行进程调度与切换的情况：
1、处理中断
2、在操作系统内核程序临界区中
3、在原子操作过程中
内核程序临界区与临界区并不相同
进程调度方式：1、非剥夺调度方式（非抢占方式）2、剥夺调度方式（抢占方式）
前者实现简单，但无法及时处理紧急任务
进程切换：指一个进程让出处理机，另一个进程占用处理机的过程
狭义的进程调度：从就绪队列中选中一个要运行的进程
广义的进程调度：选择一个进程并进行进程切换
进程切换过程：1、对原来运行进程各种数据保存
2、对新的进程各种数据的恢复
过于频繁的进程切换会导致系统的效率降低
调度算法的评价指标
- CPU利用率=忙碌的时间/总时间
- 系统吞吐量（单位时间完成作业的数量）=总共完成了多少道作业/总共花了多少时间
- 周转时间=作业完成时间-作业提交时间
- 平均周转时间=各作业周转时间之和/作业数
- 带权周转时间（大于等于1）=作业周转时间/作业实际运行的时间
- 平均带权周转时间=各作业带权周转时间之和/作业数
等待时间：
1、对于进程，等待时间指进程建立后等待被服务的时间之和
2、对于作业还要多考虑作业在外存中被等待调度的时间
响应时间：用户提交请求到首次产生响应所用的时间
调度算法
链表数据如下：
typedef struct thread {
int pid;//线程运行信号
int counter;
int nice;
struct thread* next;
}thread,*LinkList;
int algorithm(int counter,int nice) {
int priority = counter + 20 - nice;
return priority;
}
先来先服务（FCFS）
另一种思路——等待时间越久的优先
- 对于作业与对于进程，先来后到概念不同
- 对长作业有利，对短作业不利
补充与FCFS相似的FIFO：
void SCHED_FIFO() {
int Pid = 1;
LinkList H = (thread*)malloc(sizeof(thread));
LinkList T = H;
H->next = NULL;
while (1) {
int Counter = 0;
int Nice = 0;
scanf_s("%d %d", &Counter, &Nice);
//两个时间片之间增加线程
if (Counter != 0) {
LinkList p = (thread*)malloc(sizeof(thread));
p->counter = Counter;
p->nice = Nice;
p->pid = Pid;
Pid++;//为下一个线程线程pid自动加一做准备
//如果队列内暂时为空，那么线程先直接进入cpu运转
if (H->next == NULL) {
H->next = p;
p->next = NULL;
}
else {
for (LinkList p1 = H;; p1 = p1->next) {
if (p1->next->nice <p->nice) {
p->next = p1->next;
p1->next = p;
break;
}
else {
if (p1->next->next == NULL) {
p1->next->next = p;
p->next = NULL;
break;
}
}
}
}
}
//两个时间片之间不加线程,或者增加线程后
if (H->next != NULL) {
H->next->counter--;
printf("正在运行线程%d", H->next->pid);
printf("该线程还剩%d运行时间", H->next->counter);
//如果线程运行完毕
if (H->next->counter <= 0) {
LinkList p = H->next;
H->next = H->next->next;
free(p);
}
}
else {
printf("队列空，CPU空闲状态");
}
}
}
短作业优先（SJF）
短进程优先调度（SPF）
非抢占式，每次调度时选择当前已到达且运行时间最短的作业、进程
最短剩余时间优先算法（SRTN）
抢占式，每当就绪队列改变时，计算新到达进程的剩余运行时间与当前运行进程的剩余运行时间，由最短的来抢占。同时，在一个进程完成时也需要调度
- 对短作业有利，对长作业不利，可能产生饥饿现象（某些作业一直得不到运行)
在题目中，提到的“短作业/进程优先算法”默认是非抢占式的，引出概念：在所有进程都几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少
高响应比优先 （HRRN）
非抢占式，经典折中
- 等待时间相同时，要求服务时间短的优先（SJF优点）
- 要求服务时间相同时，等待时间长优先（FCFS优点）,避免饥饿
响应比=（等待时间+要求服务时间）/要求服务时间
时间片轮转（RR）
抢占式，轮流让就绪队列中的进程依次执行一个时间片（一般题目给出时间片大小）
- 下处理机时重新放回队尾，时间片不能太大也不能太小
- 公平，适用分时操作系统，不区分任务紧急度
void SCHED_RR() {
int Pid = 1;
LinkList H = (thread*)malloc(sizeof(thread));
LinkList T = H;
H->next = NULL;
while (1) {
int Counter = 0;
int Nice = 0;
scanf_s("%d %d", &Counter, &Nice);
//两个时间片之间增加线程
if (Counter != 0) {
LinkList p = (thread*)malloc(sizeof(thread));
p->counter = Counter;
p->nice = Nice;
p->pid = Pid;
Pid++;//为下一个线程线程pid自动加一做准备
//如果队列内暂时为空，那么线程先直接进入cpu运转
if (H->next == NULL) {
H->next = p;
p->next = NULL;
}
else {
for (LinkList p1 = H;; p1 = p1->next) {
if (algorithm(p1->next->counter, p1->next->nice) < algorithm(p->counter, p->nice)) {
p->next = p1->next;
p1->next = p;
break;
}
else {
if (p1->next->next == NULL) {
p1->next->next = p;
p->next = NULL;
break;
}
}
}
}
}
//两个时间片之间不加线程,或者增加线程后
if (H->next != NULL) {
H->next->counter--;
printf("正在运行线程%d", H->next->pid);
printf("该线程还剩%d运行时间", H->next->counter);
//如果线程运行完毕
if (H->next->counter <= 0) {
LinkList p = H->next;
H->next = H->next->next;
free(p);
}
//如果线程未运行完毕，接入链表尾
else {
//如果队列中只有一个线程，则继续分配时间片并运行
if (H->next->next != NULL) {
LinkList p = H->next;
H->next = H->next->next;
if (p1->next == NULL) {
p1->next = p;
p->next = NULL;
break;
}
}
}
}
}
else {
printf("队列空，CPU空闲状态");
}
}
}
优先级调度算法
抢占式，非抢占都有（注意看题），每个作业/进程都有各自优先级，选择优先级最高的
多级反馈队列调度算法
对其他算法的权衡
/多级调度算法有很多细节补充
然后进程同步和互斥也被吃了
死锁
对资源分配不合理容易发生
至少两个或两个以上的进程同时发生死锁（争夺资源而导致阻塞）
注意与“死循环”和“饥饿”的区别
必要条件：
- 互斥条件（必须相互争夺资源）
- 不剥夺条件（资源在未使用完之前不能被强行夺走）
- 请求和保持条件（已经保持了资源，但又请求资源）
- 循环等待条件（存在资源循环等待链）
处理策略：预防死锁，避免死锁，死锁的检测和解除(纯废话，但还是记一下)
银行家算法
安全序列：
按照这种序列分配顺序，就能顺利完成。
所以说安全序列可有多个
如果找不出任何安全序列，就进入不安全状态
如果能找出任何一个安全序列，就进入安全状态
算法：
每个进程声明一个m*n的最大需求矩阵Max与分配矩阵Allocation
另外留一个长度为m的一维数组Available
然后逐个对比并实验分配
- Available向量：系统中可利用的资源数目
- Max矩阵：每个进程对每种资源的最大需求
- Allocation矩阵：每个进程已分配的各类资源的数目
- Need矩阵：每个进程还需要的各类资源数
Need[i,j] = Max[i,j] - allocation[i, j]
死锁的检测和解除
资源剥夺法（挂起进程，容易饥饿）、撤销进程法、进程回退法（要记录进程历史信息）