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

Redis 的 string

Redis 的字符串就是 SET 和 GET 操作对应的类型,算是 Redis 里最常用的类型了。 0x00 动态字符串 sds Redis 内部的字符串表示,没有直接使用 C 语言字符串,而是对其进行了一定的改造,改造后的字符串在内存管理和长度计算方面的性能都有所提升。 举个例子,假设要存储的是字符串”redis“。 +——–+——–+————-+ | len | alloc | |r|e|d|i|s| | +——–+——–++———–++ | | v v flag ‘\0’ 这个图就是 sds 的内存结构。sdshdr 分四个部分,从左往右一次是字符串长度、开辟的内存空间、sdshdr 的类型以及字符串本身。在字符串初始化好之后,会返回一个指针,指向字符串本身的首地址,也就是 r 的内存地址。这样,既能方便地享受 C 语言字符串带来的兼容性,又可以对内存管理了如指掌。 0x01 redisObj typedef struct redisObject { unsigned type:4; unsigned encoding:4; unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time).
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 →

Redis 源码学习——浅谈 Redis 的字符串实现

Redis 源码学习——浅谈 Redis 的字符串实现 0x00 结构 Redis 的字符串,本质上还是沿用了 C 语言的字符串,但是还是有一些不同。Redis 的字符串附加了一些和字符串本身相关的信息。我觉得这个设计很巧妙(也许是一个常用的技巧,是我太菜了不知道)。 首先来看 sds 的定义 typedef char sds; 在目前的约定下,一个 char 是一个字节,这是开辟内存空间的最小的单位了,方便内存管理(我是这样认为的)。关于字符串的信息,定义在了几个结构体里面。 / Note: sdshdr5 is never used, we just access the flags byte directly. * However is here to document the layout of type 5 SDS strings. / struct attribute ((packed)) sdshdr5 { unsigned char flags; / 3 lsb of type, and 5 msb of string length / char buf[]; }; struct attribute ((packed)) sdshdr8 { uint8_t len; / used / uint8_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[]; }; struct attribute ((packed)) sdshdr16 { uint16_t len; / used / uint16_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[]; }; struct attribute ((packed)) sdshdr32 { uint32_t len; / used / uint32_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits / char buf[]; }; struct attribute ((packed)) sdshdr64 { uint64_t len; / used / uint64_t alloc; / excluding the header and null terminator / unsigned char flags; / 3 lsb of type, 5 unused bits */ char buf[]; }; 这几个结构体,其实是同一个作用,就是记录了字符串的各种信息,它们的区别就是用来表示不同长度的字符串,或者说用来开辟不同大小的空间。里面的几个成员变量,我认为是这样的作用:
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 →

我的 2017 —— 一个 PHPer 的自白

转眼间 2017 年过去了。我已经不能说自己是去年的毕业生了,时光匆匆,感觉自己越来越老了。 这一年,我所经历的,让我收获很多,让我懂得很多,让我明白了很多。也许是明确了某一个目标,也许是其它的什么,我觉得,2017 年也许真的是我的一个开端。 事 说实话,这一段的标题,真的不好想。所以我写的时候,空了出来。这里我要写的是,关于我对编程的一些感悟。经历了一些事,也参加了一些事,觉得,啊,原来我想要的,是这样的。 大会 2017 年,我去了 PHPCON。说实话,这是我第二次花钱去参加大会,也是花钱最多的一次。不过真的觉得很值,因为这次大会,让我明白了很多。首先,是鸟哥关于 PHP7 的介绍。他通过底层实现来介绍 PHP7 的一些优化的地方,但是由于水平有限,我不能听懂。包括韩天峰的演讲,我也一样不能完全理解。究其根本,还是由于我的基础知识太弱导致的。于是,我在会后,努力去学习这些基础知识,才发现,啊,原来他们讲的是这样的! 去年,我给我自己的定位是“Re: 从零开始的编程生活”。今年,也是这么觉得,而且感觉更加强烈了。 小会 值得一提的是,今年 7 月份,我参加了一个 Swoole 的分享会。分享会是在一家咖啡馆里开的,很有氛围(旁边就是 bilibili link(雾。会后,韩天峰 dalao 请了我们外地去的盆友吃了饭(然后被抢买单了(雾。这都不是重点,重点是,通过这次,我明白了,我接下去的路该怎么走。我更加明白了,我要学习哪些东西。 其它 其它嘛,也不好说,说了也不好。懂的自然懂。 书 上面都说了,我也知道自己该看些什么了。于是,我花了半年的时间看完了《深入理解计算机系统》,受益匪浅。同时,我看完了《深入 PHP:面向对象、模式与实践》,了解了很多常用的设计模式,完善了面向对象的很多知识。还有《Go 语言实战》。Go 是我一直想学习的一门语言,现在终于有机会完整地去学习了。我又开始看了《现代操作系统》和《数据结构与算法分析(C 语言描述)》。对于数据库,我现在正在看《高性能 MySQL》,收益颇多。 出游 沙巴 这是部门组织的出游,获得了最佳团队,拿到了一笔经费,于是有了这次出游。这次旅行,我感受到了异国风情,还和海水近距离地接触了。浮潜这个一直不敢做的项目,也尝试了。总之,这是一个不错的地方 四川 是的,今年我又去了四川,和群里的某基友一起去的。不过这次没有在成都逗留,而是直接出发去了稻城亚丁。从四川去稻城亚丁,花费了 3 天时间。从几百米的海拔,到近 5000 米的海拔。在汶川,我看到了璇口中学遗址,感触颇多。在前往稻城亚丁的路上,我看到了任何其它地方都看不到的景色。美!在亚丁,也花了 4 个小时爬山,看到了美丽的风景,真的值了。于是,我的下个目的地是——西藏。 2018 对于 2018,我给自己定了很多目标,不管能不能达成,我都要尽力去做。 2017 年,我虽然看了一些书,但是我觉得还是远远不够的。我希望在 2018 年,我能够阅读完《现代操作系统》、《数据结构与算法分析(C 语言描述)》。这些都是基础中的基础,我现在明白了,当了解了这些后,其它的也都能理解了。还有《高性能 MySQL》也要读完。再有就是《UNIX 环境高级编程》和《UNIX 网络编程》。这也是做服务端编程的基础,这两本书也许读不完,但是我会把它们当做一个持续的目标,这个目标也包括《TCP/IP 详解》。2017 年学习了 Go 语言,但是发现似乎《Go 语言实战》这本书讲的过于宽泛了。我希望能够阅读一遍《Go 程序设计语言》,辅之以实践。 2017 年,我坚持阅读 Laravel 的源码,让我学到了很多。今年,我依然会坚持阅读 Laravel 的源码。同时,我还尝试阅读了 PHP 的源码。发现,把它和上面的三本书配合起来,非常的合适。所以,2018 年,我依然要坚持阅读 PHP 的源码,同时学习扩展的编写。在有余力的情况下,我还要阅读 Nginx 的源码。
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 →