408-操作系统-基础笔记

1.概述

• 管理系统资源
  • 功能：处理机管理、存储器管理、文件管理、设备管理
  • 目标：安全、高效
• 向上层提供服务
  • 命令接口
    • 联机（交互式）：command
    • 脱机：批处理
    • 狭义的定义中，不包含GUI
  • 程序接口：系统调用（又称为 广义指令）

1.1.四个特征

并发和共享是两个最基本特征，二者互为存在条件

• 并发

  • 宏观上同时，微观上交替

    并行：同时发生

• 共享：系统中的资源可供内存中多个并发执行的进程共同使用

  • 互斥共享：在一个时间段内，这个资源只允许一个进程来使用

  • 同时共享：在一个时间段内，允许多个的进程同时对它进行访问

    所谓「同时」是宏观上的

• 虚拟：没有并发性那虚拟性就没有存在的意义

  • 空分复用：如虚拟存储
  • 时分复用：如虚拟处理器

• 异步：进程的执行走走停停，以不可预知的进度前进。有了并发性才有异步性

1.2.发展和分类

• 手工操作系统
• 批处理系统
  • 单道批处理系统：引入脱机输入/输出技术（外围机+磁带），并由监督程序负责控制作业的输入、输出
  • 多道批处理系统（操作系统开始出现）
    • 资源利用率大幅提升
    • 响应时间长，不能人机交互
• 分时操作系统：计算机以时间片为单位轮流为各个用户/作业服务，各个用户可通过终端与计算机进行交互
  • 解决了人机交互
  • 感受不到别人的存在
  • 完全公平，不区分紧急性
• 实时操作系统：及时性，可靠性
  • 硬实时 系统：必须在绝对严格的规定时间内完成处理，如导弹、自动驾驶
  • 软实时系统：能接受偶尔违反时间规定
• 网络操作系统
• 分布式操作系统
• 个人计算机操作系统

1.3.基本原理

• 运行机制

  • 两种指令
    • 特权：只有内核程序可以使用
    • 非特权
  • 两种处理器状态
    • 核心态（管态）->用户态：一条特权指令，修改PSW中的状态字，意味着让出使用权
    • 用户态（目态）->核心态：中断
  • 两种程序
    • 内核程序
    • 应用程序

• 中断和异常

  • 中断作用
    • “中断”是让操作系统内核夺回CPU使用权的唯一途径
    • 没有中断技术就没办法实现多道程序并发
  • 类型
    • 内中断（异常）：和当前执行指令有关
      • 陷入 trap：陷入指令，系统调用
      • 故障 fault：错误条件引发，可以修复。如缺页
      • 终止 abort：致命错误引发，无法修复。如除0、非法使用特权指令
    • 外中断：和当前执行指令无关
      • 时钟
      • IO设备
  • 中断机制的原理
    • 检查时间
      • 内中断：执行指令时会检查是否有异常发生
      • 外中断：每个指令周期末尾，CPU都会检查是否有外中断信号需要处理
    • 查询中断向量表，找到对应的处理程序

• 系统调用

  凡是与共享资源有关的操作（如存储分配、/O操作、文件管理等），都必须通过系统调用的方式向操作系统内核提出服务请求，由操作系统内核代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作

  • 设备管理：完成 设备 的请求/释放/启动 等
  • 文件管理：完成 文件 的读/写/创建/删除 等
  • 进程控制：完成 进程 的创建/撤销/阻塞/唤醒 等
  • 进程通信：完成 进程 之间的消息传递/信号传递 等

  • 内存管理：完成 内存 的分配/回收 等

    陷入指令是在用户态执行的，执行陷入指令（访管指令）之后立即引发一个内中断，使CPU进入核心态
    发出系统调用请求是在用户态，而对系统调用的相应处理在核心态下进行

1.4.体系结构

• 内核结构
• 微内核：频繁转换用户态和内核态，影响性能

2.进程

2.1.进程

2.1.1.概念

• 程序：静态的，存放在磁盘里的可执行文件，指令的集合
• 进程：动态的，程序的一次执行过程
  • 进程实体：PCB+程序段+数据段
  • 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位
• PCB：是进程存在的唯一标志

2.1.2.特征

• 动态性：进程是程序的一次执行过程，进程的最基本特性
• 并发性：内存中有多个进程实体，各进程可并发执行
• 独立性：进程是能独立运行、独立获得资源、独立接受调度的基本单位
• 异步性：各进程按各自独立的、不可预知的速度向前推进，操作系统要提供“进程同步机制“来解决异步问题
• 结构性：每个进程都会配置一个PCB。结构上看，进程由程序段、数据段、PCB组成

2.1.3.状态

• 创建：分配空间，初始化PCB
• 就绪
• 运行
• 阻塞：主动地等待某个事件

• 终止：CPU做善后，回收资源

• 组织方式

  • 链式：运行、就绪各有一个指针，指向一个队列，高优先级放在队头。阻塞由于原因不同可以有多个指针
  • 索引表：就绪和阻塞各有一个索引表，表项是指向一个个进程的指针

2.1.4.进程控制

创建、销毁、状态转换

• 创建原语：申请空白PCB，分配资源，初始化PCB，PCB插入就绪队列
  • 用户登录：分时系统中，用户登录成功，系统会建立为其建立一个新的进程
  • 作业调度：多道批处理系统中，有新的作业放入内存时，会为其建立一个新的进程
  • 提供服务：用户向操作系统提出某些请求时，会新建一个进程处理该请求
  • 应用请求：由用户进程主动请求创建一个子进程
• 撤销原语：找到PCB，[剥夺CPU]，终止所有子进程、资源归还父进程或操作系统、删除PCB
  • 正常结束：exit调用
  • 异常结束：被强行杀掉
  • 外界干预：用户选择杀掉进程
• 阻塞原语：找到PCB，保护进程运行现场，将PCB状态信息设置为“阻塞态”，将PCB插入相应事件的等待队列
  • 需要等待分配资源
  • 需要等待其他进程
• 唤醒原语：找到PCB，从等待队列移除，设置进程为就绪态，PCB插入就绪队列
  • 等待的事件发生
• 切换原语：运行环境存入PCB，PCB移入相应队列，选择另一个程序并更新PCB，根据PCB恢复所需的运行环境
  • 当前进程时间片到
  • 有更高优先级的进程到达
  • 当前进程主动阻塞
  • 当前进程终止

2.1.5.进程通信

• 共享存储：对其的访问应当是互斥的，自己负责实现

  只需要加一个段表或页表

  • 基于数据结构：可以理解为「特殊的全局变量」。灵活性差、速度慢
  • 基于存储区

• 消息传递：消息头包含发送pid、接收pid、消息长度等格式化信息

  • 直接通信：直接指明接受消息的pid，接收也需要指明是谁发的
  • 间接通信：发送方完善消息体，然后指明发送给哪个信箱 ；接收方指明从哪个信箱中接收数据

• 管道通信：pipe文件（内存中开辟大小固定的缓冲区（循环队列）），FIFO

  两个方向的管道互斥，由操作系统保证

  管道写满了，写数据的进程会阻塞， 直到管道里有空位了

  管道空，读进程阻塞，直到管道里有数据了

  一旦读出，数据彻底消失。408真题考过多写1读（实际上linux可以多写多读）

2.1.6.线程

• 特点
  • 在引入线程之后，进程只作为除 CPU 之外的系统资源的分配单元。线程变为调度的基本单位
  • 同一进程的不同线程间共享进程的资源
• 实现方式
  • 用户级线程：通过线程库实现逻辑线程。一个线程被阻塞，整个进程被阻塞
  • 内核级线程：并行能力强，可在多核处理机上并行执行。需要CPU状态切换
• 多线程模型
  • 一对一：退化为内核级线程，管理成本高
  • 多对一：退化为用户级线程，只有一个CPU，并行度不高
  • 多对多：克服了两种缺点

2.2.处理机调度

2.2.1.概念

• 三个层次

  • 高级调度（作业调度）

    • 每个作业只调入一次，调出一次。作业调入时会建立PCB，调出时才撤销PCB

      作业：一个具体的任务

      用户向系统提交一个作业 == 用户让操作系统启动一个程序（来处理一个具体的任务）

  • 中级调度（内存调度）：

    • 暂时调到外存等待的进程状态为挂起状态。被挂起的进程PCB会被组织成挂起队列

  • 低级调度（进程调度）：最基本的调度

• 七状态模型

• 时机

  • 需要进程调度

    • 主动放弃：正常终止、发生异常、主动请求阻塞
    • 被动放弃：时间片用完、中断、更高优先级的进程进入就绪队列

  • 不能进程调度

    进程在操作系统内核程序临界区中不能进行调度与切换 ✅

    临界区有 普通 和 操作系统临界区 的区别，操作系统临界区管理进程调度队列等数据结构

    • 中断过程中
    • 操作系统内核程序临界区中
    • 原语（原子操作）

• 切换与过程

  狭义的进程调度指的是从就绪队列中选中一个要运行的进程

  进程切换是指一个进程让出处理机，由另一个进程占用处理机的过程

  广义的进程调度包含了选择一个进程和进程切换两个步骤

  • 进程切换的过程：保存PCB，恢复另一个进程的PCB

• 方式

  • 非抢占式
  • 抢占式

2.2.2.评价指标

• CPU利用率：CPU“忙碌”的时间占总时间的比例
• 系统吞吐量：单位时间内完成作业的数量
• 周转时间
  • 周转时间：完成时间 - 提交时间
  • 平均周转时间：各作业周转时间之和 / 作业数
  • 带权周转时间：周转时间 / 实际运行时间 $\ge 1$
  • 平均带权周转时间：各作业带权周转时间之和 / 作业数
• 等待时间
  • 对于进程来说，等待时间就是指进程建立后等待被服务的时间之和，在等待I/O完成的期间其实进程也是在被服务的，所以不计入等待时间
  • 对于作业来说，不仅要考虑建立进程后的等待时间，还要加上作业在外存后备队列中等待的时间。
• 响应时间：从用户提交请求到首次响应所用的时间

2.2.3.调度算法

• 先来先服务

  • 非抢占
  • 长作业有利，短作业不利
  • 不会导致饥饿

• 最短作业优先

  “抢占式的短作业/进程优先调度算法的平均等待时间、平均周转时间最少”

  “所有进程几乎同时到达时，采用SJF调度算法的平均等待时间、平均周转时间最少”

  • 没有特别说明一般是指 非抢占式
  • 抢占式版本：最短剩余时间优先。时间点：就绪队列改变、一个进程完成
  • 短作业有利，长作业不利
  • 会导致饥饿

• 最高响应比优先

  • 响应比 = （等待时间 + 要求服务时间）/ 要求服务时间 $\ge 1$
  • 非抢占
  • 不会导致饥饿

• 时间片轮转

  进程下处理机瞬间有进程到达，一般认为到达的排在前面

  • 抢占式
  • 时间片太大，退化为先来先服务。响应变慢
  • 时间片太小，切换太频繁
  • 一般来说，设计时间片时要让切换进程的开销占比不超过$1\%$
  • 公平，响应快，适合分时操作系统

• 优先级调度：选择高优先级的

  例题： 关注答题模式

  • 抢占式和非抢占式都有

  • 优先数和优先级的关系不一定，看题目

    系统进程优先级高

    前台进程优先级高

    操作系统偏好IO型进程，因为可以让IO设备尽早投入工作，资源利用率高

• 多级反馈队列

  高级队列先运行，运行一个时间片就把进程放到下一级队列的队尾

  只有高级队列空了，它的下一级队列才能开始执行

  被抢占剥夺处理器的进程放到此队列的队尾而不是下一级队列

  • 新到达进程快速得到响应
  • 短进程使用较少时间即可完成
  • 不必估计运行时间
  • 灵活调整对各类型进程的偏好程度

2.3.同步和互斥

2.3.1.进程互斥

• 对临界资源的互斥访问，在逻辑上分：
  • 进入区：判断能否访问临界资源
  • 临界区：访问临界资源的代码
  • 退出区：解除「正在访问临界资源」标志
  • 剩余区
• 原则：有限等待，让权等待
• 软件实现
  • 单标志法：访问完临界区后把权限交给另一个进程，即进程进入临界区的权限只能由另一个进程赋予。「谦让」
  • 双标志先检查：数组记录各进程进入临界区的意愿
    • 每一个进程在进入临界区之前，都会先检查对方是否想进入临界区
    • 如果对方不想进入临界区，表达自己想要进入临界区
    • 违反忙则等待原则
    • 问题的关键在于检查和上锁这两个动作并不能一气呵成
  • 双标志后检查
    • 先上锁，后检查
    • 违反空闲让进、有限等待原则
  • Peterson算法
    • 把自己的数组记录改为True
    • 把Turn改为对方，表示可以让对方先使用
    • 如果对方想用，或者最后一次是我谦让了，那就等待
    • 违反让权等待原则：如果不能进入临界区就应当放弃CPU
• 硬件实现
  • 中断屏蔽方法
    • 不适用于多处理机
    • 权限特别大，只适用于内核进程
  • TestAndSet（TS指令/TSL指令）
    • 适用于多处理机环境
    • 一边上锁一边检查，硬件实现
  • Swap指令（XCHG指令）

2.3.2.信号量

• 整型信号量

  • 用一个变量来表示某种资源的数量

  • 不满足让权等待，会发生忙等（while死循环，不让出CPU）

• 记录型信号量

  • 用一个结构体记录资源数量和等待队列
  • wait：资源数 -1 ，如果 <0，那么阻塞进程
  • signal： 资源数 +1 ，如果 <=0，那么还有进程在阻塞，唤醒队头进入就绪队列

• 同步 by 信号量

  • 信号量设为0
  • 「一前一后」 前操作后执行V，后操作之前执行P

• 互斥 by 信号量

  • semaphore mutex=1;，要会自己定义。不是整型，是一个结构体
  • 不同临界区/资源，设置不同的信号量

2.3.3.经典问题

• 生产者-消费者
  • 两对同步：缓冲区没满 -> 生产者生产；缓冲区没空 -> 消费者消费
  • 缓冲区是临界区资源，各进程互斥地访问
  • 两个P操作顺序不能反，否则会死锁；V操作不会导致阻塞，所以顺序无所谓

semaphore mutex = 1;  //互斥信号量，实现对缓冲区的互斥访问
semaphore empty = n;  //同步信号量，表示空闲缓冲区的数量
semaphore full = 0;   //同步信号量，表示产品的数量，也即非空缓冲区的数量
void producer(){
    while(1){
        //*********生产产品
        p(empty);
        p(mutex);//*********加锁
        //产品放入缓冲区
        v(mutex);//*********加锁
        v(full);
    }
}
void consumer(){
    while(1){
        p(full);
        p(mutex);//*********加锁
        //取出产品
        v(mutex);//*********加锁
        v(empty);
        //*********使用产品
    }
}

• 多生产者-多消费者

  不是多个，而是多类

  缓冲区大小为1时不用互斥加锁，因为同一时刻最多只有一个进程不被阻塞

  不要从进程前后的角度来考虑同步关系，要从状态模型考虑同步关系

semaphore mutex = 1;  //实现互斥访问盘子（缓冲区）
semaphore apple = 0;  //盘子中有几个苹果
semaphore orange = 0; //盘子中有几个橘子
semaphore plate = 1;  //盘子中还可以放多少个水果
void dad(){
    while(1){
        //准备苹果
        p(plate);
        p(mutex);
        //把苹果放进盘子
        v(mutex);
        v(apple);
    }
}
void mom(){
    while(1){
        //准备橘子
        p(plate);
        p(mutex);
        //把橘子放进盘子
        v(mutex);
        v(apple);
    }
}
void daughter(){
    while(1){
        p(apple);
        p(mutex);
        //取出苹果
        v(mutex);
        v(plate);
        //吃掉苹果
    }
}
void son(){
    while(1){
        p(orange);
        p(mutex);
        //取出橘子
        v(mutex);
        v(plate);
        //吃掉橘子
    }
}

• 抽烟者问题

  • 代码

• 读者-写者问题

  允许多读1写

  在写时其他进程不能进入

  写之前其他进程必须全部退出

  • 如果一直有进程在读，那写进程会饿死。因此增加了写优先信号量

semaphore rw=1;     //用于实现对共享文件的互斥访问
int count 0;        //记录当前有几个读进程在访问文件
semaphore mutex =1；//用于保证对count变量的互斥访问
semaphore w =1;     //用于实现“写优先”
void writer(){
    while(1){
        p(w);//*********为了写优先
        p(rw);
        //写文件
        v(rw);
        v(w);//*********为了写优先
    }
}
void reader(){
    while(1){
        p(w);//*********为了写优先
        p(mutex);
        if(count == 0) p(rw); count++;
        v(mutex);
        v(w);//*********为了写优先
        //读文件
        p(mutex);
        count--; if(count == 0) v(rw);
        v(mutex);
    }
}

• 哲学家进餐问题
  • 思路1：限制同时进餐人数是总人数-1
  • 思路2：奇数号先拿左边，偶数号先拿右边
  • 思路3：检查完左右都可以使用后才拿起筷子

2.3.4.管程

线程安全的数据结构库

• 组成部分
  • 局部于管程的共享数据结构说明
  • 对该数据结构进行操作的一组过程
  • 对局部于管程的共享数据设置初始值的语句
  • 管程有一个名字
• 特征
  • 局部于管程的数据只能被局部于管程的过程所访问
  • 一个进程只有通过调用管程内的过程才能进入管程访问共享数据
  • 每次仅允许一个进程在管程内执行某个内部过程

2.4.死锁

• 产生条件：互斥、不可剥夺、请求和保持、循环等待

  死锁一定循环等待，但是循环等待不一定死锁。循环等待是死锁的必要不充分条件

• 发生时机

  • 系统资源竞争，如打印机
  • 进程推进顺序非法，请求和释放资源顺序不当
  • 信号量的使用不当

• 处理策略

  • 预防死锁，破坏必要条件

    • 破坏-互斥：SPOOLing技术，将设备逻辑上抽象改造为共享设备

      适用范围不广

    • 破坏-不剥夺：

      • 资源不满足时立即释放，以后需要时重新申请

        一直如此的话会进程饥饿

      • 操作系统强行剥夺。需要考虑优先级

        实现复杂

        剥夺之前的一部分工作会失效，只适用于易保存和恢复状态的资源，如CPU

        反复申请资源增加开销

    • 破坏-请求和保持：静态分配，运行之前一次性申请全部资源。资源未满足不会投入运行

      资源利用率极低，可能导致饥饿

    • 破坏-循环等待：顺序资源分配，给系统中的资源编号，每个进程必须按编号递增的顺序请求资源，同类资源（即编号相同的资源）一次申请完

      不方便增加新设备，可能所有资源都需要重新编号

      实际使用资源顺序可能不是按照编号来，会浪费资源

      必须按规定次序申请，用户编程麻烦

  • 避免死锁，防止进入不安全状态

    • 安全序列：所有进程都能得到满足顺利结束
    • 不安全状态：找不到一个安全序列，有可能死锁，除非有进程提前归还资源
    • 银行家算法：
      • 扫描所有进程，找能运行的，认为其已经运行完，回收资源，重新扫描，直到所有进程都完成
      • 检查此次申请是否超过了之前声明的最大需求数
      • 检查此时系统剩余的可用资源是否还能满足这次请求
      • 试探着分配，更改各数据结构
      • 用安全性算法检查此次分配是否会导致系统进入不安全状态

  • 死锁的检测和解除

    • 检测
      • 不能消除所有边就是发生了死锁
      • 找一个既不阻塞也不是孤点的点，将其所有边消去称为孤点
    • 解除
      • 挂起死锁进程，抢占资源。应注意防止饥饿
      • 终止部分(或全部)死锁进程。实现简单，但代价大
      • 一个或多个死锁进程回退到足以避免死锁的地步。需要记录历史信息、设置还原点
    • 如何决定对谁动手
      • 进程优先级
      • 已执行多长时间
      • 还要多久能完成
      • 进程已经使用了多少资源
      • 进程是交互式的还是批处理式的

3.内存

3.1.地址转换

• 装入的方式

  • 绝对装入：编译时就把变量地址修改为正确的地址

    灵活性很差，只适用于单道程序

  • 可重定位装入：装入内存时按照起始地址修改所有变量的地址

    需要空间分配连续，且作业一次全部装入内存

    程序运行期间不可以移动

  • 动态运行时装入：程序真的要执行时才做地址转换

    现代操作系统 使用

    需要重定位寄存器记录装入程序的起始地址

• 链接的方式

  • 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数连接成一个完整的可执行文件（装入模块），之后不再拆开
  • 装入时动态链接：将各目标模块装入内存时，边装入边链接的链接方式
  • 运行时动态链接：在程序执行中需要该目标模块时，才对它进行链接。其优点是便于修改和更新，便于实现对目标模块的共享

3.2.存储保护

• 设置上下限寄存器
• 利用重定位寄存器、界地址寄存器进行判断

3.3.内存空间扩充

• 覆盖技术

  必须由程序员声明覆盖结构

  对用户不透明，增加了用户编程负担

  • 需要常驻内存的段放在“固定区”中，调入后就不再调出（除非运行结束）
  • 不常用的段放在“覆盖区”，需要用到时调入内存，用不到时调出内存

• 交换技术：进程在磁盘和内存之间动态调度。挂起状态

  不是换出所有数据。PCB会常驻内存

  • 什么位置：磁盘分为对换区和文件区，对换区为了速度选择连续分配，文件区为了利用率选择离散分配
  • 什么时候：经常发生缺页，说明内存紧张；缺页率下降可暂停换出
  • 换出什么：优先级低、阻塞。为防止调入内存后很快换出，还会考虑内存驻留时间

3.4.空间分配

3.4.1.连续分配

• 单一连续分配

  内存当中同一时刻只能有一道用户程序，不支持多道程序并发运行，用户程序独占整个用户区

  产生内部碎片

  • 实现简单，无外部碎片
  • 可以采用覆盖技术扩充内存

  • 不(一定)需要内存保护

  • 固定分区分配

    • 分区大小相等

      缺乏灵活性，适合用一台计算机控制n个相同的对象

    • 分区大小不等

      • 根据作业大小进行划分，如多个小分区，少量大分区

    • 分区说明表：包含 大小、起始地址、状态

      无外部碎片，有内部碎片（即有的分区不能完全使用，分配给程序却没有利用到）

• 动态分区分配：在进程装入内存的时候，根据进程的大小动态地建立分区

  无内部碎片，有外部碎片（空闲区域太小，没有进程能用）

  • 用什么记录：空闲分区表 或 空闲分区链

  • 紧凑技术：把进程挪位置，空出更大的连续空闲空间

  • 分配算法

    • 首次适应：空闲分区以地址递增排列，选择第一个能满足的空闲分区（地址最小）

    • 最佳适应：空闲分区以容量递增排列，选择第一个能满足的空闲分区（容量最小）

      留下很多难以利用的小碎片

    • 最坏适应：空闲分区以容量递减排列，选择第一个能满足的空闲分区（容量最大）

      大进程无处安放

    • 邻近适应：首次适应，但每次都从上一次查找结束的位置开始往后检索

      • 使用循环链表
      • 算法开销小，不需要额外花时间重新排列

3.4.2.非连续分配

• 基本分页存储管理：内粗分为大小相等的分区（4KB），进程的逻辑地址空间也分，进程页面与内存页框一一对应

  • 概念辨析

    • 页、页面：进程的逻辑划分部分
    • 页框、页帧：内存的物理划分部分，又称为物理页面
    • 页表长度：页表总项数（如4G）
    • 页表项长度：每个页表项占多大空间（如3B）
    • 页面大小：一个页面多大（如4K）
    • 页目录表：更高层级的页表

  • 每个进程一个页表，一般放在PCB中。页面占$2^{12}$B，所以共有$2^{20}$块，至少需要3B来表示块号。块号连续存放所以不需要存储页号，已经隐含了

  • 流程：拆分页号、偏移量；越界检查($\ge$)；[扫描快表]；查找内存块号；计算物理地址

  • 为了方便页表的查询，经常会让一个页表项占更多的字节，使得每个页面恰好可以装得下整数个页表项

    例1：使用基本分页存储管理，采用了快表。访问一次快表耗时1us，访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少？（此处快表慢表不同时查询）

    $(1+100)\times 0.9+(1+100+100)\times 0.1=111$us

    例2：

• 基本分段存储管理

  • 段表：段号、段长、基址（段在内存中的起始位置）。16+32=48位即可，6字节

  • 需要检查段内地址是否大于此段的段长

  • 更容易实现信息的共享和保护

  • 只有纯代码（不可重入代码、不能被修改的代码）可以被共享的访问。那这种代码不属于临界资源，各个进程即使并发的访问这些代码也不会因为并发产生问题

    分页分段对比：

    • 页是信息的物理单位。对用户不可见；段是信息的逻辑单位。分段对用户可见，用户编程时需要显式地给出段名
    • 分页当中进程的地址空间是一维的，而分段的时候进程的地址空间是二维的

• 段页式存储管理

  • 结构
  • 分段过程程序员可见，分页不可见
  • 只要快表命中就不需要再访问段表和页表

3.5.虚拟内存

• 传统方式缺点：一次性（无法运行或并发度下降）、驻留性（浪费资源）
• 虚拟内存技术建立在离散分配的内存管理方式基础之上
• 需要新增的功能
  • 请求调页：访问的信息不在内存时，操作系统将所需信息从外存调入内存，继续执行程序
  • 页面置换：若内存空间不够，操作系统将内存中暂时用不到的信息换出到外存

3.5.1.请求调页

• 页表新增四项

• 缺页中断机构：内中断（故障）

  一条指令中可能多次缺页中断，比如 copy A to B

  如果页面被换出了内存，快表中页表项也应当删除

  访问了一个页面后要修改快表、修改访问位 [和修改位（写指令时）]

  调入内存后修改页表和快表，再访问直接从快表找到

  缺页中断之后未必发生页面置换，只有内存块已经都满了才需要页面置换

  

3.5.2.页面置换

• 最佳置换（OPT）

  • 每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问
  • 无法实现

• 先进先出置换（FIFO）

  Belady异常——当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

• 最近最久未使用置换（LRU）

  • 从后往前检查找到最久没使用的

• 时钟置换算法（CLOCK）

  • 性能和开销较均衡

  • 最近未用算法（NRU，Not Recently Used）

  • 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描

    第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描

• 改进型的时钟置换：优先淘汰未修改过的页面，减少IO次数

  • 第一轮：从当前位置开始扫描到第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
  • 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换。本轮将所有扫描过的帧访问位设为0
  • 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0，0）的帧用于替换。本轮扫描不修改任何标志位
  • 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0，1）的帧用于替换
  • 最多4轮

3.5.3.页面分配

• 驻留集：实际在内存中页面数量 / 总页面数量
• 页面分配策略
  • 固定分配：局部置换
    • 为每个进程分配一组固定数目的物理块
    • 很难在刚开始的时候就确定应该为每个进程分配多少个物理块才能才算合适
  • 可变分配：局部置换（取决于缺页频率）、全局置换（打土豪分田地，只要缺页必定分配）
    • 进程运行期间，可根据情况做适当的增加或减少
  • 预调页：主要用于进程首次调入，由程序员指出哪些先调入
  • 请求调页：运行中缺页时才调入。IO开销较大
• 调入页面的时机
  • 对换区够大：调入调出都是对换区，因为快
  • 对换区不够大：不会被修改的数据都直接从文件区调入，换出时不必写回磁盘，下次需要时再从文件区调入即可。可能被修改的部分换出时需写回磁盘对换区，下次需要时再从对换区调入
  • UNIX方式：运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入
• 抖动（颠簸）现象：频繁访问的块数目高于可用物理块数
• 工作集：在某段时间间隔里，进程实际访问页面的集合
  • 大小可以小窗口实际尺寸
  • 一般来说驻留集不能小于工作集

4.文件

4.1.逻辑结构

• 无结构文件

• 有结构文件

  • 顺序文件

    串结构：记录之间的顺序与关键字无关

    顺序结构：记录之间的顺序按关键字顺序排列

    • 随机存取

  • 索引文件：本身是定长记录的顺序文件

    • 用于对信息处理的及时性要求比较高的场合
    • 若索引表按关键字顺序排列，则可支持快速检索

  • 索引顺序文件：对记录进行分组，每一个分组建立一个索引表项

4.2.文件功能

• 目录

  • 单级目录不能重名；两级目录不同用户的文件可以重名，但是文件不能分类

  • FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。 FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）

  • 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”——多个用户的文件指向同一个文件，使用共享计数器

  • FCB改进：文件名+索引节点指针。把所有其他信息都放到索引节点中

  • 内存索引节点需要增加是否被修改、有多少个进程访问等信息

• 保护

  • 口令：时间和空间的开销都小，但是口令保存在系统内部，如果泄露就畅通无阻了

  • 加密：保密性强、不需要保存密码，但加密解密耗时

  • 访问控制

    ACL表内容： 不重要，了解即可

    如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制

• 共享

  • 索引节点：硬链接：多个索引节点指针指向同一个索引节点
  • 符号链：软链接：一个特殊的Link类型文件，记录实际指向文件的绝对路径
    • 文件实际删除不影响软链接，只是链接失效
    • 速度比硬连接慢

4.3.物理结构

4.3.1.非空闲块

通常块和内存页面一样大，也 是用逻辑块号+块内地址这种方式

• 连续分配

  • 支持顺序访问和直接访问

  • 读写速度最快

    增加内容需要整体迁移文件

    碎片无法利用，可能无法找到足够大的连续空间

• 链接分配

  没说是哪种链接分配默认是隐式链接

  • 隐式链接：每一块中存储指向下一块的指针，对用户透明
    • 支持顺序访问，不支持随机访问
    • 文件拓展方便，不会有碎片，空间利用率高
  • 显式链接：各个块的指针显式地存放在文件分配表(FAT)中
    • 一个文件只需要一张表，常驻内存
    • 支持随机访问
    • 地址转换过程不需要访问磁盘，文件访问效率高

• 索引分配：为每个文件建立一张索引表，文件名关联索引表的存放位置

  • 二级索引

    例题：假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。
    若某文件采用两层索引，则该文件的最大长度可以到256 256 1KB = 65,536KB = 64MB

  • 混合索引

• 逻辑结构 和 物理结构 概念辨析

  链式存储是用户自己选择的数据逻辑结构；链式分配是操作系统自动完成的链式分配空间，对用户透明

  索引文件和索引分配

4.3.2.空闲块

• 几种管理方法
  • 空闲表法：每一个空闲区间的起始位置和长度
  • 空闲链表法
    • 空闲盘块链
    • 空闲盘区链：连续空闲区间之间组成一条链
  • 位示图法
    • 盘块号转换字号位号，注意是否从0开始
  • 成组链接法
    • 超级块常驻内存，与磁盘同步
    • 如果有一个分组全部分配出去，需要把指向下一块的链接信息复制到超级块中
    • 回收块时如果第一个分组已经满了，需要新建一个块，指向第一个分组（类似于头插）

4.4.基本操作

• 创建：找到空间、创建文件对应目录项
• 删除：找到目录项、回收磁盘块
• 打开：找到目录项并查看权限、将目录项复制到内存中的“打开文件表”中、用户使用打开文件表的编号（文件描述符）来指明要操作的文件
  • 系统的打开文件表，整个系统只有一张，记录所有的正在被其他进程使用的文件的一些信息
  • 进程的打开文件表，记录了自己的这个进程此时打开了哪些文件
  • 示意图
• 关闭：删除进程打开文件表中的表项、修改打开计数器。按情况回收资源
• 读：指明打开文件的编号（已经打开过了）、读入多少、放在内存什么位置

4.5.文件系统层次结构

• 示意图

4.6.磁盘

块号：柱面号、盘面号、扇区号

固定头磁盘（每个磁道有一个磁头）

移动头磁盘（每个盘面只有一个磁头）

• 一次读写时间

  • 寻找时间：启动磁头臂+移动磁头

    启动 + 移动个数 * 每个时间

  • 延迟时间：旋转磁盘的时间

    转半圈的时间

  • 传输时间

    转一圈的时间 * 需要转多少圈

• 调度算法

  没有特殊说明，默认不是走到头那种算法

  • 先来先服务（FCFS）：大量分布较广的请求性能不好
  • 最短寻找时间优先（SSTF）：性能较好，可能饥饿
  • 扫描算法(SCAN)：移动到最外侧磁道（不是最大的请求，是边界）才能反向
    • LOOK调度算法：到最边上一个请求后立即反向
  • 循环扫描算法（C-SCAN）
    • 移动到最外侧磁道（不是最大的请求，是边界）才能反向
    • 立即回到起始位置，不做任何处理
    • C-LOOK：两边都是最远请求就停止，不用到头

• 优化方法

  • 交替编号：让逻辑上相邻的扇区在物理上有一定的间隔
  • 柱面号在盘面号之前：读取连续磁盘块时，减少磁头移动消耗的时间
  • 错位命名：上下盘片之间磁道命名错开

• 磁盘初始化

  • 低级格式化，划分扇区。头、数据区域（如512B大小）、尾三个部分组成。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CC循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）
  • 分区，每个分区由若干柱面组成
  • 逻辑格式化，创建文件系统。创建文件系统的根目录、初始化存储空间管理所用的数据结构（如位示图、空闲分区表）

• 引导块

  • ROM中只存放很小的「自举装入程序」，完整的自举程序放在磁盘的启动块（即引导块/启动分区）上，启动块位于磁盘的固定位置
  • 拥有引导块的逻辑磁盘就是系统盘

• 坏块管理

  • 在FAT表中标记。对系统不透明
  • 扇区备用：磁盘控制器维护坏块链表，低格时对其初始化。同时会保留一些备用扇区用于替换坏块。对系统透明

5.设备

5.1.分类

• 按使用特性

  • 人机交互
  • 存储设备
  • 网络通信设备

• 按传输速率

  • 低速：鼠标键盘
  • 中速：激光打印机
  • 高速：硬盘

• 按信息交换单位

  • 块设备：磁盘

    传输速率较高，可寻址，即对它可随机地读/写任一块

  • 字符设备：鼠标键盘

    传输速率较慢，不可寻址，在输入/输出时常采用中断驱动方式

分配时应当考虑的因素：

• 设备固有属性
  • 独占性
  • 共享性
  • 虚拟性
• 设备分配算法
  • 先来先服务
  • 高优先级优先
• 设备安全性
  • 安全分配——发出IO就阻塞，IO完成才唤醒
  • 不安全分配——可同时发出多个IO，IO设备不可用才阻塞

5.2.IO控制

• IO控制器

  • 接受和识别CPU发出的命令（控制寄存器）
  • 向CPU报告设备的状态（状态寄存器）
  • 数据交换（数据寄存器）
  • 地址识别

• 编址方式

  • 内存映象
  • 寄存器独立编址：需要设置专门的指令来进行操作

• 控制方式

  • 程序直接控制

    CPU干预频率：很频繁

    数据传送单位：一个字

    数据流向：内存和IO设备之间一定要经过CPU

  • 中断驱动

    CPU干预频率：等待IO过程中CPU可以干别的，实现了CPU和IO并行

    数据传送单位：一个字

    数据流向：内存和IO设备之间一定要经过CPU

  • DMA（直接存储器存取）

    CPU干预频率： 请在一块数据的开始和结束时需要CPU的干预

    数据传送单位：一个字 或 一个块（必须连续。不连续还是要多条指令）

    数据流向：不需要经过CPU

  • 通道控制

    CPU干预频率：很低，完成一系列读写才会有一次中断信号

    数据传送单位：一组数据块

    数据流向：不需要经过CPU

    一个通道可以控制多个 IO 控制器，而一个 IO 控制器又可以控制多个 IO 设备

5.3.IO核心子层

• 结构

• SPOOLing技术：「输入/输出设备」和「输入/输出井」之间使用内存中的「输入/输出缓冲区」进行缓冲

• 设备分配

  • 安全分配：只要分配了IO设备就一定会阻塞。资源利用率低

  • 不安全分配：进程不会被阻塞，继续往下执行。可能导致死锁，可以使用银行家算法

  • 数据结构

    • 设备控制表DCT

    • 控制器控制表COCT

    • 通道控制表CHCT

    • 系统设备表（SDT）：记录了系统中全部设备的情况，每个设备对应一个表目

      缺点：

      • 用户编程时必须使用“物理设备名”，底层细节对用户不透明，不方便编程
      • 若换了一个物理设备，则程序无法运行
      • 若进程请求的物理设备正在忙碌，则即使系统中还有同类型的设备，进程也必须阻塞等待

• 设备分配的改进

  • 逻辑设备表（LUT）建立了逻辑设备名与物理设备名之间的映射关系
  • 第一次使用设备类型请求资源时，系统查询系统设备表，并在逻辑设备表中增加表项，下次请求时直接查逻辑设备表

5.4.缓冲区管理

• 作用
  • 缓和CPU与I/O设备之间速度不匹配的矛盾
  • 减少对CPU的中断频率，放宽对CPU中断相应时间的限制
  • 解决数据粒度不匹配的问题
  • 提高CPU与I/O设备之间的并行性
• 缓冲区必须充满后才能取出数据
• 周期
• 单缓冲，T>C时，T+M；T<C时，C+M
• 双缓冲，Max(T,C+M )
• 循环缓冲区：将多个大小相等的缓冲区链接成一个循环队列
• 缓冲池