操作系统复习指南

1、CPU 调度算法

了解CPU 调度算法，如先到先服务、最短作业优先、轮转、多级反馈队列等调度算法，
以及掌握多处理器调度的特殊性。

T_周转时间 = T_完成时间 - T _到达时间

FIFO： 平均周转时间很大

SJF： 当一个长时间的任务先到达时，平均周转时间也会很大， 因为不能停止执行。

STCF： 放宽假设条件， 进程可以上下切断， 周转时间很好。

T_响应时间 = T_首次运行 - T _到达时间

STCF 的响应时间不好 ， 引入RR。

RR：根据时间片切换进程，均摊上下文切换成本，RR响应时间好， 但周转时间不好， 陷入死循环。。。

于是引入MLFQ， 综合解决两个问题。

MLFQ：

• 相同优先级的进程按RR调度

• 如果 优先级 A > B ， 先运行A

• 初始工作时，放到最高优先级队列中

• • 工作用完优先级后，降低优先级
  • 如果在工作在时间片内主动释放cpu， 优先级不变

• 经过一段时间，重新把所有的的进程放到最高优先级

进程可能恶意每次都在快运行完的时候主动释放cpu， 因此，更改第四条如下

• 如果进程用完了，一个优先级上的时间片段， 则降低优先级，无论是否主动释放cpu

确保每一个工作获得一定的比例的cpu时间， 而不是优化cpu的周转时间和响应时间， 引入比例份额调度。

彩票调度： 按彩票的数量多少来运行程序， 彩票多概率大运行多，当任务短的时候，有随机性， 引入步长调度

步长调度： 步伐短运行地多，无论怎样都是按比例，缺点是需要全局状态， 当一个新的进程加入时， 要更新全部进程的当前步长， 彩票调度只需要一个全局变量，总的彩票数。

多处理器调度： 处理缓存一致性问题， 硬件上，cpu监听总线更改缓存，软件上：

单队列调度（SQMS）： 简单，但是缓存不亲和

多队列调度（MQMS）：天生缓存亲和， 但负载不均衡！（工作窃取）

2、进程和线程

掌握进程和线程的概念，熟练使用进程和线程相关编程接口，如fork，exec，wait，
pthread_create，pthread_join等。

进化就是运行中的程序， 一个进程可以创建多个进程。

进程之间不共用内存， 线程之间可以共用内存， 但每一个线程都有自己的堆栈。

• fork()

子进程改变全局变量不会改变父进程的值， 子进程有自己的程序运行空间， copy自父进程

#include <stdio.h>
#include <stdlib.h>
#inclucde <unistd.h>
int main(){printf("hello world(pid: %d)\n",(int)getpid);int rc = fork();if(rc < 0) {// 创建失败printf("error"+ stderr);}else if(rc == 0){// 子进程printf("hello, i am child (pid: %d)",(int)getpid());}else {//!!!!!!!! 注意父进程的 rc 值是 子进程的 pidprintf("hello, i am parent of %d (pid: %d)", rc, (int)getpid());}return 0;
}

• waidpid（）

#include <stdio.h>
#include <stdlib.h>
#inclucde <unistd.h>
#include <sys/wait.h>
int main(){printf("hello world(pid: %d)\n",(int)getpid);int rc = fork();if(rc < 0) {  // 创建失败printf("error"+ stderr);}else if(rc == 0){// 子进程printf("hello, i am child (pid: %d)",(int)getpid());}else {//!!!!!!!! 注意父进程的 rc 值是 子进程的 pidint wc == wait(NULL);printf("hello, i am parent of %d (wc: %d) (pid: %d)", rc, wc, (int)getpid());}return 0;
}

rc = wc

fork 用作相同程序的拷贝作用，执行不同的程序时， 可以用

• exec()

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <fcntl.h>
#include<sys/wait.h>int main(int argc, char * argc[]){int rc = fork();if(rc < 0){printf("error" + stderr);exit(1);}else if(rc == 0){close(STDOUT_FILENO);// 关闭标准输入与输出open("./p4,output",O_CREAT | O_WRONLY | O_TRUNC, S_IRWXU);  char * myargs[3];myargs[0] = "wc"; // 可运行的程序myargs[1] = "file.c";myargs[2] = NULL;execvp(myargs[0],myargs);while(true);// this will be not ecec}else {int wc = wait(NULL);}    retrun 0;
}

// todo

3、并发同步

掌握进程并发同步相关概念，如死锁、活锁等概念，真实应用中存在的不同类型的同步
问题，熟练使用pthread库中的相关同步函数进行编程。

4、地址空间

掌握地址空间的概念，以及用户态堆内存的管理。

一个进程的地址空间应该包含运行的程序的所有内存状态，操作系统给程序的抽象， 包括代码块， 堆，栈，真实的物理空间可能在任意的地方，地址空间是连续的0KB -> 16KB 。如下图：

所谓堆内存（属于地址空间）， 申请和释放都是又程序猿自己自己自己完成（注意这里操作的是地址空间，虚拟的）。java不用

分配：

void malloc（size_t size） , size大小一般为宏来设定， 比如 sizeof(double), 注意 void 的返回类型 是返回地址的指针，可以强转， 如下：

int *x = malloc(sizeof(int));

释放：

free(x) , 分配的大小不会被用户传入， 必须由内存分配库本身记录追踪。

常见错误：

• 忘记分配内存（这个常犯， 常犯， 给一个指针赋值！！！！指针是存放在栈中的， 4个字节的）

• 没有分配足够的内存

• 忘记初始化分配的内存， NULL 一般输出为 0， 但0 不等于 NULL ，默认都是0

• 忘记释放内存（这个我一般都不是释放 ^ _ ^，web、操作系统等长时间运行的程序一定需要！！）

• 反复释放内存（内存都不释放， 这个绝对不会发生的）

• 用完之前释放内存

• 错误调用free（）， 参数传入错误的值。

5、同步原语

掌握锁、条件变量、信号量三种同步机制（熟练使用pthread库中的函数），并使用这些
机制解决实际应用问题，如生产者消费者问题。

6、分段与分页

掌握虚拟内存管理中的分段与分页机制的原理，以及比较其优缺点。

动态重定位：

基于硬件的动态重定位，使用内存管理单元（MMU）给地址空间分配内存，效率低下， 造成很多内部碎片（图中allocated but not use）。

分段：

因此引入分段解决内部碎片问题：MMU给地址空间内的每一个逻辑段都分配内存。

段的引用： 显示方式

于是乎， 在内存上产生很多外部碎片， 解决方法，基于空闲列表 和 各种管理算法：

这里我觉得不会考，但列一列：

• 最优匹配

• 最差匹配

• 首次匹配

• 下次匹配

• 分离空闲列表：经常申请的内存空间，给它一个独立的列表

• 伙伴系统： 二分分配， 合并和分配的时候很方便， 二进制与二叉树的巧合

可以看出分段会产生外部碎片， 这是一个很根本的问题，不通用， 即使有管理内存算法！

以上不会考的，应该考二级页表！

分页：

分页不是将一个地址空间按逻辑段分， 而是分割成固定大小的单元，称为 页帧。

页表： 记录每一个地址空间的每一个虚拟页（页帧）在物理内存中的位置，页表是每一个进程数据结构。

物理帧号（PFN）或称 物理页号（PPN physical page number）： 真实的物理 页帧 地址。

• 地址空间划分：

• 物理地址划分

页表项（PTE page table entry）： 记录 PFN

上图中中间的地址转换（address translation）就通过页表来存储！！

例子：

地址空间 地址 21 -> 010101

从物理地址 （vpn 01 推出 ）中拿出PTE，取出 PFN 得到地址空间的真实的物理地址， 偏移量不变， 因为页帧一样大。

如何拿出vpn对应的PTE：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT             //取出VPN
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))  // 算出物理地址， 拿到PTE的物理地址

于是呢， 有两次的内存访问， 慢！

页表存放：

简单的存放线性页表， 32 位的地址空间， 4KB（2^ 12）的页大小（大部分os，windows，linux），PTE个数：2^32 / 2^12 = 2^20, PTE大小（假设）4B， 线性页表大小 4B * 2^20 = 4MB, 所以一个进程就 4MB内存， 10个就==。。。==

以上就是页表的两个缺点！

先比较优缺点：

策略	优点	缺点
分段	很好支持稀疏地址空间，很快，算法简单，适合硬件完成，地址转换的开销极小， 代码共享（如果代码独立的段中，可以被多个运行程序共享）。	不支持一般化的稀疏地址，产生外部碎片问题很根本，难以避免，随时间推移，管理难，分配也困难。
分页	不会导致外部碎片， 很灵活，支持稀疏的地址空间	速度较慢，要两次访问内存，有可能产生内存浪费

7、TLB， 多级页表

掌握TLB 与多级页表，掌握多级页表相关的计算，比如根据地址位、页面大小、PTE 大
小等条件，进行虚拟地址到物理地址的转换；掌握多级页表的访问过程。

第6点的页表的两个问题需要解决！

解决问题1： 慢

TLB：

TLB（地址转换旁路缓冲储存器）也叫 地址转换缓存， 频繁发生虚拟到物理地址的硬件缓存。

原理（注意加粗， ** **）：

VPN = (VirtualAddress & VPN_MASK) >> SHIFT(Success, TlbEntry) = TLB_Lookup(VPN)  // TLB里面找VPN对应的物理地址if (Success == True) // TLB Hitif (CanAccess(TlbEntry.ProtectBits) == True)Offset = VirtualAddress & OFFSET_MASKPhysAddr = (TlbEntry.PFN << SHIFT) | OffsetRegister = AccessMemory(PhysAddr)  // 直接从** 缓存地址**中拿到实际的物理地址elseRaiseException(PROTECTION_FAULT)else 			// TLB MissPTEAddr = PTBR + (VPN * sizeof(PTE))PTE = AccessMemory(PTEAddr)    //没有找到就多了一次PTE ** 内存 **的寻址， 多了一次一次就一次if (PTE.Valid == False)RaiseException(SEGMENTATION_FAULT)else if (CanAccess(PTE.ProtectBits) == False)RaiseException(PROTECTION_FAULT)elseTLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)RetryInstruction()

缓存：

计算机中有很多缓存，有指令、数据、地址转换， 上面是地址转换的缓存TLB，缓存要小，越小越快（物理限制），有时间和空间局部性。cpu的数据缓存也分为多级。

曾看到一道题， TLB 和 cache 有什么不同？？？？

问题里面的问题：

当TLB中有两条相同的VPN索引两个不同的物理地址， 可以通过ASID标记（进程号）来标记， 这样就不用覆盖掉之前的VPN了， 当两个进程交互运行时， 相同的VPN可以存在于TLB中，还是上一张图。

TLB覆盖问题：

如果程序短时间内访问的页数超过了 TLB中的页数， 会产生大量未命中，因为要重写，因此要支持更大的页， 才不会访问很多页！！

TLB的替换策略：LRU

难道是问题8的？ 不是的，问题8是页的替换， 这里是TLB的替换，思路应该一样的！！

听说腾讯的面试有要求写一个LRU算法！ 基于哈希，哈希每次访问的地址，用一个链表存储哈希后的地址数值，有新的访问就把他放到链表的头结点（包括在链表中的），满了删队尾。（脑子里想起链表的操作删除，插入操作）

解决问题2： 页表很大！

更大的页

页变大， 页表条目减少， 页表也就小了， 但是页变大有内部碎片产生！因为每一页都用不完积累就多

分段+分页

分段与分页相结合，外部碎片再次产生， 页表就是为了解决外部碎片的！！！分段产生外部碎片的根源，无可避免！！

多级页表

于是乎，只有引入多级页表：

问题所在： 页表中存在很多无效区域。

基本思想：将页表分成页大小的单元，如果整页的PTE无效，就完全不分配该页的页表（很重要！）于是引入:

PDE(页目录)： 记录页表的页是否有效， 包含有效位和页帧号。

详细深入具体仔细的一个书上的例子： 完美非无可增，乃不可减，老师说必考。

首先题目： 地址空间 16KB（2^14)，地址位数14位， 页大小 64B（2^6), 偏移位数6 位，VPN位数： 14 - 4 = 8 位，页表项条数为 2^8条 , PTE的大小为 4B（假设），如果是线性页表大小为： 4 * 256B = 1KB，如果分配到PDE中， 每页存 64B/4B = 16 条PTE，一共要256/16 = 16页来存储PTE，于是页目录的索引要 4位（来自黄色的数字），如下图：

计算PTE的PFN算法：

PDEAddr = PageDirBase + (PDIndex(4位就可以找到！) - sizeof(PDE))

于是找到了PTE所在的物理页帧PFN！（第一步）

因为VPN一共8位， 找PTE所在的页用了4位， 还有4位就索引属于该页所有的PTE的那一条（来自红色的数字）！

通过下面的这条式子找到， 实际物理地址的PFN！(第二步)

PTEAddr = (PDE.PFN << SHIFT) + (PTIndex * sizeof(PTE))

最后,计算实际的物理地址！

PhysAddr = (PTE.PFN << SHIFT) + offset

总结，二级页表的访问内存数目达到了两次，访问速度慢， 但是解决了页表大的问题， 是一个时空的折中。

8、页面置换算法

掌握页面置换算法，比如FIFO，LRU等，要求能根据给定的页面访问序列，给出特定算
法的计算过程；掌握CLOCK算法。

这一块课，没有去听，^ _ ^

FIFO

这个好实现， 先进先出，用一个队列就行！

LRU

这个在TLB的替换页面中写了。

LRU 也有问题， 当内存大的时候， LRU的实现代价很大，比如存储LRU的数据结构，因此引入一个近似LRU：

近似LRU

近似LRU 要硬件的帮助， 给页增加一个使用位， 如果为1， 则认为当前页正在被使用。

clock算法

算法思路： 当要进行页替换的时候，检查当前的页的使用位，如果为1， 则意味着当前页在被使用，不适合替换，然后将这个位设置为0， 接着检查下一个页的使用位。 如果为0， 则直接替换。 算法的最坏情况是所有的页都是在被使用的， 把所有的1 都换为 0， 此时再来一遍循环选第一个替换， 实际上这种情况很少出现！

ARC算法

书上没有介绍！

9. 掌握磁盘寻道、旋转、传输时间的概念及计算过程。

10. 了解各种磁盘调度算法的原理。

11. 掌握磁盘阵列RAID-0，RAID-1，RAID-4，RAID-5的原理，并分析各种RAID在容量、可
    靠性、吞吐量三个层面的特性。熟练使用RAID的这些特性进行设计。

12. 了解文件系统接口，如open，read，write，在实现时对元数据和文件内容的读写过程。

13. 了解课堂上讲到的跟操作系统发展史相关的重要人物，并能介绍其主要贡献。

14. 作业中的难点问题需要掌握其解题方法。