由于操作系统的内容有点多，这里只记录自己的知识易错点和错题，提高学习效率！！！

引论+第一章（操作系统简介）：

• 操作系统：一组管理和控制软硬件，合理对各类资源进行调度以方便用户使用的程序集合。
• 操作系统的目标：方便性，有效性，可拓展性，开放性。
• OS的作用：
  • 用户和计算机之间的接口
  • 操作系统作为系统的管理者：CPU（处理机），存储器，I/O设备，文件管理
• 单批道处理系统特征：自动性，顺序性，单道性
• 
  • 上面这里注意一下，如果p1切换成p2了，让 p2 先跑完效率会高一些嗷！！！
• 多批道特点：多道性，无序性，调整性
• 分时系统特点：多路性，独立性，及时性，交互性
  • 分时系统响应时间：
    • 用户数*时间片 + To.s(时间开销) + Twap（信息交换时间）
• 
• 实时信息处理：
  • 特点：
    • 响应及时
    • 可靠性高
  • 特征：
    • 多路性
    • 独立性
    • 交互性
    • 可靠性
    • 及时性
• 现代OS四个基本特征:
  • 并发性（最重要，基本）
  • 共享性（基本）
  • 虚拟性
  • 异步性
• 任务共行：
  • 宏观上，多个任务并行
  • 微观上，多个任务并发
• 进程特点：
  • 资源所有权
  • 调度 / 执行：调度的实体
• 线程：
  • 进程变为资源分配的基本单位
  • 线程称为全新的资源调度基本单位
• 共享：
  • 互斥共享：一段时间内只允许一个进程使用
  • 同时访问：宏观上同时访问资源，微观上依然是十分快速的交替互斥访问。
• 虚拟：一个物理实体变为若干个逻辑上的物理实体。
• 操作系统的主要功能：
  • 处理器管理
  • 存储器管理
  • 设备管理
  • 文件管理
  • 方便用户使用的用户接口
• 公用模块儿比活跃模块儿更加底层
• 微内核的小型内核一直运行在核心态，开机后常驻于内存。支持多处理机运行的OS全部都使用了微内核结构。机制与策略分离的原理嗷！！！采用面向对象技术！！！

第二章（进程特性）：

• 顺序执行：顺序性，封闭性，可再现性
• 并发执行：间断性，失去封闭性，不可再现性
• 进程是程序的一次执行，资源分配和调度的一个独立单位。
• 进程实体结构：
  • 程序段
  • 数据段
  • PCB
• 进程特征：
  • 动态性
  • 并发性
  • 独立性
  • 异步性
• 执行 -> 就绪：
  • 时间片用完
  • 优先级高的进程抢占
• 竞争内存资源的解决：
  • 对换技术
  • 虚拟存储技术
• 进程挂起：OS , 自身 , 父进程
• PCB中的信息：进程标识符，处理机状态，进程调度信息，进程控制信息
• PCB组织方式：线性方式，链接方式，索引方式
• OS内核两大功能：支撑功能，资源管理功能
• 导致一个进程去创建另外一个进程的典型事件：
  • 用户登录
  • 作业调度
  • 提供服务
  • 应用请求（它自己创建一个新进程）
• 创建：申请空白PCB结构和标识符，分配资源，初始化进程控制块，启动调度。
• 终止：PID找到PCB，若为执行改为终止重新调度，子孙存在子孙终止，资源全部还给父系统，PCB从队列中移出
• 阻塞：发现无法执行就使用block原语阻塞自己，”执行“ 改为 ”阻塞“，PCB插入阻塞队列，调度程序重新调度并切换。
• 唤醒：PCB从阻塞队列中移出，将PCB中的阻塞改为就绪，PCB插入就绪队列中。
• 挂起：检查进程状态（就绪或阻塞）-> PCB复制到内存区域 -> 挂起正在执行，则重新调度
• 激活：静止就绪 -> 活动就绪 ， 禁止阻塞 -> 活动阻塞
• 总结：取出来，改状态，插入新队列，如果执行修改的话就要重新调度。
• 切换：

• 制约关系：
  • 直接：进程间合作（同步）
  • 间接：资源共享（互斥）
• 临界资源：一次只允许一个进程访问的资源。
• 临界区：访问临界资源的代码
• 同步机制的规则：空闲让进，忙则等待，有限等待，让权等待
• 同步的主要任务：有效共享资源和相互合作，程序具有可再现性
• 同步的解决方法：软件，硬件，信号量，管程，消息传递
• 软件方法始终解决不了”忙等“现象，降低系统效率
• 资源型信号量的取值范围 1 ~ -(n-1)
• 
• 用信号实现前驱关系：

• 任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被挂起，以等待管程变成可用的。从而实现进程互斥。
• 我们可以把管程想像成具有一个入口点，并保证一次只有一个进程可以进入。其他试图进入管程的进程，加入到挂起等待管程可用的进程队列中。当一个进程在管程中时，它可能会通过发送cwait(x)把自己暂时挂起在条件x上，随后它被放入等待条件改变以重新进入管程的进程队列中。
• 进程通信：
  • 共享存储器
  • 消息传递系统
  • 管道
• 通信的实现方法：
  • 直接：Send , Receive
  • 间接：邮箱，消息缓冲队列 - 随机性

第二章遗留：

• 生产者，消费者等问题的具体实现代码，看看第二章的课件，还有往年的期末考题。dygg的飞书中也有相应的题目和功能，记得要去康康嗷！！！

第三章（进程/作业调度）：

• 作业：数据 + 程序 + 作业说明书

• 作业步：作业经过相互关联的顺序加工步骤才能得到结果。

• 作业流：依次执行的作业步

• 调度：

  • 高级，低级，中级调度
  • 高级调度：后备队列的作业调入内存（批处理系统，分时和实时系统直接进入内存，没有这个环节）
  • 低级调度：就绪队列中的进程获得虚拟机，多道批处理，实时和分时都要使用。
  • 中级调度：就绪和挂起状态的转换

• 低级调度的三个基本机制：

  • 排队器
  • 分派器
  • 上下文切换机制

• 调度原则：满足用户的需要和系统的需要

• 共同目标：

  • 资源利用率
  • 公平性
  • 平衡性
  • 策略强制执行

• 面向用户的准则：

  • 周转时间短
  • 响应时间快
  • 截至时间的保证
  • 优先权准则

• 面向系统的准则：

  • 吞吐量高
  • 利用率好
  • 各类资源平衡并且充分的使用

• 周转时间：

  • 从进入系统开始是到离开系统的时间
  • 带权周转时间，权重 = 周转时间 / 实际服务时间

• JCB：

  • 作业标志
  • 作业类型
  • 作业状态等

• 作业三状态：

  • 收容
  • 运行
  • 完成

• 调度算法1：

  • FCFS：
    • 长作业有利
  • SJF：
    • 短作业有利
  • SPF

  例子：

  • 

  • 上面这三种都是分配处理机到执行完成或阻塞为止嗷！

• 调度算法2：

  • 优先级调度算法（PSA）：

    • 外部赋予优先级，决定紧迫程度。

  • 高相应比优先调度算法：

    • 优先权 = 1 + 等待时间 / 要求服务时间
    • 每次调度之前要计算响应比，会增加系统开销

• 进程调度的任务：

  • 选取进程
  • 保存现场
  • 处理器分配给要执行的进程

• 进程调度主要原则：

  • 优先权
  • 短进程优先
  • 时间片原则

• 调度算法3：

  • 轮转调度算法：
    • 原理：FCFS + 时钟中断 + 时间片原则
    • 时间片大小确定：略大于依次典型交互所需要的时间。
    • 
  • 抢占式优先权调度算法
  • 多队列调度算法：不同类型不同队列，优先级不同
  • 多级反馈队列调度算法：
    • 可以抢占！！！
    • 

• 调度算法4：

  • 保证调度算法：
    • 保证启动后的某个时间段内必须获得多少运行时间
    • 例如N个进程平均分配时间
  • 公平共享调度算法：
    • 按照用户数量平均分配时间，而不是进程平均分配

• 调度算法5（实时任务）：

  • 分类：
    • 非抢占轮转调度
    • 非抢占优先权调度
    • 基于时钟中断抢占的优先权抢占调度
    • 立即抢占的优先权调度
  • 最早截止时间优先算法（EDF）：
    • 最早截至时间的任务排在队列的最前面。（抢占式）
  • 最低松弛度优先算法（LLF）：
    • 松弛度 = 完成截止时间 - 剩余运行时间 - 当前时间
    • 只有松弛度变为0的时候，才会发生进程的调度。任务结束或无任务执行的时候，再比较任务的松弛度，较小的先执行。

• “优先级倒置”的现象，即高优先级进程(或线程)被低优先级进程(或线程)延迟或阻塞。 -> 动态优先级继承

• 死锁原因：

  • 竞争资源
  • 进程推进顺序非法

• 临界资源：

  • 可重用
  • 消耗性

• 不可抢占性资源：某个资源一旦分配给某个进程，则系统不能剥夺进程的使用权，只能由进程释放资源，或者进程终止运行。

• 死锁定义：一组进程中的每一个进程都在等待由该组进程中其他进程才能引发的事件，就称这组进程是死锁的。

• 四个必要条件：

  • 互斥：资源排他性使用
  • 请求和保持：手里有了盯着锅里的
  • 不可剥夺：系统抢不了，只能自己释放
  • 环路等待：死锁的时候，形成一个环形链

• 死锁解决：

  • 预防死锁：限制条件，破坏四个必要条件
  • 避免死锁：资源动态分配的过程中，防止进入不安全状态，从而避免死锁。
  • 检测死锁：确定死锁的进程和资源
  • 接触死锁：撤销或挂起一些进程。

• 预防：

  • 请求和保持：一开始就要所有资源，后面就不给了
  • 不可剥夺：进程获得不了申请的资源，自己释放，后面自己再重新申请
  • 环路等待：资源编号，按照编号递增申请资源。

• 避免死锁：

  • 迪杰斯特拉的银行家算法
  • 数据结构：
    • Available
    • Max
    • Allocation
    • Need
    • Request
  • Work = Work + Allocation，这个变量表示系统中当前步骤能够工作的机器的数量，Work就是动态的Available
  • 
  • 五列：Work Need Allocation Work+Allocation Finish
  • 先假定分配Need和Available，再去查看是否招的到安全路径。

第四章（存储器）：

• 存储器层次结构：

  • 缓存
  • 内存
  • 磁盘

• 存储器管理的目的和功能：

  • 主存储器的分配和管理：
    • 记住每个存储区域的状态
    • 实施分配
    • 接受系统或用户释放的存储区域
  • 提高主存储器的利用率
  • “扩充” 主存容量
  • 存储保护

• 存储分配方式：

  • 直接指定：使用实际存储地址
  • 静态分配：
    • 目的程序可以从空间的零地址开始，装配程序的时候对其进行连接装入时才确定它们在主存中的相应位置。
    • 分配之后不能搬家，不能申请新的存储量，装入前必须直到全部存储量且一次就要装入。
  • 动态分配：
    • 空间装入时确定
    • 可以申请附加的空间
    • 不再需要还给系统
    • 存储区域的大小是可变的
    • 允许作业在内存中“搬家”

• 地址：

  • 逻辑地址
  • 物理地址

• 名空间 -> 地址空间 -> 存储空间

• 程序的装入与链接：

  • 编译：源代码编译为目标模块
  • 链接：目标模块和库函数链接在一起，形成完整的装入模块。
  • 装入：装入程序将装入模块装入内存中。

• 程序的装入：

  • 绝对装入（逻辑地址就是实际地址）

• 可重定位装入：

  • 编译得到相对地址（从0开始）
    • 逻辑和物理不同，就是把逻辑变成物理。
    • 重定位分类如下
  • 静态重定位：
    • 一次完成
      • 物理 = 相对 + 内存中的起始地址（基地址）
        • 方便，但是不能移动，共享困难。
      • 动态在下面
  • 动态运行时装入：
    • 使用动态重定位
    • 使用在动态运行时装入。
    • 内存中存储的代码仍然是相对地址，运行的时候硬件就会自动对于数据或指令进行地址变换
    • 需要一个重定位寄存器（RR）

• 程序的链接：

  • 静态链接：运行前链接在一起，以后不再拆开：
    • 相对地址的修改
    • 变换外部调用符号
  • 装入时动态链接：
    • 变装入边链接
    • 模块更新容易修改，共享容易
  • 运行时动态链接：
    • 各模块儿独立装入并且不链接，运行时发现外部地址才链接。节省空间，最常用！

• 连续分配方式：

  • 单一连续分配：

    • 内存仅驻留一道程序
    • 系统区 + 用户区（提供给唯一的用户使用）

  • 固定分区分配：

    • 内存划分为若干个固定大小的区域，每个区域就是一个分区。
    • 划分方法：
      • 分区大小相等
      • 分区大小不等

  • 动态分区分配：

    • 分区的数目固定，大小可变

    • 分区和数目和大小都可变

    • 数据结构：

      • 空闲分区表
      • 空闲分区链

    • 分配内存和回收

    • 动态分区匹配算法：

      • 最佳适应算法：大小递增链接起来，从小到大找
      • 最坏适应算法：大小递增链接起来，从大往小找
      • 首次适应算法：地址递增次序链接，从低地址向高地址找
      • 循环首次适应算法：带旋转指针的首次适应算法，每次从上次查找结束位置开始往后找

      例题：

      

      

      • 快速适应算法：
        • 大小分类，存在多个空闲分区链表
        • 取下第一块儿分配
      • 伙伴系统：
        • 看书！！！
      • 哈希算法

• 动态重定位分区分配：

  • 紧凑 -> 分散的小分区合成一个大分区
  • 动态重定位技术
  • 时机：
    • 载入大程序，无可用空间。
    • 碎片较多，系统空闲。

• 对换：

  • 文件区：离散分配
  • 对换区：为了提高速度，连续

• 分页存储管理：

  • 离散分配（不一定连续存放）
  • 分为：
    • 分页
    • 分段
    • 段页式
  • 页号和块号
  • 页表：每个进程对应1个页表，描述进程的各页面对应的物理块儿号。页表只有系统有权访问。
  • 作业表：系统只有1张，记录作业的页表情况，包含进程号，页表长度，页表起始地址等信息。
  • 空闲块表：系统一张，记录主存空闲块
  • 
  • 注意上面这个不是物理，是逻辑，真正的物理还需要页表中的内容去转换。
  • 
  • 上面这个前后可以看作分离的，前面就是纯纯的页号，后面就是纯纯的偏移量。
  • 硬件：页表寄存器
  • 
  • 上面这个就是转换过程。注意，页面的逻辑地址在页表中对应了页面的物理地址（也是用页来表示的），然后就需要再将物理页数转换为块首址。

• 例题：

• 作业能用的只有逻辑地址嗷！！！，注意逻辑页面地址从0开始嗷！！！

• 逻辑地址的定义！！！

• 另一道例题：

• 又一道例题：

• 快表：

例题：

• 流程：快表 + 内存 或 快表 + 内存（页表） + 内存（数据）

• 分段式存储管理：方便编程，方便信息共享

• 段表和页表都在内存中，段表仍有内存分区表，内存分配算法等等。

• 段的结构是二维的嗷！！！段表若在内存中，需要访问内存两次嗷！！！

• 例子：

• 段页式：

  • 本质就是把段作为基本单位，按照分页的方法来进行管理而已嗷！！！
  • 
  • 段表 + 页表 + 数据
  • 快表！！！

• 虚拟存储器

  • 常规的问题：
    • 一次性（一个作业一次全部装入内存）
    • 驻留性（装入后驻留在内存直到作业完成）

• 局部性

• 请求分段/分页机构的硬件支持：

  • 请求分页的页表机制（分段也是）
  • 缺页中断机构
  • 地址变换机构

• 虚拟存储器特征：

  • 多次性
  • 对换性
  • 虚拟性

• 出现问题：抖动

• 请求分页存储管理方式：

  • 请求分页系统是建立在基本分页基础上的，为了能支持虚拟存储器功能而增加了请求调页功能和页面置换功能。
  • 页表：
    • 状态位：0就是不在，1就是在
    • 访问位：0未被访问，1被访问
    • 修改位：0未被修改，1被修改
    • 外存地址：指出该页外存上的地址
  • 缺页中断机构：
    • 产生缺页中断
    • CPU执行中间得到服务
  • 地址变换机构：
    • 计算物理地址
  • 最小物理块儿数的确定：
    • 单地址指令直接寻址，最少物理块数为2。（指令和数据各一块儿）
    • 分配策略：
      • 固定分配局部置换
      • 可变分配全局置换
      • 可变分配局部置换
    • 分配算法：
      • 平均分配
      • 按比例分配
      • 优先权分配

• 调页方式：

  • 预调页方式：
    • 预计不久后便被访问的页面，预先调入内存。
  • 请求调页：
    • 发现页不存在，才装入页面。

• 三种情况：

  • 系统有足够的对换区空间
  • 系统缺少足够的对换区空间
  • UNIX方式

• 页面置换算法：

  • 最佳置换算法：
    • 移出永远不再需要的页面
    • 移出最长事件不需要访问的页面
    • 
    • 理论上可行，实际困难，不知道未来的调用啊
  • 先进先出置换算法（FIFO）：
    • 选择驻留时间最长（最老）的一页淘汰
    • 先进入的先退出
    • 
  • 最近最久未使用：
    • 
  • 例题：

  

  

  • 例题2：

  

• LRU算法的硬件支持：寄存器，栈。（看书）

  • 

• 

• 最少使用置换算法（LFU）：

  • 

• Clock置换算法：

  • 
  • 
  • 
  • 上面这个我称之为一格一格往下移！！！

• 改进型Clock置换算法：

  • 
  • 
  • 最多三轮+1！！！：
    • 第一轮：没访问过，没修改过
    • 第二轮：没访问过就行（访问过的访问位置为1，这一轮之后，所有A都为0）
    • 第三轮：“没访问过，没修改过”
    • 第四轮开始：一定能找到！！！

• 缺页时间的计算：

  • ![image-20210626112237738](https://cdn.jsdelivr.net/gh/alexanderliu-creator/cloudimg/img/20210626112237.png)
    

  • CPU利用率急剧下降的原因：

    • 进程增多，缺页率足够大
      

    • 抖动或颠簸
      

  • 抖动原因：
    • 物理块分配太少
    • 置换算法不当
    • 全局置换使抖动传播

• 工作集模型：计算一个局部的宽度（帧数）
  

  • 工作集定义：最近的时间内访问的页面集合。
    

• 抖动预防：
  

  • 局部置换
    

  • 工作集的算法
    

  • L = S准则：
    

    • 缺页之间的平均时间 = 平均缺页服务时间
      

    • 老师上课讲的，内存一直是100%，磁盘的灯一直在闪！
      

• 缺段中断：

  • 五个位：

    • 状态位
    • 访问位
    • 修改位
    • 外存地址
    • 增补位（分段是否允许拓展，如果增补，则另外选择辅存空间）

  • 指令执行中间得到服务，一条指令可能引起多次不同的缺段中断。

• 地址变换机构：

  • 

• 分段的共享和保护：

  • 共享段表：所有共享段表都占有一个表项
  • 
  • 共享进程计数：多一个共享就加一，下面的就是引用它的进程和在进程中的位置。
  • 分配：
    • 第一个请求的，系统为其分配物理区，将共享段调入该区
    • 该区的始址填入段表的相应项中
    • count置为1
    • 又有调用，又增加一个表项
    • 天上相应的信息，count = count + 1
  • 回收：
    • 撤出表项
    • 取消调用者的有关记录
    • count -= 1
    • 如果count == 0：回收物理内存，删除共享段表中的表项。
  • 分段保护：
    • 越界检查
    • 存取控制
    • 环保护机构（低编号的环有高优先权）：
      • 可以访问相同环和低权环的数据
      • 可以调用相同环和高权环中的服务
      • 说白了：内环为外环提供服务，就像操作系统与应用程序一样。应用程序只能调用操作系统，不能查看操作系统的代码嗷！！！
    • 保护机构：
      • 传输控制
      • 数据访问

第五章（输入输出系统）：

• 设备管理的对象：I/O设备

• 设备管理的主要功能：

  • 缓冲区
  • 设备分配
  • 设备处理
  • 虚拟设备以及设备独立性等

• I/O系统的基本功能：

  1) 设备分配

  2) 设备映射

  3) 设备驱动

  4) I/O缓冲区的管理

• 四层结构：

  • 用户层软件
  • 设备独立性软件
  • 设备驱动程序
  • 中断处理程序
  • 设备硬件（不算在四层结构里面）

• 相关系统体系结构：

  • 应用程序（用户程序，操作系统和其他组件等）
  • API
  • 设备管理
  • 驱动程序
  • 硬件抽象

• 设备控制器：

  • 数据信号线
  • 状态信号线
  • 控制信号线

• 设备控制器的意义：

  • 设备控制器是CPU和I/O之间的接口，接收CPU的命令，控制I/O设备工作。
  • 职责是控制一个或多个I/O设备，实现I/O设备与计算机之间的数据交换

• 设备控制器的组成部分：

  • 设备控制器与处理机的接口
  • 设备控制器与设备的接口
  • I/O逻辑

• 通道的结构：

• 通道类型：
  • 字节多路通道：
    • 字节交叉方式工作
    • 时间片轮转共享主通道
  • 数组选择通道：
    • 上面不适用于高速外设，这里的数组选择通道可以连接多台高速设备。
    • 通道是被独占的
  • 数组多路通道：
    • 数组传输数据，能被多台设备占用，高速传送数据。
• 通道不足的瓶颈问题：增加设备到主机间的通路，不增加通道。（充分利用已有资源！！！）
• 总线系统的缺点：总线瓶颈，CPU瓶颈
• 问题：

• 中断处理程序：

  • 中断是I/O最低的一层，整个I/O的基础
  • 中断和陷入：
    • 中断：外中断，CPU对于I/O设备的响应
    • 陷入：CPU内部事件引起的，如出错等
  • 中断向量表：
    • 中断号 + 中断处理程序地址
  • 中断处理层的主要工作：
    • 进程上下文切换
    • 中断信号源测试
    • 读取设备状态和修改进程状态

• 设备驱动程序：

  • 设备处理程序，主要任务是启动指定设备
  • 功能：
    • 接收命令和参数，将抽象要求转换为具体要求
    • 检查请求合法性，状态等
    • 发出I/O指令
    • 及时响应控制器或通道发来的中断请求
  • 对I/O设备的控制方式：
    • 轮询可编程的I/O方式
    • 中断的可编程I/O方式
    • 直接存储器访问方式(DMA)
    • I/O通道方式
  • 特点：
    • 命令转换
    • 驱动程序与设备控制器和I/O紧密相关
    • 控制方式
    • 汇编语言书写
    • 驱动程序允许可重入
  • 轮询：
    • 忙等，CPU不断测试（CPU中无中断机构）
  • 中断驱动I/O控制方式：
    • 提高了系统的资源利用率和吞吐量
    • 但是每完成一个字/字节的传输，设备都应该向CPU请求一次中断
  • DMA：
    • 传输的基本单位是数据块
    • 直接输入内存
    • 仅仅在开始或者结束的时候，才需要CPU的干预
    • 四类寄存器：
      • CR：接收I/O命令或设备的状态
      • MAR：起始地址
      • DR：暂存设备到内存，或内存到设备的数据
      • DC：传送的字节数
  • I/O通道：
    • DMA的发展，实现CPU , 通道和I/O设备三者并行操作。
    • 

• I/O控制方式总结：

• 设备无关的I/O软件

  • 设备独立性：
    • 应用程序独立于具体使用的物理设备。
    • 设备独立性引入的概念：
      • 逻辑设备
      • 物理设备
  • 目标：
    • 实现一般设备都需要的I/O功能，并向用户层软件提供一个统一的接口。
  • 主要功能：
    • 执行设备的公有操作
    • 向用户层（或文件夹）软件提供统一的接口

• 设备控制表（DCT）：

  • 

• 控制器控制表，通道控制表，系统设备表：

  • 设备分配算法：
    • FCFS
    • 优先级高者先服务
    • 独占型设备的分配：
      • 申请，使用，释放
    • 共享设备和之前学的类似，不需要申请，但是实质上只能由一个进程使用，包含一个隐含的申请和释放命令，进程完全是有可能进入阻塞等待状态的嗷！！！

• 逻辑设备名到物理设备名映射的实现：

  • 整个系统一张LUT，不允许不同进程有相同设备名，仅适用于单用户系统
  • 不同用户登录进程PCB中有自己的LUT，用户将自己的LUT指向系统的设备表，方便嗷！！！
  • 

• SPOOLING技术：在快速辅存中建立I/O缓冲器，缓存速度不匹配的数据。

• 输入井和输出井本质上是在高速缓存中开辟的两个固定的存储区。

• SPOOLING系统组成：

  • 输入井和输出井。
  • 输入和输出缓冲区
  • 输入和输出进程

• 

• 

• 

注意！！！SPOOLing技术实际上实现了设备的虚拟性！！！

• 缓冲区管理：

  • 缓和CPU和I/O设备速度不匹配的矛盾

• 提高CPU和I/O设备的并行性

• 缓冲对换：

  • 双缓冲区组织方式

• 多缓冲区组织方式：

  • 每个缓冲区的大小相同
  • 缓冲区类型：
    • 空缓冲区Empty
    • 已装满缓冲区Full
    • 现行工作缓冲区Current

• 磁盘系统及磁盘调度：

  • 数据的组织和形式：
    • 存储面
    • 磁道
    • 柱面
    • 扇区
  • 
  • 
  • 读取数据的时间组成：
    • 寻道时间
    • 旋转延迟
    • 数据传输时间
  • 主要技术指标：
    • 平均寻道时间
    • 转速
  • 磁盘调度：
    • FCFS
    • SSTF
    • SCAN
    • CSCAN
  • FCFS：
    • 算法公平，简单
  • SSTF：
    • 寻找的磁道与当前磁道最近，某个进程有可能会饥饿
  • SCAN：
    • 优先考虑磁头移动方向，到头了返回来，电梯调度。
  • CSCAN：
    • 磁头单向移动。
    • 最小磁道号紧接着最大磁道号构成循环。
  • 上面四种算法做一下题目嗷！！！
  • 磁臂粘着
  • N-Scan：
    • 磁盘请求队列分成若干个长度为N的子队列，按照FCFS算法依次处理这些子队列。对于每个子队列，使用SCAN算法。
    • N很大的时候，和SCAN没啥区别，N=1的时候，退化为FCFS。
  • FSCAN：
    • N-Scan的简化
    • 当前请求队列按照SCAN处理，新来的请求放入另外一个等待请求的请求队列。所有新请求推迟到下一次扫描的时候处理。

• 例题：

第六章（文件系统）：

• 文件系统功能：
  • 管理文件的存储空间
  • 管理文件目录
  • 完成文件的读写
  • 实现文件的共享保护
• 文件系统的定义：操作系统中各类文件，管理文件的软件，以及管理文件所涉及到的数据结构等信息的集合。
• 结构：

• 文件，记录和数据项：

  • 基本数据项：描述一个对象的某种属性的字符集，最小逻辑数据单位，称为数据元素或字段。（属性）
  • 组合数据项：若干个基本数据组成的，组项
  • 记录：一组相关数据项的集合，描述一个对象在某方面的属性。
  • 文件：具有文件名的一组相关元素的集合。有结构的文件中，文件由若干个相关记录构成。无结构文件被看作是一个字符流。（文件是最大的数据单位，描述了一个对象集）

• 文件的属性：

  • 文件类型
  • 文件长度
  • 物理位置
  • 建立时间

• 文件分类：

  • 系统文件
  • 用户文件
  • 库文件

• 数据形式分类：

  • 源文件
  • 目标文件
  • 可执行文件

• 组织形式：

  • 普通
  • 目录
  • 特殊文件

• 文件系统模型：

  • 文件系统接口

  ---

  • 对于对象操纵和管理的软件集合

  ---

  • 对象及其属性

• 对象的操纵和管理的软件集合：

  • 文件存储空间的管理
  • 文件目录的管理
  • 逻辑地址转换为物理地址的机制
  • 文件读和写的管理
  • 文件的共享和保护等功能

• 文件系统的接口：

  • 命令接口：作为用户和文件系统交互的接口，键盘输入命令。
  • 程序接口：用户和程序的接口，程序通过系统调用取得文件系统的服务。

• 文件的结构：

  • 逻辑结构：
    • 若干记录构成
  • 物理结构：
    • 若干数据块构成

• 存储空间的管理：

  • 外存分配方法：
    • 连续分配
    • 链接分配
    • 索引分配
  • 连续分配：
    • 定义了一段线性地址，顺序存储到物理邻接的数据块中。
    • 每个文件建立一个表项，记录第一个块儿和长度。
    • 连续文件，yyds。
    • 紧凑解决利用率，顺序读快，效率高，不利用文件尺寸的动态增长。
  • 链接分配：
    • 文件装在离散的盘块中，链接指针连起来。
    • 隐式链接：每个盘块儿指向下一个，文件目录含有第一个和最后一个
      • 顺序ok , 随机访问效率低。以多个盘块儿作为一个（簇）来分配，会方便很多嗷！！！
      • 改进有限orz。
    • 显示链接：链接文件各个物理块的指针，显式放在一张链接表中嗷！！！
      • 磁盘仅有一张文件分配表（FAT）
      • 属于某一文件的第一个盘块号，作为文件地址被填入相应的FCB中。
      • 表在内存中，找的快嗷，减少访问磁盘的次数。
  • 索引分配：
    • 链接的问题：
      • 不能高效的直接存取（FAT中查找盘块号）
      • 两万多个扇区，两万的表，占用空间大嗷！
    • 单级索引分配：
      • 分配一个索引块（表），专门存所有的盘块儿号，索引块本质上式一个含有许多盘块号的数组。
      • 文件的建立 -> 目录项中填上该索引块的指针
      • 消除外部碎片。花费较多外存空间，大文件太小，小文件太大。
    • 两级索引：
      • 专门分配一级和两级索引块。
      • 
    • 混合索引：
      • inode结点！！！
      • 

• 文件存储空间管理方法：

  • 空闲分区表：
    • 为所有空闲区建立空闲表
    • 适用于可变大小分区的连续分配
    • 对换分区一般都采用连续分配方式嗷！！！
  • 空闲链表法：
    • 空闲盘区拉成一条链：
      • 空闲盘块链：分配和回收非常简单
      • 空闲盘区链：与内存动态分区匹配类似嗷，一般采用首次适应算法。
    • 适合于非连续存储文件
  • 位示图：
    • 把盘块放入二维表中
    • 1的话占用，0的话空闲。
    • 
    • 
    • 一样的，可能保存空间很大
  • 成组链接法：
    • 

• 文件目录：

  • 实现 “按名存取”
  • 提高检索速度
  • 文件共享
  • 允许文件重名

• 文件控制块内容：

  • 基本信息：文件名，文件类型等
  • 地址信息：卷，起始地址，文件长度
  • 访问控制信息：文件所有者，访问信息
  • 使用信息：创建时间，创建者，当前状态，最近修改和访问时间

• 目录项的组织方式：

  • FCB存储全部内容
  • 存储部分目录信息，文件名，索引指针等，其余保存在inode节点中。打开文件的时候，将索引节点从磁盘读到内存中。

• 目录结构：

  • 单级目录结构：
    • 所有用户的全部文件目录保存在一张表中，目录项占用一个表项。
    • 基本功能 - 按名字存取
    • 缺点：速度慢，重名打咩，文件共享打咩
  • 两级目录结构：
    • 主文件目录 - 用户 - 每个用户的文件目录
    • 解决重名，提高效率
    • 文件共享比较快乐了嗷！！！
    • 问题：不便于用户文件的逻辑分类，进一步解决重名，共享，检索效率等问题。
  • 多级目录结构：
    • 树形结构

• 目录查询技术：

  • 线性检索法
  • 
  • Hash查找

• 文件共享与访问控制：

  • 有效控制：
    • 同时存取：同时读可以，同时读并且修改不行
    • 存取权限：
      • 执行
      • 读
      • 追加
      • 更新
      • 更改权限
      • 删除
  • 共享实现：
    • 目录项中设置一个链接指针，指向共享文件的目录项。共享的用户数为1的时候，才能删除共享文件。
    • 利用共享索引节点实现文件共享，文件目录中只设置文件名和指向相应索引结点的指针。
      • 这个共享结点有一个owner，还有一个count
    • 利用符号链实现文件共享。（系统创建LINK类型的新文件，新文件中只包含被创建文件的路径名 -> 符号链接）
    • URL实现文件共享

• 例题：

补充（Shell编程）：

• shell的两大功能：

  • 命令解释器
  • 程序设计语言

• 任何用户的所有键盘命令，都是由shell来解释执行。一个用户单独启动一个shell来解释执行他发出的操作系统命令。

• 输入重定向和管道：

  • > 覆盖
  • >> 追加

• cat默认的输入来自stdin，Ctrl+d结束键盘输入

• 

• 

• 管道：

  • 前一个命令的结果作为后一个命令的输入

• 普通命令行的行尾加上&符号，就表示该命令在后台执行。

• echo：

  • 回显后面输入的东西
  • “”中的$变量符会被替换为对应的变量
  • \b\b这种东西很有用嗷！：
    • 
  • echo -n

• 系统变量：

  • $0，shell的名字
  • $1 - $9 ， 第一个到第九个参数
  • $# , 命令行上的参数个数
  • #* , 命令行上的所有参数
  • #@ , 双引号引用命令行所有参数
  • $$ , 当前进程的进程号
  • #? , 上一条命令的退出状态
  • #! , 最后一个后台进程的进程号

• 系统变量只能引用不能够修改嗷！！！

• echo中，单引号禁止变量替换。

• 反撇号代表命令的执行结果，例如：b = date

• 

• 内部命令：

  • cd
  • pwd
  • time（当前shell运行命令所花费的时间）
  • ps（获得进程状态信息）
  • sleep
  • kill

• 常用功能命令：

  • read var
  • read后的变量小于读取的参数的话，一一对应，剩下来多的给最后一个嗷！！！
  • read用于读取命令行的输入并保存到其后面的变量中。
  • expr , 用于简单的整数运算。

• 程序例子：

• 结构性语句：

  • if … then … fi

• 程序例子：

• if … then … else … fi

• exit退出脚本程序

• -d表示对于目录的判断，-f表示对于文件的判断

• 测试语句test：

  • 字符串：
    • test “answer” = “yes”
  • 整数：
    • test $num -eq 18
  • 文件属性：
    • test -d tmp

• 多路分支：case … esac

  • ;; 以单独的双分号结束，退出case语句
  • 
  • 

• 循环：

  • 
  • 

• while：

  • 
  • 循环中变量加一：
    • i = expr $i + 1

• continue

• break

• until … do … done

• 一个例子：

• awk很有意思哇！！！

• 示例：

题目嗷！！！