操作系统2

2022-09-24

进程相关

进程

定义

是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位

组成

PCB（进程存在的唯一标志）
程序段
数据段

特征

动态性（进程的最基本特征）
并发性
异步性（各进程不可预知推进，运行结果不确定）
独立性（进程是系统进行资源分配、调度的独立单位）
结构性

状态

三种基本状态

运行态：占有CPU并在CPU上运行
就绪态：具备运行条件，但没有空闲CPU
阻塞态：因等待某一事件暂时不能运行

另两种状态

创建态：进程正在创建，OS为进程分配资源，初始化PCB
终止态：进程正在撤销，OS回收进程拥有的资源、撤销PCB

具有创建终止状态的进程状态、相互转换原因及其转换图（七态）

进程控制

基本概念
- 进程控制就是要实现进程状态的转换
- 进程控制用原语实现
  - 原语是一种特殊的程序
  - 原语的执行必须一气呵成、不可中断
  - 原语用关/开中断来实现
相关原语
- 进程的创建
- 进程的终止
- 进程的阻塞（阻塞和唤醒要成对出现）
- 进程的唤醒
- 进程的切换

进程通信

线程概念与多线程模型

处理机调度

进程调度

调度算法评价指标

调度算法

进程同步、互斥

信号量机制

P(S):wait(S)

V(S):signal(S)

// 记录型信号量的定义
typedef struct {
  int value; // 剩余资源数
  struct process *L // 等待队列
} semaphore;

// 某进程需要使用资源时，通过wait原语申请
void wait(semaphore S) {
  S.value--;
  if (S.value < 0) {
    block (S.L);
  }
}

// 进程使用完资源后，通过signal原语释放
void signal(semaphore S) {
  s.value++;
  if (s.value <= 0) {
    wakeup(S.L);
  }
}

用信号量实现进程互斥、同步、前驱关系

前驱关系

生产者-消费者问题

semaphore mutex = 1; // 互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;// 同步信号量，表示生产者可生产的数量
semaphore full = 0;// 同步信号量，表示消费者可消费的数量

producer() {
  while(1) {
    生产一个产品;
    P(empty);
    P(mutex);
    把产品放入缓冲区
    v(mutex);
    V(full);
  }
}

consumer() {
  while(1) {
    P(full);
    P(mutex);
    从缓冲区取出一个产品;
    V(mutex);
    V(empty);
    使用产品;
  }
}
// 生产和使用产品函数逻辑上可以放在PV操作之间，但会导致缓冲区代码量变大，占用临界区时间增加。导致其余想访问临界区的进程阻塞
// 总之降低了并发度

多生产者-多消费者问题

semaphore mutex =  1;//实现互斥访问盘子（缓冲区）
semaphore apple = 0;//盘子中有几个苹果
semaphore orange = 0;//盘子中有几个橘子
semaphore plate = 1;//盘子中还可以放多少个水果

dad () {
  while(1) {
    准备一个苹果;
    P(plate);
    P(mutex);
    把苹果放入盘子;
    V(mutex);
    V(apple);
  }
}
mom () {
  while(1) {
    准备一个橘子;
    P(plate);
    P(mutex);
    把橘子放入盘子;
    V(mutex);
    V(orange);
  }
}
daughter () {
  while(1) {
    P(apple);
    P(mutex);
    从盘中取出苹果
    V(mutex);
    V(plate);
    吃掉苹果;
  }
}
son () {
  while(1) {
    P(orange);
    P(mutex);
    从盘中取出橘子
    V(mutex);
    V(plate);
    吃掉橘子;
  }
}

读者-写者问题

读进程优先,去掉w

semaphore rw=1//用于实现对文件的互斥访问。表示当前是否有进程在访问共享文件
int count = 0;//记录当前有几个读进程在访问文件
semaphore mutex=1;//用于保证对count变量的互斥访问
semaphore w = 1;//实现先来先服务
writer(){
  while(1) {
    P(w);
    P(rw); // 写前加锁
    写文件;
    V(rw); // 写之后解锁
    V(w);
  }
}
reader() {
  while(1) {
    P(w);
    P(mutex); // 各读进程互斥访问count
    if(count == 0) {
      P(rw);// 第一个读进程加锁，防止写
    }
    count++;// 读进程+1
    V(mutex);
    V(w);
    读文件;
    P(mutex);// 各读进程互斥访问count
    count--;// 读进程-1
    if(count == 0) {
      V(rw); //最后一个读进程“解锁”
    }
    V(mutex);
  }
}

哲学家进餐问题

可以对哲学家进程施加一些限制条件，比如最多允许四个哲学家同时进餐。这样可以保证至少有一个哲学家是可以拿到左右两只筷子的
要求奇数号哲学家先拿左边的筷子，然后再拿右边的筷子，而偶数号哲学家刚好相反。用这种方法可以保正如果相邻的两个奇偶号暂学家都想吃饭，那么只会有其中一个可以拿起第一只筷子，另一个会直接阻塞。这就避免了占有一支后再等待另一只的情况
仅当一个哲学家左右两支筷子都可用时才允许他抓起筷子。