《操作系统精髓与设计原理》学习笔记_操作系统:精髓与设计原理 学习笔记

置顶

1. 知识过于繁杂，挑重点简要记录
2. 主要针对Linux操作系统，Windows和Android需要的时候再学
3. 虽然书过了一遍，但深深的知道自己还有很多不动的地方，特别是多处理器那里，想起来刚学操作系统的时候，也是觉得没什么用，不知道在学什么，后来了解到Linux编程，再看操作系统真的有不少感悟，现在看多处理器那部分就是处于不知道干什么的状态，还是没有实践啊
4. 看完后觉得我们大二的时候上操作系统课，为什么不用这本书，觉得这里面的课后习题什么的都挺好的，附录也很好，特别是OS/161，我之前为了做大作业也尝试看过《一个64为操作系统的实现》《30天自制一个操作系统这种书》，没想到这就有一个现成的，难受。

第一章：计算机系统概述

1. 基本构成

1. 处理器
2. 内存
3. IO模块
4. 系统总线

2. 指令分类

1. 处理器<–>存储器
2. 处理器<–>IO
3. 数据处理
4. 控制

3. 中断

中断的分类

多个中断

• 禁止再中断
• 优先级

4. 内存层次

板上存储器

1. 寄存器
2. 高速缓存
3. 内存

板外存储器

4. 磁盘，CD

离线存储器

5. 磁带

5. 高速缓存

1. CPU<----字传送(快)—>高速缓存(L1,L2,L3)<—块传送(慢)----内存

6. 多处理器和多核

多处理器

• 是有多个独立的CPU,每个CPU能执行相同的功能，也叫对称处理器

多核

• 是多个处理器组装在同一个硅片上，又名芯片多处理器

二者区别

• 对于多个处理器而言，它们在执行命令的时候多个处理器之间的通信手段是电脑主板上的总线；而对于多核处理器而言，多个核心处理器之间通信时通过CPU内部总线进行信息的交互的。对于执行效率而言，多核处理器要优于多个处理器
• 若跑小程序，选多核
  对于多处理器：如果跑一个多线程的程序（常见典型情况），不考虑超线程，那么每一个线程就要跑在一个独立的CPU上，线程间的所有协作都要走总线，而共享的数据更是有可能要在好几个Cache里同时存在。这样的话，总线开销相比较而言是很大的，怎么办？那么多Cache，即使我们不心疼存储能力的浪费，一致性怎么保证？如果真正做出来，还要在主板上占多块地盘，给布局布线带来更大的挑战？所以对于个人计算机来说，都采用单处理器多核。只需要一套芯片组，一套存储，多核之间通过芯片内部总线进行通信，共享使用内存。在这样的架构上，如果我们跑一个多线程的程序，那么线程间通信将比上一种情形更快。如果最终实现出来，对板上空间的占用较小，布局布线的压力也较小。
• 若跑大程序，选多CPU多核
  假设俩大程序，每一个程序都好多线程还几乎用满cache，它们分时使用CPU，那在程序间切换的时候，光指令和数据的替换就很费事。所以，需要更强的多任务并发能力，就用多颗多核CPU的机子。

第二章：操作系统概述

1. Linux主要内核组件

1. 信号(Signals)
   • 内核使用信号向进程提供信息
2. 系统调用(System calls)
   • 为进程提供系统服务，大致分为6类：文件系统，进程，调度，进程间通信，套接字，其他
3. 进程和调度器(Processes and Scheduler)
   • 创建，管理，调度进程
4. 虚存(Virtual memory)
   • 为进程分配和管理虚存
5. 文件系统(File System)
   • 为文件，目录和其他文件对象提供一个全局的分层命名空间，并提供文件系统函数
6. 网络协议(Network protocols)
   • 为用户的TCP/IP协议套件提供套接字接口
7. 字符设备驱动(Character device drivers)
   • 如打印机，调制解调器，终端
8. 块设备驱动(Block device drivers)
   • 如各种外存
9. 网络设备驱动(Network device drivers)
   • 管理网卡和通信端口，即管理连接到网桥或路由的网络设备
10. 陷阱与错误(Traps and faults)
    • 处理CPU产生的陷阱和错误，如内存错误
11. 物理内存(Physical memory)
    • 管理实际内存中的内存页池，并为虚存分配内存页
12. 中断(Interrupts)
    • 处理来自外设的中断

2. Windows和Android先不整理，以后需要再学

第三章：进程

1. 进程介绍

进程的两个基本元素

• 程序代码
• 数据集

进程控制块(PCB)

• 标识符
• 状态
• 优先级
• 程序计数器
• 内存指针
• 上下文数据
• I/O 状态信息
• 记账信息

2. 进程状态

经典5状态

• 新建态
  • 空–>新建
• 就绪
  • 新建–>就绪
  • 运行–>就绪
  • 阻塞–>就绪
• 运行
  • 就绪–>运行
• 阻塞
  • 运行–>阻塞
• 退出态
  • 运行–>退出
  • 阻塞–>退出
  • 就绪–>退出

挂起态

• 这个主要是内存不足，就把进程先换到外存

3. 操作系统的控制结构

• 内存–>内存表
• 设备–>设备表
• 文件–>文件表
• 进程–>主进程表–>进程映像

4. 进程映像

• 进程控制块
  • 进程id
  • 处理器状态信息
  • 进程控制信息
• 用户栈
• 私有用户地址空间(程序，数据)
  • 堆
  • 静态数据区
  • 代码段
• 共享地址空间

第四章：线程

1. 线程介绍

• 一个进程可以有多个线程
• 每个线程有自己的线程控制块，用户栈，内核栈
• 所有线程共享用户地址空间

2. 线程状态

• 就绪，运行，阻塞
• 没有挂起

3. Linux中的线程

• Linux中没有给线程单独定义数据结构，所以Linux中的线程和进程没有区别
• Linux提供一种不区分进程和线程的解决方案
  • 将用户级线程映射到内核级进程上。
  • 组成一个用户级进程的多个用户级线程则映射到共享同一个组ID的多个Linux内核级进程上。
  • 因此，这些进程可以共享文件和内存等资源，使得同一个组中的进程调度切换时不需要切换上下文
• 当Linux内核执行从一个进程到另一个进程的切换时，会检查当前进程的页目录地址是否与将被调度的进程的相同。
  • 若相同，则它们共享同一个地址空间，所以此时的上下午切换仅是从代码的一处跳转到另一处
  • 可以共享同一内存空间，但不能共享同一个用户栈。所以每个线程有自己单独的栈空间

4. Linux的命名空间

• 命名空间可以使一个进程(或共享同一命名空间下的多个进程)拥有与其他相关命名空间下的其他进程不同的系统视图。
• 当前Linux有6种命名空间：mnt,pid,net,ipc,uts,user
  • Mount命名空间
    为进程提供文件系统层级结构的特定视图，因次两个不同mount命名空间的进程会看到不同的文件系统层次结构
  • UTS命名空间
    UNIX timesharing UNIX 分时，通过UTS命名空间，初始化和配置参数能够根据同一系统上的不同进程而变化
  • IPC命名空间
    隔离某些进程间通信资源，如信号量
  • PID命名空间
    隔离进程ID空间
  • 网络命名空间
    隔离与网络相关的系统资源
  • 用户命名空间
    为自身的UID集建立一个容器

第五章：并发性：互斥和同步

-1. 常用的并发机制

0. 进程和线程的管理

• 多道程序设计技术
  管理单处理器的多个进程
• 多处理器技术
  管理多处理器的多个进程
• 分布式处理器技术
  管理多态分布式计算机系统中多个进程的执行。集群就是这个的典型例子

互斥的要求

1. 一次只允许一个进程进入临界区
2. 一个在非临界区停止的进程不能干涉其他进程
3. 不允许出现需要访问临界区的进程被无限延迟的情况，即不会死锁和饥饿
4. 没有进程在临界区时，需要进入的进程要能立刻进入
5. 对相关进程的执行速度和处理器的数量没有任何要求
6. 一个进程驻留在临界区的时间必须是有限的

1. 互斥：硬件的支持

1. 中断禁用

    while(true){
        //禁用中断
        //临界区
        //启用中断
        //其余非临界区
    }
1
2
3
4
5
6

• 这种办法执行效率低
• 不能用于多处理器体系结构中，当有多个处理器，就可能有多个进程同时执行，在这种情况下，禁用中断并不能保证互斥

2. 专用机器指令

• 保证某些机器指令的原子性

2. 信号量

生产者/消费者问题

• 有一个缓冲区，生产者往里面放东西(字节或记录)，消费者取东西，一次只能有一个进行操作

3. 管程

• 为什么感觉第一次听这个概念。。。先跳过

4. 消息传递

同步

• 发送者和接收者都可阻塞或不阻塞。通常有三种组合，但任一特定操作系统通常只实现一种或两种
  • 阻塞send，阻塞receive
    发送者和接收者都阻塞，直到完成消息传递。进程间紧密同步
  • 无阻塞send,阻塞receive
    发送者可以继续执行，接收阻塞，这可能是最有用的一种组合
  • 无阻塞send,无阻塞receive
    双方都不等待

寻址

• 直接寻址
  • 进程对进程直接发送消息
• 间接寻址
  • 消息发送到一个共享的数据结构，如管道

消息格式

• 直白的说就是：具体情况具体分析

5. 读者/写者问题

条件

1. 任意数量的读进程可以读这个文件
2. 一次只有一个写进程能写这个文件
3. 若一个写进程正在写文件，则禁止任何读进程读文件

读者优先

写者优先

第六章：并发：死锁和饥饿

6.1 死锁原理

6.1.1 可重用资源死锁

• 资源可重用，如设备
• 两个进程各自占用一个设备，都需要另一个设备时死锁

6.1.2 可消耗资源死锁

• 资源只能使用一次，消耗性的，如缓冲区中的数据
• 两个进程都想从缓冲区读数据，没进程写，都处于阻塞等待状态，死锁

6.1.3 资源分配图

• 系统资源和进程的有向状态图

6.1.4 死锁条件

• 互斥
  • 一次只有一个进程可以使用某个资源
• 占有且等待
  • 当一个进程等待其他进程时，继续占有已经占有的资源
  • 解决办法：一次性占有所有资源
• 不可抢占
  • 不能强行抢占其他进程已经占有的资源
  • 解决办法：若申请其他资源不成功，则释放已占有的资源
• 循环等待
  • 存在一个闭合的进程链，每个进程至少占有此链下一个进程所需的一个资源
  • 这一条实际上是前三条的潜在结果
  • 解决办法：定义资源的线性顺序，若一个进程已经占用了R资源，接下来只能占有R之后的资源

6.1.5 处理死锁的办法

• 预防
  • 消除某一个死锁条件
• 避免
  • 基于资源分配的当前状态做动态选择
• 检测
  • 检测死锁的存在并从死锁中恢复

6.2 小结

6.3 哲学家就餐问题

假设有5跟筷子，5个座位

6.3.1 基于信号量的解决方案

• 只能允许4个人同时吃

6.3.2 基于管程的解决方案

• 实际上就是左右同时拿，只有左右同时可用才拿，只要有一个不可用，就都不拿

6.4 UNIX并发机制

• 管道
  • pipe
  • mkfifo
• 消息
  • 有msgsnd和msgrcv系统调用
• 共享内存
• 信号量
  • semctl
  • sem_op
• 信号

6.5 Linux内核并发机制

• 包含UNIX的所有
• 原子操作
  • atomic_xxx()
• 自旋锁
  • 一次只有一个进程能进入临界区
  • 其它试图获得自旋锁的进程将一直进行尝试（即自旋），直到获得该锁
  • spin_lock系列调用

第七章：内存管理

0. 内存管理术语

1. 内存管理的需求

• 重定位
• 保护
• 共享
• 逻辑组织
• 物理组织

2. 分页和分段

• 分页是对分区的改进，减少了内存碎片
• 每个进程维护一个页表
• 使用分段技术，可以把程序和与其相关的数据划分到几个段中
• 分页对程序员透明，分段通常是可见的

第八章：虚拟内存

0. 虚拟内存术语

1. 关键概念

• 内存碎片
  • 内部碎片
    已经使用的内存，不能用到的地方
  • 外部碎片
    没有使用的内存，但是太小了不能再用的内存
• 抖动
  • 频繁中断进行内存页的换进换出，常见于先进先出算法
• 置换页的基本算法
  • 最佳
    • 置换下次访问距当前时间最长的页，需要预测
    • 不可能实现，仅作为衡量其他算法性能的一种标准
  • 最近最少使用
    • 时钟策略的变体
  • 先进先出
    • 实现简单，性能较差
  • 时钟
    • 有一个只能为1或0的使用位，初始为1，若要置换，找下一个，下一个若为0，就换出，若为1就变为0，继续找下一个，就是多给了一次机会，所有的页组成一个环

第九章：单处理器调度

1. 处理器调度的类型

长程调度和中程调度主要由与系统并发度相关的性能驱动，如第7,8章的页面置换等。本章主要讲短程调度。

• 导致当前进程阻塞或抢占当前运行进程的事件发生时，调用短程调度程序。这类事件包括：
  • 时钟中断
  • IO中断
  • 操作系统调用
  • 信号（如信号量）

2. 调度算法

调度规则

优先级的使用

调度策略

• 先来先服务
• 时间片轮转
• 最短进程优先
• 最短剩余时间
• 最短相应比优先
• 反馈
  建立一组调度队列，基于每个进程的执行历史和其他一些规则，把它们分配到各个队列中
  调度算法的选择取决于预期的性能和实现的复杂度

第十章：多处理器和实时调度

1. 多处理器调度

多处理器系统分类

• 松耦合、分布式多处理器、集群
  • 由一系列相对自治的系统组成，每个处理器都有自身的内存和IO通道
• 专用处理器
  • IO处理器是一个典型的例子。此时，有一个通用的主处理器，专用处理器由主处理器控制，并为主处理器提供服务。
• 紧耦合多处理器
  • 由一系列共享同一内存并受操作系统完全控制的处理器组成

粒度

• 无约束并行性
  • 进程间没有显式的同步，每个进程都代表独立的应用或作业。这类并行性的一个典型应用是分时系统。每个yoghurt执行一个特定的应用，如字处理。
• 粗粒度和极粗粒度并行性
  • 进程间存在同步，但这种同步的级别极粗。

设计问题

多处理器中的调度涉及三个相互关联的问题

• 把进程分配到处理器
  • 分配到那个处理器
• 在单处理器上使用多道程序设计
• 一个进程的实际分派
  • 选择哪个进程运行

2. 实时调度

• 负责Linux调度的三个类
  • SCHED_FIFO:先进先出实时线程
  • SCHED_RR:轮转实时线程
  • SCHED_OTHER:其他非实时线程
• 这个还有好多没记，主要是不理解什么意思，不知道哪些是重点，以后能有实践机会了深入了解了再学。

第十一章：IO管理和磁盘调度

1. IO设备

分类

• 人可读
  • 打印机
  • 终端
  • 鼠标等
• 机器可读
  • USB秘钥
  • 传感器等
• 通信
  • 调制解调器

各设备主要差异

• 数据传输速率
• 应用
• 控制的复杂度
• 传送单位
• 数据表示
• 错误条件

2. IO功能的组织

三种执行IO的技术

• 程序控制IO
• 中断驱动IO
• 直接存储器访问(DMA)

3. IO缓冲

单缓冲

• 有一个缓冲区

双缓冲

• 两个系统缓冲区，在一个进程向一个缓冲区中传送数据的同时，操作系统正在清空(或填充)另一个缓冲区，这叫双缓冲或缓冲交换

循环缓冲

• 多于两个缓冲区

缓冲作用

• 平滑IO需求的峰值

4. 磁盘调度

磁盘性能参数

• 寻道时间
• 旋转延迟
• 传输时间
• 时序比较

调度策略

• 先进先出
• 优先级
• 后进先出
• 最短服务时间优先
• SCAN(电梯算法)
• C-SCAN，只向一个方向移动

RDIA

• 这个需要的时候再了解吧，有点抽象，不知道是干嘛的

第十二章：文件管理

1. 概述

文件和文件系统

• 一些理想的属性
  • 长期存在
  • 可在进程间共享
  • 结构
• 典型的操作
  • 创建
  • 删除
  • 打开
  • 关闭
  • 读
  • 写
• 文件系统通常为文件维护一组属性，包括所有者、创建时间、最后修改时间和访问权限

文件结构

• 4个术语
  • 域 field
    基本的数据单元，如人名，出生日期
  • 记录 record
    一组相关域的集合，如一个人作为一条记录，有名字，出生日期等域
  • 文件 file
    一组相似记录的集合
  • 数据库
    一组相关数据的集合
• 并非所有文件管理系统都会是这种结构，在类UNIX系统上，文件的基本结构是字节流。例如一个C语言程序以文件的形式存储，而没有物理域、记录等

文件管理系统

• 典型情况下，文件管理系统是用户或应用程序访问文件的唯一方式
• 文件系统架构
  • 用户程序
  • 堆 顺序 索引顺序 索引 散列
  • 逻辑IO
  • 基本IO管理程序
  • 基本文件系统
  • 磁盘设备驱动 磁带设备驱动等驱动程序

2. 文件组织和访问

• 选择文件组织的原则
  • 快速访问
  • 易于修改
  • 节约存储空间
  • 维护简单
  • 可靠性
    这些原则的优先级取决于使用这些文件的应用程序
• 5种基本组织
  • 堆
    • 不是数据结构中的堆，是最简单的文件组织形式
    • 堆文件没有结构，访问记录只能穷举查找
    • 对大多数应用都不适用，当数据难以组织时，可以用堆文件
  • 顺序文件
    • 最常用，每条记录有固定的格式
    • 通常应用于批处理应用中
    • 另一种选择是把顺序文件组织成链表的形式。但增加额外的处理和空间开销
  • 索引文件
    • 只能通过索引访问
  • 索引顺序文件
    • 克服顺序文件的缺点，增加了用于支持随机访问的文件索引和溢出文件
  • 直接或散列文件
    • 记录长度固定，快速访问，一次只能访问一条记录

3. B树

• 用于文件系统和数据库
• 每个节点有多个关键码的树

4. Linux文件系统

VFS虚拟文件系统

• VFS的4个主要对象
  • 超级块对象 superblock
    表示一个已挂载的特定文件系统
  • 索引节点对象 inode
    表示一个特定的问价
  • 目录项对象 dentry
    表示一个特定的目录项
  • 文件对象 file
    表示一个与进程相关的已打开文件

第十三章：嵌入式操作系统

1. 嵌入式系统

• 为完成某个特定功能而设计的

2. 嵌入式Linux

• 内核比普通Linux小队多
• 交叉编译，在一个平台上编译，在另一个平台上运行
• 文件系统
  • 通常使用闪存作为持久性存储设备

第十四章：虚拟机

• 这章…讲的…真抽象
• 虚拟化技术使得单个PC或服务器能够同时运行多个操作系统或一个操作系统的多个会话

第十五章：计算机安全技术

1. 入侵者与恶意软件

入侵者

• 伪装者
  • 越过系统访问控制并使用了一个合法的用户账号
  • 来自外部
• 违法者
  • 合法用户，但访问了为被授权的数据
  • 来自外部
• 秘密用户
  • 能控制系统的个体
  • 来自外部或内部

恶意软件

• 寄生型
  • 需要宿主程序
  • 如病毒，逻辑炸弹和程序后门
• 独立运行
  • 可以被操作系统调度和执行的独立程序
  • 如蠕虫和机器人程序

应对措施

• 入侵检测系统(IDS)
  • 基于宿主的IDS
  • 基于网络的IDS
• 认证
• 访问控制
• 防火墙

2. 缓冲区溢出

缓冲区溢出例子

    int main(){
        int valid = FALSE;
        char str1[8];
        char str2[8];

        next_tag(str1); //另str1里面存STATE
        gets(str2);
        if(strncmp(str1,str2,8)==0){
            valid = TRUE;
        }
        printf("str1:%s,str2:%s,valid:%d\n",str1,str2,valid);
        return 0;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

• 这个就会造成缓冲区溢出
• 一般情况下，valid,str1,str2在内存中连续存放
• 调用next_tag后，str1里面存储字符串"STATE"
• C语言库函数gets不对复制的数据量做任何检查。它从程序的标准输入读取下一行文本，知道出现\n，将其复制到缓冲区，并用C语言字符串使用的NULL作为结尾。如果读入时的字符超过7个(NULL还得占一个)，照样会读入，覆盖相邻变量的值，在本例中即覆盖str1的值，从而破坏其他变量的值
• 运行如下

//正确运行的例子
$ ./a.out
STATE
str1:STATE,str2:STATE,valid:1
//溢出例子,可以看出已经改变了str1的值
$ ./a.out
123456789abcde
str1:9abcde,str2:123456789abcde,valid:0
//溢出例子，不仅改了str1的值，还使valid为TRUE
$ ./a.out
badinputbadinput
str1:badinput,str2:badinputbadinput,valid:1
1
2
3
4
5
6
7
8
9
10
11
12

• 如果这里是比较密码，成功就登入，就可以用这种办法，不需要知道密码，直接比较成功，从而登入

编译时防御

• 编程语言的选择
• 安全编码技术
• 语言扩展及使用安全库
• 栈保护机制

运行时防御

• 可执行的地址空间保护
• 地址空间布局随机化
• 守卫页

第十六章：分布式处理、客户-服务器和集群

1. 客户-服务器计算

• 我的理解，实际上就是C/S,B/S架构，中间件是像代理服务器之类的东西

2. 分布式消息传递

• 就是客户端和服务器不能直接通过信号等传递消息，可以通过报文，用特定的结构传递信息，如HTTP
• 可靠和不可靠性
  • 是否保证传递消息的正确性
• 阻塞与无阻塞
  • 发送和接受消息是否等待

3. 远程过程调用(RPC)

• 是基本消息传递的一种变体

• 举例就是客户端给服务器发送个消息，服务器就本地调用某个程序

• 同步和异步

  • 同步RPC
    和子程序调用行为类似，要等待返回结果。
  • 异步RPC
    调用者并不等待应答

4. 集群

• 集群技术可以替代对称多处理技术(SMP)
• 集群定义为一组互联的完整计算机，这些完整计算机作为一种统一的计算资源协同工作，就像一台计算机那样。
• 集群的四个优点
  • 绝对可伸缩性
    • 一个集群可以有用数十台至数百台机器，每台机器都可以是多处理机
  • 增加可伸缩性
    • 集群能这样配置：向集群中添加系统时只需少量的额外工作，即用户可以在一个大小适度的系统上开始工作，在需求增加时可以扩展系统，而不用升级主体来用较大的系统代替较小的系统。
  • 高可用性
    • 因为集群中的每个节点都是一台独立的计算机，因此某个节点故障并不意味着服务失败。在很多产品中，软件能够自动地进行容错处理
  • 高性价比
    • 使用普通的计算机来构建集群系统，能够以非常低的价格，获得与一台大型计算机相同或更大的计算能力

练习项目

• 后期可以看一下附录的一些问题，比如理发店问题，各个小作业