操作系统进程

2026-05-312026-06-05

【408-操作系统】

信号量

Peterson算法

#define FALSE 0
#define TRUE 1
#define N 2 // 进程数量

int turn;
int interested[N];

void enter_region(int process) {
  int other;
  other = 1 - process;
  interested[process] = TRUE;
  turn = process;
  while (turn == process && interested[other] == TRUE); // 空语句
}

void leave_region(int process) {
  interested[process] = FALSE;
}

经过分析上述代码，发现可以保证同一时间只有一个进程可以进入临界区

TSL Test and set lock

enter_region:
  TSL REGISTER, LOCK  // 复制锁到寄存器并将锁设为1
  CMP REGISTER, #0    // 锁是0吗
  JNE enter_region    // 若不是0，说明锁已被设置，所以循环
  RET                 // 返回调用者，进入了临界区

leave_region:
  MOV LOCK, #0        // 在锁中存入0
  RET

使用硬件来实现

有读内存字和写内存字两部操作，能够保证这两部操作之间没有别的操作打断

实现方式是CPU将锁住内存总线，禁止其他CPU在本条指令结束前访问内存

忙等待

    以上做法都叫忙等待，如果一个进程想进入临界区，要检查是否允许，如果不允许，则该进程将原地等待，直到允许为止。

    更期待的做法实际是不允许时就挂起，等待临界区的进程出来是通知挂起的程序

生产者-消费者

简陋版代码

#define N 100    /*缓冲区中的槽数目*/
int count = 0;   /*缓冲区中的数据项数目*/

void producer(void) {
  int item;
  while (TRUE) {  /*无限循环*/
    item = produce_item();  /*产生下一新数据项*/
    if (count == N) sleep(); /*如果缓冲区满了，就进入休眠状态*/
    insert_item(item); /*将（新）数据项放入缓冲区中*/
    count = count + 1; /*将缓冲区的数据项计数器增1*/
    if (count == 1) wakeup(consumer); /*缓冲区空吗？*/
  }
}

void consumer(void) {
  int item;
  while (TRUE) {  /*无限循环*/
    if (count == 0) sleep(); /*如果缓冲区空，则进入休眠状态*/
    item = remove_item();    /*从缓冲区中取出一个数据项*/
    count = count -1;  /*将缓冲区的数据项计数器减1*/
    if (count == N-1)wakeup(producer); /*缓冲区满吗？ */
    consume_item(item);  /*打印数据项*/
  }
}

单凭上面一段代码，会出现唤醒信号丢失的问题

简述原因：例如缓冲区已空，消费者准备休眠但还未休眠，这是CPU调度算法切换成生产者工作，生产者发现生产1个后count==1，故想消费者发送唤醒信号，但此时消费者还为睡眠，故唤醒信号丢失，之后CPU调度再切换回消费者时，消费者休眠后就再也不会有唤醒信号了，生产者也会在缓冲区满后睡眠，机器全部停止工作

因而提出了信号量

有两种操作：P(Proberen 尝试)，V(Verhogen 增加)

P：检查信号量的值是否大于0，若值大于0，则将其值减去1并继续。如果该值为0，则进程睡眠
V：对信号量的值加1

P和V是原子操作，其内部的步骤是不可分割的

生产者消费者问题改正

使用3个信号量

full: 记录充满缓冲区的数量
empty: 记录空的缓冲区数目
mutex: 确保生产者和消费者不会同时访问缓冲区

#define N 100          /*缓冲区中的槽数目*/
typedef int semaphore; /*信号量是一种特殊的整型数据*/
semaphore mutex = 1;   /*控制对临界区的访问*/
semaphore empty = N;   /*计数缓冲区的空槽数目*/
semaphore full = 0;      /*计数缓冲区的满槽数目*/

void producer(void) {
  int item;
  while (TRUE) {
    item = produce_item();
    down(&empty);           // down就是P  减1或为0时睡眠
    down(&mutex);           // 进入临界区
    insert_item(item);
    up(&mutex);             // 离开临界区
    up(&full);              
  }
}

void consumer(void) {
  int item;
  while (TRUE) {
    down(&full);
    down(&mutex);
    item = remove_item(); // 取出数据项
    up(&mutex);
    up(&empty);
    consume_item(item);   // 处理数据项
  }
}

信号量同步缺点

同步操作分散

同步操作分散在各个进程中，使用不当就可能导致进程死锁（P/V的次序错误、重复、遗漏）

代码可读性差

想要了解一组共享变量以及信号量的操作是否正确，需要阅读整个并发程序的代码

经典同步问题

读者写者问题

例如，一个飞机订票系统，允许多个客户同时查看座位的分配。但是正在预定座位的客户必须拥有对数据库的独占访问。

多个进程同时读数据库是可以的
当一个进程正在写数据库，则所有其他的进程都不能访问该数据库，即使读也不行

哲学家进餐

死锁

多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种状态时，若无外力作用，这些进程都将无法再向前推进

操作系统 进程

信号量