Mengzelev's Blog

os期中复习

Word count: 2,528 / Reading time: 10 min
2019/04/15 Share

应用眼中的OS

  • 操作系统一方面需要提供程序的执行的环境相应的资源,还要提供和操作系统世界中其他对象交互的方法和约定

并发

共享内存多线程

  • 并发定义:一个程序、算法或问题的不同部分乱序或偏序执行而不影响最终结果的能力
  • 程序经历了什么?

    • 编译器优化$\to$顺序丧失
    • 操作系统中断,多处理器、缓存(硬件)$\to$原子性(all or nothing)丧失
    • 缓存,乱序(硬件)$\to$可见性丧失
  • 顺序丧失:允许源代码中内存访问指令不再按顺序甚至不再出现

  • 原子性的丧失:指令序列可以在任意时刻被中断,然后操作系统切换到其他线程执行
  • 可见性丧失:缓存&乱序

互斥

评估一把锁的基本准则

  • 能够完成基本任务:提供互斥性质
  • 锁的分配是公平的:不会有现成想要上锁却永远得不到它
  • 锁的高效的:无等待时性能?多线程同时等待时性能?多CPU每个核的线程都要上锁时性能?

自旋锁的正确性证明:

  • 建模程序的状态
  • 证明safety(只有一个线程进入临界区)和liveness(至少有一个线程能进入临界区)

几种上锁方法

  • TestAndSet;相当于atomic_xchg
  • CompareAndWait
  • LL&SC
  • FetchAndAdd:彩票锁,保证公平性

同步(CV)

  • wait(&cond):当前进程进入睡眠状态,等待cond被满足后唤醒
  • signal(&cond):唤醒在等待cond条件的某个进程
  • broadcast(&cond): 唤醒在等待cond条件的所有进程
  • 需要配合互斥锁使用:读取状态到wait()之间不能被打断,改变状态到signal之间也不能被打断

使用条件变量

记 得 上 锁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void worker(int id) {
mutex_lock(&mutex);
done[id] = 1;
signal(&joins);
mutex_unlock(&mutex);
}

int main() {
for(int i = 0; i < nworkers; ++i) create(worker,i);
for(int i = 0; i < nworkers; ++i) {
mutex_lock(&mutex);
if(!done[i]) wait(&joins, &mutex);
mutex_unlock(&mutex);
}
}

信号量

互斥锁(二元信号量)和同步都可以使用信号量来实现
信号量就相当于有一个管理员manage了一堆资源,进程需要资源时先向管理员请求(semi_wait),暂时没有资源就等,使用完毕后归还(semi_post)给管理员

需要配合锁使用
注意死锁:lock之后P,其他线程是无法获得lock的

期中考题

1
2
3
4
5
6
7
8
9
10
11
12
13
'(': lock("("); // assume lock can nest
putchar(); V(fill1);
')': P(fill1); putchar();
unlock("(");

'[': lock("(");
putchar();
V(fill2);
unlock("(");
']': P(fill2);
lock("(");
putchar();
unlock("(");
  • 不能上一把大锁(会死锁),所以拆了小锁来保证原子性
  • P不能在锁中间进行
  • 自旋锁是为了保证圆括号和方括号不冲突(互斥),信号量是为了保证左右括号配对(同步)
  • 之所以用锁而非信号量来处理圆括号和方括号的关系,是因为为了保证原子性本来就要上锁,这样一举两得。用信号量不是不可以,但一样也要上锁,造成了资源浪费。

APIs

  • sem_wait:信号量-1,表示在等待的线程增加了一个,消耗一个执行名额;如果信号量<0, 表示等待的线程数多于可执行线程数,当前线程进入睡眠
  • sem_post:信号量+1,表示执行的线程少了一个,可以让出一个执行名额

哲学家吃饭问题

One general solution: 让一个人集中管理所有叉子(信号量)

并发Bugs

  • 原子性违反(AV) –> 上锁
  • 顺序违反(OV) –> 同步

死锁出现的四个条件

  • 互斥
  • 请求与保持(同一个进程要同时上多把锁)
  • 没有抢占(不能强制解锁)
  • 循环等待

对付死锁

  • 避免:规定上锁顺序
  • 检测:打log

虚拟化

每个进程都以为自己独占CPU和整个内存空间
进程:OS提供的对运行程序的抽象

进程抽象

CPU执行指令时假设自己直接占有整个CPU
进程分时共享物理CPU

进程状态

  • Running: 进程正在处理器上执行命令
  • Ready:进程准备执行,但由于某些原因OS决定现在不让它运行
  • Blocked:进程此前执行了某些操作(e.g. I/O),让它在其他事件发生前停止执行

实现进程

  • 进程=线程+地址空间
  • 进程就是个结构体
    • 名字
    • pid
    • 上下文
    • 地址空间
    • 堆栈
    • 状态
    • 其他信息(如父进程、文件描述符等)

进程管理

  • fork
  • execve
  • exit
    • exit()是库函数,_exit()是系统调用

文件描述符

一个指向os内对象的指针
fork-exec不改变文件描述符
int dup2(int oldfd, int newfd); - 关闭newfd,并复制oldfdnewfd(dup+close的并发版)

重定向

1
2
3
4
5
6
7
8
9
pid_t pid = fork();
assert(pid != 0);
if(pid == 0) { //子进程
int fd = open(...);
dup2(fd, STDOUT_FILENO);
close(fd);
execve(...);
}
else{...}

管道

1
2
3
4
5
6
7
8
9
10
11
12
if(pipe(fds) != 0) {panic("pipe error");}
pid = fork();
if(pid == 0) {//child
dup2(fds[1], STUOUT_FILENO); //连接写口,往管道内写数据
close(fds[1]);
close(fds[0]);
}
else{ //parent
dup2(fds[0], STDIN_FILENO); //连接读口,从管道内读数据
close(fds[0]);
close(fds[1]);
}

信号

进程组实现

进程调度

衡量标准

  • 轮转时间(turnaround time): $\sum t_{complete}-t_{arrival}$
  • 响应时间(response time): $\sum t_{firstrun}-t_{arrival}$

FIFO

  • 优点:简单易实现
  • 缺点: 会产生护航效应(有一个不要脸的任务占坑很久)

SJF(Shortest Job First)

  • 当假设所有任务同时到达时的最优算法
  • 非抢占式(preemptive)算法

STCF(Shortest Time-to-Completion First)

  • 抢占式策略,又名Preemptive Shortest Job First(PSJF)
  • 轮转时间短但响应时间长

RR(Round Robin)

  • 每个进程运行一段时间片(time slice, sometimes called scheduling quantum)
  • 时间片越短,响应时间越短,但是切换上下文的时间会变长(trade-off)
  • 当考虑轮转时间时非常糟糕
  • 保证了公平性但是损失了效率

MLFQ(Multi-level Feedback Queue)

MLFQ有很多种实现但都大同小异,书上只介绍一种

  • 有很多队列,每个队列具有不同的优先级,优先级高的先运行
  • 通过观察进程过去的行为调整优先级
    • 如果一个进程频繁让出CPU,保持高优先级;反之一个进程如果长时间占用CPU则会被降低优先级
  • 并不知道一个任务是长是短,因此先假设是短的,然后根据进程的后续表现修改认知

优先级的修改

workload: 交互式短时间任务(会频繁让出CPU)+不交互的长时间任务(响应时间不那么重要)

Basic Rules

  1. If Priority(A)>Priority(B), A runs (B doesn’t)
  2. If Priority(B)==Priority(B), A & B runs in RR
  3. 一个任务最初进入系统时位于最高优先级
    4(a). 如果一个任务耗尽了时间片,则优先级下降
    4(b). 如果一个任务在时间片耗尽之前放弃了CPU,优先级不变
    4(改进). 当一个任务在一定程度上用尽了被分配到的时间,优先级就下降
    5(新增). 在一段时间$S$后,将所有任务移到最高优先级上(Priority-boost)

缺陷:

  • 饥饿:如果交互式进程很多就会完全占用CPU使得长任务得不到调度(5解决)
  • 有些心脏的应用可以玩弄这个规则,一直主动让出一小会儿CPU来使自己停留在高优先级上(4解决)
  • 任务的行为可能会随着时间改变(5解决)

PS(Proportional-share)

  • 老子才不管什么的轮转时间和响应时间,老子只要每个任务都能按比例分到一定时间

lottery scheduling

随机的好处

  • 防止了边界情况
  • 轻量级,需要记录的信息少
  • 快(太快了可能会变成伪随机数)

怎么分配彩票也是个很棘手的问题

stride scheduling

  • 根据每个任务的彩票数决定每次调度执行的时间长短
  • 每次调度都选取运行时间最短的任务

多处理器调度

不想看了【瘫

链接和加载

  • 静态链接下的加载:_start(程序自己的)->__libc_start_main->generic_start_main->...->main
  • 动态链接:
    • PLT:程序链接表,放入进行链接的代码,方便lazy linking(名字叫表格其实就是一小段代码,用来判断是否已经完成链接)
    • GOT:全局偏移表,存放函数代码开始的地址

第一条指令

  • 静态链接:a.out的entry
  • 动态链接:ld.so的entry
  • 动态链接libc:链接器使用一系列mmap把libc链接进进程地址空间

虚存抽象

多级页表(PML): 复习ICS
反置页表(IPT): 硬件维护一个全局的hash table,计算$f(as,x)$
IPT实现Copy-on-Write有困难,且PML能高效地标记一段连续内存为某个权限

mmap

把操作系统里的对象映射到进程的地址空间

  • e.g.加载可执行文件的时候把文件搬到某个地址处
  • 不映射任何文件的时候就相当于malloc
  • 只记录相关信息,余下的等发生缺页时再处理,所以非常快
  • 可以用红黑树维护分配的内存
  • fork采用写时复制

进程的地址空间

pmap-查看进程的地址空间

静态链接的程序的地址空间:代码、数据、bss、堆、栈、用户态系统调用
动态链接:多了动态链接库和链接器

期中复习

系统调用:操作系统为用户进程提供的一组API,通常在内核空间中实现,实现用户进程对操作系统对象/物理硬件访问的请求。
进程=操作系统中的数据
系统调用=这些数据上的操作

CATALOG
  1. 1. 应用眼中的OS
  2. 2. 并发
    1. 2.1. 共享内存多线程
    2. 2.2. 互斥
      1. 2.2.1. 几种上锁方法
    3. 2.3. 同步(CV)
      1. 2.3.1. 使用条件变量
    4. 2.4. 信号量
      1. 2.4.1. APIs
      2. 2.4.2. 哲学家吃饭问题
    5. 2.5. 并发Bugs
      1. 2.5.1. 死锁出现的四个条件
      2. 2.5.2. 对付死锁
  3. 3. 虚拟化
    1. 3.1. 进程抽象
      1. 3.1.1. 进程状态
      2. 3.1.2. 实现进程
    2. 3.2. 进程管理
    3. 3.3. 文件描述符
      1. 3.3.1. 重定向
      2. 3.3.2. 管道
    4. 3.4. 信号
    5. 3.5. 进程调度
      1. 3.5.1. 衡量标准
      2. 3.5.2. FIFO
      3. 3.5.3. SJF(Shortest Job First)
      4. 3.5.4. STCF(Shortest Time-to-Completion First)
      5. 3.5.5. RR(Round Robin)
      6. 3.5.6. MLFQ(Multi-level Feedback Queue)
        1. 3.5.6.1. 优先级的修改
        2. 3.5.6.2. Basic Rules
      7. 3.5.7. PS(Proportional-share)
        1. 3.5.7.1. lottery scheduling
        2. 3.5.7.2. stride scheduling
      8. 3.5.8. 多处理器调度
    6. 3.6. 链接和加载
      1. 3.6.1. 第一条指令
    7. 3.7. 虚存抽象
      1. 3.7.1. mmap
      2. 3.7.2. 进程的地址空间
  4. 4. 期中复习