1. 概述

操作系统的概念

操作系统，控制和管理整个计算机系统的硬件和软件资源，并合理的组织调度计算机的工作和资源的分配。

操作系统的特征

  1. 并发，指两个或多个时间在同一时间间隔内发生（并行指同时发生），在多道程序环境下，一段时间内宏观上有多个程序在同时执行，单处理器环境下只能有一个程序执行，故在微观上这些程序是在分时的交替进行。在操作系统中，引入进程的目的是使程序并发执行。

  2. 共享，指系统中的资源可供内存中多个并发执行的进程共同使用。共享有两种方式：

    • 互斥共享，某些资源在同一时间内只允许一个进程访问该资源。
    • 同时访问，一些资源允许多个进程在宏观上同时访问。

    并发和共享是操作系统的两个最基本的特征，两者之间又是互为存在条件的：

    • 共享是以并发为条件的，若程序不能并发执行，就不存在资源共享的问题。
    • 若系统不能对资源共享进行有效的管理，程序的并发执行也会受到影响，甚至无法运行。

  3. 虚拟，指把物理上的实体变为若干逻辑上的对应物。在操作系统中利用虚拟技术实现虚拟处理器、虚拟内存和虚拟外部设备。操作系统的虚拟技术分为：

    • 时分复用技术
    • 空分复用技术
  4. 异步，在多道程序环境下，允许多个程序并发执行，但是由于资源有限，进程的执行是以不可知的速度向前推进，这就是进程的异步性。

操作系统的功能

操作系统作为计算机资源的管理者

  1. 处理器管理，在多道程序环境下，处理器的分配和运行是以进程为基本单位，因此处理器管理可以看作是对进程的管理。进程管理的主要功能有进程控制、进程同步、进程通信、死锁处理、处理器调度等。
  2. 存储器管理，主要任务是为多道程序的运行提供良好的环境，方便用户使用以及提高内存的利用率。存储器管理的主要功能有内存分配、地址映射、内存保护与共享和内存扩充等。
  3. 文件管理，主要包括文件的存储空间管理、目录管理以及文件读写管理和保护等。
  4. 设备管理，主要任务是完成用户的I/O请求，方便用户使用各种设备以及提高设备的利用率。设备管理的主要功能有设备管理、设备分配、设备处理和虚拟设备等。

操作系统作为用户与计算机硬件系统的接口

  1. 命令接口，用户利用这些操作命令组织和控制作业的执行，主要有联机命令接口和脱机命令接口两种方式。
  2. 程序接口，由一组系统调用命令组成。系统调用指用户在程序中调用操作系统所提供的一些子功能。

操作系统的结构

  • 简单结构
  • 模块化结构
  • 分层式结构
  • 微内核结构

操作系统的发展与分类

  1. 手工操作阶段
  2. 脱机输入输出阶段
  3. 批处理阶段
    1. 单道批处理系统，自动行、顺序性、单道性。
    2. 多道批处理系统，宏观上并行，微观上串行。
  4. 分时操作系统阶段
    将处理器的运行时间分成时间片，按时间片轮流把处理器分配给各联机作业使用。其特点是同时性、交互性、独立性、及时性。
  5. 实时操作系统阶段
    实时性和可靠性。
  6. 网络操作系统和分布式计算机系统阶段
  7. 个人计算机操作系统阶段

操作系统的运行环境

1. 操作系统的运行机制

在计算机系统中CPU执行两种不同性质的程序，一种是操作系统内核程序，另一种使用户程序。操作系统在具体实现上划分为用户态和核心态以区分两种程序。操作系统内核包括四个方面的内容：

  • 时钟管理
    • 提供系统时间
    • 通过时钟中断的管理，实现进程的切换
  • 中断机制，目的是提高多道程序运行环境中CPU的利用率。现代操作系统使考中断驱动的软件。
  • 原语，不可再分割的操作。
  • 系统控制的数据结构及处理，如作业控制快、进程控制块、设备控制快、各类链表、消息队列、缓冲区、空闲区登记表、内存分配表等。为了实现有效的管理，系统需要一些基本的操作，常见的操作有如下三种：
    • 进程管理：进程状态管理、进程调度和分配、创建和撤掉进程控制块的队列维护等。
    • 存储器管理：存储器的空间分配和回收管理、内存信息保护程序、代码对换程序等。
    • 设备管理：缓冲区管理、设备分配和回收等。

2. 中断和异常的概念

  • 中断（Interruption）也称为外中断，指来自CPU执行指令以外的事件发生，如设备发出的I/O结束中断、时钟中断等。这一类中断与当前运行的程序无关，可细分为硬中断和软中断。硬中断是硬件产生的，软中断是软件产生的。
  • 异常（Exception）也称为内中断、陷入。指来自CPU执行指令内部的事件，如程序的非法操作码、地址越界、虚存系统的缺页以及专门的陷入指令等。对异常的处理一般要依赖当前程序的运行现场，而且异常不能被屏蔽，一旦出现异常立即处理。

2. 进程管理

进程的概念和特征

进程的概念

在多道程序环境下，允许多个程序并发执行，此时它们失去封闭性，具有间断性和不可再现的特征。为此引入进程的概念，以便更好的描述和控制程序的并发执行，实现操作系统的并发性和共享性。

进程控制块（PCB）用来描述进程的基本情况和运行状态，进而控制和管理进程。程序段】数据段和PCB三部分构成了进程实体。所谓创建进程，实质上是创建进程实体中的PCB；而撤销进程实质上是撤销进程实体的PCB。

引入进程实体的概念后，我们将进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

进程的特征

  • 动态性，进程最基本的特征。进程是程序的一次执行过程，有创建、活动、暂停、终止等过程，具有一定的生命周期，是动态产生、变化和消亡的。
  • 并发性，多个进程实体在一段时间内同时运行。
  • 独立性，进程是独立获得资源和接受调度的基本单位。
  • 异步性，由于进程间相互制约，进程的执行具有间断性，即进程按各自独立的、不可预知的速度向前推进。异步性会导致执行结果的不可再现性，因此操作系统中必须配置相应的进程同步机制。
  • 结构性，每个进程都配置一个PCB对其进行描述。从结构上看，进程实体是由程序段、数据段和PCB三部分组成。

进程的状态和转换

  1. 创建状态，进程正在被创建，还没进入就绪状态。
  2. 就绪状态，获得了除CPU外的所有所需资源，一旦得到处理器便可运行。
  3. 运行状态，程序获得CPU。
  4. 阻塞状态，进程正在等待某一事件而暂停运行，如等待资源不可用或等待输入输出完成。即使CPU空闲，该进程也不能运行。
  5. 结束状态，进程执行完成，释放资源。

进程控制

创建进程（创建原语）：

  • 为新进程分配一个进程标识号，并申请一个空白的PCB；
  • 为进程分配资源，如新进程的程序和数据及所需的空间等；
  • 初始化PCB，主要包括初始化标识信息、初始化处理器状态信息、初始化处理器控制信息等；
  • 如果进程就绪队列未满，就将新进程加入到就绪队列，等待调度运行。

终止进程（撤销原语）：

  • 根据进程标识符，检索PCB，从中读取进程的状态；
  • 若被终止的进程处于执行状态，立即终止该进程，将处理器资源分配给其他进程；
  • 若该进程还有子进程，则应将其所有子进程终止；
  • 将该进程所拥有的资源归还给父进程或者操作系统；
  • 将该进程PCB从队列中删除。

正在执行的进程，由于需要等待某些事件的发生，如请求资源失败等，由系统自动执行阻塞原语，将进程由运行状态变为阻塞状态。进程阻塞是进程自身的一种主动行为。

进程切换的过程：

  • 保存处理器上下文，包括程序计数器和其他寄存器；
  • 更新PCB；
  • 把进程的PCB移入相应的队列，如就绪队列、阻塞队列；
  • 选择另一个进程执行，并更新其PCB，更新内存管理的数据结构；
  • 恢复处理器的上下文。

进程的组织

进程是操作系统资源分配和独立运行的基本单位。

  • 进程控制块PCB，常驻内存，是进程存在的唯一标识

    主要包括：进程描述信息、进程控制和管理信息、资源分配清单和处理器相关信息。

  • 程序段，被调度到CPU执行的程序代码段。

  • 数据段，可以是进程对应的程序加工处理的原始数据，也可以是程序执行产生的中间结果。

进程的通信

  • 共享内存

    在通信的进程之间存在一块可以直接访问的共享空间，实现进程间的信息交换，需要使用同步互斥工具。

  • 消息传递

    在消息传递系统中，进程间的数据交换是以格式化的Message为单位的。

  • 管道通信

    是消息传递的一种特殊方式。

线程的概念和多线程模型

引入进程是为了多道程序设计并发执行，提高资源利用率和系统吞吐量。引入线程是为了减少程序在并发执行时所付出的时空开销，提高系统的并发性能。

线程是一个基本的CPU执行单元，也是程序流的最小单元，由线程ID、程序计数器、寄存器集合和堆栈组成。线程是进程中的一个实体，是系统独立调度和分配的基本单位。

线程与进程的比较：

  • 调度，线程是独立调度的基本单位，进程是资源分配的基本单位
  • 拥有资源，进程是拥有资源的基本单位，而线程不拥有系统资源
  • 并发性，不仅进程之间可以并发执行，线程之间也可以并发执行
  • 系统开销，线程开销小
  • 地址空间和其他资源，进程的地址空间相互独立，而同一进程的线程之间共享进程的资源
  • 通信，线程间通信可以直接读写进程数据段来进行通信

线程的实现方法：

  • 用户级线程
  • 内核级线程

多线程模型：

  • 多对一，将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成
  • 一对一
  • 多对多

调度的概念

处理器调度是对处理器进行分配，按照一定的算法在就绪队列中选择一个进程并将处理器分配给它运行，是操作系统设计的核心问题。

三级调度：

  • 作业调度，又称高级调度。主要任务是按一定的原则将外存上处于后备状态的作业中选择一个或几个分配内存、输出输出设备等必要资源，并建立相应进程。
  • 中级调度，又称内存调度。目的是提高内存利用率和系统吞吐率。将那些暂时不能运行的进程调至外存等待，把此时的进程状态称为挂起状态。当挂起状态的进程已具备运行条件并且内存有空闲时，由中级调度决定把哪些进程重新调入内存进入就绪队列。
  • 进程调度，又称低级调度。主要任务是按照某种方法和策略从就绪队列中选择一个进程分配处理器。

调度的时机、切换与过程

进程调度方式

  • 非剥夺调度，指当一个进程正在处理器上执行时，即使有一个更为紧急的进程进入就绪状态，仍然让正在执行的进程继续执行。

  • 剥夺调度，指当一个进程正在处理器上执行时，若有一个更为紧急的进程进入就绪状态，立即暂停正在执行的进程，将处理器分配给更为紧急的进程。

调度的基本准则

  • CPU利用率
  • 系统吞吐量，表示单位时间内CPU完成作业的数量
  • 周转时间，指从作业提交到作业完成所经历的时间
  • 等待时间，指进程等待处理器时间之和
  • 响应时间，指从用户提交请求到系统首次产生响应的时间

典型的调度算法

  • FIFS 先来先服务调度
  • SJF 短作业优先调度
  • 优先级调度
  • 高响应比优先调度
  • 时间片轮转调度
  • 多级反馈队列调度

进程同步的基本概念

多道程序设计环境下，进程并发执行，不同进程之间存在不同的制约关系。为了协调这些关系，达到资源共享和进程协作，避免进程间的冲突，引入进程同步的概念。

  • 临界资源，一次只允许一个进程访问的资源。访问临界资源的那段代码叫做临界区。
  • 同步
  • 互斥

实现临界区互斥的基本方法

硬件实现方法

  • 中断屏蔽
  • 硬件指令TestAndSet

信号量

经典同步问题

死锁的概念

死锁指多个进程因竞争资源而造成的僵局，若无外力作用，这些进程将无法继续向前推进。

死锁产生的必要条件：

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

死锁的处理策略

死锁避免

死锁检测和解除

死锁解除的方法：

  • 资源剥夺，挂起死锁进程并抢占其资源
  • 进程撤销，强制撤销一个或一部分进程并剥夺其资源
  • 进程回退，进程回退释放资源而不是被剥夺

进程与程序

死锁与饥饿

进程同步互斥的区别和联系

作业和进程的关系

3. 内存管理

内存管理的概念

内存管理的功能：

  • 内存空间的分配与回收，包括内存的分配和共享
  • 地址转换，逻辑地址转换成物理地址
  • 内存空间的扩充，利用虚拟技术或自动覆盖技术，从逻辑上扩充内存
  • 存储保护，保证各作业在各自的存储空间内运行，互不干扰

将用户程序编程在内存中执行的程序需要以下几个步骤：

  • 编译，由编译程序将用户源代码编译成若干目标模块
  • 链接，由链接程序将编译后形成的目标模块和所需库函数链接形成完整的装入模块
  • 装入，由装入程序将装入模块装入内存

程序链接的三种方式：

  • 静态链接，在程序运行之前，将各目标模块以及所需的库函数链接成完整的可执行程序
  • 装入时动态链接，将用户源程序编译后得到的目标模块，再装入内存，采用边装入变链接的方式
  • 运行时动态链接，对某些目标模块的链接，是在程序执行中需要该模块时才进行链接

装入模块装入内存的三种方式：

  • 绝对装入，在编译时，如果知道程序将驻留在内存中的某个位置，编译程序会产生绝对地址的目标代码
  • 可重定位装入，目标模块的起始地址为0，程序中的其他地址是相对于起始地址的（作业装入时需要足够的内存空间，否则不能装入）
  • 动态运行时装入（动态重定位），装入程序将装入模块装入内存后，没有立即将装入模块的相对地址转换成绝对地址，而是当程序真正执行时才进行地址转换

覆盖与交换

交换用于不同进程之间，覆盖用于同一进程

连续分配管理方式

主要包括单一连续分配、固定分区分配、动态分区分配

固定分区，优点是无外部碎片、可采用覆盖技术；缺点是有内部碎片、存储器利用率低

动态分区，缺点是有外部碎片

动态分区分配算法：

  • 首次适应
  • 最佳适应
  • 最坏适应

非连续分配管理方式

非连续分配方式允许一个程序分散装入不相邻的内存分区中，根据分区大小是否固定分为分页存储管理方式和分段存储管理方式。

分页存储管理方式又根据运行作业时是否把作业的所有页面全部装入内存才能运行区分为基本分页存储管理和请求分页存储管理。

固定分区产生内部碎片，动态分区产生外部碎片，对内存的利用率都比较低，故而引出分页思想：将内存空间划分为大小相等且固定的块，块作为主存的基本单位。每个进程也以块为单位进行划分，进程执行时，以块为单位申请主存中的块空间。

地址转换，将逻辑地址中的页号转换为内存中物理地址的页号，借助于页表，过程如下：

  • 地址变换机构自动将有效地址分为页号和页内偏移量，用页号去检索页表，执行前先检查是否越界。
  • 将页表始址与页号和页表项长度的乘积相加，得到该页表项在页表中的位置，从而得到物理块号。
  • 将有效地址的页内偏移量送入物理地址寄存器的块内地址字段。

分页管理从计算机的角度考虑，提高计算机性能和内存利用率，分页通过硬件机制实现，对用户完全透明

分段管理从程序员的角度考虑，以满足方便编程、信息保护和共享、动态增长以及动态链接等多方面的需要。

段表，每个进程都有一张逻辑空间与主存空间映射的段表，其中每一段表项对应进程的一个段，段表项记录该段在内存中的起始地址和段的长度。

虚拟内存的基本概念

虚拟内存基于局部性原理

虚拟内存有三种实现方式

  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

需要以下几个方面的硬件支持

  • 一定容量的内存和外存
  • 页表机制或段表机制
  • 中断机制，缺页中断
  • 地址转换机制，逻辑地址到物理地址的转换

请求分页管理方式

页面置换算法

  • OPT最佳置换算法
  • FIFO先进先出页面置换算法
  • LRU最近最久未使用置换算法
    • 寄存器支持
    • 特殊的栈结构
  • CLOCK置换算法

页面分配策略

抖动和工作集

抖动，指刚被换出的页面很快又要访问，需要重新调入，此时有需要再选一页调出。

工作集，指在某段时间间隔内，进程要访问的页面集合，为了防止出现抖动现象，需要选择合适的驻留集（工作集）大小。

请求分段管理方式

请求段页式管理方式

4. 文件管理

文件的概念

数据项，是文件系统中最低级的数据组织形式，有两种类型：

  • 基本数据项，用于描述对象的某种属性的一个值
  • 组合数据项，由多个基本数据项组成

记录，是一组相关的数据项集合，用于描述一个对象在某方面的属性

文件，指一组相关信息的集合，分为有结构文件和无结构文件两种，一般包含如下属性：

  • 名称
  • 标识符，表示文件系统内文件的唯一标识，对用户不可读的内部名称
  • 类型
  • 位置
  • 大小
  • 保护，文件的访问控制信息
  • 时间、日期和用户标识

所有文件的信息都保存在目录结构中，目录结构保存在外存上，文件信息在需要时调入内存。一般来说，目录条目包含文件名称及其唯一标识符，标识符定位其他属性的信息。

操作系统为文件管理提供的系统调用：

  • 创建文件，要在文件系统中找到空间并且在目录中为文件创建条目
  • 写文件，需要维护一个写位置的指针
  • 读文件
  • 文件重定位
  • 删除文件
  • 截断文件

文件的逻辑结构

  • 无结构文件，以字节为单位
  • 有结构文件
    • 顺序文件
    • 索引文件
    • 索引顺序表
    • 直接文件或散列文件

目录结构

文件控制块FCB是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项，FCB主要包含以下信息：

  • 基本信息：文件名、物理位置、逻辑结构、物理结构等
  • 存取控制信息：文件的存取权限等
  • 使用信息：文件建立时间、修改时间等

索引节点，检索目录文件过程中只用到文件名，仅当找到一个目录项时，才需要从该目录项中读出该文件的物理地址，因此有的系统采用文件名与文件信息分开的方法，文件描述信息单独形成一个称为索引节点的数据结构，简称i节点。文件目录中的每个目录项仅由文件名和指向该文件所对应的i节点的指针构成

文件共享

文件保护

文件系统层次结构

目录实现

文件实现

磁盘的结构

磁盘调度算法

磁盘的管理

5. 输入输出管理

IO设备

IO管理目标

IO管理功能

IO应用接口

设备控制器

IO控制方式

IO层次结构

IO调度概念

高速缓存与缓冲区

设备的分配与回收

SPOOLing（假脱机技术）

待完善的内容

  • [ ] 虚拟技术
  • [ ] 命令接口
  • [ ] 程序接口
  • [ ] 操作系统的结构
  • [ ] 分时操作系统与实时操作系统的比较
  • [ ] 进程的创建过程
  • [ ] 进程的阻塞和唤醒
  • [ ] 进程通信
  • [ ] 进程调度的过程
  • [ ] 调度算法
  • [ ] 死锁的四个条件
  • [ ] 死锁避免
  • [ ] 死锁预防
  • [ ] 死锁检测
  • [ ] 覆盖与交换

参考文档：https://wizardforcel.gitbooks.io/wangdaokaoyan-os/content/index.html