进程管理 | Ming

进程和线程

概念和对比

进程
- 概念
  - 运行中的程序
- 地位
  - 资源分配的基本单位
- 管理
  - PCB
- 创建和撤销
  - 操作PCB
线程
- 地位
  - 独立调度的基本单位
- 特点
  - 共享进程资源
区别
- 资源
- 调度
- 开销
- 通信
  - 线程通过读写同一进程的数据通信
  - 进程通过IPC通信

进程的状态

Ready
- 等待被调度，通过调度算法获得CPU时间，进入Running状态
Block
Running
- 耗完得到的cpu时间后进入block状态

进程调度算法

批处理系统

关心吞吐量和周转时间

FCFS（先来先服务）
- 非抢占式
- 简单粗暴
SJF（短作业优先）
- 非抢占式
- 长作业可能会饿死
SRTF（最短剩余时间优先）
- 抢占式
- 如果新来的更短，则挂起当前的

交互式系统

关心快速响应

时间片轮转
- 设置时间片，快速切换
- 时间片长度设置要合理
  
  时间片过短：进程频繁切换
  时间片过长：即时性没有保证
分配优先级
- 先执行优先级高的
- 为了防止优先级低的进程饿死，可以使其优先级随时间递增
多级反馈队列
- 设置多个时间片不同的队列，动态地将长作业放在时间片长的队列

实时系统

软实时
硬实时

进程同步

临界区（critical region）

概念
- 对临界资源访问的代码段
特点
- 访问临界资源前先进行检查以实现互斥访问

同步和互斥

同步
- 因为多个进程之间的合作关系，进程的执行需要有一定的先后顺序
互斥
- 同一时刻只能有一个进程进入临界区

信号量（Semaphore）

存储位置
- Kernel Mode
  
  如果信号量存在于用户态，进程结束时信号量会被销毁
PV操作
- up
  
  Up之后会唤醒一个因为down操作陷入睡眠的进程
  - samaphore++
- down
  
  进入临界区之前先down一下，如果semaphore=0，调用down方法的进程会陷入睡眠，等待一个命中注定的人
  - samaphore–
- 原子性
  - 可以用禁止中断来实现
Mutex
- 简化版（单值）的Semaphore
- 状态
  - 0
  - 1

生产消费者问题

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

mutex
- 锁
empty
- 剩余容量
full
- 已使用容量

管程
- 特点：同一时刻只能有一个进程使用管程
- 管程将控制操作独立出来，本质上是PV操作之上的一层包装

经典同步问题

哲学家就餐问题

#define N 5
#define LEFT (i + N - 1) % N // 左邻居
#define RIGHT (i + 1) % N    // 右邻居
#define THINKING 0
#define HUNGRY   1
#define EATING   2
typedef int semaphore;
int state[N];                // 跟踪每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);
        eat(i);
        put_two(i);
    }
}

void take_two(int i) {
    down(&mutex);
    state[i] = HUNGRY;
    check(i);
    up(&mutex);
    down(&s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

void put_two(i) {
    down(&mutex);
    state[i] = THINKING;
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    up(&mutex);
}

void eat(int i) {
    down(&mutex);
    state[i] = EATING;
    up(&mutex);
}

// 检查两个邻居是否都没有用餐，如果是的话，就 up(&s[i])，使得 down(&s[i]) 能够得到通知并继续执行
void check(i) {         
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;
        up(&s[i]);
    }
}

哲学家
- think()
- eat()
死锁问题
- 当所有哲学家同时拿起左手的筷子
解决
- takeTwo()
- putTwo()
- check(i)
  - 在邻居没有进餐的情况下才可以进餐

读者–写者问题

typedef int semaphore;
semaphore count_mutex = 1;
semaphore data_mutex = 1;
int count = 0;

void reader() {
    while(TRUE) {
        down(&count_mutex);
        count++;
        if(count == 1) down(&data_mutex); // 第一个读者需要对数据进行加锁，防止写进程访问
        up(&count_mutex);
        read();
        down(&count_mutex);
        count--;
        if(count == 0) up(&data_mutex);
        up(&count_mutex);
    }
}

void writer() {
    while(TRUE) {
        down(&data_mutex);
        write();
        up(&data_mutex);
    }
}

可以同时读，但读和写以及写和写不能同时发生
第一个读者为数据上锁避免写者访问数据

IPC

进程通信VS进程同步

通信是手段，同步是目的

通信方式

（匿名）管道（pipe）
- 特点
  - only半双工
  - only父子进程或者兄弟进程
  - 存放于内存
  - 类似队列，一端写入，一端读出
- 图
FIFO（命名管道）
- 与一般的管道相比，没有进程关系限制，存放于文件系统
- 多用于CS架构作为汇聚点，在客户进程和服务器进程之间传递数据
- 图
消息队列
- 可以独立于读写进程存在
- 读进程可以根据消息类型有选择地接收消息
信号量
- Semaphore
- Mutex
共享存储/共享内存
- 特点
  - 效率高（不需要数据的复制）
- 存在的问题
  - 各进程间的同步问题，常配合信号量使用
Socket（套接字）
- 可用于不同主机的进程间通信