《Think os》

第一章：编译

• 编译型语言和解释型语言
• 编译过程
  • 1.预处理
  • 2.解析
  • 3.静态检查
  • 4.生成机器/字节码
  • 5.链接
  • 6.优化

第二章：进程

• 进程：正在运行的程序。
• 进程包含的数据
  • 程序的执行代码。
  • 程序的数据，包括静态数据（编译期）和动态数据（栈，堆）。
  • IO状态。
  • 硬件状态，包括寄存器中的数据，进程状态码，程序计数器（标示正在执行的指令）。
• 实现进程隔离
  • 多任务
  • 虚拟内存
  • 设备抽象

第三章：虚拟内存

• 32位系统的虚拟地址：0~2^32-1，64位系统的虚拟地址：0~2^64-1
• 进程的数据被组织为5个段（从低位到高位）
  • 代码段
  • static段
  • globals段
  • 堆（从低位到高位增长）
  • 栈（从高位到低位增长） 测试程序：

  #include <stdio.h>
  #include <stdlib.h>
  int global;
  int main () {
  	int local = 5;
    void *p = malloc(128);
    char *s = "Hello, World";
    printf ("Address of main is %p\n", main);
    printf ("Address of global is %p\n", &global);
    printf ("Address of local is %p\n", &local);
    printf ("p points to %p\n", p);
    printf ("s points to %p\n", s);
  }

• 虚拟地址和物理地址之间的转换通过MMU来进行。
  • 1.程序读取或写入一个变量时，CPU生成一个虚拟地址。
  • 2.MMU把虚拟地址分成两块，分别是页号（page number）和偏移量（offset），一个页对应内存中的一段，页的大小通常为1～4KB。
  • 3.MMU从TLB中查询页号，获取其对应的物理页号，通过物理页号和偏移量生成物理地址。
• 假设操作系统是32位的，物理内存为1GB，分成1KB大小的页。
  • 因为1GB为2^30字节，一页大小为2^10字节，因此有2^20个物理页，也叫做帧。
  • 虚拟地址空间为2^30字节，一页大小为2^10字节，因此有2^22个虚拟页。
  • 偏移量的大小取决于页的大小，一页大小为2^10字节，因此需要10位来指定页中的一个字节。
  • 如果VA为32位，偏移量位10位，剩余的22位指定了虚拟页号。
  • 因为有2^20个物理页，每个物理页号由20位组成，加上10位的偏移量，最终的PA为30位。
• 解决页表占用内存大：多级页表

第四章：文件与文件系统

• 文件的抽象性
  • “文件系统”是一个文件名称到其内容的映射表。
  • “文件”是一串字节的序列。
• 文件和底层持久存储的区别：文件是基于字节的，持久存储是基于“块”的（一个块大小为1-8KB），对文件读写实际上是在对底层的块进行读写。
• 操作系统提供了一些特性，来弥补主存和硬盘之间的性能间隔：
  • 传输块：从硬盘读取一个字节耗费5~25ms，相比之下，读取一个8KB的块所多耗费的时间可以忽略不计，因此系统在读硬盘时通常倾向读取大的块。
  • 预读：当程序读取第一个块时，操作系统通常会同时读取更多的块。
  • 缓冲：在写文件时，数据会被写入到缓存区（内存），至少有一个块需要写入时才会持久化到硬盘。

第五章：字和字节

• &运算：两个操作数都为1，结果为1，否则为0。
• |运算：有一个操作数为1，结果为1，否则为0。
• ^运算：只有一个操作数为1，结果为1，否则为0。

第六章：内存管理

• 内存分配函数：malloc，calloc，free，realloc。
• malloc在运行时通常不依赖块的大小，但是可能取决于空闲块的数量。free通常很快，与空闲块的数量无关。calloc会清空块的每个字节，执行时间取决于块的大小和空闲数量，realloc执行时间取决于是否需要执行新旧内存块之间的复制。

第七章：缓存

• 程序数据的寄存器
  • 程序计数器（PC），包含下一条指令在内存中的地址。
  • 指令寄存器（IR），包含当前执行指令的机器码。
  • 栈指针（SP），包含当前函数栈帧的指针，包括函数参数和局部变量。
  • 状态寄存器。
• 当CPU从内存读取数据时，它将一份副本存到缓冲中，缓存的命中率为h，缺失率为m，每次内存访问的平均时间为：h * Th + m * Tm
• 局部性原理：CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中。1.重复引用同一个变量具有良好的时间局部性。 2.对于步长位k的引用程序，步长越小，空间局部性越小。步长为1的引用具有良好的空间局部性。k越大，空间局部性越差。

第八章：多任务

• 中断：中断是一个事件，它会停止通常的指令周期，并且使执行流跳到中断处理器的特殊代码区域内。
• 硬件中断：硬件设备->CPU，软件中断：程序->内核。
• 系统调用：执行特殊的指令触发中断，使程序流跳到内核中，内核读取系统调用的请求参数，执行操作，之后恢复中断进程的执行。
• 进程的生命周期：运行，就绪，阻塞，终止。
  • 进程被启动或恢复：就绪->运行。
  • 进程被中断：运行->就绪。
  • 进程执行不能立即完成的系统调用：运行->阻塞。
  • 进程阻塞操作完成：阻塞->就绪。
  • 进程退出：终止。
• 调度器运行时会优先调度优先级最高的进程。

第九章：线程

• 同一进程中的所有线程共享相同的代码段，static段，堆，但每个线程拥有属于自己的栈，线程不能访问其它线程的局部变量。

《现代操作系统》

进程

进程：正在运行的一个程序的实例，由一个内核对象和一个地址空间构成。

程序与进程区别

• 进程是程序执行,程序是进程的基础;
• 程序是静态的,进程是动态的;
• 进程与程序不是一一对应的关系;
• 一个程序可能启动多次,对应着多个进程。
• 一个进程可能会打开多个程序。
• 进程有生命期;
• 进程的并发性;
• 进程的制约性。

进程状态： 就绪，阻塞，运行。

进程的组成: 程序、数据集合和PCB

需要线程的原因:

• 并发实体共享同一个地址空间和所有可 用数据的能力。(进程做不倒)
• 比进程更容易创建和撤消。
• 如果存在大量的计算和大量I/O处理,多线程加快应用执行的速度。

线程组成：堆栈，寄存器，程序计数器和状态。共享进程的地址空间，打开的文件和其他资源。

两种线程模型：

• 用户空间线程模型：每个进程有各自的线程表，内核不知道线程表的存在。优点：可在不支持线程的操作系统实现。在用户空间可实现自定义的线程调度算法，不需要上下文切换。缺点：线程调用阻塞系统调用，由于内核不知道线程的存在，从而阻塞整个进程和其他线程。没有时钟中断，除非线程让出cpu，否则进程里的其他线程在时间片用完前得不到调度。
• 内核空间线程模型：由内核来维护一张所有线程的线程表。优点：一个线程阻塞时，内核可以调度就绪的其他线程。缺点：创建线程的代价大（因此可能需要线程回收）。

进程间通信（IPC)

• 竞争条件(race condition)：两个或多个进程读写某些共享数据,而最后的结果取决于精确时序。
• 临界区：访问共享内存和数据的一段程序。
• 互斥：以某种手段确保当一个进程在使用一个共享变量、文件及共享任何资 源时,其他进程不能做同样的操作。
• 睡眠和唤醒：sleep和wake。
• 信号量
• 互斥量：pthread_mutex
• 条件变量：pthread_cond(常于mutex一起使用)
• 管程
• 消息传递
• 屏障

忙等待的互斥方案

• 屏蔽中断：在进程进出临界区间的时间里屏蔽所有中断，使其他进程无法进入临界区。缺点：无法适应多核问题。
• 锁变量：使用变量锁来检查。缺点：多进程可能同时测试锁的值，仍然可能同时进入临界区。
• 严格轮换
• Peterson解法
• TSL指令

进程调度

• 非抢占式调度算法
• 抢占式调度算法

调度算法

• 先来先服务(First-Come First-Served)(FCFS)
• 非抢占;链表维护排队队列。批处理系统。
• 最短作业优先(Shortest Job First)
• 非抢占;需可预测执行时间。批处理系统
• 4个作业平均周转时间=(4a+3b+2c+d)/4, 平均周转时间最小
• 最短剩余时间优先(Shortest remaining time First)
• 最短作业优先的抢占式。批处理系统
• 当新作业到达时,其执行时间与当前运行进程的剩余时间进行比较,短的优先执行。
• 轮转调度(Round-Robin Scheduling)
• 时间片(quantum)通常20-50ms。抢占式。交互系统。
• 进程切换(process swithc),上下文切换(context swith)
• 优先级调度(Priority Scheduling)
• 设置优先级并可降低。同级别的进程采用轮转。
• 低级别可能饿死 I/O密集的进程可设置较高优先级。
• 多级队列(Multiple Queue)
• 最高优先级类运行1时间片,次高运行2时间片,再次高运行4时间片,依些类推。当完成分配的时间片后,它被移到下一类。
• 最短进程优先(Shortest Process Nest)(SPN)
• 相当于 “最短作业优先”
• 最高响应比优先
• 非抢占式响应比=(等待时间)/(所需CPU时间)

经典IPC问题

哲学家就餐

死锁

原因:

• 竞争资源
• 程序推进顺序不当

必要条件:

• 互斥条件
• 请求和保持条件
• 不剥夺条件
• 环路等待条件

处理死锁基本方法:

• 预防死锁(摒弃除1以外的条件)
• 避免死锁(银行家算法)
• 检测死锁(资源分配图)
• 解除死锁
• 剥夺资源
• 撤销进程

程序编译与链接

Bulid过程可以分解为4个步骤:预处理(Prepressing), 编译(Compilation)、汇编(Assembly)、链接(Linking)

以c语言为例:

1 预处理

预编译过程主要处理那些源文件中的以“#”开始的预编译指令，主要处理规则有：

将所有的“#define”删除，并展开所用的宏定义 处理所有条件预编译指令，比如“#if”、“#ifdef”、 “#elif”、“#endif” 处理“#include”预编译指令，将被包含的文件插入到该编译指令的位置，注：此过程是递归进行的 删除所有注释 添加行号和文件名标识，以便于编译时编译器产生调试用的行号信息以及用于编译时产生编译错误或警告时可显示行号 保留所有的#pragma编译器指令。 2 编译

编译过程就是把预处理完的文件进行一系列的词法分析、语法分析、语义分析及优化后生成相应的汇编代码文件。这个过程是整个程序构建的核心部分。

3 汇编

汇编器是将汇编代码转化成机器可以执行的指令，每一条汇编语句几乎都是一条机器指令。经过编译、链接、汇编输出的文件成为目标文件(Object File)

4 链接

链接的主要内容就是把各个模块之间相互引用的部分处理好，使各个模块可以正确的拼接。 链接的主要过程包块 地址和空间的分配（Address and Storage Allocation）、符号决议(Symbol Resolution)和重定位(Relocation)等步骤。

存储管理

分层存储体系

• 寄存器（1ns）
• 高速缓存（2ns）
• 主存（10ns）
• 磁盘（10ms）
• 磁带（100s）

存储管理的任务

• 记录存储器的使用情况,即哪些部分正被使用,哪些部分还空闲着。
• 当进程需要存储空间时,就分配给它; 然后当它运行结束后,再把存储空间回 收回来。
• 如果内存太小,容不下所有的进程,那 么就需要把内存中暂时不能运行的进程 转到磁盘上,然后再把磁盘上的另一个 进程装入内存。
• 大多数的操作系统中,存储管理位于内核之中。

内存管理的五点需求

1. 重定位
2. 保护
3. 共享
4. 逻辑组织
5. 物理组织

六种内存管理技术

• 固定分区
• 动态分区
• 简单分页
• 简单分段
• 虚拟内存分页
• 虚拟内存分段

虚拟存储技术就是利用实际内存空间和相对大的多的外部储存器存储空间相结合构成一个远远大于实际内存空间的虚拟存储空间，程序就运行在这个虚拟存储空间中，能够实现虚拟存储的依据是程序的局部性原理，即程序在运行过程中经常体现出运行在某个局部范围之内的特点。

动态分区放置算法

• 首次适配
• 最佳适配
• 邻近适配(假定最近添加的块位于内存的开始)
• 最坏适配

分页式地址重定位

计算公式

• 页号=相对地址\块尺寸
• 页内位移=相对地址%块尺寸

流程

1. 将相对地址转换成数对(页号,页内位移)
2. 建立一张作业的页与块对应表
3. 按页号去查页、块对应表
4. 由块的起始地址与页内位移形成绝对地址

页表是一种特殊的数据结构，放在系统空间的页表区，存放逻辑页与物理页帧的对应关系。 每一个进程都拥有一个自己的页表，PCB表中有指针指向页表。

实现虚拟分页需要考虑的问题

• 虚拟地址到物理地址的映射必须快
• 如果虚拟地址空间很大,页表会很大

TLB(Translation Lookaside Buffer),简称快表，加速虚拟地址到物理地址的映射。通常在MMU中。

依据

总是对少量的页面进行多次的 访问。因此,只有很少的页表 项会被反复读取,而其他的页 表项很少被访问。

页面淘汰算法

• 最佳(OPT) Optimal 替换下次访问距当前最长的页。
• 最近最少使用(LRU) Least Recently Used 置换未使用时间最长的页面。(替换主存中上次使用距当前最远的页。)
• 最不常用算法(NFU) Not Frequently Used
• 老化(aging)算法
• 先进先出(FIFO) First In First Out 由操作系统维护一个所有当 前在内存中的页面的链表,最新进入的页面放在表 尾,最久进入的页面放在表头。
• 时钟(Clock)
• 最近未使用(NRU)

缺页中断

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。