ICS2期中复习

异常控制流I

异常分类

• 中断（interrupt）：异步，来自I/O设备等硬件
• 陷阱（trap）：同步，程序有意陷入内核态以升级权限（system call）。如读写文件
  • int $0x80 system call
• 故障（fault）：同步，由某条指令引发的错误引起。如page fault，segmentation fault
• 终止（abort）同步，不可修复的错误造成的结果

用户态和内核态

内核线程：一般周期性执行，例如磁盘高速缓存的刷新、网页连接的维护、页面换入换出

内核线程只运行在内核态，而普通进程可以运行在用户态，也可以运行在内核态

内核态

• 能执行CPU指令集中的任何指令
• 能访问系统中的任何内存地址（物理地址访问）

用户态

• 既不能执行特权指令，也不能直接访问地址空间中内核区域的数据和代码
• 只能通过system call接口异常陷入内核态来做以上事情

上下文切换

• 内核维护了每个进程的上下文
• 上下文是指进程在重新启动一个进程时所需要的所有状态信息
• 上下文切换指进行多任务切换（比如通过时间片）的机制

进程的状态

• 执行：进程正在CPU上执行
• 就绪：进程正在等待被执行，并最终将被调度
• 阻塞：进程的执行被暂停，并且不会被调度
  • 进行I/O访问、调用sleep、访问锁等，可能进入阻塞状态
  • 收到SIGSTOP、SIGTSTP、SIGTTIN或SIGTTOU信号时，进程被停止
  • 收到SIGCONT，进入运行状态
• 终止：进程永久停止
  • 收到一个信号，该信号的默认行为时终止进程
  • 从主程序返回（从main函数返回一个整型）
  • 调用exit函数（记录status）

状态间的转换关系

• 执行状态被取消调度（如：时间片切换）变为就绪状态；就绪状态被调度变为执行状态
• 执行状态开始I/O操作等变为阻塞状态；阻塞状态做完I/O操作等变为就绪状态
• 进程收到终止信号变为终止状态

使用syscall

• 先把函数（kill,exit）对应的系统调用编号存入%rax
• 再将函数的参数存入%rdi,%rsi…中
• 最后syscall

异常控制流II（进程操作）

进程ID

• PID：Process ID，类型pid_t
• Getpid()：返回调用进程的PID
• Getppid()：返回其父进程的PID

退出进程

void exit(int status)

创建进程

fork()

• 父进程和新创建的子进程有不同的PID
• 子进程和父进程有重复但独立的地址空间
• 调用一次，返回两次
  • 在父进程中调用
  • 在父进程中返回子进程的PID；在子进程中返回0

收割子进程

zombie

内核并不会在进程终止后立刻将其清理掉，已终止的进程一般会保持在终止状态（称僵尸进程），直到被其父进程收割

如果父进程在没有收割其僵尸子进程的情况下终止，内核将安排系统初始进程(pid=1)收割他们

waitpid

pid_t waitpid(pid_t pid, int *status, int options)

• pid > 0：等待PID为pid的子进程

• pid = -1：等待父进程的所有子进程

• 如果没有子进程(ECHILD)或被信号中断(EINTER)，则返回-1，

• options

  • 0：waitpid函数的调用进程进入挂起状态，直到它的wait-set中的一个子进程终止返回其PID。已中止的子进程被从系统中删除，释放其资源（如果wait-set中的一个进程在进行waitpid调用的时候已经终止了，那么立刻返回其PID）

  • WNOHANG：如果wait-set中的任何子进程都还没有终止，那么立即返回0

  • WUNTRACED：将调用waitpid的进程挂起，直到wait-set中的一个子进程已经变成已终止或者停止，返回其PID。

  • WCONTINUED：将调用waitpid的进程挂起，直到wait-set中的一个正在运行的子进程终止，或者等待集合中一个被停止的进程收到SIGCONT信号重新开始

  • WNOHANG | WUNTRACED：立刻返回。如果等待集合中的进程都没有被停职或终止，则返回0；如果有一个停止或终止，则返回该进程的PID。

• status

  • WIFEXITED(status)：如果子进程通过调用exit或return正常终止，则返回true
  • WEXITSTATUS(status)：在WIFEXITED返回true的前提下，返回正常终止子进程的退出状态
  • WIFSIGNALED(status)：如果子进程因未捕获的信号而终止，则返回true
  • WTERMSIG(status)：在WIFSIGNALED返回true的前提下，返回导致子进程终止的信号编号
  • WIFSTOPPED(status)：如果引起返回的子进程当前已停止，则返回true
  • WSTOPSIG(status)：在WIFSTOPPED返回true的前提下，返回导致子进程停止的信号编号

• 收割顺序不固定

• wait(&status)是waitpid的简化版，相当于waitpid(-1, &status, 0)

休眠进程

pause：让调用函数休眠，直到该进程收到一个信号

• 父进程等待子进程结束：waitpid()

• 子进程等待父进程结束：

  • 轮询（polling):getppid()返回父进程PID，如果父进程未结束则PID一直不等于1

    while (getppid() != 1)
        sleep(1);

竞争：Shell一行执行多个命令，当父进程结束，就开始执行下一个命令，不管子进程是否执行完。因此“先父后子”子进程的数据会与其他进程的随机交叉。“先子后父”，则不会交叉。

加载和运行程序

int execve(const char *filename, const char *argv[], const char *envp[])

• 可执行对象文件filename
• 参数列表argv
• 环境变量列表envp
• execve调用一次，不返回
  • 只有在出现错误(例如无法找到文件名)时才返回

Unix Shell

Shell进程（父进程）先fork出一个子进程，然后子进程exec执行用户输入的命令/程序

• 父进程wait，直到子进程结束（前台模式）
• 父进程不wait（最后一个参数为&），可以继续输入其他命令（后台模式）

异常控制流III（信号）

• 不可靠信号：也称为非实时信号，standard signal

  • 不支持排队，信号可能会丢失，比如发送多次相同的信号，进程只能收到一次
  • 信号值取值区间为1~31（一般常见的信号）

• 可靠信号：也称为实时信号，real-time signal

  • 支持排队，信号不会丢失，发多少次，就可以收到多少次。
  • 信号值取值区间为32~64

信号产生的原因

• 硬件：敲键盘（Ctrl+C）
• 内核检测到某个系统事件：除以0，子进程终止等
• 进程调用了某些系统调用：如kill(),raise()
  • 让内核给目标进程发信号
  • 进程可以自己发送信号给自己

接收信号

• 时机：当进程从内核态刚切换到用户态时
• 信号一定是在内核态发送的，发完信号从内核态转为用户态时，处理之前发送给该进程的所有信号（通常从小到大处理）
• 该进程工作在用户态期间，不会产生新的信号（因为要先进入内核态，才能产生信号）
• 在内核态，signal信号不起作用
• 在用户态，signal所有未被屏蔽的信号都处理完毕

处理信号

对于收到的信号，进程可以有3种处理方式

• 忽略信号
• 终止
• 捕获信号，执行用户层级的signal handler

待处理信号

已经发送，但还没有接受的信号

• 每个类型最多可以有一个待处理信号
• 如果一个进程有一个类型为k的待处理信号，那么后续发送到该进程的类型为k的信号都将被丢弃
• 一个待处理的信号最多只能被接收一次。

阻塞信号

当一个信号被block时

• 仍可以被发送
• 但是其待处理信号不会被接受
• 直到该进程unblock这种信号

进程组

• 可以发送信号给多个进程，依赖于进程组（process group，pg）

• 每个进程仅属于一个进程组，进程组由一个非负数标记（进程组ID，pgid）

• 默认情况下，自己和自己的父进程属于同一个进程组

pid_t setpgid(pid_t pid, pid_t pgid)

• 把进程pid的进程组设置为pgid
• 如果pid=0，那就是指当前进程
• 如果pgid=0，那就是用pid作为pgid，“自立门户”
• setpgid(0,0)：将当前进程创建成一个新的进程组

shell为每个作业（job）创建一个单独的进程组，通常进程组ID取自作业中的父进程之一

系统调用可以被中断

当一些slow system call被信号中断后，signal handler捕获了一个信号并进行处理和返回后，system call就不继续执行了，而是立刻返回用户程序，并设置全局变量errno来报错。例如前面提到的sleep，可能提前返回

并发问题

父进程在addjob之前收到了子进程终止的信号，执行deletejob。相当于删除了一个不存在的左右，而后续又会执行addjob把这个已终止的子进程加入作业。这个错误成为竞争。

需要在fork之前阻塞SIGCHLD信号，在addjob之后再解除，保证加入了之后再删除。

等待信号

sigsuspend()：先将所有信号都阻塞，然后执行休眠，最后再解除阻塞。这样可以保证pause()不被其他信号中断

非本地跳转

int setjmp(jmp_buf env)和void longjmp(jmp_buf env, int retval)

setjmp：调用一次，返回多次。setjmp时返回0，longjmp时返回非0(retval)

longjmp：调用一次，从不返回

• 将当前堆栈上下文保存在env缓冲区中，供longjmp稍后使用，返回0

• 从env缓冲区中恢复堆栈上下文

• 触发最近一次初始化env的setjmp调用的返回值

• setjmp然后返回非零返回值

CPU调度

性能评价指标

• 周转时间，即从任务到达到任务完成的所需时间
  • 平均周转时间反应整体性能，牺牲长任务换来整体更高水平
  • 不能太公平，需要考虑用户感受、长任务长时间不被调度等问题
  • 如果长任务来自付费用户，则无法接受为了整体性能而牺牲
• 响应时间，即从任务到达到第一次被调度的所需时间

First In,First Out(FIFO)

，先到先得

• 优点：简单
• 缺点：当任务长度差距较大时，平均周转时间较长

Shortest Job First(SJF)

短任务优先

• 优点：有助于减小平均周转时间
• 缺点：响应时间很长
• 局限性：只能处理同时到达，若长任务先到达，则无法处理

Shortest Time-to-Completion First(STCF)

在 的基础上允许抢占，即剩余时间最短的任务优先

Round Robin(RR)

基于时间片，轮流执行任务

• 优点：响应时间短
• 缺点：增加上下文切换的开销

I/O问题

• I/O操作远比CPU周期要慢

• 进程执行I/O操作时，要block住，不能执行对应的CPU操作，直到I/O完成

• 则会出现局限性：

  • 剩余时间小的任务，I/O与其他任务相比较多，浪费CPU资源
  • 解决方案：当前任务执行I/O时，CPU执行其他任务

Multi-Level Feedback Queue (MLFQ)

尽可能短任务优先减小，对于周转时间和响应时间均友好

• 优先级策略

  • 优先级高的作业先执行
  • 优先级相同的按时间片轮流执行（RR）
  • 刚进入系统的作业优先级最高
  • 用完当前优先级所分配的时间后降级
  • 一段时间后，将所有作业均设为最高优先级

• 问题总结

  • 针对上述优先级策略的对抗、欺诈行为（如经常做无用的I/O，它则长时间是最高优先级）

Proportional Share

不追求优化周转时间或响应时间，而是保障每个任务得到一定比例的CPU时间

• • 随机算法

  • 每个任务持有一定的tickets，生成随机数，落在哪个任务的范围内，就调度哪个任务

  • tickets比例决定优先级

多核CPU调度

Single-Queue Multiprocessor Scheduling(SQMS)

一个大队列，哪个核闲置，就调度一个任务

• 优点：Load balance
• 缺点：性能差
  • LOCK开销大
  • cache affinity差
  • 扩展性不好
• 改进：
  • 尽量调度到一个CPU上
  • 少数任务切换

Multi-Queue Multiprocessor Scheduling(MQMS)

每个CPU核一个独立的队列（与上述策略恰好相反）

• 优点：性能好

  • Lock冲突少
  • cache affinity好

• 缺点：load imbalance

• 解决：

  • migration

  • work stealing

虚拟内存I（简介）

内存API

• malloc()，free()不是system call，只是库函数。库内部通过一定的结构来保存当前有多少可用内存

• 如果程序malloc的大小超出了库所留存的空间，那么将首先调用brk系统调用来增加可用空间，然后再分配空间

• free时，释放的内存并不立即返回给OS, 而是保留在内部结构中

• brk

  • 改变heap区大小的system call，修改heap end指针
  • 不要直接调用，一般都是内存分配的库函数调用

• mmap：system call

• calloc()：malloc() + 初始化为0

• realloc()：重新分配空间，扩充分配空间。具体操作是找到一个更大的空间，然后把旧的数据复制过去，返回新空间的指针

页表

• 页表是将虚拟页映射到物理页的页表条目(PTE)数组

• 页命中：引用VM中的字在物理内存中（DRAM缓存命中）

• 缺页：引用VM中的字不在物理内存中（DRAM缓存不命中）

• 将PTE中扩展出权限位

  • 同一物理页对于不同的进程具有不同的权限

  • 缺页处理程序在重新映射之前检查权限，如果非法，给进程发送SIGSEGV信号(段错误)

为什么要使用VM

• 有效地使用主内存：使用DRAM作为部分虚拟地址空间的缓存
• 简化内存管理：每个进程获得相同的统一线性地址空间
• 隔离地址空：一个进程不能干扰另一个进程的内存；用户程序不能访问特权内核信息

虚拟内存II（地址翻译）

CPU利用硬件MMU(Memory Management Unit)去做地址翻译

段式内存

3个segment

• 最高两位：00-code，01-heap，1X-stack
• 有些系统将code和heap放在一个segment，以节省1个bit

4个segment

• 最高两位：00-code，01-data，10-heap，11-stack

由VA计算PA

• 首先分离前两位，判断是哪一段；后面的部分作为偏移量
• 再比较偏移量和size，必须严格小于，否则就是内存访问越界。
• base+偏移量即可得到PA
  • 对于stack段，地址是负增长，因此需要先计算出stack段在虚拟内存中的最大空间大小。base-(最大空间-偏移量)得到PA

页式内存

• 虚拟地址(VA)

  • ：虚拟地址
  • VPN：虚拟页码
  • VPO：虚拟页偏移量

• 物理地址(PA)

  • ：物理地址
  • PPN：物理页码
  • PPO：物理页偏移量(与VPO相同)

• ：页面

  • 因为是页偏移量，所以VPO和PPO都是p位；剩余位数是VPN和PPN的

page table的问题

• 运行太慢（两次访问内存）
• 占用内存空间太大

快表(TLB)

TLB是MMU中一个小的虚拟内存的缓存，每一行保存一个PTE，有高度的相连度

利用TLB加速地址翻译，减少一次内存访问

VA = VPN + VPO = TLBT(tag) + TLBI(index) + VPO

• TLBT：标记位tag
• TLBI：组索引
  • m个条目，n路组相连，则一共有组，TLBI有位
  • 剩余位为TLBT的位数

PA = PPN + PPO = CT(tag) + CI(index) + CO(offset)

• CT：标记位

  • 除去组索引和块偏移的剩余位

• CI：组索引

  • 一共有m个组，组索引有位
  • 紧接在CO之前

• CO：块偏移

  • 内存访问是针对m字节的字的，行大小为n字节，则一行有个块
  • 块偏移则有位

**注意：**先按组索引找到对应的组，组索引不是开头那几位

混用页式和段式内存

• 页式内存: 细粒度，空间开销大，适合稠密地址空间
• 段式内存：粗粒度，空间开销小，适合稀疏地址空间
• 混用: 利用二者优势

如果内部空，效率也不高

多级页表

多级页表的VA有VPN 1~VPN k + VPO组成

其中VPN i是页表的组索引，由组索引在当前级别页表中确定下一级别页表的基地址，在结合下一级别页表的组索引，以此类推知道在k级页表确定最终的PPN。

倒页表

由PPN找VPN

crazy things

虚拟内存IV（动态内存分配）

malloc

• 成功：返回一个指向内存块的指针

  • 大小对齐8字节(x86)或16字节(x86-64)

  • 如果size == 0，则返回NULL

• 不成功：返回NULL(0)并设置errno

free

• 将p指向可用的内存池，返回p
• p必须来自之前的malloc或realloc

other

• calloc：malloc的版本，将分配的块初始化为零。
• realloc：更改先前分配的块的大小。
• sbrk：由分配器内部使用，用于增加或缩小堆

最大限度地提高吞吐量和峰值利用率

聚集有效负载

：malloc(p)产生一个有效负载为p字节的块，在请求完成后，聚合有效载荷是当前分配的有效载荷的总和

当前堆大小

：假设是单调不变的，即堆只在分配器使用sbrk时增长

峰值利用率

即之前最大的聚集有效负载除以当前堆大小

内部碎片

一个已分配的块比有效负载大时，则会发生内部碎片。

来源：

• 维护堆数据结构(如指针)的开销
• 为了对齐所进行的填充
• 策略(例如，返回一个大块来满足一个小请求)

外部碎片

当空间内存合计起来足够满足分配请求，但没有一个单独的空闲块足够大

因为外部碎片难以量化且不可能预测，所以分配器采取策略：维持少量的大空闲块，而不是维持大量的小空闲块

隐式空闲链表

• header中存储块的大小。因为块大小对齐，地址低位总是0，于是将其用作已分配/空闲的标志（当读取块大小时，需要将该位置回0）

• 用当前地址的header加上块大小的偏移量即可得到下一个块。所以顺序连接了所有块

• 任何操作都是线性复杂度，开销很大

查找空闲块

• first fit：从头搜索list，返回第一个符合要求的块

  • 线性复杂度
  • list开始部分有很多碎片

• next fit：从上一次搜索结束的地方开始下一次搜索

  • 均匀使用整个list
  • 可能比first fit快（因为大的空闲块都在后面）

• best fit：搜索整个list，找到所有符合条件的块，返回最小的一个

  • 比first fit更慢

• worst fit：与best fit相反，返回最大的一个块

  • 避免best fit带来的小碎片
  • 一般的碎片化也很严重，与best fit性能相当

• 无法找到合适的块，调用sbrk()系统调用扩大heap区

分配空闲块

由于需要的空间可能小于空闲空间，我们可能需要分割块

free块

• 简单地将已分配标志改为空闲状态，但会导致两个空闲块相邻，但各自块大小均不足而被跳过
• 合并前后的空闲块
  • 为了便于向前搜索，在块末尾加上footer
  • 但前一块是空闲块才需要footer，占用块则不需要。所以在当前块的header空闲位增加标记位，标记前一位是空闲还是占用，空闲了才去看它的footer。
  • 立即合并和延迟合并

显示空闲链表

• 维护空闲块的链表
• 在空闲块的header之后，加入next和prev指针，之前前一个和后一个空闲块（已分配块相应的位置用作负载）

free块

• 后进先出LIFO：在空闲列表的开头插入释放块

  • 简单，常数时间
  • 研究表明碎片比地址顺序更糟糕

• 地址顺序策略：按照地址顺序，即addr(prev) < addr(cur) < addr(next)

  • 需要搜索
  • 研究表明碎片比LIFO低

vs隐式链表

• 分配实现开销与空闲块成线性关系，而不是所有块
• 释放块的复杂度增加，需要遍历寻找合并目标
• 链表需要额外的空间

分离的空闲链表

每个大小类的块都有自己的空闲链表

简单分离存储

• 每个大小类的空闲链表包含大小相等的块
  • 如{17~32}类，所有块的大小都是32
• 按照目标大小选择对应的类，从中分配一个块，使用剩余的部分就浪费了，变成内部碎片
  • 如目标大小是20，则分配一个32的块
  • 如果该类中没有空间，就向OS申请一个这样大小的内存
• 缺点：内部碎片和外部碎片（因为不合并）

分离适配

• 每个空闲链表中是一个空间范围的空闲块

• 搜索对应大小类的空闲链表，直到找到合适的块

  • 如果找到了一个合适的块：按照分割实际使用大小后，剩下的部分放到对应大小类的空闲链表中
  • 如果找不到块，就尝试下一级更大的空闲列表
  • 不断重复，直到找到合适的空闲块。

• 如果还是找不到，则用sbrk向OS申请额外的堆内存，分割出实际使用大小后，把剩下的部分放到合适的空闲链表中

• free块时，放到对应大小类的空闲链表中即可。

• first fit + 分离适配 的性能与在整个堆 best fit 的性能相当，但效率快很多

伙伴系统

• 分离适配的一个特例，每个大小类都是2的整数幂

• 为了分配大小的块

  • 在比大的块中选择最小的块，每次递归二分这个块，直到大小与相等
  • 每次剩下的半块（即伙伴）被放到相应大小类的空闲链表中

• 当释放一个的块

  • 找到其伙伴进行合并，递归合并，直到遇到已分配的伙伴为止

• 伙伴的地址很好计算，仅与自已有一位不同

• 大小规整，会带来内部碎片

垃圾收集

• 自动回收已分配的空间，应用不用free

• “保守”的垃圾收集器不一定会收集到所有垃圾

• 假设内存管理者可以区分指针和非指针

将内存视为一个有向图：

每个块是图中的一个节点，每个指针是图中的一条边。不在堆中指向堆中的指针称为根节点（例如寄存器、堆栈上的位置、全局变量）

保守Mark&Sweep

• 在每个块的头部使用额外的标记位，标记从根开始并在每个可到达的块，扫描所有未标记的块和空闲块。

• is_ptr()：通过检查一个字是否指向已分配的内存块来确定它是否是指针。但是，在C中指针可以指向块中间

• 有一堆类似上述的API，用来完成标记和扫描

• 确定块的起点：使用平衡二叉树来跟踪所有已分配的块，平衡二叉树的指针可以存储在header中(使用两个额外的字)。利用size判定指针p是否在该段内存中。

• 把一切看起来像指针的东西都当做指针

内存相关的危险和陷阱

• 间接引用坏指针
• 读未初始化的内存
• 允许栈缓冲区溢出
• 假设指针和它指向的对象大小相同
• 造成错位错误
• 误解指针运算
• 引用指针而不是它指向的对象
• 引用不存在的变量
• 多次free
• 引用被释放的块
• 没有释放块

工具

• 调试器：gdb

  • 发现错误的指针解引用很好用
  • 很难检测到其他内存错误

• 二进制翻译器：valgrind

  • 强大的调试和分析技术
  • 重写可执行对象文件的文本部分
  • 在运行时检查每个单独的引用（错误的指针，覆盖，在分配块之外的引用）

虚拟内存III（swap,system,mmap）

swap

• 物理内存资源不够时，只能将部分内存中的内容交换到磁盘上

• 磁盘上需要保留一定空间，专门用来存放交换出来的内存中的内容

• 当空闲页面数量小于一定阈值，后台线程就负责淘汰页面，直到空闲页面数量大于一定阈值

替换策略

• OPT

• FIFO

• random

• LRU

Linux

• task_struct中的mm指向mm_struct
• 在其中页目录pgd确定mmap
• 找到vm_area_struct
• 其中有vm_end和vm_start对应每个虚存区域的起始地址；vm_next指向下一个区域的vm_area_struct
• vm_flags标注着该进程是否私有

如何判断VA是否合法：

• 扫描所有vm_arear_struct，判断他是否在某个段的合法区域内
• 再看权限是否合法，如果只写/只读/读写
• 实际实现中是将链表组织成了树。

mmap

• 将一个文件、设备或者其它对象映射进内存
• 脏页在内存和交换空间之前来回复制

MAP_SHARED

• 对应射区域的写入数据会复制回文件内，而且允许其他映射该文件的进程共享。
• 但不保证立即写回文件，有一定延迟。显式调用msync()/munmap()可以强制刷回文件

MAP_PRIVATE

• 创建一个私有的copy-on-write映射，写入内容不反映到磁盘
• 对应射区域的写入操作会产生一个映射文件的复制，即私有的"写时复制"(copy on write)，对此区域作的任何修改都不会写回原来的文件内容。
• 私有对象的副本：对映射的更新对映射同一文件的其他进程不可见，并且不会传递到底层文件。

SIGBUS

读写在虚拟内存范围，但不在当前文件所在页的范围内

SIGSEGV

读写不在虚拟内存范围内

重看fork

• vm_area_struct为这些区域创建一个新的进程，作为私有的Copy-On-Write

• 任何进程对这些页面的写入都会导致页面错误

• 错误处理程序识别copy-on-write，复制页面，并恢复写权限。

• 副本复制被推迟到绝对必要的时候(例如，当其中一个进程试图修改共享页面时)

如果有一个进程试图对私有区域的一些页进行写入操作，就会触发保护故障。Fault handler会发现这个区域比较特殊，是私有的copy-on-write区域，则不会报错，而是做一些特殊处理

• 在物理内存中创建页的新副本
• 更新页表项以指向新副本
• 恢复对页的写权限