操作系统（二）进程管理（进程同步与死锁）

CPU调度策略

任务调度策略的三个基本准则

  • 任务周转时间：从新建到完成的时间
  • 任务响应时间：从提交请求到首次响应的时间（前台任务关心）
  • 系统吞吐量：一段时间内系统能完成的任务数

调度算法

  1. 先来先服务

  2. 最短作业优先调度：不可抢占，平均周转时间短（作业运行时间只能近似给出）

  3. 最短剩余时间有限：最短作业优先的可抢占版本

  4. 时间片轮转调度：保证响应时间

    时间片设得太短会导致过多的进程切换，降低了CPU效率；设得太长会引起对短作业的交互请求的响应时间变长

  1. 多级反馈队列调度：动态调整任务类型（近期多IO可能为前台任务，无IO时间片结束未完成可能为后台大任务）

    运行流程

    1. 设置多级就绪队列，各级队列优先级从高到低，时间片从小到大
    2. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。 若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回最下级队列队尾
    3. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片

调度算法比较

其他
  1. IO占比越大，任务优先级越高

进程同步与互斥

实现临界区互斥的基本方法

软件实现

Peterson算法：访问临界区前判断其他进程是否要用，要用则循环等待；等其他进程使用完后访问临界区

硬件实现

  1. 开关中断：只适用于单处理机，可以使得一个处理机内任务不中断。如果多处理机要实现互斥需要总线支持
  2. TestAndSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#define LOCKED 1
volatile int lock = 0;
void Critical() {
     while (TestAndSet(&lock) == 1);
     critical section // only one process can be in this section at a time
     lock = 0 // release lock when finished with the critical section
}

// 原子操作
int TestAndSet(int* lockPtr) {
    int oldValue;
    oldValue = *lockPtr;
    *lockPtr = LOCKED; //不管原来有没有上锁，先加锁
    return oldValue; //返回本来是否上锁
}

信号量

记录型信号量支持让权等待（while判断循环的都不是让权等待）

退出临界区的进程负责唤醒阻塞态进程（区别于while判断循环的自发进入临界区）

1
2
3
4
5
struct semaphore
{
  int value; // value of block_process or free resource
  PCB *queue; // process queue wait on sem
};
1
2
3
4
5
6
7
8
9
10
11
12
13
void P(semaphore s)
{
  s.value--;
  if (s.value < 0)
  	sleep_on(s.queue);
}

void V(semaphore s)
{
  s.value++;
  if (s.value <= 0) // release one wake_up one(唤醒阻塞队列的队头任务)
  	wake_up(s.queue);
}

生产者/消费者模型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// use semaphore
semaphore empty = BUFFER_SIZE; // count of empty size
semaphore full = 0; // count of resource in space
semaphore mutex = 1; // prevent change to space

void producer()
{
  P(empty); //确保有空间
  P(mutex);
  buffer[in] = item;
  in = (in + 1) % BUFFER_SIZE;
  V(mutex);
  V(full);
}

void consumer()
{
  P(full); //确保有东西
  P(mutex);
  item = buffer[out];
  out = (out + 1) % BUFFER_SIZE;
  V(mutex);
  V(empty);
}

读者/写者模型

读者优先
读写公平

哲学家进餐问题

各哲学家互斥得拿筷子，即同一时间至多有一个哲学家拿筷子阻塞

死锁

死锁的四个必要条件

  • 互斥：资源不能被共享，一个资源每次只能被一个进程使用
  • 不可剥夺：进程已获得的资源，在未使用完之前，不能强行剥夺
  • 请求与保持：一个进程因请求资源而阻塞时，对已获得的资源保持不放
  • 循环等待：若干进程之间形成一种头尾相接的循环性资源等待关系

死锁预防（不会发生死锁）

破坏“请求与保持”：一次性申请进程所需的所有资源

破坏“循环等待”：资源按顺序申请（其实达不到，没法预测程序走的分支）

缺点：

  • 需要预先计算程序要请求的资源
  • 可能很久以后才使用的资源早早地预留下来，造成资源的浪费

死锁避免（拒绝某些资源请求）

每次申请资源都要判断是否出现死锁的危险，如果有危险就拒绝这次请求

通过银行家算法计算安全序列，充分性算法，完全避免死锁

算法优先分配给能满足进程所需最大资源量的进程，一次分配所有所需要的所有资源

缺点：

  • 每次资源请求发生就要计算，且时间复杂度不小（时间复杂度O(mn^2)，m为资源种类，n为进程数）
  • 需要已知进程执行完成所需的资源总数

银行家算法（‼️）

  1. 判断请求是否小于所需资源
  2. 判断请求是否小于当前系统资源量
  3. 尝试分配，判断能否找出安全序列
  4. 若能找到则分配，若不能找到则不分配

求安全序列

最大资源组A，已分配组B，还需资源组C（C=A-B）

系统资源组P

  1. 查看还需 资源A 小于等于 系统资源P 的进程
  2. 一次分配后，将已分配的资源回收，更新系统P
  3. 返回1，若所有进程都能分配，则存在安全序列（不唯一）

备注：

  1. 存在安全序列 -》无死锁进程
  2. 不存在安全序列不一定发生死锁（依赖于请求资源的序列）

不发生死锁的最小资源量

每个所需资源都-1后累加，再加一（每个所需资源都-1为请求与保持的最坏情况，+1即可确保分配不发生死锁）

死锁检测/恢复（排查因资源导致的阻塞进程）

检测发生死锁的进程（资源未被使用，进程长时间未调度等），恢复进程并重新分配资源（改进的银行家算法）

改进的银行家算法分配每次进程请求的资源，而不是分配所需的所有资源，因为有事进程对于资源使用后就会释放，这样系统有更多余量

缺点：

  • 回滚的处理问题

死锁忽略（大部分PC机操作系统）

不进行死锁处理