X

曜彤.手记

随记,关于互联网技术、产品与创业

吉 ICP 备10004938号

《现代操作系统(第四版)》读书笔记(第 1-3 章)


旧书清理系列。别人安利的“操作系统”类书籍,主要看 1-6 章对应的重点部分。

第 1 章 - 引论

  1. (Page:2)操作系统
  1. (Page:14)存储器:

(CSAPP 中讲过的内容不再记录)

  1. (Page:17)设备驱动程序:专门与控制器对话,发出命令并接收响应的软件。
  1. (Page:17)实现输入输出的三种方式:
  1. (Page:18)总线:ISA -> PCI -> PCIe
  2. (Page:20)启动计算机的过程
  1. (Page:22)操作系统概念:
  1. (Page:32)brk used to be POSIX, but it was removed in POSIX 2001
  2. (Page:34)kill 系统调用:向进程发送信号。若该进程准备好捕捉一个特定的信号,那么对应的信号处理程序会处理该信号。否则,信号到来时杀掉该进程(名字由来)。
  3. (Page:36)操作系统结构:

第 2 章 - 进程与线程

  1. (Page:48)进程模型

  1. (Page:50)进程的创建和终止

- 进程创建

- 进程终止

  1. (Page:52)进程的状态

  1. (Page:53)进程的实现
进程管理 存储管理 文件管理
寄存器 正文段指针 根目录
程序计数器(PC) 数据段指针 工作目录
程序状态字 堆栈段指针 文件描述符
堆栈指针 用户 ID
进程状态 组 ID
优先级
调度参数
进程 ID
父进程
进程组
信号
进程开始时间
使用的 CPU 时间
子进程的 CPU 时间
下次定时器时间
  1. (Page:54)CPU 利用率:1 - p^np 为进程等待 I/O 操作的时间与其停留在内存中的时间之比;n 为内存中进程个数)。
  2. (Page:54)线程概述
进程中所有线程共享 每个线程独有
地址空间 程序计数器
全局变量 寄存器
打开文件 堆栈(存放调用栈帧)
子进程 状态
即将发生的定时器
信号与信号处理程序
账户信息
模型 特性
多线程 并行性、阻塞系统调用
单线程进程 无并行性、阻塞系统调用
有限状态机 并行性、非阻塞系统调用、中断
  1. (Page:60)Posix 线程:
线程调用 描述
pthread_create 创建一个新线程
pthread_exit 结束调用的线程
pthread_join 等待一个特定线程的退出
pthread_yield 释放 CPU 来运行另一个线程
pthread_attr_init 创建并初始化一个线程的属性结构
pthread_attr_destroy 删除一个线程的属性结构
  1. (Page:61)线程实现

- 在用户空间中实现

- 在内核中实现

- 混合实现

  1. (Page:64)调度程序激活(Scheduler Activation):
  1. (Page:65)弹出式线程
  1. (Page:67)进程间通信(IPC):

- 实现互斥的几种方法

- 睡眠与唤醒

- 信号量(Semaphore):

- 互斥量

- 管程

- 消息传递

- 屏障

  1. (Page:83)避免锁:读-复制-更新:将更新过程中的移除和再分配过程分离
  2. (Page:84)调度

- 调度算法种类

- 批处理系统中的调度

- 交互式系统中的调度

第 3 章 - 内存管理

  1. (Page:103)早期组织内存的三种方案:一个时刻只能有一个进程运行

  1. (Page:106)两种解决内存超载的方法

- 交换

- 虚拟内存

  1. (Page:107)空闲内存管理算法

- 位图

- 空闲链表

  1. (Page:113)加速分页过程

- 虚拟地址到物理地址的快速转换

- 支持大型虚拟地址空间

  1. (Page:117)页面置换算法

- 最优页面置换算法

置换出很(最)久之后才会用到的页面(无法实现)。

- 最近未使用页面置换算法(NRU,Not Recently Used):

在最近一个时钟滴答中,淘汰一个没有被访问的(R 位为 0)已修改(M 位为 1)的页面较好。初始时,R 位与 M 位均为 0,一旦任何一个页面引起缺页中断时(被访问),R 位会被置位,且 R 位会在每次时钟中断时清零(周期内)。M 位会在页面修改后置位。

- 先进先出页面置换算法(FIFO):

维护一个所有当前在内存中的页面的链表,最新进入的放在表尾,最早进入的放在表头。当发生缺页中断时,淘汰表头的页面,并将新调入的页面放在表尾(可能会淘汰常用页面)。

- 第二次机会页面置换算法

上述算法的改进。淘汰时检查最老页面的 R 位,如果为 0(最近没有使用),可以立刻置换;否则,清零该位并把页面放到链表的尾端。

- 时钟页面置换算法

上述算法的改进。将所有页面都保存在一个环形链表中,一个指针指向最老的页面。当发生缺页时,算法首先检查指针指向的页面,如果 R 位为 0 就淘汰该页面,并把新页面插入这个位置,然后指针前进。否则清零 R 位,指针前进(省去了将页面移动到链表尾端的步骤)。

- 最近最少使用页面置换算法(LRU,Least Recently Used):

基于一个观察:在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。

在缺页中断时,置换未使用时间最长的页面。内存中维护一个所有页面的链表,最近最多使用的在表头,最近最少使用的在表尾。每次访问内存时都必须更新整个链表。在链表中找到一个页面,删除它,然后把它移动到表头。实现成本较高,一般需要硬件支持。

- 优化的最不常使用置换算法(NFU,Not Frequently Used)(较好):

将每个页面与一个软件计数器(一般 8 位够用)相关联,计数器初值为 0,每次时钟中断时,由操作系统扫描内存中的所有页面,将每个页面的的计数器值右移一位,然后将该页面的 R 位加到计数器最左端的位(老化)。

发生缺页中断时,将置换计数器值最小的页面

- 工作集页面置换算法

工作集模型:在让进程运行以前,确保它的工作集就已经在内存中(预先调页),从而减少缺页中断率。

该算法在发生缺页中断时,淘汰一个不在工作集中的页面。工作集可以被定义为过去 10ms 中的内存访问所用到的页面集合。算法执行如下图所示:

- 工作集时钟页面置换算法较好):

上述算法的改进。构建一个循环表,当装入第一个页面后,把它加到该表中。随着更多的页加入,它们形成一个环。每个表项包含来自基本工作集算法的上次使用时间、R 位和 M 位。

每次缺页时,首先检查指针指向的页面。如果 R 位被置 1,该页面在当前时钟滴答中被使用过,那么该页不适合被淘汰。然后把该页 R 位置零,指针指向下一个页面,并重复该算法。否则,如果页面生成时间大于特定值且 M 位为零,则可以将此页面替换掉。

  1. (Page:125)分页系统设计问题

- 局部分配策略于全局分配策略

- 负载控制

- 页面大小

- 分离的指令空间与数据空间

为指令(I 空间)和数据(D 空间)设置分离的地址空间,两者拥有各自独立的页表。链接器需要对数据/代码进行重定向。

- 共享页面

- 共享库

(之前书中讨论过太多次,略)

- 内存映射文件

共享库的通用机制。进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。映射时不会实际读入页面内容,而是在访问时按“页”读入,磁盘文件被当做后备存储。当进程退出或解除文件映射时,改动被写回磁盘。

可用于进程间通信:一个进程在共享内存上写,另一个进程执行读。

- 清除策略

增加“分页守护进程”,定期唤醒以检查内存状态。如果空闲页框过少,该进程通过预定的页面置换算法选择页面换出内存。如果页面被修改过,则将其写回。

一种实现方式是使用“双指针时钟”,前指针由分页守护进程控制,后指针用于页面置换。

- 虚拟内存接口

提供可以直接“操作”虚拟内存的接口,诸如 mmap 等。命名虚拟内存可用于多个进程间的通信。

  1. (Page:131)有关实现的问题:

- 分页工作时期

- 缺页中断处理

- 指令备份

通过引发“缺页中断”的地址无法快速简单地找到当前正在执行的对应指令(无法确定页面内容上放置的是操作码还是操作数)。某些计算机上,CPU 会通过一个隐藏的内部寄存器来在每条指令执行之前,将 PC 的内容复制到给寄存器。

- 锁住内存中的页面

锁住正在进行 I/O 操作的内存中的页面,防止全局页面置换算法在调度其他进程时,将正在执行 I/O 操作的其他进程的页面换出。或者选择在内核缓冲区中完成所有 I/O 操作,然后再将数据复制到用户页面。

- 后备存储

在磁盘上设置特殊的交换分区以存放换出的页面。系统启动时,交换分区为空。第一个进程启动时,留出与该进程一样大的交换区块。新进程启动后,同样分配与其核心映像同等大小的交换分区。进程结束后,释放交换区。

进程表中需要记录进程交换区的磁盘地址。写回页面时,写回地址可以由“虚拟地址空间中的页面偏移量加到交换区开始地址”得到。

交换区的初始化可以通过将整个进程映像复制到交换区实现(代码段可以映射到源文件)。或者单纯在页面换出时为其分配磁盘空间,换入时再回收(需要每个进程维护一张表,记录页面在磁盘上的位置)。

- 策略和机制的分离

进程运行,出现缺页中断。缺页中断处理程序找出需要哪个虚拟页面,并发送一条消息给外部页面调度程序。调度程序从磁盘中读入所需页面,并复制到自己地址空间的某一位置。然后告诉缺页中断处理程序该页面的位置。该程序从外部页面调度程序的地址空间中清除对该页面的映射,然后请求 MMU 处理程序把它放到用户地址空间的正确位置。(页面置换算法可以放到外部页面调度程序或内核的缺页中断处理程序中)

  1. (Page:134)分段

为了使程序和数据可以被划分为逻辑上独立的地址空间,并且有助于共享和保护



这是文章底线,下面是评论
  暂无评论,欢迎勾搭 :)