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

2023年1月21日约 1086 字预计阅读 3 分钟

第二章进程管理（进程同步与死锁）

进程同步

多个进程间可能存在依赖关系，为了保证其按依赖关系执行，操作系统需要通过一种机制保证

同步问题的解决

利用信号解决同步问题

        
        
        
    
// counter: the count of item in buffer
// empty: buffer have empty space or not
// full: buffer have item or not
void producer()
{
  while (true)
  {
    if (counter == BUFFER_SIZE)
      sleep_on(empty);
    buffer[in] = item;
    in = (in + 1) % BUFFER_SIZE;
    counter++;
    if (counter == 1)
      wake_up(full);
  }
}

void consumer()
{
  while (true)
  {
    if (counter == 0)
      sleep_on(full);
    item = buffer[out];
    out = (out + 1) % BUFFER_SIZE;
    counter--;
    if (counter == BUFFER_SIZE - 1)
      	wake_up(empty);
  }
}

问题是上述方法无法解决多生产者/消费者的情况，因为只能释放旧的进程，所以需引入新的变量来记录更多的信息

将信号扩展为信号量

信号量若为n（n<0）表示有｜n｜的进程阻塞，大于0表示有n个空闲资源

        
struct semaphore
{
  int value; // value of block_process or free resource
  PCB *queue; // process queue wait on sem
}

        
        
        
    
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);
}

        
        
        
    
// 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);
}

临界区

在多个进程修改同一共享资源时根据调度序列的不同可能出现语义错误，故需要引入临界区对共享资源保护

在软件上可以通过Lamport面包店算法实现，采用“轮换+标记”

在硬件上可以通过硬件原子指令法实现，一条硬件指令执行的过程不可能被中断，确保了原子性

信号量的实现与使用

死锁

死锁的四个必要条件

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

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

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

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

缺点：

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

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

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

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

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

缺点：

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

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

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

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

缺点：

回滚的处理问题

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

不进行死锁处理

目录