学习资料：老师的PPT、作业、计算机操作系统（第四版）汤子瀛、汤小丹等，加自己的另一篇总结

学习计划：每天复习1章内容+例题+习题+总复习PPT的主要内容

学习时长：距离考试10天，学习计划8天，留1~2天总复习  19年1月1号复习完了zzz，超出预期的速度

考试：概念忘记，可以用例子来解释

第一章 概论

操作系统的基本概念

  • 概念：操作系统是配置在计算机硬件上的第一层软件，是对硬件系统的首次扩充，主要作用是管理设备，提高它们的利用率和系统的吞吐量，并为用户和应用程序提供一个接口
  • 目标：方便性、可扩充性、开放性、有效性（提高系统资源的利用率，系统的吞吐量）
  • 作用：计算机和用户的接口、资源管理、资源抽象（封装）

操作系统的发展过程

  • 单道：内存中仅有一道程序
    • 优点：自动、顺序、单道
    • 缺点：系统资源得不到充分利用
  • 多道：内存中按调度算法执行程序
    • 优点：资源利用率高、系统吞吐量达
    • 缺点：平均周转时间长、无交互能力
  • 分时：一台主机上有多个终端，时间片轮转法
    • 优点：多路性、独立性、及时性、交互性
  • 实时：系统的正确性，取决于逻辑结果和产生结果的时间，允许抢占。最大特点是响应快
  • 分时和实时的区别
    • 多路性、独立性、及时性、交互性、可靠性

操作系统的基本特性

  • 并发
    • 并行并发、进程、线程
  • 共享
    • 互斥共享、同时访问（实质是交替访问）

操作系统的虚拟技术

  • 时分复用技术：利用处理机空闲时间，转去为其他用户服务
    • 虚拟处理机技术：多道程序设计技术
    • 虚拟设备技术：将一个IO设备虚拟为多个IO设备，并分配给每一个用户
  • 空分复用技术：利用存储器空闲时间，转去为其他程序服务
    • 虚拟内存
    • 虚拟存储器技术
  • 异步性：每次运行过程不可预知

操作系统的管理功能

  • 进程控制：创建、撤销进程
  • 进程同步：让多个进程协调进行
  • 进程通信
  • 调度

第二章 进程管理

  • 前驱图的定义
    • 定义：DAG图，描述进程执行的先后顺序
  • 程序顺序执行的特征
    • 顺序性、封闭性、可再现性
  • PCB定义
    • 定义：为每个进程配置的进程控制块，描述进程的基本情况和活动过程
  • 进程控制-进程状态转换（重点）
  • 信号量、临界区定义
    • 临界区：并发进程中，每个进程访问临界资源的代码称为临界区
    • 信号量
      • 整型信号量：开一个整型变量S
      • 记录型信号量：整型信号未实现“让权等待”，多定义一个变量list,来存储让权了的进程
      • AND型信号量：多个进程共用多个临界区资源
  • 同步机制应遵循的准则
    • 空闲让进、忙则等待、有限等待、让权等待
  • 经典同步问题（重点）
    • 有限缓冲区
      • 代码：循环队列，in=(in+1)%n,out=(out+1)%n，临界区资源counter(全局变量)
    • 生产者-消费者问题
      • 记录型信号解决，代码 
        • int in=0,out=0;
item buffer[n];
auto mutex=1,empty=n,full=0;
void producer{
    while(1){
        new temp;
        wait(empty);
        wait(mutex);
        buffer[in]=temp;
        in=(in+1)%n;
        signal(mutex);
        signal(full);
    }
}

void consumer(){
    while(1){
        wait(full);
        wait(mutex);
        int good=buffer[out];
        out=(out+1)%n;
        signal(mutex);
        signal(empty);
    }
}

           

      • AND型信号解决：利用Swait()代替两个连续的wait，即只有资源都空闲的时候才执行
      • 管程解决，代码：写一个类，封装了put和get两个函数
    • 哲学家进餐问题
      • 记录型信号量解决会死锁，直接写AND型，代码： 
        int statu[5]={1,1,1,1,1};
while(1){
    Swait(statu[i],statu[(i+1)%n]) //对于第i位哲学家来说
    do ... sth ...
    Ssignal(statu[i],statu[(i+1)%n]) //对于第i位哲学家来说
}

         

    • 读者-写者问题：同一时刻只允许一个进程读，不允许读+读 / 写+写 / 写+读

第三章 调度与死锁

低级、中级、高级调度定义

  • 高级调度：又称长程调度或作业调度，调度对象是作业，功能是用某种调度算法决定就绪队列中那几个作业调入内存
  • 中级调度：又称内存调度，目的是为了提升吞吐率和资源利用率，功能是将外存中的程序块调入内存，并加入就绪队列
  • 低级调度：又称进程调度或短程调度，调度对象是进程，功能是用算法决定哪个进程获得处理机
  • 总结：高级调度→哪些作业调入内存；中级调度→外存到内存；低级调度→哪个进程获得处理机
  • 作业，是一个总任务，而进程是作业的各个子任务。高级调度做作业分配，中级调度和低级调度面向进程，分别决定了哪些进程允许进入内存和哪些进程允许获得处理机（处理机包括CPU和主存储器）

调度规则

  • CPU利用率、吞吐量、周转时间（完成时间-到达时间）、平均周转时间（）、带权周转时间（周转时间/真实执行时间，）、平均带权周转时间（）、等待时间、响应时间

算法（重点）

  • 先来先服务
  • 短作业优先
  • 优先级调度
  • 时间片轮转法

死锁定义

  • 若干个进程在争夺资源，最后陷入无限期的阻塞和等待中

死锁条件

  • 互斥
  • 不剥夺
  • 请求与保持
  • 循环等待

死锁避免方法-银行家算法（重点）

  • 贪心首先完成能完成的

死锁预防、解除方法

  • 预防：打破除了互斥的其他三个条件
  • 解除：抢占资源、终止进程

第四章 存储器管理

连续分配

  • 概念：为了能将程序装入内存，必须为它分配一定大小的内存空间，连续分配方式是最早出现的存储器分配方式
  • 类型
    • 单一连续分配：系统分为用户区和系统区
    • 固定分区分配
    • 动态分区分配：首次适应（先找到先用）、最坏适应（找到最大的用）、最佳适应算法（找到最小的用）
    • 动态可重定位分配算法：紧凑（去除小碎片，相当于平移）、重定位（重定位寄存器存在进程在内存的首地址）

基本分页式（重点）

  • 物理地址和逻辑地址的区别
    • 逻辑地址：理解为虚拟地址，包括了偏移量
    • 物理地址：数据真实存放的地方
  • 页表定义及作用
    • 定义：为了能在内存中找到每个页面对应的物理块
    • 作用：实现从页号到物理块号的地址映射
  • 地址变换机构
    • 基本地址变换机构：比下图少了个快表的部分
    • 具有快表的地址变换机构：实质上快表先建立了一个映射表，节约了去页表找页号的时间，相当于预处理

基本分段式

  • 段表作用：逻辑段到物理内存区的映射
  • 地址变换机构：段表寄存器

分段式和分页式的区别

  • 分页管理
    • 没有外碎片，但会产生内碎片（页可能填不满）
    • 一维地址
    • 主要用于实现虚拟内存
    • 以页为单位，大小静态
  • 分段管理
    • 没有内碎片，但会有外碎片
    • 二维地址
    • 以段为单位，大小动态

段页式的实现过程

  • 程序分成若干个段，每个段对应一个页表

虚拟存储器

  • 定义：具有调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统
  • 页面置换算法
    • 最佳置换算法
    • 先进先出算法
    • 最近最少使用算法
    • 最少使用次数算法

第五章 输入输出系统

缓冲管理

  • 缓冲区作用
    • 缓和CPU和IO设备速度不匹配的矛盾
    • 提高CPU和IO设备之间的并行性
    • 减少CPU的中断频率，放宽对CPU中断响应时间的限制
    • 解决数据粒度（数据单元大小）不匹配的问题
  • 单缓冲
  • 双缓冲（缓冲对换）：减少了用户响应时间
  • 循环缓冲区
    • 三个指针
      • nextg：指向装了数据的空缓存区
      • nexti：空缓存区
      • Current：正在使用的缓存区
    • 使用
      • Getbuf，装载和读取数据
      • Releasebuf，释放缓存区
  • 缓冲池
    • 组成：emq,inq,outq
    • 工作方式
      • 收容收入Getbuf（emq）
      • 提取输入Getbuf（inq）
      • 收容输出Getbuf（enq）
      • 提取输出Getbuf（outq）
  • SPOOLING系统（重点） 
    • 假脱机技术：利用专门的外围机，当需要用数据的时候，可以直接从磁盘读入 (我感觉就是一个缓存区吧。
    • 组成
      • 输入井和输出井：模拟输入的磁盘
      • 输入缓冲区和输出缓冲区：输入缓冲区，在给输入井之前，先放缓冲区缓一缓
      • 输入进程和输出进程：模拟外围机，从外部输入数据到缓冲区
      • 井管理程序：用于控制作业与磁盘井之间信息的交换

设备分配（请求与保持条件）

  • 安全算法：每当进程发出I/O请求后，便进入阻塞状态
  • 不安全算法：仅当进程所请求的设备已被另一个进程占用时，才进入阻塞状态

磁盘调度算法

先来先服务、最短寻道时间优先（贪心）、SCAN（单向再折返）、CSCAN（单向到最后一个，再跑到另一端的第一个）

第六章 文件管理

文件逻辑结构

  • 按是否有结构分类
    • 有结构文件：分为定长记录和不定长记录
    • 无结构文件：流式文件
  • 从文件组织方式
    • 顺序文件
    • 索引文件
    • 索引顺序文件

文件存储空间管理

  • 空白文件目录：这种方法将盘空间的一个未分配区域称为一个空白文件，系统为所有的空白文件建立一个目录，每个空白文件在这个目录中建立一个表目。
  • 空白块链：这种方法将盘上的所有空白块用链接指针或索引结构组织成一个空白文件。
  • 位示图：它将文件存储器的存储空间建立一张位示图，用以反映整个盘空间的分配情况

文件目录管理

  • 要求：按名存取、提高读目录的检索速度、文件共享、允许文件重名
  • 文件控制块FCB
    • 基本信息类：文件名、物理位置、逻辑结构、物理结构
    • 存取控制信息类：权限
    • 使用信息类：文件建立的日期和时间，上一次修改的时间