揭开钢琴的盖子

层次结构：应用软件、操作系统、计算机硬件

冯若依曼体的存储思想：存储器、运算器、控制器

cpu核心：取指执行

汇编指令：MOV SUB REP JMP

启动盘：boot扇区、set4个扇区、sysytem模块

启动流程：从引导扇区读入512字节，引导扇区代码

操作系统启动

核心：取指执行

磁盘、内存、中断

setup模块

进入保护模式

寻址范围：2的32次方、4GB

GDT表项

sysytem模块

入口函数、数据结构、机器码

数据结构和算法：栈、链表、跳表、树、图、动态规划

while、main、内存、中断

内存初始化、页大小4kb

把磁盘系统程序读入内存，完成初始化：boot、setup、head、main

操作系统接口

系统调用

接口、适配器、函数

命令行、图形化界面

消息队列、中断、消息处理机制、流程图、时序图

系统调用（系统函数）

posix：统一接口定义

系统调用的实现

内核态、用户态、用户段、内核段（硬件支持）

内核程序与用户程序隔离

中断处理（硬件提供主动进入内核的方法）

固定程序、固定策略、固定流程

核心：int指令（中断指令）

函数的作用（目的）

中断处理程序、sysytem_call

操作系统历史

分时系统

核心：任务切换、进程管理、文件管理、图形界面

多进程结构

涉及内容：CPU、内存、IO、磁盘、文件

核心知识：CPU管理、内存管理、磁盘管理、进程管理

CPU管理

CPU工作原理：取指执行

相较于cpu执行，io执行特慢，因此不能阻塞等待

提升cpu利用率：进程切换

并发：交替执行

进程上下文、寄存器

多进程图像

PCB进程控制块

启动第一个进程：生成新的进程、执行程序

多进程组织管理

就绪队列、等待队列、阻塞队列

进程状态图：新建态、就绪态、运行态（阻塞态）、终止

事件机制、进程调度、先进先出算法

虚拟内存、多进程地址隔离

生产者-消费者实例

原子性（进程切换）上锁

用户级线程

进程=资源+指令执行序列

线程=一个资源+多个指令执行序列

分治思想

• 一个网页浏览器

• 多个线程交替执行

• 共享进程资源

线程：调度的基本单位

缓冲区：缓存数据，提效

核心：yield

栈：压栈、出栈

TCB：线程控制块

线程切换、两个TCP、两个栈

内核级线程

kenel thread

MMU内存管理单元

系统调用、中断

TCB线程控制块

线程切换：提效

内核级线程实现

fork系统调用、触发中断

pc执行的下一条指令

保存上下文信息

中断入口、中断出口

内核线程switch_to的五段论

• 中断入口：进入切换，将用户栈与内核栈的链拉好

• 中断处理：引发切换，启动磁盘读或者时钟中断

• schedule：找到下一个线程的TCB

• switch_to ：内核栈切换(第一级切换），执行ret切到某个内核程序（一段能返回第二级的代码，一段包含iret的代码（中断返回））

• 中断出口：iret(第二级切换），内核栈切到用户栈

操作系统那棵树

linux kernel source tree

提升效率：多进程切换

跳转实现：栈

用户栈、内核栈

程序就是人思维的代码表达

中断事件、时钟中断

CPU调度策略

就绪队列、FIFIO

周转时间、响应时间、吞吐量

取舍平衡、结合实际情况

短作业优先（平均周转时间小）

时间片轮转调度

优先级调度

饥饿现象：有些进程永远得到消费

调度算法

• FCFS：先来先服务，first come，first served；

• SPN(SJF) SRT: 短进程优先(短作业优先)短剩余时间优先，shortest process next(shortest job first) shortest remaining time；

• HRRN:最高响应比优先，highest response ratio next；

• Round robin,轮循，使用时间切片和抢占来轮流执行任务；

• Multilevel feedback queues,多级反馈队列，多级反馈队列，优先级队列中的轮循；

• fair share scheduling, 公平共享调度；

一个实际的schedule函数

就绪队列

优先级调度、动态维护counter

counter时间片、优先级

进入io阻塞的进程，切换为就绪态后，counter变大

进程同步与信号量

进程合作、先后次序、阻塞

信号与信号量、睡眠、唤醒

量用来记录，信号用来休眠与唤醒

互斥信号量（锁、临界区）

信号量临界区保护

原子性、临界区只能有一个进程操作

• 1、互斥进入

• 2、有空让进

• 3、有限等待

自旋锁

标记法、轮转法、非对称标记

多个进程、面包店算法

临界区保护、硬件支持、阻止调度

硬件原子指令法（不会被打断）

中断唤醒、sem信号量

死锁处理

互相等待对方持有的资源

死锁条件

• 1、互斥使用

• 2、不可抢占

• 3、请求和保持（先占有资源，再请求别的资源）

• 4、循环等待

死锁处理

• 1、死锁预防

• 2、死锁避免，检查每个资源请求

• 3、死锁检测+恢复，释放资源、回滚

• 4、死锁忽略

银行家算法，检测是否会有死锁

悲观锁：申请资源就检测

乐观锁：发现问题，再检测

内存使用与分段

存储器、运算器、控制器

程序加载入内存、取指执行

重定位、修改程序的地址（相对地址，逻辑地址）

• 1、编译时重定位

• 2、载入时重定位

• 3、运行时重定位（采用）

重要的概念：swap（交换）

引入分段、分治思维、段号+段内偏移

代码段、数据段、栈段、动态数组段、函数段

LDT进程段表

段号、基址、长度、保护

内存分区与分页

1、程序分段

2、申请空闲内存

3、载入程序

内存划分：固定分区、可变分区

空闲分区表：始地址、长度

已分配分区表：始地址、长度、标志

分区的动态分配策略：首次适配、最佳适配、最差适配

引入分页、分段（存在大量碎片、效率低、需要时常内存紧缩）

物理内存：4KB

页表：页号（逻辑页号）、页框号（物理页号）、保护

MMU：内存管理单元

多级页表与快表

页大小：4kb

32位寻址大小：4gb

页：4kb、4gb需要2的20次方项放入内存、需要4m内存、10个进程就需要20m内存

又要连续，还要让页表占用小（多级页表）

类比思维：章目录、节目录

页目录号（10bits）、页号（10bits）、offset（12bits）

多级页表增加访问次数

TLB（快表）相关联快速存储、寄存器

局部性原理：时间局部性、空间局部性

段页结合的实际内存管理

程序（段）虚拟空间（页）物理内存

重定位：段表：段号+段偏移、页表：页号+页偏移

段页式内存管理、核心内存分配

单级页表、多级页表

• 1、分配虚存、建段表

• 2、分配内存、建页表

页目录号、页号、offset

虚拟内存、映射、物理内存

内存换入换出-请求调页

磁盘、换入、换出

缺页中断、从磁盘中读取段页数据，加载入内存

换出算法、FIFO页面置换

内存（店面）、磁盘（仓库）

MIN页面置换（最久将使用的页）

LRU页面置换（最近不常用、需要动态维护、代价高）

页面置换算法、工作集法

IO与显示器

全局观、宏观、微观

文件操作、抽象接口

缓冲区、buffer、提效

文件系统、设备驱动

PCI总线、总线控制器、CPU-内存总线

端口对应设备

生磁盘的使用

磁盘单位、扇区、512B（磁生电、电生磁)

柱面、磁头、扇区、缓存

磁盘驱动、磁盘控制器

读写基本单位：扇区

从扇区到盘块

多个进程通过队列使用磁盘

请求队列、磁盘驱动、磁盘控制器、磁盘

磁盘调度：FCFS算法、SCAN算法（电梯算法）

生磁盘到文件

文件得到盘块号（映射）

文件：建立字符流到盘块集合的映射关系

字符、字符流

FCB：文件控制块

文件名、起始块、块数

映射方式：

• 1、连续结构实现（适合读，不适合动态）

• 2、链式结构实现（适合动态、读慢）

• 3、索引结构实现

实际系统实现：多级索引

文件使用磁盘的实现：文件表、磁盘数据盘块

多级索引映射：直接数据块；一重间接、二重间接

目录与文件系统

抽象：目录树

目录与文件

• 根据目录、得到目录的FCB

• FCB找到磁盘块

• 标识TAG

• 磁盘格式化

目录解析代码实现：初始化、必要全局变量、文件根目录、磁盘挂载

操作系统全图

CPU、进程、线程、内存、文件、内核、磁盘、中断、输入输出设备
推荐结合阅读地址：清华大学公开课：操作系统
原文链接：【哈工大】操作系统 李治军

本作品采用《CC 协议》，转载必须注明作者和本文链接