OS_RE

lec1 Introduction

lec2 Boot

lec3 Memory Management

lec4 Process/Thread

进程与线程

并发

  • 若干个程序同时在系统中运行，这些程序在执行的时间上是重叠的

并行

  • 多个程序，它们在同一时间度量下同时运行在不同的处理机上，则称两个程序是并行执行的

并行则一定并发，而并发不一定并行。因为并发只是在宏观维度下两个程序在执行时间上是重叠的，在这期间，它们可能是运行在同一处理机的不同时间段，，也可能运行在完全不同的处理机上。并行则要求两个程序运行在完全不同的处理机上。

竞争

  • 多个程序读写同一个共享数据的结果依赖于它们的执行顺序

进程

进程的定义

  • 进程是对CPU资源的一种抽象
  • 进程与程序不同。进程可以简单理解为程序运行的过程。同时其是系统进行资源分配与调度（线程发明前）的基本单位
  • 进程包含程序、数据、进程控制块

进程的控制

  • 就绪状态：进程获取除处理机外所有所需资源，等待分配处理机资源
  • 执行状态：占用处理机资源。处于此状态下的进程数小于等于CPU数目
  • 阻塞状态：正在执行的进程，由于发生某种事件而暂时无法执行，便放弃了处理机处于阻塞状态
    alt text

线程

线程的定义

线程又称轻量级进程。将资源与计算分离，提高了并发效率

  • 减少了进程切换的开销
  • 提高进程内的并发程度
  • 共享资源
    alt text

线程的实现

  • 用户级线程
    • 线程在用户空间，不需要或仅需要极少内核支持
    • 优点：轻量、切换上下文迅速
    • 缺点：由于实现在用户空间，线程之间的关联强，线程并不完全算作CPUO调度的基本单位
  • 内核级线程
    • 线程实现在内核
    • 优点：真正实现内核对多个线程的调度
    • 缺点：线程切换的效率较低
      alt text

混合实现的线程模型
大多数情况下，系统同时拥有用户级线程与内核级线程的方式

  • Many-to-One
    • 多个用户级线程映射到一个内核级线程
    • 优点：线程管理效率高
    • 缺点：线程间耦合过强，并非严格意义上的独立
  • One-to-One
    • 每个用户级线程映射唯一内核级线程
    • 优点：线程间独立
    • 缺点：开销较大，影响用户程序的性能
  • One-to-Many
    • n个用户级线程映射到m个内核级线程（m <= n）
    • 特点：中和了前两种方案的优点与缺点，达到相对的平衡

进程调度

CPU调度：CPU调度的任务是控制协调多个进程对CPU的竞争，也就是按照一定的策略，从就绪队列中选择一个进程，并将处理机的使用权交给该进程。

调度的分类

  • 高级调度（“宏观调度”、“作业调度”）
    • 对用户提交的若干作业，对每个作业进行调度。时间跨度通常是分钟、小时或者天
  • 中级调度（“内外存交换”）
    • 对储存器资源角度而言。将进程的部分或者全部换到外存上，将需要使用的部分换入内存
  • 低级调度（“微观调度”、“进程、线程调度”）
    • 对CPU资源角度而言，时间跨度通常是毫秒级
    • 依据是否根据时钟中断做出调度决策分为抢占式和非抢占式
    • 依据不同应用领域，分为批处理系统、交互式系统、实时系统
      alt text

度量指标

  • 吞吐量：单位时间完成的作业数
  • 周转时间：作业从提交到完成的时间
  • 带权周转时间：周转时间/服务时间（实际执行时间）
  • 平均周转时间：周转时间和/作业数
  • 平均带权周转时间：带权周转时间和/作业数

批处理系统的调度策略

  • FCFS(First Come First Serve)
    • 先来先服务
    • 公平，容易理解和实现
    • 有利于长作业
    • 有利于计算密集型作业，不利于I/O密集型作业
  • SJF(Shortest Job First)
    • 最短作业优先服务，非抢占
    • 优点：改善了FCFS的平均周转时间等，提高系统吞吐量，在所有作业均可运行的情况下，最小化平均周转时间！！！
    • 缺点：对长作业不利、难以预估作业的执行时间
  • SRTN(Shortest Remaining Time Next)
    • 剩余时间最短进程优先，抢占
    • 可能导致饥饿
  • HRRN(Highest Response Ratio Next)
    • 考虑作业的运行时间，又考虑作业的等待时间
    • Response Priority = (1 + T已经等待) / T要求运行
    • 不会导致饥饿，效果不错

交互式系统的调度策略

  • RR(Round Robin)
    • 队列中的进程依次执行一小段时间（时间片）
  • PRS(Priority Scheduling)
    • 赋予每个进程不同优先级，高优先级的进程可以优先进行
  • MQ(Multiple Queue)
    • 不同的队列可以有不同的优先级、时间片长度、调度策略等等
    • 进程按照优先级分入不同的队列，队列之间按照优先级进行调度
  • MFQ()
    • 时间片轮转算法与优先级算法的综合
    • 多级优先队列，优先级越高则时间片越短；优先级越低则时间片越长。进程早高一级队列运行完时间片会移入下一级队列
    • 仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾

进程同步

互斥方法

忙等方法

  • 严格轮转法（谦让）
    int turn = 0; // 轮到哪个进程访问临界区了

    // process 0
    while (turn != 0);
    critical_region();
    turn = 1;
    ...

    // process 1
    while (turn != 1);
    critical_region();
    turn = 0;
    • 缺点：不满足空闲让进与忙则等待
  • Peterson算法（有限谦让）
    #define true 1
    #define false 0
    #define N 2;
    int turn = 0; // 某个进程谦让，不进入临界区
    int wanted[N] = {0}; // 某个进程希望进入临界区


    enter_region(int process) {
      int other = 1 - process;
      wanted[process] = true;
      turn = process;
      while (turn == process && wanted[other] == true);
    }

    leave_region(int process) {
      wanted[process] = false;
    }
  • Dekker算法（有限谦让）
    #define true 1
    #define false 0
    int turn = 0; // 谦让给某个进程进入临界区
    int wanted[N] = {0}; // 某个进程希望进入临界区

    enter_region(int process) {
      wanted[process] = true;
      int other = 1 - process;
      while (wanted[other]) {
        if (turn == other) {
          wanted[process] = false;
          while (turn == other);
          wanted[process] = true;
        }
      }
    }

    leave_region(int process) {
      wanted[process] = false;
      int other = 1 - process;
      turn = other;
    }
  • 基于关中断方案
    • TestAndSet、swap指令等

基于信号量

(to be continued…)

死锁

由于资源占用互斥，当某个进程提出资源申请之后，使得一些进程在无外力协助的情况下，永远分配不到必须的资源而无法执行

死锁类型

  • 资源死锁：某个进程集合中每个进程等待的事件都是释放该进程集合中其他进程的资源
  • 通讯死锁：因为通讯信息丢失导致两通信进程互相等待
  • 活锁：两个以上线程由于互相谦让资源，导致都拿不到资源

死锁条件

  • 互斥条件：进程分配到的资源具有排他性使用，一段时间只能由一个进程占用
  • 保持与请求条件：已获得资源的线程可以申请新的资源
  • 不剥夺条件：资源不能被剥夺，只能等待使用完后释放
  • 环路等待条件

处理死锁方法

  • 鸵鸟算法：就是装死
  • 死锁检测与死锁恢复
    • 资源分配图
      • 表示进程对资源的持有或者请求
      • 识别空闲资源，对空闲资源进行分配，一旦满足了进程的运行要求，则消去边（分配空闲资源并释放）
      • 死锁是有环路的充分不必要条件
    • 资源向量
      • 类似银行家算法
        alt text
  • 死锁预防
    • 静态破坏死锁的四个必要条件
  • 死锁避免
    • 动态破坏死锁的四个必要条件，分配前判断是否安全
    • 银行家算法

lec5 I/O

I/O设备

特点：种类多、差异大

设备分类

  • 传输速度：低速、中速、高速
  • 信息交换单位：字符设备、块设备、网络设备
    • 字符设备：以字符为单位发送或者接收字符流的设备，不可寻址。例如打印机、鼠标等
    • 块设备：以块为单位进行发送或者接收数据的设备，每个块独立于其他块读写。例如硬盘、USB盘等
  • 使用特性：存储设备、输入输出设备
  • 共享属性：独占设备、共享设备、虚拟设备

硬件组成

  • I/O接口（设备控制器）
    • 功能
      • 接收与识别命令
      • 数据交换（CPU与控制器、设备与控制器）
      • 标识设备状态等
      • 地址识别、数据缓冲等
    • 类型
      • 数据传输方式：并行接口、串行接口
      • 主机访问I/O：程序查询接口、中断接口、DMA接口
      • 功能选择特性：可编程接口、不可编程接口
  • I/O端口（接口中直接可以被CPU访问的寄存器）
    • 类别
      • 数据寄存器：传输数据
      • 状态寄存器：查询状态
      • 控制寄存器：改变设备模式等
    • 地址
      • 独立I/O编址：独立的I/O和内存空间，拥有独立的I/O指令
      • 内存映像编址：内存映射I/O，控制器的内存/寄存器映射为物理内存空间的一部分，通过已有的访存指令进行I/O

I/O控制技术

  • 程序控制
    • I/O通过程序的方式来进行，每次读写通过CPU进行，例如轮询、忙等
    • 优点
      • 实现简单
    • 缺点
      • CPU利用率低，CPU资源浪费
  • 中断驱动
    • I/O通过程序的方式发起，每次读写通过CPU进行。在操作完成时由外设向CPU发出中断信号，通知该程序
      • 优点
        • 外设进行数据处理时，CPU不必等待，而是继续执行其他程序，提高了CPU的利用率，也可以处理不确定事件
      • 缺点
        • 输入/输出需要多次中断CPU，中断次数过多浪费时间
  • 直接内存访问(DMA)
    • 程序设置DMA若干寄存器值，通过DMA控制器发起I/O操作。由DMA控制器与内存直接发生成批的数据交换。开始结束时才通过中断通知CPU
    • 优点
      • CPU只在开始、结束时干预I/O操作，后续操作无需CPU控制
    • 缺点
      • 各类信息依旧依赖CPU控制，占用CPU时间
      • 每个设备都占用一个DMA控制器，设备增加时DMA控制器也需要增加
  • 通道技术(Channel)
    • 通过以通道指令为基础的通道程序，可以进行较为复杂的I/O控制。一个DMA控制器只能控制一台或者少数几台同类设备；而一个通道可以同时控制多种设备。
    • 优点
      • 执行通道程序可以完成几组I/O操作，减少CPU干预
    • 缺点
      • 费用较高

I/O软件组成
软件由上层到底层共分为四类：用户层软件、设备独立性软件、设备驱动程序、中断处理程序

  • 用户层软件
    • 与用户交互的接口
    • 格式化I/O等、支持I/O的库函数
  • 设备独立性软件
    • 分为逻辑设备和物理设备，为物理设备统一访问驱动程序的接口
      • 优点
        • 设备分配灵活
        • 易于实现重定向输出等
      • 设备逻辑表(LUT)用于将逻辑设备映射为物理设备
    • 执行所有设备共有操作（分配与回收）
    • 缓存控制、分块操作等
  • 设备驱动程序
    • 与硬件相关，实现系统对硬件的各种操作
    • 和设备的固件要分开
    • 设备固件位于设备内部，其实现对于操作系统也是透明的。但是提供了寄存器使用的规则等
    • 设备驱动程序属于操作系统，将固件的行为解析封装为简单的操作，例如对于IDE磁盘则为ide_write、ide_read
  • 中断处理程序
    • 用于保存与切换CPU环境
    • 进程上下文切换、读取设备状态和修改进程信息等
      alt text

I/O缓冲技术

  • 缓冲技术可以提高外设利用率：
    • 匹配CPU与外设的不同处理速度
    • 减少CPU的中断次数
    • 提高CPU和I/O设备之间的并行性
  • 专用缓冲：适用于特定的I/O进程和计算进程
    • 单缓冲：每当用户进程发出一个I/O请求时，OS便在主存中分配一个缓冲区
    • 双缓冲
    • 环形缓冲
  • 缓冲池：为了方便管理，将相同类型的缓冲区链成队列
    • 空缓冲队列，输入队列，输出队列

I/O设备管理

  • SPOOLing假脱机技术，将具有独享属性的设备转为具有共享属性的设备
    • 即专门利用一道SPOOLing程序来与I/O进行交互
    • 用户程序和SPOOLing程序交互，称为虚拟I/O过程
    • SPOOLing程序与真实I/O交互，称为真实I/O过程

lec6 Disk

磁盘访问时间

  • 平均寻道时间、平均旋转时间、读写时间
  • 平均寻道时间：启动磁头和跨越磁道
  • 平均旋转时间：旋转寻找扇区 (1/2r r:转/秒)
  • 读写时间：磁头进行读写时间 (b/N * 1/r b：需要写入bit、N：总体bit、r：转/秒)

磁盘调度算法

  • 先来先服务(FCFS)，最短寻道时间优先算法(SSTF)，扫描算法(SCAN)，循环扫描算法(CSCAN)，LOOK，C-LOOK
  • 先来先服务算法：简单，公平，效率不高
  • 最短寻道时间优先：改善了磁盘的平均服务时间，可能产生饥饿
  • 扫描算法：当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复。克服了最短寻道优先的缺点，但两侧磁道的被访问频率低于中间磁道
  • 循环扫描算法：类似示波器扫描电压工作
  • 釆用SCAN算法和C-SCAN算法时磁头总是严格地遵循从盘面的一端到另一端，显然，在实际使用时还可以改进，即磁头移动只需要到达最远端的一个请求即可返回，不需要到达磁盘端点。
  • LOOK，C-LOOK

磁盘空间管理

  • 空闲表法
  • 空闲链表
    • 空闲盘块链
    • 空闲盘区链
  • 位视图
  • 成组链接法

RAID廉价磁盘冗余阵列

  • RAID0

    • 条带化处理
    • $D$容量RAID0 = $D$正常磁盘容量
    • 优点：读写速度加倍，并行化处理
      • 可以认为将某个数据若干相邻的数据块存储在不同的磁盘中，这样理论上读取该数据的时间将缩短为读取数据块的时间
    • 缺点：出错概率加倍
      • 不妨假设组内有两块磁盘，总有$D$容量。对于存储的一份$d$容量的数据，假设该数据均匀地分在两块磁盘中。且设磁盘每单位容量出错的概率为$p$。则该数据损坏的概率为$p\times\frac{d/2}{D/2} + p\times\frac{d/2}{D/2}$
      • 而两块磁盘不组成RAID0时导致数据不可用的概率是$p\times\frac{d}{D}$

  • RAID1

    • 镜像冗余处理
    • $2\times D$容量RAID1 = $D$正常磁盘容量
    • 优点：出错概率减少
      • 即数据备份到两块磁盘中，出错的概率由$p\times\frac{d}{D}$下降为$(p\times\frac{d}{D/2})^2$
    • 缺点：冗余导致容量降低
      • 理由略

  • RAID01

    • 组间进行镜像冗余，组内进行条带化处理
    • $2\times D$容量RAID01 = $D$正常磁盘容量
      正常情况strip： disk1 (12345678)

                    RAID1
                      |
                -------------
                |           |
              RAID0       RAID0
                |           |   
              -----       -----
              |   |       |   |
              1   2       1   2
              3   4       3   4
              5   6       5   6
              7   8       7   8
            disk1 disk2 disk3 disk4
    • 较正常情况容量减少一半，速度增加一倍
    • 同理分析出错概率，即两份镜像组都出现问题，镜像组出问题即组内任意一块磁盘出现问题
      • 设8条的磁带（即正常情况）的disk容量为$D$,数据容量为$d$，概率为$(p\times\frac{d/2}{D/2} + p\times\frac{d/2}{D/2})^2 = \frac{4\times p^2\times d^2}{D^2}$

  • RAID10

    • 组间进行条带化，组内进行镜像冗余
    • $2\times D$容量RAID10 = $D$正常磁盘容量
      正常情况strip： disk1 (12345678)

                    RAID0
                      |
                -------------
                |           |
              RAID1       RAID1
                |           |   
              -----       -----
              |   |       |   |
              1   1       2   2
              3   3       4   4
              5   5       6   6
              7   7       8   8
            disk1 disk2 disk3 disk4
    • 较正常情况容量减少一半，速度增加一倍
    • 分析出错概率，出现问题需要两组磁盘子队列其中一组出错，但是每组出现问题需要内部磁盘块同时出现问题即，$(p\times\frac{d/2}{D/2})^2 + (p\times\frac{d/2}{D/2})^2 = \frac{2\times p^2\times d^2}{D^2}$

由上分析，RAID10的可靠性比RAID01要高，而且随着条带的增多可靠性呈二次函数增长

  • RAID2

    • 海明码校验
    • 数据按位分配给组内各个磁盘
    • $D + log(D)$容量RAID2 = $D$正常磁盘容量
    • 校验位不发生错误的情况下$log(n)$位海明码纠正$n$位数据位任意一位的错误

  • RAID3

    • 纯奇偶校验
    • 数据按位分配给组内各个磁盘
    • $D + 1$容量RAID3 = $D$正常磁盘容量
    • 恢复指定位置一位错误

  • RAID4

    • 纯奇偶校验
    • 数据按块分配给各个磁盘（由此提高磁盘访问的并行性，每次访问不必从每个磁盘中读取位然后拼在一起）
    • 奇偶校验单独作为一个磁盘，每次写入时需要更改该盘，数据修改的瓶颈集中在奇偶校验盘
    • $D + 1$容量RAID4 = $D$正常磁盘容量

  • RAID5

    • 纯奇偶校验
    • 数据按块分配给每个磁盘
    • 奇偶校验的部分不作为单独一个磁盘存在，而是零散分布在各个磁盘中，此时奇偶检验的更改可以在多个磁盘上同步发生。
    • $D + 1$容量RAID5 = $D$正常磁盘容量

  • RAID6

    • 奇偶校验及其其他校验码
    • 数据按块分配给每个磁盘
    • 校验的部分不作为单独一个磁盘存在，而是零散分布在各个磁盘中。
    • $D + 2$容量RAID6 = $D$正常磁盘容量

lec7 文件系统

文件

  • 文件即一组带标识的、在逻辑上有完整意义的信息项的序列，包含文件体和文件说明

文件的逻辑结构

  • 流式文件结构
    • 构成文件的基本单位是字符，文件是有逻辑意义，无结构的一串字符的集合

目录

  • 目录是由文件说明索引组成的用于文件检索的特殊文件

目录分类

  • 单级文件目录，二级文件目录，多级文件目录
  • 一级文件目录：根目录下就是文件
  • 二级文件目录：根目录下增加每个用户的目录
  • 多级目录：层次化目录，形成复杂的目录树

文件控制块与文件属性

  • 文件控制块(FCB)：保存管理文件所需的所有有关信息
  • 信息：
    • 基本信息：文件名，物理位置，文件逻辑结构（记录，流式），文件物理结构（顺序，索引）
    • 访问控制信息：文件所有者，访问权限
    • 使用信息：创建时间，上次修改时间，当前使用信息

文件的物理结构

  • 连续文件
    • 由一组在磁盘连续区域的物理块构成
    • 优点：结构简单、实现容易、顺序存取与随机存取速度快
    • 缺点：不利于文件动态扩充，创建文件时需要给出文件大小，对用户不方便
  • 串联文件结构/链接文件结构
    • 不连续的物理块通过链表的方式组合在一起
    • 优点：空间利用率高、易于动态扩充或者修改、顺序存取速度快
    • 缺点：随机存取效率低，空间损失等
  • 索引文件结构
    • 一个文件的信息存放在若干个不连续物理块中。系统为每个文件建立一个专用数据结构：索引表，并将这些物理块的块号存放在该索引中