Intro

  • 操作系统：是软件，且是系统软件；基本职能是控制和管理系统资源；提供服务，方便用户使用
    • 四大特征：并发，共享，虚拟，不确定
    • 类型：分时，实时，微机，网络，分布式，嵌入式，智能卡，云OS
    • 架构：微内核 micro kernel，宏内核/单体内核 monolithic kernel；SMP(Symmetric MultiProcessing)
    • 主要模块：进程管理，内存管理，设备管理，文件管理，用户
  • IO 基础
    • 脱机输入输出，批处理系统
    • 缓冲：解决速度不匹配问题；spooling
    • 中断：减少轮询；分为 IO (timer), Hard error, Soft error/exception
    • DMA
    • SPOOLing
      • 把一台物理设备虚拟成逻辑上的多台设备
      • 驱动程序：预输入，井管理，缓输出
      • 架构：接口-内存缓冲-井（暂时持久化）-内存缓冲-设备
  • 作业：一个完整的任务，包括多个作业步/程序

内存管理

  • 作用：提高主存的利用率，将尽可能多的作业同时加载到主存中
  • 层次：寄存器，主存，辅助存储器
  • 部分：寄存器，L1，L2，L3/主存，本地二级，远程二级
  • 需求：重定位，保护，共享，逻辑组织，物理组织
  • 管理技术：单一连续，固定分区，动态分区，分页/分段，虚拟内存
    • 重定位：分区导致的；静态/动态重定位：动态链接/PIC
    • 存储保护：上下限寄存器
    • 碎片：分区-内碎片；动态-外碎片
    • 可变分区分配算法
      • 首次适配：空闲分区链表按地址排序；分配快，回收效率高，碎片多，性能下降
      • 临近适配：循环首次适应，记忆上次指针位置；分配较快，碎片少
      • 最佳适配：空闲分区链表按块从小到大排序；分配慢，回收慢，利用率高，碎片小多
      • 最差适配：空闲分区从大到小；分配较快，回收慢，碎片中等
    • 算法对比
      • 复杂度：最佳（2+2）> 最差（1+2）>首次（1+1）>循环（1+1）
      • 小碎片产生的可能性：最佳 >首次 > 循环 > 最差
      • 后继大作业分配成功的可能性：最佳 >首次 > 循环 > 最差
    • 内存扩充技术：主辅存交换
      • 覆盖技术：预先程序分块
      • 交换技术：引入分页分段
  • 虚拟存储系统
    • 系统抖动：反复换出换入的现象
    • 任务：地址映射，缺页处理，物理内存回收分配
    • 特点：延迟分配，用户空间不受物理限制
    • 基础：异常中断机制；页表项
    • 地址翻译：页表 页号+偏移；快表 TLB 页号+flag
    • 多级页表；反向页表（逻辑页号+进程ID Hash）
    • 空闲页：位图，链表
  • 淘汰算法
    • 最优淘汰算法 Optimal：淘汰下次访问最远的
    • FIFO：某些情况抖动大
    • LRU：计数器，定时清理；复杂，会淘汰新页
    • 访问 FIFO：低效
    • NUR / 时钟算法：初始/访问1，扫描清零；rw: 先R后W
    • (Unix) 双时钟 前指针更新 flag，后指针淘汰
    • 年龄法/老化法：NUR 但是换成计数器
  • 读取/清除策略：请求式，预先式；驻留集：可直接访问物理内存（有效虚拟内存）
  • 替换策略：页缓冲（RO空闲页表，W修改页表）
  • 内存分配算法
    • Buddy System：二分，用于分配页；Linux lazy merge
    • Slab System：用于分配 Bytes；slub (Linux), slob (embed)

进程管理

  • 进程：系统进行资源分配和调度的一个可并发执行的独立单位
    • 组成：代码段(RO)，数据上下文（用户层，内核层，寄存器）
    • 管理结构：PCB
    • 一个进程只能对应于一个程序
    • fork, exec
  • 状态转换
    • 三状态：Running, Ready, Block
    • 五状态：Created(Limited by Process Number), Ready, Running, Sleep(Block/Wait/Uninterruptable sleep), Terminated(Traced/Stopped)
    • 挂起 Suspend: 需要评估加载资源
    • *Linux: Ready/Running, Sleeping, Uninterruptable sleep, Stopped, Zombie
    • *Windows: Ready, Standby, Running, Waiting, Transition, Terminated
    • 神秘 Job control block: 提交，后备，运行，完成
  • PCB：进程（标识，CPU，调度，记录）、内存、IO、文件
    • struct proc：核心内容，常驻内存部分
    • struct text: 代码段相关
    • struct user: 用户信息，proc 结构，信号处理，事件记录等
    • PCB 链表
    • 模式：内核态用户态
  • 线程
    • 进程：资源分配单位；线程：调度执行单位
    • 独立资源：执行状态，上下文，TLS，控制块
    • 共享资源：地址空间，程序代码，全局变量，设备文件
    • 优势：创建，终止，切换，通信快（x
    • 用户级多线程：假的，切换更快，更轻
  • 调度
    • 层次：长程/高级，中程/中极，短程/低级：队列，内存，CPU；通常只有一个进程调度
    • 准则：面向用户/系统；优先 IO、交互、段、优先级
    • 调度方式：不可剥夺，可剥夺
    • 时机：中断，异常，Trap
  • 调度算法
    • FCFS/FIFO：简单，不可抢占
    • SJF/SPN 最短优先：较简单，难预测
    • SRT 最短剩余时间：抢占，难预测，好于 SPN
    • HRRN 最高相应比：R=1+Waited/Runtime，折中
    • Round Robin 时间片轮转：剥夺式；改进：不同规格时间片
    • (Unix, Windows) Feedback：优先调度优先级最高的队列；高优先级时间片短；时间片用完降低优先级
    • (Linux) CFS 完全公平调度：vruntime = 实际运行时间 * NICE_0_LOAD/ 当前进程权重；队列按 vruntime 排
  • 多核处理器
    • 调度：公共就绪队列，私有就绪队列，两级
    • 负载均衡：推/拉
    • 亲和性（软，硬）；原因：hot cache, tlb
  • 实时调度：硬实时任务必须按时完成，软实时任务尽量完成
    • 静态表驱动，静态优先级驱动抢占调度，基于动态规划的调度，动态尽力调度
    • 时限调度：最早截止时间，最小松弛（最晚启动）时间
    • RMS 速率单调调度：（周期任务）调度 U=1/T 最大的任务；要求 $\sum \frac{t_i}{T_i}\le n(2^{1/n}1)$
  • 优先级逆转
    • 原因：高优先被低优先互斥阻塞
    • 解决：优先级继承（改任务优先级）；优先级置顶（设资源优先级）
  • 多处理器调度
    • 负载共享：全局队列
    • 群调度：全局“群”队列；分配
    • 处理器专派：线程绑核
    • 动态调度：？

进程间通信

  • 同步与互斥
    • 临界资源：一个时刻只能被一个进程访问或使用的资源
    • 临界区：是一段代码。进程通过这段代码访问临界资源
      • 原子性，可嵌套，可中断
    • 实现方法：硬件支持，用户态算法，操作系统
      • 中断禁用：仅单处理器，单临界区，危险
      • 特殊指令：简单
      • 用户态算法：可能死锁饥饿
        • Peterson 算法
      • 操作系统：信号量（需了解算法）
        • P/V, wait/signal
  • 同步实例
    • 半同步：单向等待依赖
    • 生产者和消费者问题: semaphore_t buf, ch; mutex<queue_t> queue;
      • producer: P(buf); push queue; V(ch);
      • consumer: P(ch); pop queue; V(buf);
    • RWLock: mutex<int> count; mutex rwlock;
      • reader: if (count++ == 0) P(rwlock); READ; if (--count == 0) V(rwlock);
      • writer: P(rwlock); WRITE; V(rwlock)
      • 解决 writer 饿死：维护 writer wait flag
    • 管程：RAII 锁 Mutex<T>
  • 消息
    • 进程间数据交换：消息，共享内存，管道 FIFO，socket，软中断/信号 signal
    • 原语：send, recv
    • signal: PCB 有 signal field 和对应 handler；无优先级，针对进程，不及时，用户态处理
    • FIFO pipe: 命名 mknod/mkfifo, 匿名 pipe；类似字符文件，单向；匿名管道用于同一进程族；环形缓冲区 ring buffer *PIPE_SIZE=64k, PIPE_BUF=4k；
    • 消息：msgget, msgsnd, msgrcv
    • 共享内存：shmget, shmat, shmdt
  • 死锁
    • 原因：资源竞争；硬件资源分配不当；软件编写不当
    • 条件：充分（循环等待）；必要（互斥，保持并等待，不可剥夺）
    • 资源分配图 Resource allocation graph RAG
    • 应对方法：
      • 预防：消除条件之一
        • 保持且等待：静态分配策路，失败全回滚
        • 不可剥夺：剥夺
        • 循环等待：资源排序，只能申请相较已获得编号更大的资源
      • 避免：允许条件，算法避免死锁
        • 介入时间：进程启动时，资源分配时
        • 拒绝进程启动：进程需要资源总和≤可用资源
        • 银行家算法：申请者告知未来最大需求；分配者计算死锁
          • 数据：max, alloc, need, available; request
          • (a) request < need （否则 error）
          • (b) request < available （否则 block）
          • (c) 试修改： need -= request; alloc += request（check alloc < max）
          • (d) Coffman 算法：假定 need 全同时变成 request，找到可行进程链；$O(n^2)$
        • 适用条件：进程间无同步，事先声明需求和可用资源
      • 死锁检测（从死锁恢复）：Coffman 算法
        • 死锁消除：撤销死锁进程，剥夺资源

附：Peterson 算法

int locker, try_lock[2]={0};

void lock(int pid) {
    int other = 1-pid;
    try_lock[pid] = 1;
    locker = pid;
    while(pid == locker && try_lock[other]);
}

void unlock(int pid) {
    try_lock[pid] = 0;
}

信号量 (see also linux/kernel/locking/semaphore.c at master · torvalds/linux)

typedef struct { 
  long count;
  mutex_t lock; // can replace with a spinlock
  condvar_t var; // can replace with a task queue
} semaphore_t;

// Initialize semaphore with initial count
void semaphore_init(semaphore_t* sem, long initial_count) {
    assert(initial_count >= 0);
    sem->count = initial_count;
    mutex_init(&sem->lock);
    condvar_init(&sem->var);
}

// Acquire resource (P operation/down operation)
void semaphore_acquire(semaphore_t* sem) {
    mutex_lock(&sem->lock);
    while (sem->count < 0)
        condvar_wait(&sem->var, &sem->lock); // unlock, wait and lock
    sem->count--;
    mutex_unlock(&sem->lock);
}

// Release resource (V operation/up operation)
void semaphore_release(semaphore_t* sem) {
    mutex_lock(&sem->lock);
    sem->count++;
    if (sem->count <= 0) condvar_notify_one(&sem->var);
    mutex_unlock(&sem->lock);
}

设备管理

  • 设备
    • 三层含义：物理设备，控制物理设备的设备，虚拟/逻辑设备
    • 分类
      • 块设备，流设备/网络设备，字符设备（无缓存）
      • 物理设备，逻辑设备
      • （特性）共享设备，独占设备，虚拟设备（SPOOL）
    • 作用：统一接口，提高效率，解耦
    • 功能：配置，控制驱动，缓冲，调度分配
    • 资源：IO 地址，IO 中断号，DMA/通道，IO 缓冲区
      • IO 通道类型：字节多路，选择，成组多路
  • 缓冲：单，双，环
  • 中断
    • 分类：IO (timer), Hard error, Soft error/exception
    • 处理：内核态 恢复现场；用户态 检查调度标志、信号设置标志，处理标志或恢复现场
  • 设备分配
    • 设备控制表 DCT：I/O操作映射到实际的设备；记录抽象设备描述，设备地址，驱动参数等
    • 控制器控制表 COCT，通道控制表 CHCT，系统设备表 SDT
    • Tree: SDT-DCT-CHCT-COCT
    • 设备开关表
    • 静态分配，动态分配
  • 设备请求管理：I/O请求块；分配缓冲区-写 buf-buf 挂请求块-请求队列
  • 统一接口
    • 统一标识，统一操作
    • 操作：抽象为文件名-文件操作
    • 主设备号：可以找到相应的设备驱动程序
    • 次设备号：指定具体的物理设备
  • 设备驱动：工作在内核态，可编译在内核也可以作为 kernel module 动态加载

文件系统

  • 磁盘
    • 机械硬盘
      • 术语：控制器，移动臂，磁头，扇区，磁道，盘片，柱面
      • 工作时序：等待设备，等待通道，寻道，旋转，数据传输
      • 磁盘时延 = 寻道时间 + 旋转时间 + 传输时间 + 控制器负载 = Ts+1/2r+b/rN+Tf
      • 使用：分区，格式化
      • MBR；分区表
      • 减少延迟：缓存（替换策略 LRU LFU），ramfs/tmpfs, RAID, 调度算法
      • 寻道调度策略：FCFS, SSTF, SCAN, C-SCAN; PRI, LIFO, N-SCAN, FSCAN
        • FCFS：先来先得
        • SSTF：最短寻道时间
        • SCAN: 双向扫
        • C-SCAN: 单向扫
        • N-SCAN: 分组 FCFS
        • (Linux IO elevator)
        • noop: 合并到最近的请求之后 or 队列尾部
        • deadline: 通过时间以及硬盘区域进行分类
        • anticipatory: 等待 6ms 再向处理下一请求组
        • cfq: IO 带宽按进程平均
      • RAID: 0(N) 1(kN) 2(N+m) (N+1, bit) 4(N+1, block) 5(N+1, distrib block), 6(N+2)
    • SSD
      • 前端协议 (sata, nvme)，FTL（逻辑地址-物理地址映射），NAND
      • FTL：块，页，混合
      • GC，写放大，磨损平衡
  • 文件系统
    • 要求：命名，分层；多用户，抗损，利用率
    • 文件类型：普通，目录，设备
    • 文件属性：类型，保护，其他
    • 逻辑组织
      • 字段，记录，文件
      • 堆文件（自描述串行），顺序文件（固定格式），索引顺序文件，索引文件（散列文件）
    • 资源分配
      • 策略：预分配，动态分配
      • 分块
      • 储存方式：连续，链接，索引，混合（extent）
    • 空间管理：位图，链表
      • 簇 cluster：软空间单元，多个 page/扇区；extent: 多个簇；volumn 卷：逻辑分区（部分磁盘、多个磁盘）
      • FAT：文件分配表 - 数据；表项：簇情况（空闲，保留，链表，终止，坏…） (ref)
      • NTFS: MFT (Master File Table) 主文件表
      • UNIX: superblock: 文件系统元数据；inode 索引节点: 文件元数据
      • 空闲块索引：把所有空闲块看作是一个大文件；superblock 会缓存空闲inode；多叉树组织
    • 目录文件
      • 作用：分层，加快检索，隔离保护
      • 内容：文件名，文件属性，inode 簇
      • 结构：线性，哈希表，B树
      • FAT：文件名，文件属性，时间日期，起始簇，长度
      • 现代：目录项仅放文件名，其余 inode；inode 多级索引(ext2/3)
      • 内存索引节点 inode
    • 系统调用：create, open, close, link, unlink, read, write, lseek; mknod, chmod, chdir, dup, stat, fcntl, umask
    • 目录结构：根目录，.，..，链接
    • 路径搜索：绝对/相对
    • 分布：引导块-超级块-I节点区-数据区
    • UNIX文件控制块 struct file；进程打开文件表
  • 虚拟文件系统
    • 在具体文件系统和操作系统的文件服务接口间实现虚拟层
    • ext2
    • ext3: journal (log, checkpoint)
    • ntfs: journal
    • ffs, apfs, exfat, hystor: SSD 写放大

信息安全

  • 基本概念
    • CIA: 保密性，完整性，可用性；真实性，责任性
    • 威胁类型：信息泄露，欺诈，中断，侵占
    • 威胁主体：入侵者，恶意软件
    • 入侵防护：物理，网络，系统，应用
    • 安全保障技术：数据加密，身份认证，访问控制
    • 需求：权限管理，访问控制，安全隔离，安全审计
    • 评估主体：计算机信息系统，可信计算基，主体（用户，进程），课题（文件，内存），敏感标记，安全策略
    • GB17859－1999：《计算机信息系统安全保护等级划分准则》：用户自主，系统审计，安全标记，结构化，访问验证
    • TCSEC：D,C1,C2,B1,B,B3,A1,A2 保护级别
  • 操作系统机制
    • Linux: 用户标识，保护位，日志；superuser, 审计，完整性保护
    • Windows: AD, 身份验证，访问控制
    • 标识和鉴别，可信路径管理，禁止客体重用，最小特权管理，访问控制技术（自主，强制），隐蔽信道检测与控制，安全审计
  • 安全操作系统设计与实现
    • 引用监视器
    • 安全策略：自主存取控制策略，强制存取控制（BLP）策略，BIBA策略，中国墙策略
    • 安全模型：有限状态机模型，访问控制矩阵，基于角色的访问控制模型（RBAC）
    • 安全体系结构：GFAC，Flask
    • 安全操作系统原型：RSBAC，SELinux（基于 Flask）

过拟合

  • 操作系统的一个功能是控制和管理各用户的程序，并有效地组织多道程序的运行：错
  • 调度算法考量：处理器使用率、吞吐量、周转时间、等待时间、响应时间
  • 用户编制的程序与实际使用的物理设备无关是由（）功能实现的：设备独立性
  • 互斥 进步 有限等待 是临界区同步要求
  • Buddy 可减少外部碎片，块分配减少内部碎片
  • 设备号不算地址参数
  • UNIX 成组链接
  • SAS控制器可以直接操控SATA硬盘
  • IDE 不常见
  • 移臂调度
  • 可变分区不能位图
  • 记录成组；块因子：块长/逻辑记录长
  • 入侵者：伪装者（利用合法用户），越权者（访问未被授权），秘密用户（逃避审查和访问控制）