Planet X

《操作系统》复习笔记

整理:@刘国栋

第二章 进程与线程

2.1 进程

  • 不管是只有一个CPU的计算机还是多CPU的计算机,都支持(伪)并发操作的能力。
  • 进程是用于描述并行的一种概念模型。从概念上来说,每个进程拥有它自己的虚拟CPU
  • 一个进程就是一个正在执行的程序的实例。包括程序计数器、寄存器和变量的当前值。实际上只有一个物理程序计数器,所以在每个程序运行时,它的逻辑程序计数器被装入实际的程序计数器中。当该程序执行结束(或暂停执行)时,物理程序计数器被保存在内存中该进程的逻辑程序计数器中。
  • 在任何一个瞬间,一个CPU只能运行一个进程。
  • 进程的创建有4种主要方式:

    • 系统初始化
    • 正在运行的进程发出系统调用创建进程协助其工作
    • 用户请求(键入命令、点击图标)创建新的进程
    • 批处理作业的初始化

    在以上情况中,新进程都是由于一个已经存在的进程执行了一个创建进程的系统调用而创建的。

    在UNIX系统中,这个系统调用是fork。调用fork后,子进程和父进程拥有相同的存储映像、环境字符串和打开的文件。通常,子进程接着执行execute或类似的系统调用,以修改其存储映像并运行新的程序。

  • 在UNIX和Windows中,父进程和子进程有各自不同的地址空间。

  • 进程的终止

    • 正常退出(自愿)。
    • 出错退出(自愿)。
    • 严重错误(非自愿)。
    • 被其他进程杀死(非自愿)。
  • 进程的状态

    • 运行态(该时刻此进程实际占用CPU)。
    • 就绪态(可运行,但因为其他进程在运行而暂时停止)。
    • 阻塞态(除非某种外部事件发生,否则进程不能运行)。
  • 进程的实现: 操作系统维护着一张表格(一个结构数组),即进程表(进程表存放在内核中)。每个进程占用一个进程表项,叫做进程控制块(PCB)。该表项包含了进程状态的重要信息,例如程序计数器堆栈指针内存分配情况所打开文件的状态账号和调度信息等。

  • 中断发生后的操作系统底层工作步骤(上下文切换过程)

    1. 中断硬件程序计数器寄存器等压入堆栈
    2. 硬件从中断向量装入新的程序计数器。(中断向量是靠近内存底部区域的,和每一I/O类关联的一个位置。它包含中断服务程序的入口地址。)
    3. 汇编语言过程保存寄存器值
    4. 汇编语言过程设置新的堆栈
    5. C语言中断服务例程运行。
    6. 调度程序决定下一个将运行的进程。
    7. C过程返回至汇编代码(为新的进程装入寄存器值以及内存映射)。
    8. 汇编语言过程开始运行新的当前进程。
  • 多道程序设计模型

    假设一个进程等待I/O操作的时间与其停留在内存中的时间比为$p$,当内存中同时有$n$个进程时,则CPU空转概率为(所有$n$个进程都在等待I/O)$p^n$,CPU利用率 = $1 - p^n$。

2.2 线程

  • 为什么需要线程?
    • 在许多应用中同时发生着多种活动。我们需要并行实体具有共享同一个地址空间和所有可用数据的能力
    • 线程比进程更轻量级
    • 若多个线程都是CPU密集型的,那么并不能获得性能上的增强,但是如果存在着大量的计算和大量的I/O处理,拥有多个线程允许这些活动彼此重叠进行,从而会加快应用程序的速度。
  • 进程用于把资源集中到一起,而线程则是在CPU上被调度执行的实体。
  • 多个进程来自不同用户,彼此之间可能存在敌意。但同一个进程的多个线程来自同一个用户,属于彼此合作的关系,为了完成某一任务而共同工作。
  • 一个进程中所有线程共享地址空间全局变量打开文件子进程即将发生的报警信号与信号处理程序账号信息。每个线程自己的内容有程序计数器寄存器堆栈状态
    • 通常每个线程会调用不同的过程,有各自不同的执行历史,所以线程需要自己的堆栈。每个线程的堆栈有一帧,供各个被调用但还没有从中返回的过程使用。在该帧中存放了相应的局部变量和返回地址。
  • 线程的状态:跟进程一样,运行、阻塞、就绪或终止 。
  • 跟进程不同的是,线程库无法利用时钟中断强制线程让出CPU。所以有一个常见的线程调用thread_yield,它允许线程主动放弃CPU从而让另一个线程运行。
  • IEEE在POXIS(Portable Operating System Interface of UNIX)中定义了线程的标准,叫做Pthread
  • 用户空间的线程VS内核中的线程
    • 在用户空间实现线程
      • 内核对线程一无所知,依然按照单线程进程来处理。
      • 在用户空间管理线程时,每个线程有其专用的线程表。跟进程表类似,记录每个线程的属性。
      • 优点:可以在不支持线程的操作系统上实现
      • 优点:切换线程时,只需要在线程表中保存该线程的寄存器,并把新线程的保存值重新装入机器的寄存器中,切换堆栈指针和程序计数器。由于线程表不在内核中,保存线程状态和调度程序都是本地过程,不需要陷入内核,不需要上下文切换,也不需要对内存的高速缓存进行刷新,所以线程调度非常快捷
      • 优点:允许每个进程有自己定制的调度算法。
      • 优点:用户级线程有较好的扩展型,因为内核空间的内核线程需要固定表格空间和堆栈空间,如果内核线程太大就会出现问题。
      • 缺点:如何实现阻塞系统调用。(?)
      • 缺点:页面故障问题。因为内核不知道线程的存在,如果一个线程触发Page Fault,则整个进程会被阻塞。
      • 缺点:如果一个线程开始运行,那么该进程中的其他线程就不能运行。
    • 在内核中实现线程
      • 在内核中存放线程表。当一个线程希望创建或者撤销一个已有线程时,它进行一个系统调用,对内核中的线程表更新完成线程创建或撤销工作。
      • 所有能阻塞线程的调用都以系统调用的形式实现,与用户线程相比,代价比较大。
      • 进行线程调度时,可以选择其他进程的线程,而用户级线程始终运行自己进程中的线程。
      • 缺点:速度慢!
    • 总的来说,用户级线程和内核级线程的差别在于性能。用户级线程的线程切换需要少量的机器指令,而内核级线程需要完整的上下文切换,修改内存映像,使高速缓存失效,这导致了若干数量级的延迟。另一方面,在使用内核级线程时,一旦线程阻塞在I/O上,不需要像在用户级线程中那样将整个进程挂起。
  • 弹出式线程:在消息到达时创建一个处理该消息的线程。由于这种线程相当新,创建很快。

2.3 进程间通信(IPC)

  • 竞争条件:两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序,称为竞争条件

  • 临界区:对共享内存进行访问的程序片段称作临界区

  • 互斥:以某种手段确保当一个进程在使用一个共享变量或文件时,其他进程不能做同样的操作。

  • 互斥的几种实现方案

    • 屏蔽中断

      • 把屏蔽中断的权利交给用户进程是十分不明智的。
      • 在多核CPU中,屏蔽一个CPU的中断不会阻止其他CPU干预第一个CPU所做的操作。
      • 用一个变量lock,0表示无锁,1表示加锁。
      • 仍然可能存在竞争条件。
    • 严格轮换法

      • 设置一个turn变量,一个进程退出临界区时,修改turn为另一个进程的ID。
      • 在一个进程比另一个慢很多的情况下,并不是一个好方法。可能出现这样的情况:0号进程把turn修改为1后,1号进程还在忙于非临界区操作,0号进程想再次进入时turn仍为1。
    • Peterson解法

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        #define FALSE 0
        #define TRUE 1
        #define N 2
        int turn;
        int interested[N];
        void enter_region(int process){
        int other;
        other = 1 - process;
        interested[process] = TRUE;
        turn = process;
        while(turn == process && interested[other] == TRUE);
        }
        void leave_region(){
        interested[process] = FALSE;
        }
    • TSL指令

      • 执行TSL(Test and Set Lock)指令的CPU会锁住内存总线,以禁止其他CPU在本指令结束之前访问内存

      • 1
        2
        3
        4
        5
        6
        7
        8
        9
        enter_region:
        TSL REGISTER, LOCK
        CMP REGISTER, #0
        JNE enter_region
        RET
        leave_region:
        MOVE LOCK, #0
        RET
    • XCHG指令

      • 与TSL类似
  • 睡眠和唤醒(sleep & wakeup):以上几种互斥的实现方式都有忙等待的特点。睡眠和唤醒机制可以避免忙等待。

  • 信号量:用一个整形变量来累计唤醒次数。up、down操作。

  • 互斥量:简化版的信号量,只有0和1.

  • 管程:任意时刻管程中只能有一个活跃进程。

  • 条件变量:当一个管程过程发现无法继续运行时(例如生产者发现缓冲区满),它会在某个条件变量上执行wait操作,该操作导致调用进程自身阻塞,并且还将另一个等在管程之外的进程调入管程。另一个进程,(例如消费者)可以执行signal唤醒正在睡眠的伙伴进程。

    • 条件变量不是计数器,也不能积累。如果向一个条件变量发送信号,但是该条件变量没有等待进程,则该信号会永远丢失。即,wait操作必须在signal之前。
  • sleep&wakeup VS wait&signal: sleep 和wakeup在这种情况下会失败:当一个进程想睡眠时,另一个进程视图去唤醒它。管程则不会发生这种情况,管程过程的自动互斥保证了这一点。

  • 消息传递(send & recieve)

    • 消息的编址
      • 为每个进程分配唯一的地址,让消息按进程的地址编址。
      • 引入新的数据结构,信箱(mailbox),对一定数量的消息进行缓冲。在使用信箱时,send和recieve的地址参数就是信箱的地址,而不是进程的地址。当一个进程试图向一个满的信箱发消息时,它将被挂起,直到信箱内有消息被取走。
      • 使用信箱的另一种极端方法:彻底取消缓冲。如果send在recieve之前,则send进程被阻塞,知道recieve发生。如果先执行recieve,则recieve进程被阻塞,直到send发生。
  • 屏障(barrier):在有些应用中划分了阶段,必须所有的进程都就绪才能进入下一个阶段。可以在每个阶段的结尾安装屏障。

2.4 调度

经常会有多个进程或线程同时竞争CPU,如果只有一个CPU可用,那么就必须选择下一个要运行的进程。在操作系统中完成选择工作的这一部分称为调度程序,使用的算法称为调度算法

  • 非抢占式调度算法:挑选一个进程,然后让该进程运行直至被阻塞,或者直到该进程自动释放CPU。这样做的结果是,在时钟中断发生时不会进行调度。

  • 抢占式调度算法:挑选一个进程,并且让该进程运行某个固定时段的最大值,如果在该时段结束时,进程仍在运行,它就被挂起,而调度程序挑选另一个进程运行(如果存在一个就绪进程)。进行抢占式调度,需要在时间间隔的末端发生时钟中断,以便把CPU控制返回给调度程序。

  • 调度算法分类

    • 对于批处理系统:非抢占式算法,或者对每个进程都有长时间周期的抢占式算法,通常是可以接受的。这种方式减少了进程的切换从而改善了性能。
    • 对于交互式用户环境:为了避免一个进程霸占CPU,抢占式必须的。
    • 对于实时系统:抢占有时是不需要的。因为进程了解它们可能会长时间得不到运行,所以通常很快完成格子的工作并阻塞。
  • 调度算法的目标

    • 所有系统
      • 公平:给每个进程公平的CPU份额
      • 策略强制执行:看到所宣布的策略执行
      • 平衡:保持系统所有部分都忙碌
    • 批处理系统
      • 吞吐量:每小时最大作业数
      • 周转时间:从提交到终止间的最小时间
      • CPU利用率:保持CPU始终忙碌
    • 交互式系统
      • 响应时间:快速响应请求
      • 均衡性:满足用户的期望
    • 实时系统
      • 满足截止时间:避免丢失数据
      • 可预测性:在多媒体系统中避免品质降低
  • 常用调度算法

    • 批处理系统

      • 先来先服务
      • 最短作业优先
      • 最短剩余时间优先
    • 交互式系统

      • 轮转制度
      • 优先级调度
      • 多级队列
      • 最短进程优先
      • 保证调度
      • 彩票调度
      • 公平分享调度
    • 实时系统

      分为硬实时软实时

      硬实时:必须满足绝对的截止时间。

      软实时:虽然不希望偶尔错过截止时间,但是可以容忍。

      在实时系统中,如果有$m$个周期事件,事件$i$以周期$P_i$发生,并需要$C_i$秒CPU时间处理一个事件,那么可以处理负载的条件是:$\sum_{i=1}^{m}\frac{C_i}{P_i}\leq1$, 满足这个条件的系统被称为可调度的

第三章 存储管理

  • 分层存储器体系 (Memory Hierarchy)
    • 高速缓存:快速、昂贵、易失性, MB级别
    • 内存:速度与价格适中,易失性,GB级别
    • 磁盘存储:低速、廉价、非易失性,TB级别
    • 可移动存储设备:DVD、USB等
  • 操作系统中管理分层存储器体系的部分称为存储管理器。它的任务是有效地管理内存,记录哪些内存时正在使用的,哪些是空闲的。在进程需要时为其分配内存,在进程使用后释放内存。

3.1 无存储器抽象

  • 存储器模型就是物理内存。所有程序都引用了绝对物理地址。操作系统可能位于ROM,也可能位于RAM中。

  • 在有些存储器组织方案中,设备驱动程序位于内存顶端的ROM中,而操作系统的其他部分则位于下面的RAM的底部。在ROM中的部分被称为BIOS(Basic Input Output System)。

  • 把物理地址暴露给进程会带来下面几个严重问题:

    • 如果用户程序可以寻址内存的每个字节,它们就可以很容易地破坏操作系统。
    • 所有程序都引用了绝对物理地址,在同时运行多个程序时,可能出现错误。

3.2 一种存储器抽象:地址空间

  • 地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间,这个地址空间独立于其他进程的地址空间。

  • 基址寄存器和界限寄存器

    • 实现地址空间的一种比较简单的方法是使用基址寄存器界限寄存器来实现一种比较简单的动态重定位。它所做的是简单地把每个进程的地址空间映射到物理内存的不同部分。
    • 当一个程序运行时,程序的起始物理地址装载到基址寄存器中,程序的长度装载到界限寄存器中。每次进程访问内存,CPU硬件会在把地址发送到内存总线前自动把基址值加到进程发出的地址值上。同时,它检查程序提供的地址是否超过界限寄存器里的值,如果访问超过了界限,会产生错误并中止访问。
    • 缺点:每次访存都需要进行加法和比较运算。比较可以做得很快,但加法由于进位传递时间的问题会比较慢。
  • 在实际的计算机中,内存不能够保存所有进程。处理内存超载有两种方法,最简单的策略是交换技术。另一种是虚拟内存技术。

  • 交换技术

    • 把一个进程调入内存,使该进程运行一段时间,然后把它存回磁盘。空闲进程存在磁盘上,所以它们不运行时不会占用内存。
    • 大部分进程在运行时都要增长,为了减少因内存区域不够而引起的进程交换和移动所产生的开销,可以在换入或移动进程时为它分配一些额外的内存。
  • 空闲空间管理

    • 使用位图:内存可能被划分为小到几个字或大到几千字节的分配单元。每个分配单元对应于位图中的一位,0表示空闲,1表示占用。
    • 使用链表:维护一个记录已分配内存段和空闲内存段的链表。其中链表的一个结点或者包含一个进程,或者是两个进程间的一个空闲区。链表中每一结点都包含以下域:空闲区、进程的指示标志、起始地址、长度和指向下一结点的指针。在链表中分配内存单元时,有首次适配、下次适配、最佳适配、最差适配等方法。如果为进程和空闲区维护各自独立的链表,那么这四个算法的速度都能得到提高。

3.3 虚拟内存

  • 交换技术无法解决的问题是软件的膨胀。运行的程序往往大到内存无法容纳。

  • 虚拟内存的基本思想是:每个程序拥有自己的地址空间,这个空间被分割成多个块,每一块称作一页或页面。每一页有连续的地址范围,这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

  • 由程序产生的地址称为虚拟地址,它们构成一个虚拟地址空间。虚拟地址不是直接被送到内存总线上,而是被送到内存管理单元(MMU),MMU把虚拟地址映射为物理内存地址。

  • 虚拟地址空间按照固定的大小划分成称为页面(page)的若干单元。在物理内存中对应的单元称为页框。页面和页框的大小通常是一样的。现在的系统常用页大小一般从512字节到64KB。RAM和磁盘之间的交换是以整个页面为单位进行的。

  • 内存对MMU一无所知,它看到的全是真实的物理地址。

  • 缺页中断(Page Fault):当程序访问一个未映射的页面,会触发缺页中断,CPU陷入操作系统。操作系统找到一个很少使用的页框并把它的内容写回磁盘,随后把需要访问的页面读到刚才回收的页框中,修改映射关系,然后重新启动引起陷阱的指令。

  • MMU 内部工作机制:例如,对于16位的虚拟地址,可以被分为4位的页号和12位的偏移量。4位的页号可以表示16个页面,12位的偏移可以为一页内全部4096个字节编址。可用页号作为页表的索引,以得出对应于该虚拟页的页框号。如果“在/不在”标记位是0,则引起操作系统陷阱,如果是1,则将在页表中查到的页框号复制到输出寄存器的高3位,再加上输入虚拟地址的低12位偏移量,这就构成了15位物理地址,输出寄存器的内容就被作为物理地址送到内存总线。因此:内存对MMU一无所知,它看到的全是真实的物理地址。

  • 页表:页表的目的是把虚拟页面映射为页框。从数学角度说,页表是一个函数,它的参数是虚拟页号,结果是物理页框号。

  • 页表项的结构

    ​ |\\\\\\\| 高速缓存禁止位 | 访问位 | 修改位 | 保护位 | “在/不在”位 | 页框号 |

    • 页表项的结构与机器密切相关,不同机器的页表项存储的信息大致相同。
    • 页框号:这是最重要的域,毕竟页映射的目的就是找到这个值。
    • “在/不在”位:表示该表项对应的虚拟页面现在是否在内存中。
    • “保护”位:指出一个页面允许什么类型的访问。最简单的形式只有一位,0表示读/写,1表示只读。更先进的方法是使用三位,分别对应是否启用读、写、执行。
    • 修改位:在写入一页时自动设置修改位,在操作系统重新分配页框时,这一位非常有用,如果一个页面已经被修改过(即它是“脏”的),那么必须把它写回磁盘。如果没有被修改过,直接丢弃即可。
    • 访问位:不管是读还是写,系统都会在该页面被访问时设置访问位。它的值被用来帮助操作系统在发生缺页中断时选择要淘汰的页面。
    • 高速缓存禁止位:对于那些映射到设备寄存器而不是常规内存的页面而言,这个特性是十分重要的。假如操作系统正在紧张地循环等待某个I/O设备对它刚刚的命令作出相应,保证硬件不断地从设备中读取数据而不是访问一个旧的被高速缓存的副本是十分重要的。
  • 转换检测缓冲区(Translation Lookaside Buffer, TLB):又称为相联存储器。是为了解决加速分页问题而设计的。(如果每次访存都要访问内存中的页表,则程序执行速度通常被CPU从内存中取指令和数据的速度所限制。)TLB是一个小型的硬件设备,将虚拟地址直接映射到物理地址,而不必再访问页表。它通常在MMU中,包含少量的表项,实际中很少超过64个。每个表项记录了一个页面的相关信息,包括虚拟页号页面的修改位、保护码和该页对应的物理页框。除了虚拟页号不在页表中,其他域跟页表中的域基本是意义对应的。另外还有一个域用来记录这个表项是否有效。

  • TLB工作机制:将一个虚拟地址放入MMU中进行转换时,硬件首先通过将该虚拟地址与TLB中所有表项并行地进行匹配,判断虚拟页面是否在其中。如果发现了一个有效的匹配并且要进行的操作不违反保护位,就将页框号直接从TLB中取出而不必再访问内存中的页表。当虚拟页号不在TLB中时,就会进行正常的页表查询,从TLB中淘汰一个表项,用新找到的页表项替代它。

  • 软件TLB管理:TLB表项被操作系统显示地装载,发生TLB访问失效时,不再由MMU到页表中查找并取出需要的页表项,而是生成一个TLB失效并将问题交给操作系统解决。

    • 软失效:当一个页面访问在内存中而不在TLB中时,将产生软失效,此时要做的就是更新一下TLB,不需要磁盘I/O。
    • 硬失效:页面本身不在TLB中,也不在内存中,此时需要一次磁盘读取以装入该页面。
  • 多级页表:解决虚拟地址空间过大的问题。引入多级页表可以避免把全部页表一直保存在内存中。索引顶级页表得到的表项中含有二级页表的地址或页框号。根据虚拟地址中二级页表的索引找到二级页表中对应的物理地址。

  • 倒排页表:在64位虚拟地址的分页系统中,光是页表的大小就已经远超内存大小。以前的方案不可行。倒排页表的设计时,在实际内存中,每一个页框有一个表项,而不是每一个虚拟页面有一个表项。虽然节省了空间,但查询起来很费时。

3.4 页面置换算法

  • 最优页面置换算法:在内存中的页面都用该页面首次被访问前所要执行的指令数作为标记。最优页面置换算法规定应该置换标记最大的页面。此算法不可能实现。

  • 最近未使用页面置换算法(Not Recently Used,NRU):利用了页表项的R位(访问位)和M位(修改位)。R位会定期地(比如在每次时钟中断时)被清零,以区分最近没有被访问的页面和被访问的页面。

    发生缺页中断时,操作系统会检查所有的页面并根据它们当前的R位和M位的值,分为4类:

    • 第0类:没有被访问,没有被修改。
    • 第1类:没有被访问,已经被修改。
    • 第2类:已经被访问,没有被修改。
    • 第3类:已经被访问,已经被修改。

    NRU算法每次从编号最小的非空类中随机选择一个页面淘汰之。

  • 先进先出页面置换算法(FIFO):由系统维护一个所有当前在内存中的页面的链表,最新进入的页面被放在表尾,最早进入的放在表头。发生缺页中断时,淘汰表头的页面并把新调入的页面加到表尾。

  • 第二次机会页面置换算法:FIFO可能会把经常使用的页面置换出去,为了避免这一问题,对该算法做一个简单的修改:检查最老页面的R位,如果R位是0,那么这个页面既老又没用,可以立刻被置换掉;如果是1,就把R位清零,把该页面放到表尾,就向刚装入一样,然后继续搜索。

  • 时钟页面置换算法:第二次机会置换算法需要经常在链表中移动页面,既降低了效率又不是很有必要。一个更好的办法是把页面保存在一个类似钟面的环形链中(其实就是环形链表),一个表指针指向最老的页面,发生缺页中断时,算法首先检查表指针直线的页面,如果R位是0就淘汰该页面,并把新的页面插入这个位置,如果是1就清除R位并把表指针前移一个位置。

  • 最近最少使用页面置换算法(Least Recently Used,LRU):对最优页面置换算法的很好的近似是基于这样的假设,在前面几条指令中频繁使用的页面很可能在后面的几条指令中被使用。LRU的思想是,在发生缺页中断时,置换未使用时间最长的页面。

    • 两种特殊硬件实现LRU的方法:
      • 用一个64位计数器,在每条指令执行完后加1,每个页表项必须有一个足够容纳这个计数器值的域,每次访问内存后,将计数器的值保存到被访问页面的页表项中。发生缺页中断时,所有页表项中计数器值最小的,就是最近最少使用页面。
      • 在一个有$n$个页框的机器中,维持一个初值为0的 $n\times n$ 的矩阵。当访问到页框 $k$ 时,硬件首先把 $k$ 行的位都置成1,再把 $k$ 列的位都置成0。在任何时刻,二进制数值最小的就是最近最少使用的。
    • 用软件模拟LRU:一种可行的方案是NFU(Not Frequrntly Used, 最不常用)算法。 该算法将每个页面与一个软件计数器相关联,计数器的初值为0。每次时钟中断时,由操作系统扫描内存中所有的页面,将每个页面的R位加到相应的计数器上。这个计数器大体跟踪了各个页面被访问的频繁程度,发生缺页中断时,置换计数器值最小的页面。
    • 老化算法:对NFU做一个小小的修改就能很好地模拟LRU,在R为被加进计数器之前先将计数器右移一位,将R位加到计数器最左端的位而不是最右端的位。
  • 工作集页面置换算法: 一个进程当前正在使用的页面集合称为它的工作集。在任意时刻 $t$ ,都存在一个集合,它包含所有最近 $k$ 次内存访问所访问过的页面。这个集合 $w(k,t)$ 就是工作集

    不少分页系统都会设法跟踪进程的工作集,以确保在进程运行以前,它的工作集就已在内存中了,从而大大减少缺页中断次数。在进程工作前预先装入其工作页面也称为预先调页。通过这些信息,可以直接推导出一个页面置换算法:当发生缺页中断时,淘汰一个不在工作集中的页面。

  • 工作集时钟(WSClock)页面置换算法:每次缺页中断时,首先检查指针指向的页面,如果R位为1,该页面在当前时钟滴答中就被使用过,不会被淘汰,把其R位置为0,指向下一个页面。如果R位为0:如果页面生存时间大于 $t$ 并且页面是干净的,它就不在工作集中,可以被替换。如果该页面被修改过,为了避免磁盘操作,指针继续向前走。如果指针经过一圈之后,还没有调度过写操作,说明所有的页面都在工作集中,随机置换一个页面。(?)

  • 总结

    | 算法 | 注释 |
    | :——————————-: | :——————————: |
    | 最优算法 | 不可实现,但可用作基准 |
    | NRU(最近未使用)算法 | LRU的很粗糙的近似 |
    | FIFO(先进先出)算法 | 可能抛弃重要页面 |
    | 第二次机会算法 | 比FIFO有很大改善 |
    | 时钟算法 | 现实的 |
    | LRU(最近最少使用)算法 | 很优秀,但很难实现 |
    | NFU(最不经常使用)算法 | LRU的相对粗略的近似 |
    | 老化算法 | 非常近似LRU的有效算法 |
    | 工作集算法 | 实现起来开销很大 |
    | 工作集时钟算法 | 好的有效算法 |

3.5 分页系统中的设计问题

  • 局部分配策略和全局分配策略
    • 局部算法:发生缺页中断时,仅淘汰相应进程的页面。可以有效地为每个进程分配固定的内存片段。
    • 全局算法:淘汰内存中生存时间最小的页面,不管它属于哪个进程。可以在可运行进程之间动态地分配页框。
  • 页面大小
    • 小页面的优点:减少内部碎片;减少内存中的没用程序。
    • 小页面的缺点:对于相同的程序,页面大小越小,需要的页面数量就越多,传输大小页面的时间基本一样,所以总时间就增多。同时,页面越小,页表就越大,进程切换上下文时需要装载的页表增大,所需时间增长。
    • 最优页面大小公式: $P = \sqrt{2se}$. 进程平均大小是 $s$ 个字节,每个页表项需要 $e$ 个字节。
  • 共享库
    • 传统的链接是指,在链接一个程序时,链接器会在库中寻找被调用了但是没有被定义的函数,如果找到了,则将它们加载到可执行二进制文件中。当链接器完成任务后,一个可执行二进制文件被写到磁盘,其中包括所需的全部函数。静态链接大量的库会浪费大量的磁盘空间,在装载这些程序时也会浪费大量的内存空间。
    • 因此,我们需要共享库(Windows中被称为DLL,动态链接库)。当一个程序和共享库链接时,链接器没有加载被调用的函数,而是加载了一小段能够在运行时绑定被调用函数的存根例程。依赖于系统和配置信息,共享库或者和程序一起被装载,或者在其所包含函数第一次被调用时被装载。如果其他程序已经装载了某个库,则不需要再次装载。
  • 内存映射文件:进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。在多数的实现中,在映射共享的页面时不会实际读入页面的内容,而是在访问页面时才会被每次一页地读入。如果两个进程映射了同一个文件,它们就可以通过共享内存来通信。

3.6 有关实现的问题

  • 操作系统要在下面四段时间里做与分页有关的工作:创建进程时,进程执行时,缺页中断时和进程终止时。
    • 创建进程时: 操作系统要确定程序和数据在初始时有多大,为它们创建一个页表。还要在内存中为页表分配空间并初始化。当进程被换出时,页表不需要驻留在内存中,但当进程运行时,它必须在内存中。另外,操作系统还要在磁盘交换区中分配空间,以便在一个进程换出时在磁盘上有放置此进程的空间。
    • 调度一个进程执行时:必须为新进程重置MMU,刷新TLB,以清除以前进程遗留的痕迹。新进程的页表必须成为当前页表,通常可以通过复制该页表或者把一个指向它的指针放进某个硬件寄存器来完成。
    • 发生缺页中断时,操作系统必须通过读硬件寄存器来确定是哪个虚拟地址造成了缺页中断。通过该信息,它要计算需要哪个页面,并在磁盘上对该页面进行定位。
    • 进程退出时,操作系统必须释放进程的页表、页面和在硬盘上所占用的空间。
  • 缺页中断处理
    • 硬件陷入内核,在堆栈中保存程序计数器。
    • 启动一个汇编代码例程保存通用寄存器和其他易失信息,以免系统被破坏。
    • 当操作系统发现一个缺页中断,尝试发现需要哪个虚拟页面。
    • 一旦知道了发生缺页中断的虚拟地址,检查这个地址是否有效,并检查存取与保护是否一致,如果不一致,向该进程发出一个信号或者杀掉该进程。如果地址有效,没有保护错误发生,则检查是否有空闲页框。
    • 如果选择的页框脏了,就写回磁盘,并发生一次上下文切换,挂起产生缺页中断的进程,让其他进程运行直至磁盘传输结束。
    • 一旦页面写回磁盘完成,操作系统装入新的页面。该页面被装入后,产生缺页中断的进程仍然被挂起,并且如果有其他可运行的用户进程,则选择另一个用户进程运行。
    • 当磁盘中断发生时,表明该页已经被装入,页表已经更新可以反映它的位置,页框也被标记为正常状态。
    • 恢复发生缺页中断指令以前的状态,程序计数器重新指向这条指令。
    • 调度引发缺页中断的进程,操作系统返回调用它的汇编语言例程。
    • 该例程恢复寄存器和其他状态信息,返回到用户控件执行。就好像缺页中断从未发生过一样。

3.7 分段

  • 我们可以设计多个互相独立的成为的地址空间。每个段由一个从0到最大的线性地址序列构成。不同的段长度一般都不同。段的长度在运行期间可以动态改变。
  • 每个段都是一个独立的地址空间,它们可以独立地增长或减小而不会影响到其他的段。
  • 要在这种分段或者二维的存储器中指示一个地址,程序必须提供两部分地址,一个段号和一个段内地址。
  • 一个段可能包括一个过程,一个数组,一组数值变量,但它一般不会同时包含多种不同类型的内容。
  • 分段的优点:
    • 简化了对长度经常变动的数据结构的管理
    • 简化了程序的编译和链接
    • 有助于在几个进程之间共享过程和数据

第四章 文件系统

4.1 文件

  • 文件是进程创建的信息逻辑单元。进程可以读取已经存在的文件,并在需要时建立新的文件。存储在文件中的信息必须是持久的。
  • 文件是一种抽象机制,它提供了一种在磁盘上保留信息而且方便以后读取的方法。
  • 文件扩展名:许多操作系统支持文件名用圆点隔开成为两部分。圆点后面的部分称为文件扩展名,文件扩展名通常表示文件的一些信息。在某些操作系统(UNIX)文件扩展名只是一种约定,操作系统并不强迫使用它。某些操作系统(Windows)对扩展名赋予含义。
  • 文件结构
    • 无结构字节序列:UNIX、Windows采用这种方法。把文件看成字节序列为操作系统提供了最大的灵活性。
    • 固定长度记录的序列
    • 记录树:每个记录并不具有同样的长度,而记录的固定位置上有一个“键”字段。这棵树按“键”字段进行排序,从而可以对特定“键”进行快速查找。
  • 文件类型
    • 普通文件
      • ASCII文件:由多行正文组成,每行用回车符/换行符结束。最大的优势是可以显示和打印,还可以用任何文本编辑器进行编辑。
      • 二进制文件:有一定内部结构,使用该文件的程序才了解这种结构。无法打印、显示。
      • 一种UNIX可执行二进制文件:文件头 | 正文 |数据 | 重定位位 | 符号表
    • 目录:管理文件系统结构的系统文件
    • 字符特殊文件:和输入/输出有关,用于I/O类设备
    • 块特殊文件:用于磁盘类设备
  • 文件存取:早期只能顺序存取,当用磁盘来存储文件时,可以随机存取,不按顺序读取,或者按照关键字而不是位置来记录。
  • 文件属性(attribute):与文件相关的信息,如创建日期、文件大小等。又被称为元数据(metadata)
  • 文件操作(P148)

4.2 目录

  • 文件系统提供目录文件夹用于记录文件,在很多系统中,目录本身也是文件。
  • 一级目录系统:只有一个根目录。用于简单的嵌入式装置。
  • 层次目录系统:目录树
  • 路径名
    • 绝对路径名:由从根目录到文件的路径组成。UNIX的路径分隔符是“/”,Windows是“\”。不管采用哪种分隔符,如果路径名第一个字符是分隔符,那么就是绝对路径。
    • 相对路径名:用户可以指定一个目录作为当前的工作目录,这时所有的不从根目录开始的路径名都是相对于工作目录的。
    • “.”指当前目录, “..”指父目录。
  • 目录操作(P152)
  • 硬连接和软连接
    • 硬连接:link指令允许在多个目录中出现同一个文件。这个系统调用指定一个存在的文件和一个路径名,并建立从该文件到路径名所指名字的连接。增加了文件i-node的计数器的计数。
    • 软连接:符号连接,所建立的文件名并没有真的指向相应的文件,而是指向了命名另一个文件的小文件。在对符号文件进行读或写操作的时候,系统会自动把该操作转换为对源文件的操作,但删除链接文件时,系统仅仅删除链接文件,而不删除源文件本身。符号链接的优点是能跨越磁盘的界限,甚至可以命名远程计算机上的文件。

4.3 文件系统的实现

  • 文件系统布局

    • 文件系统存放在磁盘上。多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。磁盘的0号分区称为主引导记录(Master Boot Record),用来引导计算机。

    • 在MBR的结尾是分区表,该表给出了每个分区的起始和结束地址。表中的一个分区被标记为活动分区。

    • 计算机被引导时,BIOS读入并执行MBR。

    • MBR确定活动分区,读入该分区的第一个块,称为引导块(boot block)。

    • 引导块中的程序将装载该分区的操作系统(每个分区都有引导块,即使不含有操作系统)。

    • 对于每一个磁盘分区,一般会有这样的布局:

      ​ | 引导块 | 超级块 | 空闲空间管理 | i节点 | 根目录 | 文件和目录 |

    • 超级块包含文件系统所有的关键参数,超级块中的典型信息包括:确定文件系统类型用的魔数、文件系统中数据块的数量以及其他重要管理信息。

  • 文件的实现

    • 连续分配:把每个文件作为一连串连续数据块存储在磁盘上。
      • 优点:实现简单;读操作性能好。
      • 缺点:浪费磁盘空间,磁盘会变得零碎。
    • 链表分配:为每个文件构造磁盘块链表。每个块的第一个字作为指向下一块的指针,块的其他部分存放数据。
      • 优点:充分利用磁盘块,不会因为磁盘碎片而浪费磁盘空间。
      • 缺点:随机读取性能差;由于指针占去了一些空间,每个磁盘块存储数据的字节数不再是2的整数次幂,怪异的大小降低了系统的运行效率。
    • 在内存中采用表的链表分配:在内存中存放一个文件分配表(File Allocation Table,FAT),把上述方法中每个磁盘块的指针取出,放在文件分配表中。
      • 优点:改进了链表分配的不足,整个块都可以存放数据。整个链表都在内存中,使得随机存取也更容易,不需要任何的磁盘引用。
      • 缺点:必须把整个表都存放在内存中。对于大磁盘不太实用。
    • i节点:给每个文件赋予一个称为i节点的数据结构,其中列出了文件属性和文件块的磁盘地址。
      • 优点:相对于在内存中采用表的方式,这种机制的优势在于,只有在对应文件打开时,其i节点才在内存中。总的占用空间更小。
  • 目录的实现

    • 目录系统的主要功能是把ASCII文件名映射成定位文件数据所需的信息。
    • 一种简单的方法是把文件属性直接存放在目录项中。
    • 对于采用i节点的系统,可以把文件属性放在i节点而不是目录项中,这种情况下的目录项只有文件名和i节点号。
    • 处理长度可变文件名的方法:使目录项自身都有固定长度,而将文件名放在目录后面的堆中。
  • 共享文件

    • 方案一:共享的磁盘块不列入目录,而是列入i节点,目录指向i节点。(?)
      • 想要删除文件时,系统只能知道该文件目前被多少个目录使用,但是却不能找到指向该文件的全部目录项并删除它们。
    • 方案二:符号链接
      • 不存在上述问题。因为符号链接只是用了路径名,没有指向i节点的指针。
      • 但符号链接需要额外的开销。
  • 日志结构文件系统

    • Log-structured File System, LFS
    • 产生原因:CPU运行速度越来越快,RAM内存容量变得很大,同时磁盘高速缓存也迅速地增加,进而,不需要磁盘访问操作,就有可能满足直接来自文件系统高速缓存的很大一部分读请求。更糟糕的是,在大多数文件系统中,写操作往往都是零碎的,极其没有效率。
    • 基本思想:将整个磁盘结构化为一个日志。每隔一段时间,或是有特殊需要时,被缓冲在内存中的所有未决的写操作都被放到一个单独的段中,作为日志末尾的一个邻接段写入磁盘。
    • 清理线程:周期地扫描日志进行磁盘压缩。
  • 日志文件系统

    • 保存一个用于记录系统下一步要做什么的日志。这样当系统在完成它们即将完成的任务前崩溃时,重新启动后可以 通过查看日志获取崩溃前计划完成的任务。
  • 虚拟文件系统

    • 绝大多数UNIX操作系统都使用虚拟文件系统概念尝试将多种文件系统统一成一个有序的框架。关键的思想就是抽象出所有文件系统都共有的部分,并且将这部分代码放在单独的一层,该层调用底层的实际文件系统来具体管理数据。

4.4 文件系统的管理和优化

  • 磁盘空间管理
    • 块大小:太大会浪费大量的磁盘空间,太小会导致大多数文件跨越多个块,增加了寻道时间、旋转延迟。
    • 记录空闲块
      • 采用磁盘块链表
      • 采用位图
  • 文件系统备份:合理的做法是只备份特定目录及其下的全部文件,而不是备份整个文件系统。
  • 文件系统的一致性
  • 文件系统性能
    • 高速缓存:高速缓存里有许多块,常用方法是将设备和磁盘地址进行散列操作,然后在散列表中查找结果。具有相同散列值的块在同一个链表中连接在一起。
    • 块提前读:适用于顺序读取的文件。
    • 减少磁盘臂移动

第五章 输入/输出

5.1 I/O硬件原理

  • I/O设备大致可以分为:块设备字符设备
    • 块设备把信息存储在固定大小的块中,每个块有自己的地址。块设备的基本特征是每个块都能独立于其他块而读写。例如硬盘、CD-ROM、USB盘。
    • 字符设备以字符为单位发送或接收一个字符流,而不考虑任何块结构。字符设备是不可寻址的,也没有任何的寻道操作。例如打印机、网络接口、鼠标、实验用的老鼠以及大多数与磁盘不同的设备。
  • I/O设备一般由机械部件和电子部件两部分组成。机械部件是设备本身,电子部件被称作设备控制器
  • 每个控制器有几个寄存器用来与CPU进行通信。通过这些寄存器,操作系统可以命令设备发送数据、接收数据、开启或关闭,或者执行其他操作。
  • 许多设备还有一个操作系统可以读写的数据缓冲区
  • CPU与I/O设备的通信
    • 特殊I/O指令:每个控制寄存器被分配一个I/O端口号,使用特殊的I/O指令结合端口号进行访问。
    • 内存映射I/O:将所有控制寄存器映射到内存空间,每个控制寄存器被分配唯一的内存地址。
      • 优点:不需要特殊的保护机制来组织用户进程执行I/O操作;可以引用内存的每一条指令,也可以引用控制寄存器。
      • 缺点:对一个设备控制寄存器进行高速缓存可能是灾难性的。硬件必须针对每个页面具备选择性禁用高速缓存的能力。
  • DMA(直接存储器存取)
    • 只有硬件具有DMA控制器时系统才能使用DMA。无论DMA控制器在物理上处于什么地方,它都能够独立于CPU而访问系统总线。
    • DMA控制器包含多个可以被CPU读写的寄存器,其中包括内存地址寄存器、字节计数寄存器、一个或多个控制寄存器。控制寄存器指定要使用的I/O端口、传送方向、传送单位以及在一次突发传送中要传送的字节数。
    • 许多总线能够以两种模式操作:每次一字模式和块模式
      • 每次一字模式:DMA控制器请求传送一个字并且得到这个字。如果CPU也想使用总线,它必须等待。这被称为”周期窃取“
      • 块模式:DMA控制器通知设备获得总线,发起一连串的传送,然后释放总线。这一操作被称为”突发模式“
      • 飞越模式:DMA控制器通知设备控制器直接将数据传送到主存。
  • 中断
    • 当一个I/O设备完成交给它的工作时,它就产生一个中断。它通过在分配给它的一条总线信号线上置起信号而产生中断。该中断信号被主板上的中断控制器芯片检测到,由中断控制器芯片进行下一步的操作。
    • 如果有另一个中断正在处理,或者另一个设备在总线上具有更高优先级的一条中断请求线同时发出中断请求,该设备的中断将暂时不被理睬。
    • 为了处理中断,中断控制器在地址线上放置一个数字表明哪个设备需要关注,并置起一个中断CPU的信号。中断信号导致CPU停止当前正在做的工作并开始处理中断。地址线上的数字被用作指向一个称为中断向量的表格的索引,以便读取一个新的程序计数器。这一程序计数器指向相应的中断服务过程的开始。
    • 精确中断:将机器留在一个明确状态的中断称为精确中断
      • PC(程序计数器)保存在一个已知的地方
      • PC所指向的指令之前的所有指令已经完全执行
      • PC所指向的指令之后的所有指令都没有执行
      • PC所指向的指令的执行状态是已知的

5.2 I/O软件原理

  • I/O软件的目标
    • 设备独立性:应该能够编写出这样的程序:它可以访问任意I/O设备而无需事先指定设备。
    • 统一命名:一个文件或一个设备的名字应该是一个简单的字符串或一个整数,它不依赖于设备。
    • 错误处理:错误应该在尽可能接近硬件的层面得到处理。高层软件甚至不知道错误的存在。
    • 同步和异步传输:大多数物理I/O是异步的,CPU启动传输后便转去做其他工作,直到中断发生。
  • 程序控制I/O:CPU要不断地查询设备以了解设备的状态,这一行为经常称为轮询忙等待。程序控制I/O十分简单但有缺点,即直到全部I/O完成之前要占用CPU的全部时间。
  • 中断驱动I/O:允许CPU在等待I/O设备变成就绪状态的同时做某些其他的事情。例如,在等待打印机打印完某个字符串时,CPU调用调度程序,运行其他某个进程。当字符串打印完成,打印机产生一个中断,这一中断将停止当前的进程并保存其状态。
  • 使用DMA的I/O:中断驱动的缺点是中断次数太多,浪费了一定数量的CPU时间。这一解决方案是使用DMA直接给IO设备提供数据。

5.3 I/O软件层次

  • I/O软件通常组织为四个层次:(由上至下)

    • 用户空间I/O软件
      • 尽管大部分I/O软件都在操作系统内部,但是仍然有一小部分在用户空间,包括与用户程序连接在一起的库,甚至完全运行于内核之外的程序。系统调用一般由库过程实现。
      • 假脱机:多道程序设计系统中处理独占I/O设备的一种方法。是一种虚拟设备技术,使各作业在执行期间只使用虚拟的设备,而不直接使用物理的独占设备。使独占的设备变成可共享的设备,使得设备的利用率和系统效率都能得到提高。
      • 守护进程:创建一个特殊进程,称为守护进程,以及一个特殊目录,称为假脱机目录。该进程是允许使用某I/O设备(例如打印机)特殊文件的唯一进程,通过保护特殊文件防止用户直接使用,可以解决某些进程不必要地长期空占打印机的问题。
    • 与设备无关的操作系统I/O软件
      • 设备驱动程序的统一接口:使得添加新设备变得容易。
        • 对于每一种设备类型,操作系统定义一组驱动程序必须支持的函数。
        • 给I/O设备命名。与设备无关的软件负责把符号化的设备名映射到适当的驱动程序上。
        • 设备保护。防止无权访问设备的用户访问设备。
      • 缓冲
      • 错误报告:许多错误是设备特定的并且必须由适当的驱动程序来处理,但是错误处理的框架是设备无关的。
      • 分配和释放专用设备:某些设备,在任意给定的时刻只能由一个进程使用。
      • 与设备无关的块大小:不同的磁盘可能具有不同的扇区大小。应该由与设备无关的软件来隐藏这一事实并且向高层提供一个统一的块大小。
    • 设备驱动程序
      • 连接到计算机上的I/O设备都需要某些设备特定的代码来对其进行控制。这样的代码称为设备驱动程序。一般由设备制造商编写并随同设备一起交付。
      • 为了访问设备的硬件,设备驱动程序通常必须是操作系统内核的一部分。
    • 中断处理程序
      • 中断处理程序先做它要做的全部工作以便对中断进行处理。然后,它将启动中断的驱动程序解除阻塞。

5.4 盘

  • 磁盘磁盘被组织成柱面,每一个柱面包含若干磁道,磁道数与垂直堆叠的磁头个数相同。磁道又被分为若干扇区
  • 磁盘驱动器本身包含一个微控制器,微控制器承担了大量的工作并允许实际的控制器发出高级命令。
  • RAID:Redundant Array of Inexpensive Disk。
    • 0级RAID:将RAID模拟的虚拟单个磁盘划分成条带。每个条带具有k个扇区。将数据分布到多个驱动器上。能够实现并行操作。
    • 1级RAID:将0级RAID复制一份。执行写操作时,每个条带都被写了两次。执行读操作时可以使用其中任意一个副本。具有容错性,恢复很简单。
    • 2级RAID:0级和1级操作的是扇区,2级RAID工作在字(或字节)的基础上。将虚拟磁盘的每个字节分割成4位的半字节对,然后对每个半字节对加入一个汉明码从而形成7位的字。要求各个驱动器的旋转必须同步。
    • 3级RAID:是2级RAID的简化版本,为每个数据字计算一个奇偶校验位并且写入一个奇偶驱动器中。要求驱动器精确同步。
    • 4级RAID:再次使用条带,而不是具有奇偶校验的单个字。与0级RAID类似,但是将条带对条带的奇偶条带写到一个额外的磁盘上。如果一个驱动器崩溃,则损失的字节可以通过读出整个驱动器组从奇偶驱动器中心计算出来。缺点是,对于微小的更新性能很差。
    • 5级RAID:在所有的驱动器上均匀地分布奇偶校验位。
  • 读写磁盘的时间主要由三个因素决定:寻道时间、旋转延迟、实际数据传输时间。对于大多数磁盘来说,寻道时间占主导地位。
  • 磁盘臂调度算法
    • 先来先服务
    • 最短寻道优先:总是处理与磁头距离最近(根据柱面的相对距离来看)的请求以使寻道时间最小化。
      • 缺点: 大部分时间,磁头将停留在磁盘的中部区域,两端极端区域的请求将不得不等待。
    • 电梯算法:保持在一个方向上移动,直到在那个方向上没有请求为止,然后改变方向。
  • 磁盘控制器中存在高速缓存。许多磁盘控制器总是读出多个扇区并对其进行高速缓存。
  • 错误处理:对于坏块存在两种一般的处理方法:
    • 在控制器中对它们进行处理
      • 出厂前对坏扇区进行替换。将备用扇区重映射或者将所有扇区向上移动一个扇区。
    • 在操作系统中对它们进行处理

5.5 时钟

  • 时钟又称为定时器。对于任何多道程序设计系统的操作都是至关重要的。时钟负责维护时间,并且防止一个进程垄断CPU。

  • 时钟由三个部件组成:晶体振荡器、计数器、存储寄存器。把石英晶体切割并安装在一定的压力下,就可以产生非常精确的周期性信号。它给计算机的各种电路提供同步信号。该信号被送至计数器,使其递减计数至0。当计数器变为0时,产生一个CPU中断。

  • 可编程时钟通常具有几种操作模式:

    • 一次完成模式(one-shot mode):产生中断后,时钟停止工作,直到软件再一次显式地启动它。
    • 方波模式(square-wave mode):当计数器为0并且产生中断后,存储寄存器的值自动复制到计数器中,并且整个过程无限期地再次重复下去。这些周期性的中断称为时钟滴答(clock tick)。

第六章 死锁

6.1 资源

  • 资源:需要排他性使用的对象称为资源。资源可以是硬件设备或是一组信息。
  • 可抢占资源:可以从拥有它的进程中抢占而不会产生任何副作用。
  • 不可抢占资源:在不引起相关的计算失败的情况下,无法把它从占有它的进程处抢占过来。
  • 死锁不可抢占资源有关。

6.2 死锁概述

  • 定义:如果一个进程集合中的每个进程都在等待只能由该进程集合中其他进程才能引发的事件,那么,该进程集合就是死锁的。
  • 资源死锁的条件
    • 互斥条件:每个资源要么已经分配给了一个进程,要么就是可用的。
    • 占有和等待条件:已经得到了某个资源的进程可以再请求新的资源。
    • 不可抢占条件:已经分配给一个进程的资源不能强制性地被强占,它只能被占有它的进程显式地释放。
    • 环路等待条件:死锁发生时,系统中一定有由两个或两个以上的进程组成的一条环路,该环路中的每个进程都在等待着下一个进程所占有的资源。
  • 有四种处理死锁的策略:
    • 鸵鸟算法。忽略该问题。
    • 检测死锁并恢复。
    • 仔细对资源进行分配,动态避免死锁。
    • 通过破坏引起死锁的四个必要条件之一,防止死锁的产生。

6.3 鸵鸟算法

6.4 死锁检测和死锁恢复

  • 每种类型只有一个资源的情况:构造一张资源分配图。如果图中包含一个或一个以上的环,那么死锁就存在。

  • 使用检测有向图环路的算法。

  • 每种类型多个资源的情况:基于矩阵的算法来检测从$P_1$到$P_n$这$n$个进程中的死锁。

    • 现有资源向量E:$E_i$代表资源$i$的总数。

    • 可用资源向量A:$A_i$代表当前可供使用的资源数。

    • 当前分配矩阵C:$C_{ij}$代表进程$i$持有的资源$j$的数量。

    • 请求矩阵R:$R_{ij}$代表进程$i$所需要的资源$j$的数量。

    • 恒等式: $\sum_{i=1}^{n} + A_j = E_j$

    • 检测算法:

      1)寻找一个没有标记的进程$P_i$,对于它而言R矩阵的第i行向量小于或等于A

      2)如果找到这样的一个进程,那么将C矩阵第i行加到A中,标记该进程,转到第1步

      3)如果没有这样的进程,算法终止。

  • 从死锁中恢复

    • 利用抢占恢复:将某个资源从它的当前所有者那里转移到另一个进程。许多情况下,需要人工干预。
    • 利用回滚恢复:周期性地对进程进行检查点检查。将持有所需要资源的进程回滚到某一个时间点,在此时间点它还没有取得该资源,这时我们把该资源分配给一个死锁进程。
    • 通过杀死进程恢复:杀死环中的一个进程;选一个环外的进程作为牺牲品以释放该进程的资源。

6.5 死锁避免

  • 资源轨迹图:沿着轨迹进入阴影交叉区域表示会发生死锁。

  • 安全状态:如果没有死锁发生,并且即使所有的进程突然请求对资源的最大需求,也仍然存在某种调度次序能够使得每一个进程运行完毕,则称该状态是安全的。

  • 反之,则是不安全状态。不安全状态不是死锁。

  • 单个资源的银行家算法

    • 银行家向一群客户分别承诺了一定的贷款额度。算法要做的是判断对请求的满足是否会导致进入不安全状态。如果是,就拒绝请求,如果满足请求后系统仍然处在安全状态,就予以分配。
    • 为了看状态是否安全,银行家看他是否有足够的资源满足某一个客户,如果可以,那么这笔投资被认为是能够收回的,并且接着检查最接近最大限额的一个客户,以此类推。如果所有的投资都可以被收回,那么该状态是安全的。
  • 多个资源的银行家算法

    • 与检测死锁时用到的矩阵类似。

    • 两个矩阵:已分配资源E和仍需要的资源R。

    • 算法:

      1)查找R中是否有一行,其没有被满足的资源数均小于或等于A。如果不存在这样的行,那么系统存在死锁。

      2)假如找到这样的一行,将该进程标记为终止,并将其资源加到A上。

      3)重复以上步骤,直到所有进程都被标记为终止。

  • 银行家算法虽然有意义但缺乏实用价值。很少有进程在运行前就知道其所需要的资源最大值,而且进程数也不是固定的。

6.6 死锁预防

  • 破坏互斥条件:允许某些资源被分配给多个进程。例如假脱机打印机技术,可以允许多个进程同时产生输出,但真正使用物理打印机的是打印机的守护进程。
  • 破坏占有和等待条件
    • 禁止已持有资源的进程再等待其他资源。可以在开始执行前请求所需的全部资源,如果所需的全部资源可用,那么就将它们分配给这个进程。
    • 另一种不同方案是,当一个进程请求资源时,先暂时释放其当前占用的所有资源,然后再尝试一次获得全部资源。
  • 破坏不可抢占条件:虚拟化的方式使得不可抢占设备变得”可抢占“。
  • 破坏环路等待条件:将资源统一编号,进程可以在任何时刻提出资源请求,但是所有的请求必须按照资源编号的顺序(升序)提出。

6.7 其他问题

  • 两阶段加锁:在第一阶段,进程试图对所有所需的记录进行加锁,一次锁一个记录。如果第一阶段加锁成功,就开始第二阶段,做具体的工作。如果第一阶段需要的记录已经被加锁,就释放该进程已经加锁的记录,并重新开始第一阶段。
  • 通信死锁:并没有占有资源。
    • 可以通过超时来解决通信死锁。
  • 活锁:没有发生死锁(没有进程阻塞),但是从现象上看好像死锁发生了,这就是活锁
  • 饥饿:某些进程永远得不到服务,虽然并没有发生死锁。

补充内容

程序内存空间

  • 堆栈段
    • 为函数内部的局部变量提供存储空间。
    • 进行函数调用时,存储“过程活动记录”。
    • 用作暂时存储区。如计算一个很长的算术表达式时,可以将部分计算结果压入堆栈。
    • 栈区(stack):由编译器自动分配释放 ,存放函数的参数值、局部变量的值等。其操作方式类似于数据结构中的栈。
    • 堆区(heap):由程序员分配释放(malloc / free), 若程序员不释放,程序结束时可能由操作系统回收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表。
  • 数据段(静态存储段):包括BSS段(Block Started by Symbol)
    • BSS段存储未初始化或初始化为0的全局变量、静态变量,具体体现为一个占位符,并不给该段的数据分配空间,只是记录数据所需空间的大小。
    • 数据段存储经过初始化的全局和静态变量。
  • 代码段
    • 又称为文本段。存储可执行文件的指令;也有可能包含一些只读的常数变量,例如字符串常量等。
    • .rodata段:存放只读数据,比如printf语句中的格式字符串和开关语句的跳转表。也就是你所说的常量区。例如,全局作用域中的 const int ival = 10,ival存放在.rodata段;再如,函数局部作用域中的printf(“Hello world %d\n”, c);语句中的格式字符串”Hello world %d\n”,也存放在.rodata段。

调度算法

  • 平均周转时间:计算每个任务结束的时间。
  • 平均等待时间:计算每个任务开始的时间。
  • 轮转法的时间片一般设置为 20 - 30ms,是一个比较适中的范围。

信号量

  • 在Dijkstra的信号量算法中,P是down,V是up。

二级页表

  • 引入二级页表后,实际上只需要四个页表:顶级页表、正文段、数据段和堆栈段。