《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 →

《现代操作系统》读书笔记——进程

一个进程就是一个正在执行的程序实例,它包括程序计数器、寄存器以及变量的当前值。一个程序运行,它的逻辑计数器装入 CPU 的程序计数器中;一个程序暂停,CPU 的程序计数器被保存在内存的逻辑程序计数器中,在下次运行前不占用 CPU。 要特别注意的是,进程并不是在 CPU 中一直运行的,CPU 会在各进程之间来回切换,所以每个进程执行的速度是不确定的。所以,大多数进程并不受 CPU 多道程序设计或其它进程相对速度的影响。 进程的创建和终止 有四种情况会导致进程的创建,它们分别是系统初始化、正在运行的程序执行了创建进程的系统调用、用户请求创建一个新进程、一个批处理作业的初始化。拿 Linux 为例,Linux 启动时的第一个进程是 0 号进程,它是所有进程的祖先。其次是 1 号进程,它是所有用户进程的祖先。 我们都知道 Nginx。当我们启动 Nginx 后,它一直在默默地监听端口执行 WEB 服务,而我们没有感知。这一类进程,便是守护进程。 任何进程,都可以创建一个新的进程,这个进程便是子进程,执行的是 fork 系统调用。进程可以 fork 子进程,子进程共享父进程的数据,但是,子进程对数据做的任何修改,对于父进程,都是不可见的。子进程的内存地址空间,是父进程的副本,是不同的地址空间。 进程只能有一个父进程,但是一个进程可以有多个子进程。在 UNIX 中,进程不能剥夺其子进程的继承权。 可写的空间是不共享的,共享的空间是不可写的。子进程可以共享父进程的内存空间,但是要通过写时复制共享。即在修改部分内存,先要明确地复制,以确保发生在私有的内存区域。 进程终止通常由下面的情况引起,正常退出、出错退出、严重错误、被其他进程杀死。其中后面两种情况是非自愿的。Linux 中自愿终止进程可以通过调用 exit 系统调用完成。 进程的状态 进程由三种状态,运行、阻塞和就绪。 处在运行态的进程,在这个时刻实际占用 CPU。 处在就绪态的进程具备可以运行条件,但是因为其它进程正在运行,而被操作系统暂停运行。 处在阻塞态的进程,因该进程调用了本地阻塞的系统调用,导致暂停运行。处在阻塞态的进程,不具备可以运行的条件。除非外部某实践发生,例如本地阻塞的调用完成,方能够转换为就绪态,等待操作系统调度。 进程的实现 操作系统维护这一个进程表,每一个进程的详细信息都保存在这张进程表中。包括程序计数器、堆栈指针、内存分配情况、文件打开情况、中断向量等。 如前面所说,每个进程都不是一直在 CPU 中运行地。其中就绪态和阻塞态是非运行状态。当操作系统将正在运行的进程切换为就绪态,或者进程因为调用了本地阻塞的系统调用而进入阻塞态时,其运行信息被保存在进程表中。当操作系统重新切换进程为运行状态时,将进程表中的信息恢复,就像进程没有中断一样。 以 IO 为例。当一个进程 A 调用了网络 IO 的系统调用时,由于该系统调用时阻塞的,于是操作系统将其切换为阻塞态,并且将它的现场都保存在进程表中,并将此地址与中断向量映射保存。然后,切换 B 进程。一段时间过去,此时可能是 C 进程在 CPU 中运行,A 进程调用的 IO 完成了,则该硬件发生了一个中断。此时,操作系统将中断正在运行的 C 进程,同时通过中断向量找到进程表中的 A 进程的现场并恢复到 A 进程没有中断时的状态,继续运行。
Read more →

《现代操作系统》读书笔记——线程

Read more →