操作系统——期末复习

单项选择+基本概念（25字以内）+综合题（编程+计算）

并发

并发程序的加速比，n个并行流，可被并行化指令部分比例为p，加速比为 $speedp=\frac{1}{1-p+\frac{p}{n}}$
互斥
- 临界区：访问共享资源的一个代码，资源通常是一个变量或数据结构
- 竞态条件：出现在多个执行线程大致同时进入临界区时，它们都试图更新共享的数据结构，导致非预期的结果
- 安全性：“没有坏事发生”；活性：“好事终将发生”

条件变量

cond_wait(cond_t* cv, mutex_t* lk)

cond_signal(cond_t* cv)

cond_broadcast(cond_t* cv)

可以使用futex实现条件变量

futex_wait(int* address, int expected)

futex_wake(int* address)

一个简单的生产者消费者例子——打印括号

void produce() {
  while (1) {
    mutex_lock(&lk);
    while (!(depth < n)) {
      cond_wait(&cv_p, &lk);
    }
    printf("(");
    depth++;
    cond_signal(&cv_c);
    mutex_unlock(&lk);
  }
}
void consume() {
  while (1) {
    mutex_lock(&lk);
    while (!(depth > 0)) {
      cond_wait(&cv_c, &lk);
    }
    printf(")");
    depth--;
    cond_signal(&cv_p);
    mutex_unlock(&lk);
  }
}

一个更加复杂的例子——打印fish

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t lk;
pthread_cond_t cond;

char cur;
int cnt = 0;

int OK4T1() {
  return cnt == 0 || (cnt == 1 && cur == '>') || (cnt == 2 && cur == '>');
}

int OK4T2() {
  return cnt == 0 || (cnt == 1 && cur == '<') || (cnt == 2 && cur == '<');
}

int OK4T3() { return cnt == 3; }

void T1() {
  while (1) {
    pthread_mutex_lock(&lk);
    while (!OK4T1()) {
      pthread_cond_wait(&cond, &lk);
    }
    printf("<");
    cur = '<';
    ++cnt;
    fflush(stdout);
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&lk);
  }
}

void T2() {
  while (1) {
    pthread_mutex_lock(&lk);
    while (!OK4T2()) {
      pthread_cond_wait(&cond, &lk);
    }
    printf(">");
    cur = '>';
    ++cnt;
    fflush(stdout);
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&lk);
  }
}

void T3() {
  while (1) {
    pthread_mutex_lock(&lk);
    while (!OK4T3()) {
      pthread_cond_wait(&cond, &lk);
    }
    printf("_");
    cur = '_';
    cnt = 0;
    fflush(stdout);
    pthread_cond_broadcast(&cond);
    pthread_mutex_unlock(&lk);
  }
}

int main() {
  pthread_t t1, t2, t3;
  pthread_create(&t1, NULL, (void *)T1, NULL);
  pthread_create(&t2, NULL, (void *)T2, NULL);
  pthread_create(&t3, NULL, (void *)T3, NULL);
  pthread_join(t1, NULL);
  pthread_join(t2, NULL);
  pthread_join(t3, NULL);
}

编译加上-lpthread参数

macOS clang疑似有问题，具体原因待定

信号量

P(sem_t* sem)

V(sem_t* sem)
- 可以使用互斥锁+条件变量实现信号量
信号量并不适用打印fish问题
死锁：某个小组中的成员都在等待另一个成员（包括自己）采取行动，比如发送消息或释放锁，因此无法继续执行的状态

AA型死锁，ABBA型死锁

哲学家问题

虚拟化

进程和线程

进程：拥有独立地址空间的运行实体，可以包含一个或多个线程

进程控制块PCB：描述进程，方便操作系统管理。类似的有线程控制块TCB
fork

多进程的线程进行fork时，只有一个线程被复制，就是那个调用fork的线程
execve：将当前进程重置成一个可执行文件描述状态机的初始状态
exit
调度
- 时间片轮转调度（Round-Robin）：每个任务会获得一段固定时间的资源（时间片），若任务没完成则回到队列，一般来说时间片设置为10ms到100ms（上下文切换context switch一般小于10microseconds）
- FCFS：先来先服务
- 优先级：优先级高的进程先执行，但可能导致饿死，低优先级的进程可能永远不会执行，解决方案是老化，随着时间推移增加进程的优先级
- 多级反馈队列：多个队列，不同队列有不同优先级，轮流执行
实时系统的调度
- 单调速率：周期较短的任务有较高的优先级
- 最早截止日期优先：截止日期越早，优先级越高
优先级反转：一个高优先级的任务反而受制于一个低优先级任务

低优先级的T1首先运行，获得互斥锁，高优先级的T2其次运行，此时申请互斥锁但无法获得，引发死锁。

解决方案：优先级极限/优先级继承
- 优先级极限：当一个任务试图获取一把锁时，该任务的优先级被提升到与该锁关联的优先级上限相同的优先级。
- 优先级继承：一个持有锁的任务，当有其他任务试图获取该锁，那么持有锁的任务的优先级将被提升到那个更高优先级任务的优先级。
TLB地址转换旁路缓冲：页表的缓存
虚拟内存：支持多个并发运行的进程使用大虚拟地址空间，只将常用的页面保留在内存中，具有“部分”加载程序的执行能力
帧替换算法：物理内存页满时，决定淘汰哪一页，以便为即将访问的新页面腾出空间。常见的算法有：OPT（最优算法）、FIFO（先进先出算法）、LRU（最近最少用算法）、LFU（最不经常使用）

多级页表：如果某级页表中的某条目为空，则下一级页表无需存在。减少空间占用

地址翻译比较

方法	优点	缺点
分段	快速上下文切换（段映射由CPU维护）	外部碎片
单级页表	无外部碎片快速且易于分配	表的规模巨大内部碎片
多级页表	表大小约为虚拟内存中需要用的页面数量快速且易于分配	每次页面访问涉及多次内存引用
倒排页表	表大小约为物理内存中的页面数量	需要复杂的哈希函数页表没有缓存局部性

持久化

驱动程序：一段专门为某种硬件编写的软件，让操作系统能“理解与控制”该硬件
DMA：直接内存访问。给控制器访问内存和总线的权限；要求它直接在内存和控制器之间传输数据块
软链接：创建一种不同类型的文件，是路径名的别名，效率比硬链接低，可能有引用悬空问题
硬链接：在目录中创建另一个名称，并将其指向原始文件的相同inode号。本质是inode号的别名，每个inode号有引用计数。因为inode号在文件系统中唯一，不能链接另一个文件系统中的文件；也不能链接目录，防止循环等问题
inode多级索引
日志：文件的更新被作为事务（transaction）保存在日志中
磁盘管理：公平有效地利用磁盘空间