进程

运行 <-> 就绪
  ↘    ↗
    阻塞

运行：该时刻实际占用 CPU
就绪：操作系统调度了其他进程运行而暂时停止
阻塞：逻辑上不能继续运行，比如等待用户输入

假如内存为 8G，操作系统和相关表格占 2G，用户程序也占 2G，内存最多容纳 3 个用户程序
假设 80% 时间用于等待 I/O 操作
CPU 利用率 = 1 - 0.8 ^ 3 = 49%
如果增加 8G 内存，则最多容纳 7 个用户程序
CPU 利用率 = 1 - 0.8 ^ 7 = 79%，吞吐量提高为 79% - 49% = 30%
如果再增加 8G 内存，则最多容纳 11 个用户程序
CPU 利用率 = 1 - 0.8 ^ 11 = 91%，吞吐量只提高了 12%，可见第一次增加内存比较划算

线程

进程间通信（Inter Process Communication）

// 进程 A
while (true) {
  while (x) {
  }
  critical_region();
  x = true;  // 允许进程 B 进入临界区
  noncritical_region();
}

// 进程 B
while (true) {
  while (!x) {
  }
  critical_region();
  x = false;  // 允许进程 A 进入临界区
  noncritical_region();
}

constexpr int N = 2;  // 进程数量为2
int turn = 0;         // 轮到的进程
vector<bool> interested(N);

void enter_region(int process) {
  int other = 1 - process;  // 另一进程（进程号为 0 或 1）
  interested[process] = true;
  turn = process;  // turn 只有一个，即使两个进程调用也只有后一个赋值会保留
  while (turn == process && interested[other]) {
  }
}

void leave_region(int process) {  // 调用上述函数完成后调用此函数
  interested[process] = false;
}

// 若进程 A 调用 enter_region 则很快返回，
// 此时进程 B 调用将在 while 循环挂起，
// 直到进程 A 调用 leave_region
// 若进程 AB 同时调用 enter_region，
// turn 为后赋值者，
// 则先赋值者退出循环并调用 leave_region，后赋值者再退出循环

TSL RX, LOCK // 将内存字 LOCK 读到寄存器 RX 中，然后在该内存地址写一个非零值，读写是原子操作

enter_region:
    TSL REGISTER, LOCK  ;复制锁到寄存器并设置值为 1
    CMP REGISTER, #0    ;值是否为 0
    JNE enter_region    ;不是 0 则循环
    RET                 ;返回，进入临界区

leave_region:
    MOVE LOCK, #0
    RET

enter_region:
    MOVE REGISTER, #1    ;在寄存器放一个 1
    XCHG REGISTER, LOCK  ;原子交换寄存器和锁变量的内容
    CMP REGISTER, #0     ;值是否为 0
    JNE enter_region     ;不是 0 则循环
    RET                  ;返回，进入临界区

leave_region:
    MOVE LOCK, #0
    RET

生产者-消费者问题

constexpr int N = 100;  // 缓冲区的槽数
int cnt = 0;            // 缓冲区数据数

void producer() {
  while (true) {
    int item = produce_item();  // 生成新数据
    if (cnt == N) {
      sleep();
    }
    insert_item(item);  // 将消息放入缓冲区
    ++cnt;              // 1
    if (cnt == 1) {
      wakeup(consumer);  // 2
    }
  }
}

void consumer() {
  while (true) {
    if (!cnt) {
      sleep();  // 3
    }
    int item = remove_item();  // 从缓冲区取一个数据
    --cnt;
    if (cnt == N - 1) {
      wakeup(producer);
    }
    consume_item(item);  // 打印数据
  }
}

// 问题在于 cnt 的访问存在 race condition，
// 如果消费者执行到 3 处，cnt 为 0，在即将 sleep 之前，
// 生产者在此之后才执行到 1 处，此时 cnt 为 1，执行到 2 处，调用 wakeup，
// 但此时消费者还未 sleep，因此 wakeup 的信号丢失，没有实际作用，
// 接着消费者 sleep，生产者开始下一轮循环，
// 生产者下一轮循环到 1 处，cnt 为 2，到 2 处，不再调用 wakeup，消费者保持 sleep，
// 生产者继续之后的循环，并且每一轮都不会唤醒消费者，
// 最终生产者执行到 cnt 为 N 时 sleep，两个进程都将永久 sleep

信号量（semaphore）

constexpr int N = 100;  // 缓冲区的槽数
using semaphore = int;
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();
    up(&mutex);
    up(&empty);
    consume_item(item);
  }
}

互斥量（mutex）

mutex_lock:
    TSL REGISTER, MUTEX  ;将互斥量复制到寄存器，并将互斥量置为 1
    CMP REGISTER, #0
    JZE ok               ;如果互斥量为 0，它被解锁，所以返回
    CALL thread_yield    ;互斥量忙，调度另一个线程
    JMP mutex_lock       ;稍后再试
ok: RET

mutex_unlock:
    MOVE MUTEX, #0       ;将互斥量置0
    RET

管程（monitor）

消息传递（message passing）

send(destination, &message);
receive(source, &message);

constexpr int N = 100;

void producer() {
  message m;  // 消息缓冲区

  while (true) {
    int item = produce_item();
    receive(consumer, &m);    // 等待消费者发送空缓冲区
    build_message(&m, item);  // 建立一个待发送的消息
    send(consumer, &m);       // 发送数据项给消费者
  }
}

void consumer() {
  message m;

  for (int i = 0; i < N; ++i) {
    send(producer, &m);  // 发送 N 个空缓冲区
  }

  while (true) {
    receive(producer, &m);        // 接收包含数据项的消息
    int item = extract_item(&m);  // 将数据项从消息中提取出来
    send(producer, &m);           // 将空缓冲区发送回生产者
    consume_item(item);
  }
}

屏障（barrier）

调度

调度算法的评价指标

批处理系统中的调度

先来先服务（First-Come First-Served，FCFS）

进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

先到先服务，因此调度顺序为 P1 -> P2 -> P3 -> P4
P1      P2   P3 P4
------- ---- -  ----

周转时间 = 完成时间 - 到达时间
P1 = 7 - 0 = 7
P2 = 11 - 2 = 9
P3 = 12 - 4 = 8  // 只运行 1，却需要等待 8，可见 FCFS 算法对短作业不利
P4 = 16 - 5 = 11
平均周转时间 = 8.75

带权周转时间 = 周转时间 / 运行时间
P1 = 7 / 7 = 1
P2 = 9 / 4 = 2.25
P3 = 8 / 1 = 8
P4 = 11 / 4 = 2.75
平均带权周转时间 = 3.5

等待时间 = 周转时间 - 运行时间（不考虑等待 I/O 操作的时间）
P1 = 7 - 7 = 0
P2 = 9 - 4 = 5
P3 = 8 - 1 = 7
P4 = 11 - 4 = 7
平均等待时间 = 4.75

最短作业优先（Shortest Job First，SJF）

进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

P1 先到达，P1 运行结束时 P2、P3、P4 均到达，P3 运行时间最短先运行
P2、P4 运行时间相同，P2 先到达，因此 P2 先于 P4 运行

最终调度顺序为 P1 -> P3 -> P2 -> P4
P1      P3 P2    P4
------- -  ----  ----

周转时间 = 完成时间 - 到达时间
P1 = 7 - 0 = 7
P2 = 12 - 2 = 10
P3 = 8 - 4 = 4
P4 = 16 - 5 = 11
平均周转时间 = 8

带权周转时间 = 周转时间 / 运行时间
P1 = 7 / 7 = 1
P2 = 10 / 4 = 2.5
P3 = 4 / 1 = 4
P4 = 11 / 4 = 2.75
平均带权周转时间 = 2.56

等待时间 = 周转时间 - 运行时间（不考虑等待 I/O 操作的时间）
P1 = 7 - 7 = 0
P2 = 10 - 4 = 6
P3 = 4 - 1 = 3
P4 = 11 - 4 = 7
平均等待时间 = 4

最短剩余时间优先（Shortest Remaining Time Next，SRTN）

进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

P2 到达时，P1 剩余 5，P2 为 4，运行 P2
P3 到达时，P1 剩余 5，P2 剩余 2，P3 为 1，运行 P3
P4 到达时，P3 运行结束，P1 剩余 5，P2 剩余 2，P4 为 4，运行 P2
最后依次运行 P4 和 P1

最终调度顺序为 P1 -> P2 -> P3 -> P2 -> P4 -> P1
P1 P2 P3 P2 P4    P1
-- -- -  -- ----  -----

周转时间 = 完成时间 - 到达时间
P1 = 16 - 0 = 16
P2 = 7 - 2 = 5
P3 = 5 - 4 = 1
P4 = 11 - 5 = 6
平均周转时间 = 7

带权周转时间 = 周转时间 / 运行时间
P1 = 16 / 7 = 2.29
P2 = 5 / 4 = 1.25
P3 = 1 / 1 = 1
P4 = 6 / 4 = 1.5
平均带权周转时间 = 1.51

等待时间 = 周转时间 - 运行时间（不考虑等待 I/O 操作的时间）
P1 = 16 - 7 = 9
P2 = 5 - 4 = 1
P3 = 1 - 1 = 0
P4 = 6 - 4 = 2
平均等待时间 = 3

高响应比优先（Highest Response Ratio Next，HRRN）

进程 到达时间 运行时间
P1   0        7
P2   2        4
P3   4        1
P4   5        4

响应比 = （等待时间 + 运行时间） / 运行时间
P1 运行至结束，P2、P3、P4 均到达，响应比分别为
P2 = (5 + 4) / 4 = 2.25
P3 = (3 + 1) / 1 = 4
P4 = (2 + 4) / 4 = 1.5
运行 P3，P3 结束时，响应比分别为
P2 = (6 + 4) / 4 = 2.5
P4 = (3 + 4) / 4 = 1.75
运行 P2，最后运行 P4

最终调度顺序为 P1 -> P3 -> P2 -> P4
P1      P3 P2    P4
------- -  ----  ----

交互式系统中的调度

时间片轮转调度（Round-Robin Scheduling，RR）

A -> B -> C -> D

若 A 用完时间片，但仍在运行，则插入到队列尾
B -> C -> D -> A

若 B 用完时间片，但仍在运行，并到达一个新进程 E，则先插入新进程
C -> D -> A -> E -> B

若 C 用完时间片之前就结束了，则直接切换到下一个进程
D -> A -> E -> B

优先级调度

多级反馈队列调度

最短进程优先

T0
T0/2 + T1/2
T0/4 + T1/4 + T2/2
T0/8 + T1/8 + T2/4 + T3/2  // T0 在此时估计时间中的占比下降到 1/8

保证调度

彩票调度（Lottery Scheduling）

公平分享调度