Series /

操作系统学习笔记

Summary

主要参考《现代操作系统》,《操作系统概念》,《操作系统设计与实现》。

其中讲得比较细的是《操作系统概念》,推荐。

Contents

第 1 章 介绍
ch-1-introduction
2021
November 9
中断和异常的区别 中断:是为了设备与 CPU 之间的通信。典型的有如服务请求,任务完成提醒等。比如我们熟知的时钟中断,硬盘读写服务请求中断。中断的发生与系统处在用户态还是在内核态无关,只决定于 EFLAGS 寄存器的一个标志位。我们熟悉的 sti, cli 两条指令就是用来设置这个标志位,然后决定是否允许中断。在单个 CPU 的系统中,这也是保护临界区的一种简便方法。中断是异步的,因为从逻辑上来说,中断的产生与当前正在执行的进程无关。事实上,中断是如此有用,Linux 用它来统计时钟,进行硬盘读写等。 异常:异常是由当前正在执行的进程产生。异常包括很多方面,有出错(fault),有陷入(trap),也有可编程异常(programmable exception)。出错(fault)和陷入(trap)最重要的一点区别是他们发生时所保存的 EIP 值的不同。出错(fault)保存的 EIP 指向触发异常的那条指令;而陷入(trap)保存的 EIP 指向触发异常的那条指令的下一条指令。因此,当从异常返回时,出错(fault)会重新执行那条指令;而陷入(trap)就不会重新执行。这一点实际上也是相当重要的,比如我们熟悉的缺页异常(page fault),由于是 fault,所以当缺页异常处理完成之后,还会去尝试重新执行那条触发异常的指令(那时多半情况是不再缺页)。陷入的最主要的应用是在调试中,被调试的进程遇到你设置的断点,会停下来等待你的处理,等到你让其重新执行了,它当然不会再去执行已经执行过的断点指令。 可编程中断:这类中断可由编程者用 int 指令来触发。在 Linux 中,使用了一个,也是唯一的一个可编程中断,就是 int 0x80 系统调用。硬件对可编程中断的处理与对 trap 的处理类似,即从这类异常返回时也是返回到触发异常的下一条指令。关于可编程中断,还有另外一种说法:软件中断(software interrupt),其实是一个意思.
第 2 章 进程
ch-2-process
2021
September 4
2.1 进程介绍 1 进程的创建 通过 fork 克隆调用进程 通过 execve exec* 函数组结尾字母的含义: e – 环境变量。一个指向环境变量的指针数组被显式传递给新进程的映像。 l – 参数列表。命令行参数单独(一个列表)传递给函数。 p - PATH 变量。使用 PATH 环境变量查找要执行的文件。 v – 参数向量。命令行参数作为指针数组(向量)传递给函数。 通过 fork 创建的子进程与父进程是隔离的,相互不可见。但是父进程打开的文件等资源可以传递给子进程使用。 2 进程的终止 进程退出的原因: 正常退出 异常退出 致命错误 被杀死 3 进程的层次 进程组:一个进程及其所有深层后代构成的整体。 信号相关:发送给一个进程的信号,可以传递到相关的进程组的所有成员。 在 MINIX 中有两个特殊的进程: 轮回服务器(reincarnation server):提供服务器和驱动的重启。 初始化(init):执行 /etc/init 脚本,使其向轮回服务器发出命令,从而启动引导映像中不存在的驱动程序和服务器。如果其中某些进程中止,再生服务器就会重启,从而增加 MINIX 系统的容错性。 (例子:用户登录的过程) 完成此操作后,init 会读取配置文件 /etc/ttytab 以查看存在的终端。 init fork 为每个进程创建一个 getty 进程,在其上显示登录提示,然后等待输入用户名。用户名输入后,getty 会通过 exec 启动 login 进程,将用户名作为参数。如果用户登录成功,login 将执行用户的 shell。所以 shell 是 init 的子进程。 用户的命令创建的 shell 的子进程是 init 的孙子进程。
第 3 章 进程管理
ch-3-process-management
2021
November 9
进程上下文 进程的上下文包括: 用户空间:虚拟内存、栈、全局变量 内核空间:内核堆栈、寄存器状态 进程的状态 下面是进程的状态转移: @startuml [*] -> 创建 创建 --> 就绪 就绪 --> 执行 执行 -> 阻塞 : (调度) 执行 -> 就绪 : (调度) 阻塞 -> 就绪 : (调度) 执行 --> 终止 : (调度) 终止 -> [*] @enduml 从运行到就绪:中断 从就绪到运行:被调度 时间片用完:转移到就绪 1)就绪 —— 执行:对就绪状态的进程,当进程调度程序按一种选定的策略从中选中一个就绪进程,为之分配了处理机后,该进程便由就绪状态变为执行状态; 2)执行 —— 阻塞:正在执行的进程因发生某等待事件而无法执行,则进程由执行状态变为阻塞状态(不是变成等待),如进程提出输入 / 输出请求而变成等待外部设备传输信息的状态,进程申请资源(主存空间或外部设备)得不到满足时变成等待资源状态,进程运行中出现了故障(程序出错或主存储器读写错等)变成等待干预状态等等; 当进程进入阻塞状态,是不占用 CPU 资源的。 3)阻塞 —— 就绪:处于阻塞状态的进程,在其等待的事件已经发生,如输入 / 输出完成,资源得到满足或错误处理完毕时,处于等待状态的进程并不马上转入执行状态,而是先转入就绪状态,然后再由系统进程调度程序在适当的时候将该进程转为执行状态; 4)执行 —— 就绪:正在执行的进程,因时间片用完而被暂停执行,或在采用抢先式优先级调度算法的系统中,当有更高优先级的进程要运行而被迫让出处理机时,该进程便由执行状态转变为就绪状态。 挂起进程在操作系统中可以定义为暂时被调离内存的进程 阻塞的两种情况 因为用户原因,程序所固有的。如等待输入。 因为系统原因,被迫的。如 CPU 被调配给另一个进程。 进程和线程的区别 In a system with the operating system supporting kernel-level threads, the process is the basic unit for resources allocation, while the thread is the basic unit for CPU scheduling.
第 3 章 存储管理
ch-3-storage-management
2021
September 24
存储管理 3.1 无存储器抽象 即让程序直接访问物理内存 缺点:保护和重定位 用户程序很容易破坏 OS 难以同时运行多个程序 3.2 地址空间 1 地址空间 每个进程都有一个自己的地址空间,并且这个地址空间独立于其他进程的地址空 2 简单动态重定位 把每个进程的地址空间映射到物理内存的不同部分。 当一个进程运行时,程序的起始物理地址装载到基址寄存器中,程序的长度装载到界限寄存器 每次进程访存,会自动把地址加上基质,并检查是否越界。(这也是缺点:每次都要进行加法和比较运算) 3 交换 两种处理内存超载的通用方法:交换(swapping)和虚拟内存(virtual memory) 交换(swapping)技术:把一个进程完整调入内存,使该进程运行一段时间,然后把它存回磁盘 虚拟内存:让程序在只有一部分被调入内存的情况下运行。 交换会导致内存产生空闲区(空洞,hole),所以要进行空闲区合并(内存紧缩,memory compaction)内存紧缩的效率很低。 空闲内存管理 使用 Bitmap 管理 按照一定单位划分内存,每个单位对应到内存的一位,表示空闲或占用。 使用链表管理 链表的结点表示一个进程或一个空闲区。保存有如下信息: 类型(空闲或进程) 起始地址 长度 下一节点指针 为新建的进程分配内存: 首次适配(first fit)算法:存储管理器沿着段链表进行搜索,直到找到一个足够大的空闲区,将该空闲区分为两部分,一部分供进程使用,另一部分形成新的空闲区。 下次适配(next fit)算法:每次找到合适的空闲区时都记录当时的位置。以便在下次寻找空闲区时从上次结束的地方开始搜索,而不是像首次适配算法那样每次都从头开始。(性能略低于首次适配法) 最佳适配(best fit)算法:搜索整个链表(从开始到结束),找出能够容纳进程的最小的空闲区。更慢,而且更浪费内存,因为会产生大量无用的小空闲区。 最差适配(worst fit)算法:总是分配最大的可用空闲区 为进程和空闲区维护各自独立的链表,可以提高分配内存的效率,但是内存释放的速度会变慢。 快速适配(quick fit)算法:它为那些常用大小的空闲区维护单独的链表。例如, 有一个 n 项的表,该表的第一项是指向大小为 4KB 的空闲区链表表头的指针,第二项是指向大小为 8KB 的空闲区链表表头的指针,第三项是指向大小为 12KB 的空闲区链表表头的指针,以此类推。 3.3 虚拟内存 虚拟内存的基本思想是:每个程序拥有自己的地址空间,这个空间被分割成多个块,每一块称作一页或页面(page)。每一页有连续的地址范围。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。 分页 由程序产生的地址称为虚拟地址(virtual address),它们构成了一个虚拟地址空间(virtual address space)
第 6 章 进程同步
ch-6-process-synchronization
2021
November 2
信号量 wait () 的定义可表示为: wait(S) { while(S <= 0) ;// no-op S--; } signal 的定义可表示为 signal(S) { S++; } 换言之:Lock & Unlock 信号量为什么会有负数? 信号量表示的是当前可用的资源个数,当信号量为负时,申请资源的进程就只能等待了。所以,信号量是负的多少,就表明有多少个进程申请了资源但无资源可用只能处于等待状态。 为什么要互斥? 多个线程并发访问和操作同一数据且执行结果与访问发生的特定顺序有关,称为竞争条件(race condition)。 程序必须避免竞争条件。 临界区(critical section):只能有一个进程在执行的代码片段。 请求进入临界区的代码段称为进入区(entry section),临界区之后可能有退出区 (exit section),其他代码为剩余区(remainder section)。 解决临界区问题的协议必须满足三个要求: 不该来的时候不要来:互斥 (mutual exclusion)。 该来的时候要来:前进(progress)。如果临界区没有进程,则应当立即让下一个进程进去。 不来可以,一直不来不行:有限等待(bounded waiting)。一个进程在提出进入临界区请求后,只需要等待临界区被使用有上限的次数后,该进程就可以进入临界区。换言之不能饿死。 (《现代操作系统》)不应对 CPU 的速度和数量做任何假设。 抢占内核(preemptive kernel):允许处于内核模式的进程被抢占 非抢占内核(nonpreemptive kernel):不允许处于内核模式的进程被抢占。 实现互斥 —— 忙等待法 连续测试一个变量直到某个值出现为止(通常在循环中实现),称为忙等待(busy waiting)。用于忙等待的锁,称为自旋锁(spin lock)。 屏蔽中断 在单处理器系统中,最简单的方法是使每个进程在刚刚进入临界区后立即屏蔽所有中断,并在就要离开之前再打开中断。屏蔽中断后,时钟中断也被屏蔽。CPU 只有发生时钟中断或其他中断时才会进行进程切换,这样,在屏蔽中断之后 CPU 将不会被切换到其他进程。 总结:我们要防止竞争,而没有进程切换就没有竞争,而没有时钟中断就没有进程切换,而屏蔽中断就没有时钟中断。所以通过屏蔽中断来防止竞争。 缺点: 权限:用户进程不应该拥有屏蔽中断的权力 扩展性:多核处理器就不能用了
第 8 章 习题
ch-8-problem-sets
2021
November 23
8.1 Explain the difference between internal and external fragmentation. 内部碎片 操作系统可以决定虚存的页面大小。当页面比较大的时候,平均的情况下, 最后一个页面中有一半是空的。 多余的空间就被浪费掉了, 这种浪费称为内部碎片(internal fragmentation) 。假设进程平均大小是 s 个字节, 页面大小是 p 个字节, 每个页表项需要 e 个字节。 那么每个进程需要的页数大约是 s/p, 占用了 se/p 个字节的页表空间。 内部碎片在最后一页浪费的内存是 p/2。 (《现代操作系统》P267) 内部碎片是已经被进程使用的,因此叫 “内部”。 除了内存,磁盘分块也会出现类似的情况,当下一帧填不满当前磁盘块的时候, 则磁盘块剩余的部分就保持空闲状态。 同样称为内部碎片。 外部碎片 在系统运行一段时间后内存被划分为许多块, 一些块包含着段, 一些则成了空闲区, 这种现象称为棋盘形碎片或外部碎片(external fragmentation) 。 (《现代操作系统》P289) 外部碎片是尚未使用,但是因为太小无法被分配的。所以称为 “外部”。 8.3 Given five memory partitions of 100 KB, 500 KB, 200 KB, 300 KB, and 600 KB (in order), how would each of the first-fit, best-fit, and worst-fit algorithms place processes of 212 KB, 417 KB, 112 KB, and 426 KB (in order)?
第 9 章 内存管理
ch-9-memory-management
2021
November 23
**基址寄存器(B)**和 界限寄存器 (L) 限定了进程能访问地址的范围 $[B,B+L]$。 这两个值只能以特权指令加载。即必须是内核模式下加载,往往只有操作系统有此权限。 指令与数据绑定到内存地址的时机 编译时(compile time):生成绝对代码(absolute code)。 加载时(load time):生成可重定位代码(reloadable code)。 执行时(execution time):进程在执行时可以从一个内存段移到另一个内存段。绝大多数通用计算机操作系统采用这种方法。 CPU 生成的地址通常称为逻辑地址(logical address),而内存单元所看到的地址(即加载到内存地址寄存器(memory-address register)中的地址)通常称为物理地址(physical address)。 从虚拟地址到物理地址的映射由被称为 内存管理单元(memory-management unit,MMU) 的硬件设备来完成 内部碎片与外部碎片 内部碎片 操作系统可以决定虚存的页面大小。当页面比较大的时候,平均的情况下, 最后一个页面中有一半是空的。 多余的空间就被浪费掉了, 这种浪费称为内部碎片(internal fragmentation) 。假设进程平均大小是 s 个字节, 页面大小是 p 个字节, 每个页表项需要 e 个字节。 那么每个进程需要的页数大约是 s/p, 占用了 se/p 个字节的页表空间。 内部碎片在最后一页浪费的内存是 p/2。 (《现代操作系统》P267) 内部碎片是已经被进程使用的,因此叫 “内部”。 除了内存,磁盘分块也会出现类似的情况,当下一帧填不满当前磁盘块的时候, 则磁盘块剩余的部分就保持空闲状态。 同样称为内部碎片。 外部碎片 在系统运行一段时间后内存被划分为许多块, 一些块包含着段, 一些则成了空闲区, 这种现象称为棋盘形碎片或外部碎片(external fragmentation) 。 (《现代操作系统》P289) 外部碎片是尚未使用,但是因为太小无法被分配的。所以称为 “外部”。 内存管理方案 固定分区(fixed partitions) 将物理内存分为固定的区域。不同的进程拥有不同的基地址。 硬件需求:基址寄存器
第 10 章 虚拟内存
ch-10-virtual-memory
2021
December 3
背景 虚拟内存将用户逻辑内存与物理内存分离。在物理内存有限的情况下,为程序提供了巨大的虚拟内存。 随着动态内存分配,栈向下生长,堆向上生长。但实际上中间空余的虚拟空间并不真实占用物理内存。另外,一个进程可以有多个线程,每个线程有自己的栈,但它们共享一个堆。 虚存的实现方式: 按需分页 按需分段 按需换页(Demand Paging) 延迟交换器(Lazy swapper):仅当需要页时把页换入内存。 页表项的有效位:指出页是否在内存。 若无效页被引用,则触发页故障(page fault)。 **EAT(有效访问时间)**计算: 页故障率 $p$ EAT = (1 – p) x memory access + p (page fault overhead + swap page out + swap page in + restart overhead ) 写时复制 Copy-on-Write (COW) 使得父子进程开始可以共享页,直到其中一方修改内存。 页面置换算法 页置换算法的思想在各种缓存系统中普遍应用。 我们可以将高速容器(如内存相对于磁盘)看作有限个槽。此数量即可用帧数。 基本页置换 假设需要换入一个新帧 有空闲帧,则使用它 否则,选择一个牺牲帧(victim frame) 将牺牲帧写入到低速容器,用新帧取代其原来位置 FIFO 页置换 用一个 FIFO 队列管理页。需要置换时,队头页被换出,新帧加入队尾。 缺点:Belady 异常 Belady 异常:使用 FIFO 算法时,会出现增加可用帧数,缺页率反而提高的现象。 个人认为,这种现象出现的本质原因是,死板 FIFO 导致将高频页面换出,从而命中率下降。使用栈可避免 Belady 异常。
第 11 章 习题
ch-11-problem-sets
2021
December 18
11.2 What are the advantages of the variation of linked allocation that uses a FAT to chain together the blocks of a file ? 链接分配的一个重要变种是文件分配表(FAT)的使用。这个简单而有效的磁盘空间分配方法用于 MS-DOS 操作系统。每个卷的开头部分的磁盘用于存储该表。在该表中,每个磁盘块都有一个条目,并可按块号来索引。FAT 的使用与链表相同。目录条目包含文件首块的块号。通过这个块号索引的表条目包含文件的下一块的块号。这条链会继续下去,直到最后一块;而最后一块的表条目的值为文件结束值。未使用的块用 0 作为表条目的值来表示。为文件分配一个新块只要简单找到第一个值为 0 的 FAT 条目,用新块的地址替换前面文件结束值,用文件结束值替代 0。由块 217、618、339 组成的文件的 FAT 结构如图 3 所示。 图 3 文件分配表 如果不对 FAT 采用缓存,FAT 分配方案可能导致大量的磁头寻道时间。磁头必须移到卷的开头,读入 FAT,找到所需块的位置,再移到块本身的位置。在最坏的情况下,每块都需要移动两次。优点是改善了随机访问时间;因为通过读入 FAT 信息,磁头能找到任何块的位置。 11.3 Consider a system where free space is kept in a free-space list. a. Suppose that the pointer to the free-space list is lost.