《Operating Systen: Three Easy Pieces》读书笔记 —— 第十五章

本章介绍的是如何设计进程的虚拟地址空间,并且提出了几个待解决的问题: 1. 如何使虚拟地址高效。 2. 如何实现应用程序的复杂的功能需求。 3. 操作系统如何完整地掌握对内存的控制权。 4. 严格限制进程对内存的访问。 要实现这四个需求,就如同虚拟 CPU 一样,需要硬件的支持。也就是 hardware-based address translation: 将程序中的虚拟地址空间翻译成进程在内存中的真实地址。 和虚拟 cpu 一样,首先提出三个假设。 1. 进程的内存空间在物理内存中是连续的。 2. 进程的内存空间大小不会超过物理内存。 3. 进程的内存空间大小是相同的。 0KB +—————-+ | Program Code | 2KB +—————-+ | Heap | 4KB +—————-+ | | | | | | | | | Free | | | | | | | | | 14KB+—————-+ | Stack | 16KB+—————-+ 对于一个程序来说,地址空间应该是从零开始增长的。但是,在物理内存中,是多个进程共享同一个物理内存,并且操作系统需要占用从零开始的空间,所以实际上进程在物理内存中被分配的地方并不是从零开始的,也就是说可能是内存中的任意一个地方。所以,需要有一套机制,来实现虚拟地址和物理地址之间的转换 Dynamic Relocation 这个也叫做 Hardware Based Relocation。这要求 CPU 提供两个寄存器,一个是 base,一个是 bounds。
Read more →

《Operating Systen: Three Easy Pieces》读书笔记 —— 第七章

这一章主要的依然是进程调度的问题。由于前面的调度方法 SJF、RR 等等都有一定的缺点。 SJF 优化了周转时间,但是对应答时间是一场灾难。RR 优化了应答时间,但是对周转时间是一场灾难。 这里提出了一个调度方法 Multi-level Feedback Queue (MLFQ)。可以同时解决两个问题。 这个方法的本质就是通过进程过去的运行规律,来对其将来的运行加以干涉。 优先级 建立一些 queue,并且赋予优先级,然后根据进程的运行状态,放到不同的 queue 里。然后根据不同的等级进行调度。 规则 1:如果 A 进程优先级高于 B,那么就运行 A。 规则 2:如果 A 进程和 B 进程优先级相同,则使用 RR 来执行 A 和 B 进程。 我们根据进程占用 CPU 的时间来决定优先级。进程越长,优先级就越低。也就是如果进程是 CPU 密集的,那么它的优先级低,如果进程的 I/O 比较多,那么它的优先级高。可以参考之前的 STCF,一旦 I/O 就会让出 CPU,则就可以将其看成由 I/O 分成的若干个短进程。 决定优先级 但是,当一个进程到达 CPU 的时候,我们没有办法知道它的长短。所以一开始并不能决定它的优先级是高还是低,那么开始就直接将它假定是高优先级的进程。同时操作系统会一直观察。 经过一个时间片后,如果当前进程没有让出 CPU,那么就会将这个进程降低一个优先级。如此循环。如果发现在时间片内进程让出 CPU 了,那么就维持进程在当前的优先级不动。 规则 3:如果一个任务开始执行,那么久吧就把它放在最高优先级中。 但是这样做会有一些问题: 1. 如果高优先级的进程一直在运行,那么低优先级的进程就得不到调度,就会变成饥饿状态。 2. 如果开发者通过一些无关紧要的 I/O 让出 CPU 来欺骗调度,那么它(长进程)也会顺利被认为是高优先级进程。 3.
Read more →

《Operating Systen: Three Easy Pieces》读书笔记 —— 第六章

本章讨论的问题是如何对进程调度。 在讨论之前,现有五个假设: 1. 每个任务都执行相同的时间。 2. 所有的任务都在同一时间到达。 3. 一旦开始,每个任务都会运行至结束。 4. 所有的任务都是 CPU 密集型的。 5. 每个任务运行的时间是已知的。 首先定义一个指标 turnaround time。 First In, First Out (FIFO) or First Come, First Served (FCFS) 先来先服务,顾名思义,按照任务在队列中的先后顺序进行调度。 但是,将第一个假设去除,即每个任务执行的时间不相同,那么就会出现下面的问题。 如果长进程在队列的前面,一系列运行时间短进程在队列的后面,那么时间短的任务就需要等待。 书中的一个比喻很恰当,当在超市排队结账时,前面有一个人推着十个购物车在结账,那么后面的一些只有几件东西的顾客一定是非常绝望的。 Shortest Job First (SJF) 在队列中的几个进程,操作系统选择其中最短的进行调度,然后按照时间进行优先级排序。 但是,如果将第二个假设去除,即任务不是同时到达的,就会出现下面的问题。 如果长进程先到达,短进程后到达,就会出现同样的问题 Shortest Time-to-Completion First (STCF) 上一章说了 CPU 会有一个时钟中断。那么,在长进程运行时,短进程到达了,可以利用时钟中断的时候 OS 掌握控制权,借着这个机会调度新来的短进程执行,然后再恢复长进程的执行。 接下来再定义一个指标 response time,也就是首次响应时间,举个例子,如果用户输入一个字符,结果要等前面的一堆任务完成才能响应,那么很尴尬的是,用户需要坐在显示器前面等待这样一个事情。 如果按照这个指标来看,SJF 对这个指标完成度非常差。 Round Robin (RR) 有一个进程的队列。 在这种方式上,定义了一个 time slice。每个进程运行 time slice 时间后,OS 会切换其它的进程,如此循环,知道进程退出。这样就能做到 response time 变的很小。当然这样也存在了一定的开销,那就是相较于 SJF 和 FIFO 来说,上下文切换就会变得很频繁。
Read more →

《Operating Systen: Three Easy Pieces》读书笔记 —— 第五章

这一章讨论的问题是操作系统如何运行程序,并且掌握 CPU 的控制权。 如上一章所讲,操作系统将程序代码加载到内存中,设置寄存器的值,然后跳转到 main 函数执行。这样,进程是直接在 CPU 运行的,这样对于一个进程来说是最高效的。 但是,对于操作系统来说,需要解决两个问题:如何控制进程以防止其做不该做的事情,如何能够切换正在运行的进程。 限制级的操作 这是解决第一个问题,如何控制进程以防止其做不该做的事情(限制级的操作)。 用户进程是运行在用户空间的,用户空间的运行环境是有限制的,例如其不能进行 I/O 的调用。相对的,这些限制级的操作是需要在内核空间来完成的。一旦用户空间的代码执行了这些操作,就会触发异常。 用于解决这个问题,操作系统引入了系统调用的概念。用户进程在需要限制级的操作时,执行诸如 write() 的系统调用函数,来进行内核空间的操作。 系统调用是操作系统在启动阶段就在 CPU 中注册好的一系列程序,这些程序执行了内核空间的操作,每个系统调用都有相应的数字标识。用户程序需要执行限制级的操作时,只需要执行 trap 指令将自身陷入陷阱,同时传递系统调用标识来代表需要执行什么操作,之后的一切就由操作系统接管了。这样,既保留了进程直接运行在 CPU 的高效率,又实现了对某些操作的限制。 不过,为了避免应用开发者记忆系统调用的标识,操作系统会定义一系列的系统调用函数,来执行 trap 指令,并传递系统调用标识。 一个完整的用户程序进行系统调用的步骤如下: 操作系统在启动的时候初始化一个陷阱列表。 操作系统初始化程序的数据,然后跳转到 main 函数的地方,执行 return-from-trap 指令切换到用户态。 这时,进程需要进行 I/O 请求,于是执行了一个 I/O 相关的系统调用函数(本质上是执行了 trap 指令,传递了 I/O 相关的标识),这时,进程不再控制 CPU,取而代之的是操作系统。 操作系统开始执行这一部分的操作,在处理结束后,操作系统执行 return-from-trap 指令切换到用户态,进程继续执行。 进程结束后从 main 函数返回,这时也会做一次系统调用 exit,操作系统将这个进程的数据清除,整个过程结束。 进程的切换 这是解决第二个问题,操作系统如何保持对 CPU 的控制。 当进程正在运行的时候,操作系统一定是没有占据 CPU 的,这时,操作系统无法干涉进程的运行。 协作式 如前面所讲,系统调用会陷入内核态。在陷入内核态后,操作系统就可以接管 CPU 了。这时,操作系统便可以干预进程的运行了。协作式就是利用了系统调用或者异常来使操作系统获得 CPU 的控制权来进行进程切换的。 但是,协作式有一个问题:它对进程是完全信任的,也就是它信任程序一定不会长时间占用 CPU(每隔一段时间进行一次系统调用)。但是,并不是所有的程序员都会这么做。那么问题来了,如果程序没有系统调用,那么进程将会一直占据 CPU。这样操作系统就没有机会获得 CPU 的控制权。
Read more →

Operating Systen: Three Easy Pieces》读书笔记 —— 第四章

《Operating Systen: Three Easy Pieces》读书笔记 —— 第四章 进程 这一章,主要介绍了操作系统提供给用户的最基本的元素,进程。 进程主要解决了一个问题:如何给用户营造出一个计算机拥有许多个 CPU 的假象,以同时运行多个程序。 这其实是一种对 CPU 的虚拟化,使用有限的 CPU 虚拟出无限的 CPU 来同时运行不同的程序。 但是,一个 CPU 在同一时刻只能被一个进程所占用。这就意味着操作系统每时每刻都在切换不同的进程,操作系统需要决定下一时刻运行哪个进程,以及保存进程的寄存器数据、堆栈数据等来等待下一次运行。 进程的接口 操作系统会抽象出这样一些接口: Create: 创建一个进程,也就是运行一个程序。 Destory: 退出一个进程,销毁进程的上下文。 Wait: 进程暂停执行,等待某件事情发生后继续执行。 Miscellaneous Control: 挂起一个进程,以及恢复执行。 Status: 进程的状态。 进程的创建 进程创建时,操作系统会将硬盘上的代码复制到内存中,同时在内存中初始化数据。 早期的操作系统,会在进程创建时,将所有的代码以及数据复制到内存中。现代操作系统,会进行懒加载,也就是只复制需要用到的数据到内存中。 在这之后,操作系统会找到程序的执行点,也就是 C 语言中的 main 函数,同时将 argc 和 argv 存放到栈中,并开辟一块空间叫做堆(heap),来存储动态的内容。 同时,操作系统会初始化如 I/O 以及文件描述符等。在 UNIX 系统中,会默认创建三个文件描述符,分别是输入、输出、错误。 最后,在上面的准备工作完成后,操作系统会跳转到 main 函数的地方,开始执行。 进程的状态 进程由三个状态,分别是运行、就绪和阻塞。 运行 (Running): 进程在这个状态会占据 CPU。 就绪 (Ready): 进程在这个状态,说明已经准备好执行,正在等待操作系统的调度。 阻塞 (Block): 进程在做诸如 I/O 的阻塞的操作时候,会进入这个状态,这时,操作系统会调度其它进程。 进程的数据结构 // the registers xv6 will save and restore // to stop and subsequently restart a process struct context { int eip; int esp; int ebx; int ecx; int edx; int esi; int edi; int ebp; }; // the different states a process can be in enum proc_state { UNUSED, EMBRYO, SLEEPING, RUNNABLE, RUNNING, ZOMBIE }; // the information xv6 tracks about each process // including its register context and state struct proc { char *mem; // Start of process memory uint sz; // Size of process memory char *kstack; // Bottom of kernel stack // for this process enum proc_state state; // Process state int pid; // Process ID struct proc *parent; // Parent process void *chan; // If !
Read more →

《深入理解计算机系统》读书笔记:5.5 vs 5.6

0x00 前言 没有看过或者没有看到这里的小伙伴们,看到这个标题一定觉得摸不着头脑。那这里就先来解释一下背景。 double poly(double a[], double x, long degree) { long i; double result = a[0]; double xpwr = x; for (i = 1; i <= degree; i++) { result += a[i] * xpwr; xpwr = x * xpwr; } return result; } double polyh(double a[], double x, long degree) { long i; double result = a[degree]; for (i = degree; i >= 0; i–) { result = a[i] + x * result; } return result; } 这是 CSAPP 的两道题,每一题是一段代码,这两段代码实现了同一个功能。这两道题有一个共同的问题,比较这两段代码的性能。
Read more →

csapp-bomb-lab-phase-1

第一题比较简单,但本菜鸡也做了两个小时(╯‵□′)╯︵┻━┻。。。 首先打开事先已经反汇编的 bomb.s 文件,通过 bomb.c 已经知道每一关都是一个函数,它们的命名都是 phase_x,x 代表该关卡的数字,如果某个关卡输入的不正确,就会引爆炸弹 explode_bomb。首先看 main 函数的这几行 400e1e: bf 38 23 40 00 mov $0x402338,%edi 400e23: e8 e8 fc ff ff callq 400b10 <puts@plt> 400e28: bf 78 23 40 00 mov $0x402378,%edi 400e2d: e8 de fc ff ff callq 400b10 <puts@plt> 400e32: e8 67 06 00 00 callq 40149e <read_line> 400e37: 48 89 c7 mov %rax,%rdi 400e3a: e8 a1 00 00 00 callq 400ee0 <phase_1> 400e3f: e8 80 07 00 00 callq 4015c4 <phase_defused> 400e44: bf a8 23 40 00 mov $0x4023a8,%edi 打开 gdb,先给这一行打上断点 break *0x400e23,然后 run 起来。这里可以看到调用了 puts 这个函数,寄存器 %edi 存储的是函数的第一个参数,我们把它的结果打印出来 x/s 0x402338、x/s 0x402378,发现得到了运行 bomb 后输出的字符串。说明第一关就是从这里开始的。
Read more →