一、操作系统简介

  1. 功能

    1. 对上/用户角度:控制软件

      • 管理应用程序
      • 为应用程序提供服务:声卡、显卡
      • 杀死应用程序
    2. 对下:资源管理

      • cpu、内存

      • 管理外设、分配资源

  2. 操作系统位于硬件之上、应用程序之下

  3. 操作系统的界面属于外壳shell,主要研究内核kernel

  4. 操作系统内部组件包括

    • cpu调度器
    • 物理内存管理
    • 虚拟内存管理
    • 文件系统管理
    • 中断处理与设备驱动
  5. 特征

    • 并发:同时存在多个运行的程序
    • 共享:应用程序“同时”访问内存、cpu
    • 虚拟:多道程序设计技术
    • 异步:程序执行走走停停
  6. 实例

    1. UNIX家族
    2. Linux家族
      • redhat、ubuntu
      • 移动终端、服务器大多数是linux
    3. Windows家族
  7. 结构

    • 微内核
    • 外核
    • 虚拟机

二、启动

  • OS起始存放在硬盘DISK

  • 基本I/O处理系统BIOS先检测各种外设,加载bootloader

  • Bootloader加载OS进内存,让cpu可以执行操作系统

三、中断、异常和系统调用

  1. 定义

    • 系统调用(来源于应用程序)
      应用程序主动向操作系统发出服务请求
    • 异常(来源于不良的应用程序)
      非法指令或者其他坏的处理状态(如:内存出错)
    • 中断(来源于外设)
      来自不同的硬件设备的计时器和网络的中断
  2. 处理时间

    • 中断:异步
    • 异常:同步
    • 系统调用:异步或同步
  3. 响应

    • 中断:持续,对用户应用程序是透明的
    • 异常:杀死或者重新执行意想不到的应用程序指令
    • 系统调用:等待和持续
  4. 中断处理机制

    • 硬件
      1. 设置中断标记[CPU初始化]
      2. 将内部、外部事件设置中断标记
      3. 中断事件的ID
    • 软件
      1. 保存当前处理状态
      2. 中断服务程序处理
      3. 清除中断标记
      4. 恢复之前保存的处理状态
  5. 异常处理机制:异常编号

    1. 保存现场
    2. 异常处理
    3. 杀死产生了异常的程序
    4. 重新执行异常指令
    5. 恢复现场
  6. 系统调用

    • Win32 API用于 Windows
    • POSIX API用于POSIX-based systems
      (包括UNIX,LINUX,Mac OSX的所有版本)
    • Java API 用于JAVA虚拟机(JVM)
  7. 跨越操作系统边界的开销

    • 在执行时间上的开销超过程序调用
    • 开销
      • 建立中断/异常/系统调用号与对应服务
        例程映射关系的初始化开销
      • 建立内核堆栈
      • 验证参数
      • 内核态映射到用户态的地址空间
        更新页面映射权限
      • 内核态独立地址空间
        TLB

四、内存

4.1计算机体系结构

  • CPU:程序执行控制

  • 内存:存放代码和数据

  • 设备:硬盘、键盘、鼠标等外设

cpu——>缓存(速度快、容量小)——>主存

4.2地址空间和地址生成

  1. 地址空间定义
    • 物理地址空间:硬件支持的地址空间
    • 逻辑地址空间:一个运行的程序所拥有的内存范围
  2. 逻辑地址生成
    • C语言:编译、汇编、链接、载入(程序重定位,经过这步程序从磁盘到内存中)
    • 编译:将基于符号的地址变为逻辑地址
    • 操作系统:逻辑地址、物理地址之间的映射
  3. 物理地址生成
    • cpu
      • 运算器需要在逻辑地址的内存内容
      • 内存管理单元MMU寻找在逻辑地址和物理地址之间的映射
      • 控制器从总线发送在物理地址的内存内容的请求
    • 内存
      • 内存发送物理地址内存的内容给CPU
    • 操作系统
      • 建立逻辑地址和物理地址之间的映射

4.3连续内存分配

  1. 内存碎片问题

    • 空闲内存不能被利用
    • 外部碎片
    • 内部碎片
  2. 分区的动态分配

    1. 什么时候需要内存分配
      • 当一个程序准许运行在内存中时,分配一个连续的区间
      • 分配一个连续的内存区间给运行的程序以访问数据
    2. 分配策略
      • 首次适配
      • 最优适配
      • 最差适配
  3. 碎片整理

    • 压缩式碎片整理:把运行程序在内存中移动
    • 交换式碎片整理:主存——>磁盘(虚拟内存)

4.4非连续内存分配

  1. 分段

    • 作用:更好的分离和共享

    • 实现:逻辑地址空间分散到多个物理地址空间

    • 分段寻址方案——段访问机制

      • 段号、段内偏移

      • 操作系统设置段表

  2. 分页

    • 实现
      • 划分物理内存至固定大小的帧Frame
      • 划分逻辑地址空间至相同大小的页Page
    • 帧Frame
      • 帧号、帧内偏移
      • 可以得出物理地址
    • 页page
      • 页号、页内偏移
      • 可以得出逻辑地址
    • 页寻址方案——页寻址机制
      • 页号、页表基址
      • 操作系统建立页表
      • 页表保存了逻辑地址–物理地址之间的映射关系
      • CPU——>逻辑地址——>页表——>物理地址——>物理内存空间
  3. 页表

    1. 页表结构
      • 每个运行的程序都有一个页表
    2. 地址转换的实例
    3. TLB
      • 关联内存实现、具备快速访问性能,缓存及其访问的页帧转换表项、节省空间
      • 如果TLB命中,物理页号可以很快被获取
      • 未命中,对应的表项被更新到TLB中
    4. 二级页表
      • pageNumber分为两块p1、p2
      • 节省空间、开销大、时间换空间
    5. 多级页表
    6. 反向页表
      • 基于页寄存器的方案
      • 基于关联内存的方案
      • 基于哈希查找的方案

五、虚拟内存

5.1起因

内存相对于寄存器速度慢,所以内存和寄存器之间有cache

硬盘比内存容量大,但是速度慢

磁带比硬盘容量还大

计算机系统中,尤其是多道程序运行下内存不够用

  • 手动的覆盖
  • 自动地交换
  • 自动的虚拟存储技术

5.2覆盖技术

  1. 目标

    较小的可用内存中运行较大的程序。常用于多道程序系统,与分区存储管理配合使用

  2. 原理

    • 程序划分为独立程序模块
    • 共享内存、分时执行
    • 常用功能常驻内存、不常用功能放于外存
  3. 缺点:覆盖模块从外存装入内存,实际上是以时间延长换取空间节省

5.3交换技术

  1. 目标

    多道程序在内存中时,让正在运行的程序或需要运行的程序获得更多的内存资源

  2. 方法

    • 暂时不能运行的程序送到外存
  3. 存在的问题

    • 交换时机的确定:只当内存空间不够或者有不够的危险时
    • 交换区的大小:足够存放进程的所有内存映像的拷贝;能对这些内存映像直接存取
    • 程序换入时的重定位:动态地址映射
  4. 覆盖发生在一个程序里,程序员需要手动指定逻辑关系;交换发生在程序之间,由操作系统内部完成,不需要程序员设置

5.4虚存技术

  1. 目标
    • 覆盖技术做的更好:由操作系统自动完成
    • 交换技术做的更好:只对进程的部分内容在内存和外存之间进行交换
  2. 程序的局部性原理
    • 时间局部性:连续两次访问集中在一个较短时期
    • 空间局部性:访问的数据在较近的区域
  3. 基本概念
    • 可以在页式或段式内存管理的基础上实现
      • 需要执行的部分页面或者段装入到内存
      • 执行过程中,将尚未在内存但是须执行的程序调入到内存
      • 内存中暂时不使用的页面或段保存在外存
  4. 基本特征
    • 大的用户空间:物理内存和外存相结合
    • 部分交换:部分虚拟地址空间进行的
    • 不连续性:物理内存分配的不连续,虚拟地址空间使用的不连续
  5. 实现——虚拟页式内存管理
    • 页表
      • 完成逻辑页到物理页帧的映射
    • 虚拟页式存储管理技术
      • 在页式存储管理的基础上增加请求调页和页面置换功能
      • 运行过程中程序或者要访问的数据不在内存中,则向系统发出缺页中断请求,系统在处理这个中断时,将外存中相应页面调入内存,使得程序继续运行
    • 页表表项
      • 驻留位:表示该页是在内存还是外存
      • 保护位:表示允许对该页做何种类型的访问
      • 修改位:该页在内存中是否被修改过(决定是否把它的内容写回外存)
      • 访问位:该页面被访问过则设置此位(用于页面置换算法)
    • 缺页中断
    • 后备存储
      • 一个虚拟地址空间的页面可以被映射到一个文件(在二级存储中)的某个位置
      • 代码段:映射到可执行二进制文件
      • 动态加载的共享库程序段:映射到动态调用的库文件
      • 其他段:可能被映射到交换文件
    • 虚拟内存性能

5.5页面置换算法

  1. 功能

    当缺页中断发生,需要调入新的页面而内存已满时,选择内存中哪个物理页面被置换

  2. 目标

    尽可能地减少页面的换进换出次数(即缺页中断的次数)

  3. 页面锁定

  4. 最优页面置换算法(局部页面置换算法1)

    1. 基本思路
      • 距离下一次访问等待时间最长的逻辑页面作为置换的页面
    2. 理想情况,可作为其他算法的性能评价的依据
  5. 先进先出算法FIFO(局部页面置换算法2)

    1. 基本思路
      • 选择在内存中驻留时间最长的页面并淘汰之
      • 当发生一个缺页中断时,把链首页面淘汰出去,把新的页面添加到链表的末尾
    2. 性能较差,并且有belady现象0
  6. 最近最久未使用算法LRU(局部页面置换算法3)

    1. 基本思路
      • 选择最久未使用的那个页面,并淘汰之
    2. 最优页面置换算法的近似,基于程序的局部性原理
    3. LRU算法需要记录各个页面使用时间的先后顺序,开销比较大
      • 实现方法
        1. 系统维护一个页面链表
        2. 设置一个活动页面栈
  7. 时钟页面置换算法(局部页面置换算法4)

    1. 基本思路
      • LRU的近似,FIFO的改进
      • 装入内存页面的页表项的访问位初始化为0,被访问置为1;各个页面组织成环形链表,指针指向最老页面
  8. 二次机会法

    1. 修改clock算法,使它允许脏页总是在一次时钟头扫描中保留下来,同事使用脏位和使用位来指导置换

    2. Enhanced Clock algorithm

      used dirty used dirty
      0 0 —> replace page
      0 1 —> 0 0
      1 0 —> 0 0
      1 1 —> 0 1
  9. 最不常用算法Least Frequently Used ,LFU(局部页面置换算法5)

    1. 基本思路

      当一个缺页中断发生时,选择访问次数最少的那个页淘汰之

    2. 实现方法

      对每个页面设置一个访问计数器,每当一个页面被访问时,该页面的访问计数器加一。在发生缺页中断时,淘汰技术值最小的那个页面

    3. LRU和LFU的区别

      LRU考察的是多久未访问,时间越短越好;而LFU考察的是访问的次数或频度,访问次数越多越好

  10. Belady现象、LRU、FIFO、Clock的比较

    1. Belady现象

      • 现象

        在采用FIFO算法时,有时会出现分配的物理页面数增加,缺页率反而提高的异常现象

      • 原因

        FIFO算法的置换特征与进程访问内存的动态特征是矛盾的,与置换算法的目标是不一致的(即替换较少使用的页面),因此,被它置换出去的页面并不一定是进程不会访问的

      • LRU页面置换算法没有Belady现象

    2. LRU、FIFO、Clock的比较

      • LRU、FIFO本质上都是先进先出的思路
      • LRU时针对页面的最近访问时间来排序、开销大
      • FIFO是针对页面进入内存的时间来排序、开销小
      • 如果一个页面进入内存后没有被访问,那么它的最近访问时间就是它进入内存的时间。即LRU退化为FIFO