↓Skip to main content
  1. Docs/

操作系统学习笔记

3921 字· 0 · 0 ·
操作系统
Table of Contents
1. 绪论>

1. 绪论 #

1.1 操作系统概述>

1.1 操作系统概述 #

1.1.1 操作系统的定义>

1.1.1 操作系统的定义 #

  • Operating System 是指控制和管理整个计算机系统的硬件与软件资源，合理地组织和调度计算机的工作和资源的分配，进而为用户和其他软件提供方便接口与环境的程序集合。

  • 操作系统是计算机系统中最基本的系统软件。

1.1.2 操作系统的功能>

1.1.2 操作系统的功能 #

  • 操作系统是用户和计算机硬件之间的接口。

    • 命令接口

      • 联机命令接口（交互式命令接口）

        适用于分时和实时操作系统

      • 脱机命令接口（批处理命令接口）

        适用于批处理系统

    • 程序接口（系统调用、广义指令）

      用户通过在程序中使用这些系统调用来请求操作系统的服务

      如：使用各种外部设备、申请分配和回收内存等

      例：图形接口不是操作系统的一部分，但图形接口所调用的系统命令是操作系统的一部分

  • 操作系统是计算机系统资源的管理者。

    • 处理机管理（进程管理）

    • 存储器管理

    • 文件管理

    • 设备管理

  • 操作系统用作扩充机器

    • 操作系统使得裸机功能更强、更方便使用
    • 因此，覆盖了软件的机器称为扩充机器或虚拟机
1.1.3 操作系统的目的>

1.1.3 操作系统的目的 #

  1. 方便性：使计算机更易于用户使用。
  2. 有效性：以有效的方式管理计算机系统的资源，合理地组织计算机的工作流程， 以防止对计算机资源的不当或错误使用。这是操作系统可用的关键因素。
  3. 可扩展性：为用户的的开发搭建一个平台，允许修改、并引进新的功能。 操作系统为计算机上所有软件的性能提高提供了平台，另外，操作系统提供了一系列功能用以支持用户程序的运行。
1.2 操作系统的发展过程>

1.2 操作系统的发展过程 #

  • 手工操作（无操作系统）

  • 批处理阶段（开始出现操作系统）

    • 单道批

    • 多道批

  • 分时操作系统（交互性强）

  • 实时操作系统（及时性、可靠性、交互性不如分时）

  • 网络操作系统（服务于计算机网络，集中式控制）

  • 分布式操作系统（建立在网络操作系统上，分布控制）

  • 个人计算机

1.3 操作系统的结构>

1.3 操作系统的结构 #

1.3.1 整体>

1.3.1 整体 #

例如 CP/M 和 MS-DOS，以及原始的 UNIX 操作系统。MS-DOS 系统设计的目标是利用最小的空间提供最多的功能

image-20230107150738940

  • 优点
    • 由于整体结构的操作系统的应用程序和底层硬件之间没有太多接口，所以这种类型的 操作系统结构紧密，接口简单直接，系统效率较高，具有良好的性能。
  • 缺点
    • 这种结构 的模块独立性差，易形成复杂的调用关系，使得增强或维护这样的操作系统很困难，修改 其中的一个模块将会影响到其他模块。
1.3.2 分层>

1.3.2 分层 #

分层操作系统的例子有 VAX/VMS 和 UNIX 等。

由于增强或维护整体结构的操作系统所遇到的问题，导致了分层操作系统的出现。

层次结构正是从这点出发，力求使模块间调用的无序性变为有序性。

  • image-20230107150819169
  • 优点
    • 增加了系统的可读性和可适应性，简化了系统的设计和实现。
    • 易于调试、修改、扩充、维护和保证正确性。
  • 缺点
    • 操作系统的效率不高。由于所有请求在到达硬件之前要经过很多层，每一层所 产生的系统开销会使得操作系统的效率较低。
    • 层的定义较为困难。在设计层次结构时，各系统对划分层次的数目有不同的看法，有时很难决定特定层中应该包含的内容。
1.3.3 微内核>

1.3.3 微内核 #

采用微内核的思想开发的操作系统有：Minix、Tru64 UNIX、L4、QNX 等。

在分层操作系统中，设计者要确定内核—用户的边界，所有的层都在内核中。然而， 随着操作系统的开发人员开始给系统添加越来越多的特性，使得内核变得越来越大且难于管理。

微内核（micro-kernel）设计的思想是：将操作系统划分成小的、定义良好的模块。

微内核通常只提供了最基本的操作系统功能，如进程管理、通信原语和低级内存管理。

在内核外部实现的系统程序或用户级程序提供了其余的操作系统服务，这些程序被称为服务器。应用程序和不同的服务器通过传递给微内核的消息进行通信，微内核验证消息，然后在操作系统的不同模块之间传送消息，并允许对硬件进行访问。例如：如果客户程序希望访问一个文件，那么它必须与文件服务器进行交互。客户程序和服务器不会直接交互，而是通过微内核的消息传递来进行通信。

  • image-20230107150843348

  • 优点

    • 良好的扩充性：通过添加服务器就可以简单地增加新的服务种类而不需要修改 内核。
    • 可靠性好：如果某个特定的服务器出现问题，那么可以重新配置和启动该服务 器，而不必重新启动整个操作系统。
    • 高灵活性：由于内核和服务器之间是分隔的，所以使用单个微内核就可以构造 出满足各种特定环境的不同的操作系统。例如：Mac OS X、Tru64 UNIX 以及某些变种的 Linux 都可以在 Mach 微内核上实现。
    • 可移植性强：由于微内核可以直接和底层硬件进行交互，所以可以很方便地将 操作系统移植到各个不同的平台上。
1.4 操作系统的特征>

1.4 操作系统的特征 #

1.4.1 并发性（Concurrency）>

1.4.1 并发性（Concurrency） #

宏观多道程序同时执行，微观交替执行，对有限物理资源进行多用户共享以提高效率。

1.4.2 共享性（Sharing）>

1.4.2 共享性（Sharing） #

互斥访问，同时访问

并发和共享相互依存

1.4.3 异步性（Asynchronism）>

1.4.3 异步性（Asynchronism） #

在操作系统控制下多个进程的执行次序和每个进程的执行时间是不确定的。

1.4.4 虚拟性（virtuality）>

1.4.4 虚拟性（virtuality） #

虚拟指把一个物理上的实体变为若干逻辑上的对应物。

虚拟技术可分为：时分复用和空分复用。

如：虚拟处理器、虚拟存储器、虚拟内存、虚拟外部设备。

假脱机技术 **SPOOLing ** (Simultaneous Peripheral Operations On-Line) 技术可把物理上的一台独占设备变成逻辑上的多台虚拟设备；

若有进程要求对它打印输出时，SPOOLing系统并不是将这台打印机直接分配给进程，而是在共享设备（磁盘或磁鼓）上的输出SPOOLing存储区中为其分配一块存储空间，进程的输出数据以文件形式存放于此。在SPOOLing 系统中，实际上并没有为任何进程分配，而只是在输入井和输出井中，为进程分配一存储区和建立一张I/O请求表。这样，便把独占设备改造为共享设备。

题目>

题目 #

  • 计算机开机后，操作系统最终会被加载到 RAM

BIOS（Basic Input Output System）：它是一组固化到计算机内主板上一个ROM芯片上的程序，它保存着计算机最重要的基本输入输出的程序、开机后自检程序和系统自启动程序，它可从CMOS中读写系统设置的具体信息。

ROM（Read-Only Memory）：只读存储器ROM，所存数据通常是装入整机前写入的，整机工作过程中只能读出。

EPROM：可擦除可编程只读存储器，一旦编程完成后，EPROM只能用强紫外线照射来擦除。

RAM （Random Access Memory）：随机存取存储器，也叫主存，是与 CPU直接交换数据的内部存储器。RAM在计算机和数字系统中用来暂时存储程序、数据和中间结果。

1.5 UNIX 系统简介>

1.5 UNIX 系统简介 #

UNIX 操作系统是一个多用户分时操作系统。

由于它的绝大部分代码是用 C 语言编制 的，故可移植性极好。

1.5.1 UNIX综述>

1.5.1 UNIX综述 #

  • UNIX特点

    1. 内核简洁，可常驻内存，保证系统高效运行，同时可以开发大量核外程序为用户服务。

    2. 用C语言编写，具有良好的可移植性。

    3. 树形结构文件系统

      搜索速度快、安全性、保密性、可维护性；

      文件系统可装卸，用户可以同时使用多个文件系统；

    4. 外设和文件统一看成文件，在用户面前，操作方式相同。

    5. I/O重定向和管道，灵活性高

      通过 I/O 重定向，可以指定命令或程序从何处得到输入和将结果送到何处去，从而改变了默认的输入源位置和输出目标位置。

      管道让一个命令或程序的输出成为另一个命令或程序的输入。

    6. 良好的用户接口，提供shell和系统调用

    7. 开放式的操作系统

      允许用户自己编写工具和程序

      提供TCP/IP协议，可实现网络互联

    8. 开发环境优良

      提供有大量的软件开发工具，如源代码控 制系统（SCCS）、词法分析器自动生成器（Lex）、优化 C 编译器和源代码调试工具等。

    9. 丰富的使用程序，软件厂商支持

  • UNIX的分层体系结构

    • image-20230107151437547
1.5.2 UNIX内核功能>

1.5.2 UNIX内核功能 #

  • UNIX内核结构

    分为三级：用户级、核心级、硬件级

    image-20230107151450180

  • UNIX内核功能简述

    1. 文件子系统

      (1) 空闲文件存储空间的管理；

      (2) 为文件分配文件存储空间；

      (3) 回收文件释放的文件存储空间；

      (4) 文件存取控制；

      (5) 搜索文件；

      (6) 为用户提供系统调用服务。

      UNIX 文件分为四类：正规文件、目录文件、设备文件和管道文件。

      正规文件：存放程序、数据等（无格式的字符流文件，可按照自己的格式来解释文件）

      目录文件：存放文件系统中各个目录信息的文件（字符流式文件，系统将其解释为文件目录，所有的目录文件构成整个 UNIX 文件系统的树状结构）

      设备文件：代表一个物理设备，用户可以按处理正规文件的方式对其进行处理，但设备文件除了有关文件管理的信息外，并不占据实际的物理存储块

      管道文件：用来存放管道数据。

    2. 进程控制子系统

      进程是一个具有独立功能的程序对其所处理的数据在处理机上的执行过程。

      (1) 进程的创建；

      (2) 进程的调度；

      (3) 进程间的通信；

      (4) 进程间的同步控制。

    3. 设备管理子系统

      完成进程和外设间数据交换的功能

    4. 存储管理子系统

      (1) 管理内存的空闲空间；

      (2) 对交换区空间（一般在磁盘上）进行管理；

      (3) 对虚拟存储空间进行管理。

      物理内存空间是十分有限的。为了充分提高宝贵的内存的使用效率，UNIX 后期版本 只把进程的一小部分程序和数据放在内存中，而把剩余的程序和数据放在外存，然后采用 交换和请求调页的存储管理策略实现对内存的管理，提供用户比物理内存大得多的虚拟地 址空间。UNIX 的早期版本仅采用交换技术进行内存管理。

      交换技术：就是指当内存满了以后，就将一个程序从内存换出，将另一个程序放入内存，换出的内存数据保存在硬盘上，当该程序再次被换入的时候，就将硬盘上的数据拷贝到内存。

2.处理机管理>

2.处理机管理 #

对处理机的管理就是对进程的管理，处理机分配和调度的对象大都是以进程为单位

传统的进程也可以看成是只有一个线程的进程

2.1 多道程序设计>

2.1 多道程序设计 #

所谓多道程序设计是指允许让多个计算问题同时装入一个计算机系统的主存储器，并允许它们共享资源、并发执行的程序设计技术。

2.1.1 单道程序的顺序执行>

2.1.1 单道程序的顺序执行 #

程序的顺序执行有两个特点：

  1. 封闭性：程序在运行时独占资源
  2. 可再现性：初始条件相同，则在何时执行结果都相同
2.1.2 多道程序的并发执行>

2.1.2 多道程序的并发执行 #

多道程序的特点：

  1. 并发性：宏观上同时运行，微观上顺序执行
  2. 资源共享性
  3. 并发的程序相互制约
  4. 不确定性
2.2 进程的基本概念>

2.2 进程的基本概念 #

程序是完成某一特定功能的指令序列，是一个静态的概念；而处理机的执行活动是程序的执行过程，是一个动态的概念。同一个程序，在一段时间内，可以多次被执行，而且是并发执行，这样这些并发执行的动态过程也无法简单地用程序加以区别。可见，程序这个静态的概念无法正确描述程序的动态执行情况，但是进程能很好地描述程序的并发执行， 这些是引入进程这个概念最重要的原因。

2.2.1 进程的定义>

2.2.1 进程的定义 #

进程=程序+数据+执行

进程实体=程序段+相关的数据段+PCB

进程控制块（Process Control Block，简称 PCB），用于记录有关该进程的资料

进程分为系统进程和用户进程两类

Windows 操作系统在初始化后，将自动产生诸如SMSS（对话管理）、LSASS（安全管理）、WINLOGON（登陆管理）、 explore（Windows 壳）等系统进程，之后用户可以创建新的用户进程。

2.2.2 进程的属性>

2.2.2 进程的属性 #

  1. 动态性。

  • 进程动态产生，动态执行，动态消亡；

  • 进程有生命周期，而且在其生命周期内，进程的状态是动态变化的。

  1. 并发性。

这是指多个进程实体可同存于主存之中，且能在一个时间段内宏观上同时运行。

  1. 独立性。

这是指进程实体是一个能够独立运行、独立分配资源和独立接收调度的基本单位，而且它有自己的程序计数器和内部状态。

  1. 异步性。

这是指每个进程按各自独立的、不可预知的速度向前推进。

  1. 交往性。

这是指一个进程在运行过程中可能会与其他进程发生直接的或者间接的相互作用。

进程之间可能要互斥地使用某些资源，相关进程之间可能需要必要的同步和通信等。

2.2.3进程与程序的关系>

2.2.3进程与程序的关系 #

  1. 考虑动态性

进程是程序的一次执行过程，进程是一个动态概念；

而程序是完成某个特定功能的指令的有序序列，即程序是一个静态概念。

程序是代码的集合，而进程是程序的执行。

程序可以作为一种软件资源长期保存，可以被复制，可以在不同的计算机上运行；

而进程，是有生命周期的，它动态地被创建，并被调度执行后消亡。

  1. 考虑并发性

进程具有并发特征，而程序没有。由于一个进程可以与其他进程并发执行，即进程具有并发性；而程序并不反映执行过程，所以不具有并发特征。

  1. 考虑资源

进程是系统进行资源分配和调度的一个独立单位，即资源分配是以进程为单位的，而不是以程序为单位的。

  1. 考虑结构

程序的组成是代码，而进程实体的组成包括：程序、数据和 PCB。

  1. 考虑生成性

进程可以生成其他进程，而程序则无法生成新的程序。

  1. 考虑对应关系

一个程序多次执行可以对应多个进程；通过调用关系，一个进程也可以包括多个程序。

2.3 进程的状态及转换>

2.3 进程的状态及转换 #

2.3.1 进程的基本状态及转换>

2.3.1 进程的基本状态及转换 #

image-20230107151538117

  • 共五种状态（三个基本状态）
  1. 初始态：进程刚被创建时，由于还没正式提交给操作系统的处理机调度程序对其进行管理，因此只能处于一个特殊的初始状态；
  2. 终止态：进程在执行结束后，将退出执行而被终止，此时也不受处理机调度程序的管理，即进程处于另一个特殊的状态——终止状态；
  3. 执行态：进程在处理机上执行，即处于执行状态；
  4. 就绪态：已经具备执行所需的所有必要条件，只要占用 CPU 就可以执行，但由于该进程使用CPU的时间太长，为了公平，把CPU让给别的进程使用；
  5. 阻塞态：由于进程在运行过程中执行了某种阻塞操作（如读写），此时该进程用不到CPU，便将CPU交给别的进程使用，即进入了阻塞态。

  • 每个进程在执行过程中（不包含初始状态和终止状态），任何时刻必须处在三个基本状态之一，而且只能处在三个基本状态之一（不能同时处于两个状态）。

  • 进程的状态是如何转换的呢？

  1. 初始态变为就绪态：当操作系统完成对进程创建的必要操作后，相应的系统进程将进程的状态转换为就绪状态。
  2. 就绪态变为执行态：进程被处理机调度选中而获得处理机时，进程由就绪状态变为执行状态。
  3. 执行态变为阻塞态：这是由于执行进程自己的原因造成的，执行进程等待某个事件发生或者等待使用某种资源，此时进程无法继续执行直到等待的条件满足，这种情况下， 进程由执行态变为阻塞态。
  4. 阻塞态变为就绪态：事件完成，即资源得到满足或者等待的事件已经发生，此时进程由阻塞态变为就绪态，等待再次被处理机调度选中执行。
  5. 执行态变为就绪态：处于执行态的进程被剥夺处理机时引起的，通常与调度策略有关，比如运行时间片已到或者出现更高优先级的进程等，此时，进程由执行态变为就绪态。
  6. 执行态变为终止态：当一个进程完成任务自然结束，或是出现了无法克服的错误， 或是被操作系统或其他进程所终结时，进程由执行态变为终止态。
2.3.2 具有挂起功能的进程状态及转换>

2.3.2 具有挂起功能的进程状态及转换 #

随着系统的运行，更多的进程被不断创建，当系统资源不能满足进程运行的需求时， 系统须把某些进程对换到磁盘中，暂时不让其参与进程调度，以达到平滑系统负荷的目的， 这个过程称为“挂起”。

  • 引起进程挂起的原因：
  1. 运行需要：内存中的进程均处于阻塞态，而处理机空闲，此时需要把一些阻塞进程挂起（即对换出去），以腾出内存空间装入就绪进程，使之运行；
  2. 调节负荷的需要：由于进程竞争资源而导致系统的资源不足或负荷过重，此时，需要挂起部分不太重要的进程，以调节系统负荷，以保证系统的正常运行（需要说明的是： 系统也可能把一些定期执行的进程，如监控程序、审计程序、记账程序等对换出去，以减轻系统的负荷）；
  3. 用户请求：用户请求挂起自己的进程，以便分析其执行情况，或根据中间执行情况 进行其他处理；
  4. 父进程要求：父进程可以要求挂起自己的某个子进程，以便对该子进程进行考察、 分析或修改，或者协调各个子进程的运行；
  5. 操作系统需要：第一，当系统出现故障或某些功能受到破坏时，系统需要挂起某些进程以检测和排除故障；第二，有时系统因需要检查运行过程中的资源使用情况而挂起某些进程。
  • 新增的两个状态：
  1. 静止就绪态：表明进程具备运行条件，但目前进程不在主存中而是处于被挂起状态，只有当它被对换到主存中才能被调度执行；
  2. 静止阻塞态：表明进程在等待某一事件，且进程不在主存中。
  • 具有挂起功能的进程状态转换图

image-20230107152116537

状态转换详解

  1. 活跃阻塞态挂起变为静止阻塞态：
  • 若当前不存在活跃就绪进程，则至少有一个活跃阻塞进程将被对换出去成为静止阻塞进程;
  • 操作系统依据当前的资源状况和性能要求，可以将某些活跃阻塞进程对换出去成为静止阻塞进程；
  1. 静止阻塞态激活变为活跃阻塞态：
  • 操作系统已经得知导致进程阻塞的事件即将结束；
  • 内存中已经有了一大块自由空间；
  1. 静止阻塞态变为静止就绪态：
  • 事件完成，即资源得到满足或者等待的事件已经发生；
  1. 静止就绪态激活变为活跃就绪态：
  • 当静止就绪态进程具有比活跃就绪态进程更高的优先级；
  • 内存中已经有了一大块自由空间；
  • 当内存中没有活跃就绪态进程；
  1. 活跃就绪态挂起变为静止就绪态：
  • 这种状态变化主要是由于系统调节负荷的需要， 或者是系统优化性能的需求。

可见，只有处于活跃就绪态的进程在得到 CPU 后才能立即投入执行，而处于静止就绪态的进程只有先成为活跃就绪态后，才可能被选中调度执行。这种方式虽然提高了内存的利用效率，但同时也使得管理更加复杂且增加了系统开销。

2.4 作业的基本概念>

2.4 作业的基本概念 #

2.4.1 作业的定义>

2.4.1 作业的定义 #

把一次计算（或事务处理）过程中，从输入开始到输出结束，用户要求计算机所做的关于该次计算（或事务处理）的全部工作，称为一个作业。

在批处理系统中，作业是抢占内存的基本单位。

作业是否成功建立要看是否加入了作业表表项

  • 从用户的角度

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

      作业说明书：表达用户对作业的控制意图，一般由用户使用某种作业控制语言来书写

      包含三个方面的内容：

      1. 作业的基本描述
      2. 作业的控制描述
      3. 作业的资源需求描述。

    • 作业步：用户把要求计算机系统做的每一项相对独立的工作称为一个作业步。

      作业步之间相互独立却又有联系。

  • 从系统的角度

    • 作业=多个程序+多份数据+作业控制块 JCB（Job Control Block）

      • JCB：操作系统通过 JCB 来控制程序和数据，为其分配资源，使之执行并对其进行操作。

      • JCB 包括的主要内容有：

        1. 作业名
        2. 作业状态
        3. 资源需求
        4. 作业类型
        5. 作业控制方式
        6. 作业优先权

      • 作业表：为了对作业进行管理，操作系统将所有作业的 JCB 构成一张表，称为作业表。

        作业表一般存放在外存的固定区域中，而且其长度是固定的，即系统能同时容纳的作业数量是有限的。

      • **输入作业流 **：当有若干个作业被成功创建，进入系统，被依次存放在外存上，这就形成了输入的作业流；

      • 处理作业流：当输入作业流在操作系统的控制下，逐个作业进行处理，这称为处理作业流。

2.4.2 作业与进程的关系>

2.4.2 作业与进程的关系 #

作业的处理依赖于进程：计算机为了处理一个作业，首先，操作系统为该作业创建一个根进程；然后，在执行作业控制语句时，根据作业说明书的要求， 由系统或根进程为该作业创建相应的子进程；之后，系统为各个子进程分配资源，并调度各子进程执行以完成作业的要求。

  • 作业与进程之间的区别

    1. 本质

      作业就是用户要求计算机完成的一项任务；

      进程是系统为了完成作业而设置的动态执行体。

    2. 资源

      作业中的作业说明书事先说好了资源的分配关系，这是静态的；

      进程是操作系统分配资源的基本单位，这是动态的。

    3. 作业和进程的对应关系

      一个进程对应一个作业

      一个作业需要多个进程

2.4.3 作业的状态及转换>

2.4.3 作业的状态及转换 #

image-20230107152144842

  • 共四种状态

    1. 提交态：作业由输入设备进入外存储器（也称输入井）的过程称为提交态。处于提交态的作业，其信息正在进入系统。

      可以有两种输入方式：

      1. 作业由用户直接通过终端键盘向计算机中输入其作业；
      2. 将作业提交给操作员，并由操作员利用输入设备进行输入。

    2. 后备态：作业的全部信息都已进入输入井，并且作业控制块 JCB已经创建，此时称作业处于后备状态。

      其中，系统为该作业建立 JCB， 并把它加入到后备作业队列的过程称为作业注册。

    3. 运行态：一个处于后备态的作业，一旦被作业调度程序选中而被送入内存中，并分配相应的资源而一组与该作业对应的进程建立后，该作业就进入了运行态。

      与作业相对应的进程，刚被创建时处于就绪状态（并非初始态），等待进程调度，参与处理机竞争，并按进程的状态转换方式转换状态。

    4. 完成态：当作业终止，但作业所占用的资源尚未全部被系统回收时的状态称为完成态。

      作业终止可能有两种方式：

      1. 正常运行结束；
      2. 因发生错误而终止。资源需要回收，等待系统收拾烂摊子。
2.5 进程的描述与上下文>

2.5 进程的描述与上下文 #

进程实体=程序段+相关的数据段+PCB

进程控制块（PCB）是进程实体的一部分，是操作系统为了描述和控制动态的进程及其运行而为进程定义的一种数据结构。它是进程存在的惟一标志，进程的 PCB 都是全部或部分常驻内存的，程序和数据集放在外存中，直到该进程执行时再调入内存。

2.5.1 进程控制块 PCB>

2.5.1 进程控制块 PCB #

  • PCB 的作用

    1. 提供了进程的描述信息、控制信息和资源信息等（几乎是管理进程的所有信息）

    2. 标识进程的存亡。

      进程创建时，操作系统为其创建PCB，当进程消亡时，操作系统回收其PCB

    3. 操作系统是根据 PCB 来对并发执行的进程进行管理和控制的。

      正是由于 PCB 的存在，才使得进程成为一个能独立运行的基本单位，才使得进程能与其他进程并发执行。

  • PCB 中的信息

    1. 进程标识符。

    2. 进程的当前状态。

      仅当进程处于就绪状态时，才可能被调度执行。

      若进程处于阻塞状态，还需要在 PCB 中记录阻塞的原因，以供唤醒原语唤醒进程时用。

    3. 进程相应的程序和数据地址。

      将 PCB 与其程序和数据联系起来。

    4. 进程资源清单。

      列出进程所拥有的除了处理机之外的资源记录，如打开的文件列表，拥有的 I/O 设备等。

    5. 进程优先级。

      通常是一个表示进程使用 CPU 的优先级别的整数。

    6. CPU 现场保护区。

      当进程因某种原因不能继续占用 CPU 时，需要将 CPU 的各种状态信息保护起来。

      被保护的 CPU 现场信息通常有：程序状态字 PSW、程序计数器的内容、 通用寄存器的内容和用户栈的指针等。

    7. 进程同步和通信机制。

      用于实现进程之间的互斥、同步和通信所需的信号量、信箱或消息队列的指针等。

    8. 进程所在队列的 PCB 的连接字。

      进程 PCB 根据进程的当前状态，插入到不同的队列中。PCB 连接字指出该进程所在队列中下一个进程 PCB 的首地址。

    9. 与进程相关的其他信息。

      如进程的家族信息、进程所属的用户、进程占用 CPU 的时间、进程记账信息等。

2.5.2 进程上下文>

2.5.2 进程上下文 #

  1. 进程上下文

    • 操作系统中把进程实体和支持进程运行的环境合称为进程上下文（process context）。
    • 一个进程的上下文的结构一般由以下几个部分构成：
      • PCB
      • 正文段（即程序段经过编译后形成的机器指令代码集）和数据段
      • 与该进程有关的各种寄存器和堆栈的值
    • 进程上下文结构

  2. 进程上下文切换

    步骤：

    1. 状态保存（state save）
    2. 选取新进程
    3. 状态恢复（state restore）
2.6 进程的控制>

2.6 进程的控制 #

创建、删除进程；进程状态转换；进程通信

达到在多个进程之间同步和高效并发执行的同时，也实现资源的共享和协调。

2.6.1 进程控制机构>

2.6.1 进程控制机构 #

进程的控制由操作系统的内核完成

  1. 什么是操作系统的内核

    • 操作系统的内核由一些与硬件密切相关的模块，以及共用的基本操作构成；

    • 内核常驻内存，并给予特殊保护（核心态）；

    • 内核包含支撑功能（中断处理、时钟处理、原语操作）和资源管理功能（括进程管理、存储器管理、文件管理和设备管理）；

  2. .内核中与进程控制紧密相关的机构

    • 进程管理

      将进程管理放在内核的原因

      1. 进程管理的相关模块的运行频率较高
      2. 它们被多种功能模块所调用

    • 原语操作

      • 操作系统使用系统原语实现对进程状态改变的控制。

      • 原语是不可分割的，是机器指令的延伸

      • 对用户透明，但可以当做一类特殊的系统调用

2.6.2 进程控制原语>

2.6.2 进程控制原语 #

创建原语、撤销原语、阻塞原语和唤醒原语。

  1. 进程创建原语

    • 进程可以通过调用进程创建原语来创建子进程，子子孙孙创建下去就构成了家族关系

    • 进程创建原语的主要操作步骤：

      1. 向系统申请一个空闲的 PCB：扫描空闲PCB表项，获得该PCB的内部名称作为新进程的标识号PID；
      2. 为新进程分配各种资源；
      3. 初始化新进程 PCB 的内容：PCB 中填入进程名、家族信息、数据和程序地址、进程优先级、资源清单以及进程状态（就绪态）等信息；
      4. 将新进程的 PCB 插入到就绪队列。

  2. 进程撤销原语

    • 进程撤销的原因

      1. 进程完成任务而正常撤销
      2. 进程由于出现某些故障或错误而被迫撤销。

    • 两种撤销策略

      1. 只撤销指定进程
      2. 撤销指定进程及其子孙进程

    • 撤销指定进程及其子孙进程的操作步骤

      1. 从系统的 PCB 表中检索出被撤销进程的 PCB，并从中读出该进程的状态，设置重新调度标志，以便在该进程撤销后将 CPU 分配给其他的进程；；
      2. 如果正处在执行态，则立即终止，设置重新调度标志；
      3. 检查子孙进程，递归终止；
      4. 递归回收被终止进程的全部资源：把属于父进程的资源归还给父进程，属于自己申请的资源则归还系统，注销其资源描述清单；
      5. 递归释放被终止进程的PCB
      6. 如果重新调度标志为真，则转到进程调度程序。

  3. 进程阻塞原语

    • 调用该原语的进程由执行态变为阻塞态。

    • 什么时候要将进程的执行态转变为阻塞态？

      1. 当进程请求某事件尚未发生，主动放弃处理机

    • 操作步骤

      1. 停止调用者自身执行
      2. 保存断点信息
      3. 设置自己的状态为阻塞态
      4. 将自己的PCB插入相应事件的等待队列
      5. 转进程调度程序，从就绪队列中选择新的进程投入运行

  4. 进程唤醒原语

    • 发现者将一个被唤醒的进程的状态由阻塞态变为就绪态。

    • 什么时候要将进程的阻塞态转变为就绪态？

      1. 等待的资源得到满足

    • 操作步骤

      1. 找出标识

      2. 从阻塞队列移出

      3. 设置为就绪态

      4. 插入就绪队列

      5. 考虑被唤醒进程和当前运行进程的优先级

        若被唤醒进程优先级更高则需要设置调度标志，并转进程调度程序。

2.7 线程>

2.7 线程 #

比进程更小的能独立运行的基本单位

2.7.1 线程的概念>

2.7.1 线程的概念 #

  • 什么是线程？

    1. 是由进程进一步派生出来的一组代码的执行过程;
    2. 是进程中相对独立的一个执行流；
    3. 是系统独立调度的基本单位。

  • 为什么系统引入线程可以提高效率和并发性？

    1. 线程继承共享所属进程的一切资源；
    2. 线程本身运行只需要很少一部分资源；
    3. 所以线程切换的开销比进程小得多。

  • 什么时候线程不应该引入？

    1. 实时系统（进程调度少）
    2. 个人数字助理系统
    3. 任务单一的系统

  • 传统进程 和 多线程环境中的进程的区别

    1. 传统的进程管理资源和指令的执行，多线程环境中的进程只负责资源分配和保护，线程负责执行任务；

    2. 每个线程都有独立的系统堆栈和用户堆栈

      image-20220404195338628

    3. 线程控制块（Thread Control Block，简称 TCB）是标志一个线程存在的数据结构，与 PCB 相比，TCB 中的内容较少，因为PCB还需要记录资源分配信息。

2.7.2 线程与进程的关系>

2.7.2 线程与进程的关系 #

线程和进程的比较

  • 资源

    进程可以拥有自己的资源

    线程可以访问进程的资源

  • 调度

    线程是调度的基本单位

  • 并发性

    两者都可以并发执行

  • 系统开销

    进程大于线程

  • 安全性

    进程比线程安全

    因为，同一个进程下的多个线程可以共享进程的资源，会发生数据篡改并导致错误

2.7.3 线程的实现>

2.7.3 线程的实现 #

  1. 用户级线程（User-Level Thread，简称 ULT）

    • 在用户空间，由应用程序在线程库（的支持下完成，系统内核不知道线程的存在；

    • 线程库是一组可供所有的应用程序共享的应用级软件包，它可以创建线程、销毁线程、支持线程通信、支持线程调度、保存和恢复线程上下文。（相当于用户级的操作系统）

    • 线程的 TCB 保存在用户空间，并由线程库维护，线程的建立也需由线程库在同一个进程内创建一个新线程。

    • 优点：

      • 灵活。不依赖于操作系统，可以采取与应用程序相适应的线程调度策略。
      • 效率高。不用陷入操作系统内核。

    • 缺点：

      • 无法并行。内核一次最多只给一个进程分配处理机，而所有线程均依赖于这个处理机。
      • 会导致进程堵塞。一个线程未满足，则整个进程受阻。

  2. 内核级线程（Kernel-Level Thread，简称 KLT）

    • 与线程有关的工作通过系统调用交给操作系统内核处理
    • TCB存于操作系统空间
    • KLT是处理机调度的基本单位
    • 优点：
      • 并发性好。
      • 通常不会导致进程堵塞
    • 缺点：
      • 系统开销大。因为要在内核和用户两种模式切换。
      • 系统内核空间容易被迅速耗尽。因为线程的数量远远大于进程的，因此操作系统会限制一个应用所创建的进程。

  3. 组合线程或混合线程（hybrid thread）

    • 组合线程通常还需要一个用户和系统都可见的中间实体，用于在用户级线程和内核级线程之间建立联系。 在 Solaris 系统中称该中间实体为轻进程。

    • 每一个中间实体都与一个内核级线程相对应

    • 线程0轻进程0内核线程0
      进程66线程1轻进程1内核线程1
      线程2轻进程2内核线程2

    • 如果设计合理的话，组合线程机制能结合前两类线程的优点，并克服其缺点。

2.8 处理机调度原理>

2.8 处理机调度原理 #

处理机调度就是指CPU资源在可运行实体之间的分配

调度的实质：资源分配

2.8.1 处理机的四级调度>

2.8.1 处理机的四级调度 #

  1. 作业调度

    • 对象：作业
    • 输入井 –> 内存
    • 后备态 –> 运行态 –> 完成态
    • 作业调度程序只负责控制，实际的存储和设备管理由相应的管理程序完成

  2. 交换调度、中级调度

    • 对象：进程

    • 功能：短期平滑和调整系统负荷

    • 外存 <–> 内存

    • 激活：静止就绪态/静止阻塞态 –> 活跃就绪态/活跃阻塞态

    • 挂起：活跃就绪态/活跃阻塞态 –> 静止就绪态/静止阻塞态

    • 实质：存储管理中的对换功能，涉及内存的管理和扩充

    • 问：并发的程度是不是越高越好？不是

      1. 切换进程和线程，系统开销大；
      2. 主存有限
      3. 资源竞争激烈，导致死锁

  3. 进程调度、低级调度

    • 对象：进程
    • 内存 <–> 内存
    • 活跃就绪态 –> 执行态
    • 与前两种最大不同：被选中的进程能够实际获得CPU
    • 运行频率很高并且需要常驻内存，因此算法时间复杂度不能太高

  4. 线程调度

    1. 内核级线程调度

      • 内核级线程调度和进程调度的主要区别：在同一个进程内的内核级线程切换不会引起资源的切换

    2. 用户级线程调度

      • 操作系统在设计时不需要考虑用户级线程
2.8.2 处理机调度的目标>

2.8.2 处理机调度的目标 #

  1. 提高系统资源利用率

    使各个部件均忙碌

  2. 提高系统吞吐量，降低平均周转时间

  3. 降低平均响应时间

  4. 提供相对的公平机制

  5. 其他

    • 考虑优先级
    • 使系统重要参数有可预测性
2.8.3 处理机调度的方式>

2.8.3 处理机调度的方式 #

  1. 非抢占（non preemptive scheduling mode）

    • 优点：
      1. 简单
      2. 系统开销小
    • 缺点：
      1. 不考虑优先级，会延误时机；
      2. 导致短作业的周转时间增加；

  2. 抢占

    • 常见剥夺原则：
      1. 时间片原则
      2. 优先级原则
      3. 短作业优先原则
    • 优点：
      1. 保证并发性
      2. 保证响应及时性
    • 缺点：
      1. 实现复杂
      2. 系统开销大，影响性能
2.8.4 处理机调度的时机>

2.8.4 处理机调度的时机 #

什么时候会引起调度程序工作？

中断是调度的前提，但不是发生中断就一定会调度。

  1. 发生请求，并等待（如：IO）
  2. 进程执行结束
  3. 发生错误
  4. 执行原语
  5. 优先级更高抢占处理机
  6. 时间片用完
2.9 调度算法>

2.9 调度算法 #

资源分配算法

批处理系统目标：提高吞吐量

分时系统：响应时间和公平性

实时系统：及时响应

2.9.0 调度算法的评价指标>

2.9.0 调度算法的评价指标 #

CPU\IO设备利用率=忙碌时间\总时间

系统吞吐量=总共完成的作业数\总共使用的时间

周转时间=作业完成时间-作业提交时间

平均周转时间=各作业周转时间之和\作业数

带权周转时间=作业周转时间\作业实际运行的时间 >=1 越小越好

平均带权周转时间=各作业的带权周转时间之和\作业数

等待时间=等待处理机状态时间之和（正在等待IO设备完成的期间其实进程也是在被服务的，所以不计入等待时间）

响应时间=从用户首次提交请求到首次产生响应所用的时间

响应比=（等待时间+要求服务时间）\ 要求服务时间

2.9.1 先来先服务（First Come First Serve）>

2.9.1 先来先服务（First Come First Serve） #

  • 优点： 1. 简单 2. 公平 3. 不会饥饿
  • 缺点：
    1. 容易使短作业感到不满
2.9.2 最短周期优先 （Shortest Job/Process First）>

2.9.2 最短周期优先 （Shortest Job/Process First） #

  • 优点：

    1. 简单
    2. 平均周转时间最短

  • 缺点：

    1. 作业或进程的执行时间无法预知
    2. 对长作业不利，可能饥饿

  • 改进：最短剩余时间优先算法SRTN

    比较进程所需要的剩余时间，更少时间的抢占处理机。

2.9.3 最高优先级优先（Highest Priority First）>

2.9.3 最高优先级优先（Highest Priority First） #

  1. 静态优先级

    • 调度对象在进入系统时便被赋予一个固定的优先级
    • 优点：
      1. 简单
      2. 系统开销小
    • 缺点：
      1. 不公平
      2. 不灵活

  2. 动态优先级

    • 优先级动态调整
      • 当进程获得某种资源时，其优先级被动态提高，以便能更快获得处理机投入执行，以避免资源的浪费；
      • 当进程处于就绪状态时，其优先级随着等待处理器的时间的增长而提高，而占有处理机的进程的优先级则随着它使用处理机的时间的增长而降低，以保证公平性等。
      • IO繁忙型进程可以适当提高优先级，这样可以尽早地让IO设备投入工作
    • 优点：
      1. 公平
      2. 灵活
      3. 资源利用率高
      4. 防止饥饿
    • 缺点： 1. 复杂 1. 系统开销大
2.9.4 时间片轮转法（Round Robin）>

2.9.4 时间片轮转法（Round Robin） #

  1. 固定时间片轮转

    需要定时时钟，时间片使用完后发生中断，进入调度程序，选择下一个进程占有处理机

  2. 可变时间片轮转

    需要定时时钟，但是时钟中断处理程序每次需要设置新的时钟常量，然后才转入处理机调度程序，选择下一个进程占有处理机。

    • 优点：
      1. 公平
      2. 灵活
      3. 响应及时
    • 缺点： 1. 复杂 2. 系统开销大 3. 对偏重 I/O 的进程处理不太公平。
2.9.5 多级反馈队列>

2.9.5 多级反馈队列 #

设计原则

  1. 多级队列，Q1优先级最高

  2. 时间片和优先级等级成反比，Q1时间片最小

  3. 新进程进入Q1队尾，队内按先来先服务执行

  4. 若在Q1所分配的时间片内完成作业，则撤离系统；否则，进入下一级队列Q2，直到Qmax

  5. 前一队列空了才能轮到下一队列执行

  6. 若被抢占，则被抢占的进程回到当前列的队尾

    多级反馈队列调度

  • 优点

    1. 短周期优先处理

      因为短周期进程一般在优先级较高的几个队列之中即被执行完毕

    2. 系统开销小

      因为运行时间长的进程后面将进入优先级较低的队列，而这些队列的时间片较长，因而进程调度引起的进程切换的开销也比较小。

  • 缺点

    1. 可能发生饥饿

      如果优先级较高的队列一直不为空，则优先级 较低的队列中的进程可能长时间无法得到执行。

2.9.6 实时调度>

2.9.6 实时调度 #

实时系统无需考虑吞吐量、平均需要时间等

只需要做到：对时间要求最紧迫的任务先占用处理机

如：最早截止任务优先（earliest deadline first）算法，也称动态优先级调度算法。

2.9.7 高响应比优先（HRRN）>

2.9.7 高响应比优先（HRRN） #

响应比=（等待时间+要求服务时间）\ 要求服务时间 >=1

综合了FCFS（等待时间）和SPF（要求服务时间），是非抢占算法，不会导致饥饿

2.10 UNIX 系统进程的结构>

2.10 UNIX 系统进程的结构 #

2.10.1 进程控制块 PCB>

2.10.1 进程控制块 PCB #

  • UNIX 进程控制块（也称进程登记表）分为二个部分：proc 结构和 user 结构。

  • proc 结构常驻内存，user 结构不常驻内存。

  • 把 UNIX 进程控制块分成二部分的原因是为了节省内存空间

  1. proc结构

    • 每个进程占用数组中的一个元素。

      例如 0 号进程（又称系统进程）的 proc 结构则占用 proc[0]。

    • 内容

      1. 进程状态
        1. p_stat 进程状态
        2. p_flag 进程标志
        3. p_pri 进程优先数
      2. 用户标识符
      3. 进程标识符
      4. 存储区位置和长度
      5. 软中断信号：记录其他进程发来的软中断信号
      6. 计时项
      7. 调度参数：进程调度时用到的参数
      8. 指向user结构的指针：通过该指针使 proc 结构和 user 结构成为一个整体，构成 完整的进程控制块 PCB。
      9. 指向虚拟存储空间管理表格的指针：用于实现虚实地址变换。

  2. user 结构

    • 不常驻内存，只有进程执行时才需存取的控制信息
    • 进程的私有数据结构，只能自己存取
2.10.2 进程的上下文>

2.10.2 进程的上下文 #

  1. 用户级上下文

  2. 寄存器上下文

  3. 系统级上下文

    静态部分：

    • proc结构
    • user结构
    • 用于虚实地址映射的虚拟存储空间管理表格

    动态部分：

    • 核心栈

      核心栈（kernal stack）是进程执行核心程序时使用的栈，栈中装有进程调用核心函数时用到的有关参数和返回地址。

    • 若干层寄存器

      层的数目是变化的，满足后进先出的规则

2.10.3 进程的状态及转换>

2.10.3 进程的状态及转换 #

进程的状态

正在执行的进程是处于核心态还是用户态由当前进程的 PSW 状态字中相应位来决定。

  1. 用户态执行
  2. 核心态执行
  3. 内存就绪态
  4. 内存睡眠态
  5. 外存就绪态
  6. 外存睡眠态
  7. 被剥夺态（相当于内存就绪态）：当运行的进程要从核心态返回到用户态时
  8. 创建态：创建态是除进程 0 之外的所有进程的初始状态
  9. 僵死态：执行了exit，此时进程已经不存在。但它留下了一个包含状态码和计时统计信息供其父进程来收集。僵死态是进程的终态

UNIX 进程的状态转换

转换过程

3. 进程同步与通信>

3. 进程同步与通信 #

进程的通信机制可以协调进程之间的关系

低级通信：传送的信息量少，包括进程的互斥与同步

高级通信：传送大量数据，目的是信息交换

3.1 进程的并发执行>

3.1 进程的并发执行 #

会产生进程间互斥和同步，对临界资源的访问如果不合理，会产生死锁的问题

3.1.1 与时间有关的错误>

3.1.1 与时间有关的错误 #

并发的进程中共享了公共变量，使得程序的执行与并发进程执行的速度有关，这种错误的结果往往与时间有关，因此被称为“与时间有关的错误”。

3.1.2 Bernstein条件>

3.1.2 Bernstein条件 #

我们希望程序能够同时具有封闭性、可再现性、并发性。

若Bernstein条件被满足，则并发执行不会对执行结果的封闭性和可再现性产生影响

3.1.3 临界资源与临界区>

3.1.3 临界资源与临界区 #

临界资源：系统中一次只允许被一个进程使用的一类资源

临界区：就是在进程中访问临界资源的那一段程序

进入区：进入临界区前的检测区

退出区：将被访问的临界资源标志恢复为未访问状态

剩余区：其余的代码

3.2 进程的互斥>

3.2 进程的互斥 #

3.2.1 软件实现方法>

3.2.1 软件实现方法 #

  1. 严格轮换

    int turn=1; /*设置一个公共整型变量，用来标识允许进入临界区的进程。*/
/*
	进程强制以交替的次序严格轮流进入临界区
	缺点：忙等待、资源利用不充分
*/
进程 1：
    while (TRUE) 
    {
        while (turn != 1); /*进入区*/
        Critial_region1(); /*临界区*/
        turn = 2; /*退出区*/
        other_region1(); /*剩余区*/
    }
进程 2：
    while (TRUE) 
    {
        while (turn != 2); /*进入区*/
        Critial_region2(); /*临界区*/
        turn = 1; /*退出区*/
        other_region2(); /*剩余区*/
    }

  2. Dekker算法

    算法复杂，被取代

  3. Peterson算法

    enum boolean {false, true};
/*标识数组，标识每个进程，true为表示该进程想进入临界区*/
Boolean flag[2] = {false, false}; 
 /*公共变量，turn=i的时候，i可以进入临界区*/
int turn;
/*缺点：依旧忙等待，但可以使得进程可以在有限的时间内进入临界区*/
进程 1：
    while (TRUE) 
    {
        flag[0] = true; /*进入区*/
        /*进入区2，通过turn值的设置和其后的while语句来保证任何时候最多只有一个进程可以进入临界区*/
        turn = 2; 
        /*进入区3，当对方不在临界区并且不想进入临界区时才允许自己进入临界区*/
        while (flag[1] && turn == 2); 
        Critial_region1(); /*临界区*/
        flag[0] = false; /*退出区*/
        other_region1(); /*剩余区*/
    }
进程 2：
    while (TRUE) 
    {
        flag[1] = true; /*进入区*/
        turn = 1; /*进入区*/
        while (flag[0] && turn == 1); /*进入区*/
        Critial_region2(); /*临界区*/
        flag[1] = false; /*退出区*/
        other_region2(); /*剩余区*/
    }
3.2.2 硬件实现方法>

3.2.2 硬件实现方法 #

  1. 关中断

    每个进程在刚进入临界区之后就立即关闭所有中断，直到进程离开临界区再打开中断

    优点：简单

    缺点：

    1. 不适用与多CPU系统，因为中断只对执行该命令的那个CPU有效
    2. 使用不当，后果严重
    3. 限制处理器交叉执行程序的能力，会影响系统效率
    {
    disable； /*关中断，进入区*/
        Critial_region();/*临界区*/
    enable； /*开中断，退出区*/
        other_region(); /*剩余区*/
}

  2. 使用测试和设置指令（testandset）

    会忙等待

    /*use=0的时候说明资源未被占用，
若进程在访问临界区时的use=1，则会一直测试use，直到它等于0*/
TestAndSet(use)
{
    while (use == 1);
    use = 1;
}
/*用测试与设置指令实现进程互斥的描述如下*/
boolean use = 0; /*初始资源空闲*/
进程 i：
TestAndSet(use); /*进入区*/
Critial_region(); /*临界区*/
use = 0; /*退出区*/
other_region(); /*剩余区*/

  3. 使用对换指令（swap）

    会忙等待

    /*。在进入临界区之前，
先交换 use 与 k，若交换后 k=0，说明资源未被占用，则进入临界区；若交换后 k=1，说明资
源被占用，继续交换 use 与 k 直到 k=0。*/
Swap( boolean *a, boolean *b)
{
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

//用交换指令实现进程互斥的描述如下：
boolean k = true; /*初始化为 1*/
boolean use =false; /*初始资源空闲*/
while ( k != 0)
Swap(&use, &k); /*进入区*/
Critial_region(); /*临界区*/
use = 0; /*退出区*/
other_region(); /*剩余区*/
3.3 进程的同步>

3.3 进程的同步 #

3.3.1 同步的概念>

3.3.1 同步的概念 #

不同的进程之间具有先后的制约关系

3.3.2 同步的实现方法>

3.3.2 同步的实现方法 #

sleep和wakeup原语：

进程 1：
… /*其他代码*/
S1; /*S1 语句，须在进程 2 的 S2 语句之前执行*/
wakeup(进程 2);/*唤醒进程 2*/
… /*其他代码*/
进程 2：
… /*其他代码*/
sleep; /*阻塞自己*/
S2; /*S2 语句，须在进程 1 的 S1 语句之后执行*/
… /*其他代码*/

这种方法会信号丢失

3.3.3 生产者-消费者问题>

3.3.3 生产者-消费者问题 #

3.4 信号量>

3.4 信号量 #

P （Down）减少 使用资源

V（Up）增加 释放资源

3.4.1 信号量的原理>

3.4.1 信号量的原理 #

信号量只能被两个标准的原语wait（S）和signal（S）访问

  1. 整型信号量

    依旧未解决忙等待的问题

  2. 记录型信号量

    解决了忙等待问题，需要一个代表资源数目的整型变量value和一个进程链表L，用于链接所有等待该资源的进程。

    typedef struct{
    int value;
    struct process *L;
}semaphore;

    • wait操作

      void wait(semaphore S){
    S.value--;//请求一个该类资源
    if(S.value<0){//表示资源已经分配完
        add this process P from S.L;//插入该类资源的等待队列
        wakeup(P);//自我阻塞
    }
}

    • signal操作

      void signal(semaphore S){
    S.value++;//释放一个资源
    if(S.value<=0){//如果＋1后仍然资源不足，则表示有进程在等待该资源
        remove a process P from S.L;//从等待队列中移出队首进程
        wakeup(P);//调用wakeup原语唤醒该进程
    }
}
3.4.2 用信号量实现进程互斥>

3.4.2 用信号量实现进程互斥 #

总的来说就是PV操作要夹紧使用互斥资源的那个行为（临界区），中间不能有其他的代码。

若有三个并发进程，设 R 为互斥信号量，其初值为 1，则其取值范围为（-2，-1，0，1）。

其中 R=1 表示所有进程都未进入临界区；

R=0 表示有 1 个进程进入临界区；

R=-1 表示有 1 个进程进入临界区且有另一个进程等待进入临界区；

R=-2 表示有 1 个进程进入临界区且另两个进程等待进入临界区。

进程 1：
Down(R); /*进入区*/
Critial_region1(); /*临界区*/
Up(R); /*退出区*/
other_region1(); /*剩余区*/
进程 2：
Down(R); /*进入区*/
Critial_region2(); /*临界区*/
Up(R); /*退出区*/
other_region2(); /*剩余区*/
进程 3：
Down(R); /*进入区*/
Critial_region3(); /*临界区*/
Up(R); /*退出区*/
other_region3(); /*剩余区*/
3.4.3 用信号量实现进程的同步>

3.4.3 用信号量实现进程的同步 #

可以根据进程关系前驱图来确定PV的顺序

与上一节用 sleep 和 wakeup 原语解决本问题相比，信号量使得信号可以累积而不会丢失。

若进程1先上处理机，则顺利执行s1，然后V(S)操作会使得S=1，且唤醒进程2，进程2在执行s2语句之前会先检查S，执行P(S)操作，使得S-1，此时S-1=0，可以顺利执行s2语句。

若进程2先上处理机，则会使得S-1=-1，阻塞自己，直到进程1执行s1和V(S)，进程2才会继续运行。

Semaphore S=0; /*公共信号量初始化为 0*/
进程 1：
… /*其他代码*/
S1; /*S1 语句，须在进程 2 的 S2 语句之前执行*/
Up(S); /*Up 原语*/
… /*其他代码*/
进程 2：
… /*其他代码*/
Down(S); /*Down 原语*/
S2; /*S2 语句，须在进程 1 的 S1 语句之后执行*/
… /*其他代码*/
3.4.4 用信号量解决生产者—消费者问题>

3.4.4 用信号量解决生产者—消费者问题 #

  1. 单生产者单消费者问题

    semaphore mutex = 1;//临界区互斥信号量
semaphore empty = n;//空闲缓冲区
semaphore full = 0;//缓冲区初始化为空
producer(){
    whlie(1){
        product an item in nextp;
        P(empty);//先同步，生产数据
        P(mutex);//互斥夹紧
        add nextp to buffer;
        V(mutex)；
        V(full);  //唤醒消费者进程     
    }
}
comsumer(){
    while(1){
        P(full);
        P(mutex);
        remove an item from buffer;
        V(mutex);
        V(empty);//唤醒生产者进程
        comsume teh item;
    }
}

    需要注意的是：生产者进程先执行 Down(empty)，然后执行 Down(mutex)，他们的顺序是不能颠倒的；消费者进程先执行 Down(full)，然后执行 Down(mutex)，他们的顺序也是不能颠倒的。否则可能出现错误。 我们假设把他们的顺序都颠倒，会出现什么情况呢？一种情况：当生产者进程把缓冲区放满了，调度程序继续让生产者进程运行，它先执行 Down(mutex)，进入临界区，接着执行 Down(empty)时将被阻塞；接着轮到消费者进程执行，它也先执行 Down(mutex)，然而生产者进程已进入缓冲区，因此消费者进程也会被阻塞。这样一来，生产者和消费者进程都将阻 塞，都指望对方唤醒自己，陷入了无休止的等待了。

  2. 多生产者多消费者问题

    问题描述：桌子上有一个盘子，每次只能向其中放入一个水果。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。只有盘子为空时，爸爸或妈妈才可向盘子中放一个水果：仅当盘子中有自己需要的水果时，儿子或女儿可以从盘子中取出。

    问题分析： 1)关系分析。这里的关系要稍复杂一些。由每次只能向其中放入一只水果可知，爸爸和妈妈是互斥关系。爸爸和女儿、妈妈和儿子是同步关系，而且这两对进程必须连起来，儿子和女儿之间没有互斥和同步关系，因为他们是选择条件执行，不可能并发。

    2)整理思路。这里有4个进程，实际上可抽象为两个生产者和两个消费者被连接到大小为1的缓冲区上。

    3)信号量设置。首先将信号量plate设置互斥信号量，表示是否允许向盘子放入水果，初值为1表示允许放入，且只允许放入一个。信号量apple表示盘子中是否有苹果，初值为0表示盘子为空，不许取，apple=1表示可以取。信号量orange表示盘子中是否有橘子，初值为0表示盘子为空，不许取，orange=1表示可以取。

    image-20220506205301523

    image-20220506205327857

3.4.5 信号量小结及其不足>

3.4.5 信号量小结及其不足 #

优点：

  1. 可以解决忙等待的问题
  2. 可以解决所有互斥和同步问题
  3. 不会丢失信号

缺点：

  1. 维护复杂，容易产生错误

使用要点：

  1. 互斥夹紧，同步在前
3.4.6 分析步骤>

3.4.6 分析步骤 #

  1. 分析活动，划定临界资源和临界区
  2. 设置互斥信号量semaphore mutex = 1不同临界资源需要不同的互斥信号量）
  3. 分析什么地方需要实现同步关系（一前一后）
  4. 前驱关系图，每一对前驱关系都要设置一个同步信号量，前V后P
  5. 互斥夹紧，同步在前（互斥时PV成对出现在同一个进程中，同步时PV出现在不同进程中）

image-20220630110059255

3.5 管程(Monitor)>

3.5 管程(Monitor) #

为了解决信号量存在的分散编程带来的困难;

管程是一个程序语言级别的构造，其正确性由编译器负责保证。是有些高级语言带有管程，而有些高级语言则不支持管程。

管程是一个软件模块

3.5.1 管程的定义、结构和原理>

3.5.1 管程的定义、结构和原理 #

  • 管程应该具备的性质

    • 要有数据，和对数据的操作

    • 管程这种扩展了的抽象数据类型的描述对象是共享资源

    • 能单独编译

    • 满足信息掩蔽原则，即调用者不知道内部具体的实现细节

    • 具有互斥和同步的机制（核心）

      同一时间只有一个进程或线程访问管程；

      这一机制在Java中以关键字synchronized标识；

  • 管程由4部分构成

    • 管程的名称

    • 局部与管程内部的共享数据结构说明

    • 操作过程（函数）

    • 对共享数据赋初值的语句

      image-20220507120723091

  • 入口等待队列

    申请进程只能互斥地进入管程，进程1进入了管程后，编译器会给该管程加锁，此时进程2、进程3等必须加入等待队列，等待进程1使用完管程解锁。

    这种入口等待队列可以很好的实现互斥，那么同步如何实现？

  • 条件变量和同步原语 wait 和 signal

    • 一个进程被阻塞或挂起的原因 （或条件）可以有多个，而条件变量就是在管程中被用来描述这些原因（或条件）的一种抽象数据类型。因此为了描述多种原因，可以在管程中可以设置多个条件变量。

    • 条件变量只是一个特殊的链表或者队列，该链表或者队列只能在管程内被 wait 和 signal 原语操作。由于条件变量必须在管程内才能被操作，因此，对条件变量的访问也都是互斥的。

    • wait(x)：

      • 第一，调用者进程或线程离开管程（即把锁打开）；
      • 第二，将调用者挂在条件变量 x 的等待队列上；
      • 第三，调用者被挂起，等待被唤醒。

    • signal(x)：

      • 把条件变量 x 的等待队列上的第一个等待者唤醒的作用。
      • 如果该队列为空，则不产生任何效果。

    • 条件变量和信号量的比较：

      • 相似点：条件变量的wait/signal操作类似于信号量的PV操作，可以实现进程的阻塞/唤醒。
      • 不同点：条件变量是“没有值”的，仅实现了“排队等待”功能；而信号量是“有值”的，信号量的值反映了剩余资源数，而在管程中，剩余资源数用共享数据结构记录。
3.5.2 用管程解决生产者—消费者问题>

3.5.2 用管程解决生产者—消费者问题 #

image-20220507125739878

3.5.3 管程的不足>

3.5.3 管程的不足 #

  1. 管程对编译器的依赖性。因为管程需要编译器把互斥原语加在管程的开始和结尾。 对于许多程序设计语言，并没有实现管程机制。
  2. 管程只能在单台计算机上发挥效果。由于那些直接支持管程的原语并没有提供机器之间的信息交换方法，因此管程无法在多计算机环境下或者网络环境下发挥作用。

image-20220507130129519

3.6 进程的高级通信>

3.6 进程的高级通信 #

高级通信机制可以归结为三大类：

  1. 消息传递系统：在单机和网络环境都有广泛的应用
  2. 共享存储器系统：以通信的高效而著称，然而其不足也比较明显
  3. 共享文件系统：以管道通信最为典型，管道通信由 UNIX 首创，目前已被许多系统所支持，成为一种重要的通信方式。
  • 直接通信：直接与目标进程进行通信
    • 消息缓冲机制
  • 间接通信：进程之间的通信要通过某种中间实体作为媒介
    • 邮箱机制
3.6.1 消息缓冲机制>

3.6.1 消息缓冲机制 #

利用内存中共用消息缓冲区来实现任意两个进程之间的信息交换

  • 单向通信：不等回答、不发送回答

  • 双向通信：发送者发送完消息后阻塞自己，直到接收者回答才会继续前进；接收者接收到信息前也阻塞等待直到收到发送者发来的消息，并且给发送者发送一个回答信息

  • 通信过程

    1. 发送者在自己的内存空间设置一个发送区，填入消息
    2. 发送者申请一个消息缓冲区，将发送区的消息送到缓冲区，并挂在消息链上
    3. 接收者在自己的内存设置接收区
    4. 接收者摘下消息链第一个信息，将消息从缓冲区复制到接收区，并释放缓冲区

    注意：

    1. 消息链、缓冲区是临界资源（PV原语）
    2. 如何管理消息链？消息链有多条消息、接收者接收信息时消息链可能为空（信号量）
3.6.2 邮箱机制>

3.6.2 邮箱机制 #

引入一种双方共享的数据结构——邮箱，并用邮箱的地址作为消息的间接地址。如：email

  • 邮箱的创建（创建者是邮箱的拥有者）

    • 由操作系统创建

      • 公用邮箱

        给系统中的核准进程使用和读取， 且在系统运行期间始终存在

      • 提供邮箱创建和撤销原语

    • 由用户进程创建

      • 私用邮箱

        由接收者向系统提出创建申请，归接收者拥有，而发送者只是邮箱的使用者

      • 共享邮箱

        拥有者和共享者都能读取邮箱中的消息

      • 当邮箱的拥有者进程结束时，邮箱也随之消失

3.6.3 共享存储区>

3.6.3 共享存储区 #

互斥地访问共享空间

有基于数据结构（低级）和基于存储区（高级）的共享

3.6.4 管道>

3.6.4 管道 #

半双工，如果想实现双向同时通信，需要设置两个管道

访问管道需要互斥

只有管道写满才可读，读完了才能写（没写满，不允许读，反之一样）

读出去的数据不可恢复，因此管道中的读进程最多只有一个

3.7 死锁>

3.7 死锁 #

3.7.1 什么是死锁>

3.7.1 什么是死锁 #

  • 各进程互相等待对方手里的资源，导致各进程都阻塞，无法向前推进的现象

  • 死锁产生的条件

  1. 互斥
  2. 不剥夺
  3. 请求和保持
  4. 循环等待
3.7.2 死锁的表示>

3.7.2 死锁的表示 #

资源分配图

3.7.3 死锁的检测和清除>

3.7.3 死锁的检测和清除 #

  • 检测

    • 简化：最终能消除所有的边，一定没有发生死锁

  • 清除

    • 资源剥夺

      挂起死锁进程，剥夺其资源给其他进程用，需要注意避免饥饿

    • 终止进程

      代价大

    • 进程回退

      回退到足以避免死锁的地步，要求系统记录历史信息

3.7.4 死锁的预防>

3.7.4 死锁的预防 #

破坏死锁产生的条件

  1. 互斥——把只能互斥使用的资源改造为允许共享使用的资源（SPOOLing）
  2. 不剥夺——申请不到便主动释放或剥夺其他进程的资源
  3. 请求和保持——运行前一次性申请所有需要的资源
  4. 循环等待——必须按编号递增的顺序请求资源
3.7.5 死锁的避免>

3.7.5 死锁的避免 #

银行家算法

计算安全序列

4. 存储管理>

4. 存储管理 #

4.1 存储管理的基本功能>

4.1 存储管理的基本功能 #

4.1.1 转换>

4.1.1 转换 #

用户通过汇编语言或高级语言编写的程序，称为源程序。源程序是不能被计算机直接执 行的，需要通过编译、连接、加载后，装入内存才能运行。

  1. 连接和加载

    • 连接

      生成装入模块（可执行文件），里面的是逻辑地址

      • 静态连接（程序运行前就形成完整的装入模块，之后不再拆开）
      • 动态连接
        • 装入时动态（边运行边连接）
        • 运行时动态（用的时候才连接）

    • 加载

      将逻辑地址转为物理地址

      • 绝对加载（只适用于单道程序环境）
      • 可重定位加载（地址变换是在装入时一次完成的，必须一次分配全部空间）
      • 运行时动态加载（装入时依旧是逻辑地址，需要重定位寄存器的支持，重定位寄存器放装入模块的起始位置）

  2. 地址转换

    • 静态地址重定位
    • 动态地址重定位

image-20220630131904284

4.1.2 存储保护和共享>

4.1.2 存储保护和共享 #

  • 内存信息保护方法

  1. 上下界寄存器

  2. 保护键法

  3. 界限寄存器

    重定位寄存器 物理起始地址

    界地址寄存器 逻辑地址长度

  • 为了充分利用内存空间，应避免每个进程拥有单独的副本，而允 许它们访问该程序的同一个副本，这一工作称为存储共享。
4.1.3 内存分配回收>

4.1.3 内存分配回收 #

  1. 连续分配方式

    一般无内存保护

    只适用于单用户、单任务的操作系统

    有内部碎片，存储器利用率很低

  2. 离散分配方式

    分页存储管理方式，分段存储管理方式和段页式存储管理方式

    当进程大小超出内存的可用空间时，这个进程是无法运行的

  3. 虚拟存储管理方式

    请求分页式管理方式、请求分段式管理方式和请求段页式管理方式

    通过实现部分装入和部分对换功能，形成了虚拟存储管理方式

4.1.4 内存扩充>

4.1.4 内存扩充 #

  1. 由应用程序控制的：覆盖方式

    分为固定区和覆盖区

    image-20220630181746920

    对用户不透明，不能实现虚拟存储器

  2. 操作系统控制的：交换方式、请求调入方式和预调入 方式

    交换技术：进程暂时换出外存，PCB留在内存

    和覆盖的区别：覆盖在同一个进程之间，交换在不同进程之间

4.2 分区存储管理>

4.2 分区存储管理 #

4.2.1 固定分区>

4.2.1 固定分区 #

  1. 大小相等
  2. 可变大小
4.2.2 动态分区>

4.2.2 动态分区 #

image-20220630183529299

克服固定分区中小进程占据大分区的现象，避免分区内部 出现碎片；

进程进入内存前并不建立分区，而是根据进程大小对内存进行划分，因此，内存中分区个数是可变的。

由于各个进程执行时，都会装入与之相符的分区中，并连 续存储，因而进程大小受限于内存空间的容量，无法实现虚拟存储。

紧凑技术：（两种策略）

  1. 释放后立即进行紧凑
  2. 找不到足够大的分区再进行紧凑
4.2.3 地址转换和存储保护>

4.2.3 地址转换和存储保护 #

4.2.4 存储共享>

4.2.4 存储共享 #

4.2.5 分配和回收算法>

4.2.5 分配和回收算法 #

  1. 固定分区的分配算法

  2. 动态分区的分配算法

    1. 首次适应

      每次都从低地址开始查找，找到第一个能满足大小的空闲分区

    2. 最佳适应

      空闲分区按容量递增次序连接，因此第一个找到的满足要求的空闲分区，一定是刚刚好合适的

      优先使用更小的空闲区，会产生很多外部碎片

    3. 最坏适应

      空闲分区按容量递减次序连接

      优先使用最大的空闲区，导致大进程到达很可能没空闲分区可用了

    4. 邻近适应

      每次查找都从上一次结束的位置开始查找，减少查找开销

    image-20220630185320587

  3. 动态分区的回收算法

    image-20220630185705624

  4. 移动技术

    紧凑

4.2.6 覆盖和交换>

4.2.6 覆盖和交换 #

  1. 覆盖

    • 同一主存区可以被不同的程序段重复使用

    • 以时间延长来换空间节省的技术

    • 要求程序员根据程序的逻辑结构将程序划分不同的程序段，并事先规定好它们的执行顺序和覆盖顺序

  2. 交换

    • 把等待中的进程换出外存
4.2.7 分区存储管理的优缺点>

4.2.7 分区存储管理的优缺点 #

  • 优点
    1. 支持多道程序设计，实现了多个进程对内存的共享。提高了内存和 CPU 的利用效率；
    2. 简单
  • 缺点
    1. 要求进程在分区内连续存储，因而进程大小受内存空间容量的限制；
    2. 难以实现存储共享
    3. 固定分区分配算法会产生内部碎片，动态分区分配算法会产生外部碎片，因而， 内存利用率不高。
4.3 分页式存储管理>

4.3 分页式存储管理 #

分区存储管理要求每个进程在分区内是连续存储的，致使不论是固定分区管理，还是 动态分区管理，在内存空间利用率上都是低效的，因为前者产生内部碎片，后者产生外部碎 片。在动态分区管理中，虽然紧凑是解决内存外部碎片的一种途径，但需要移动大量信息， 花去不少处理机时间，代价比较高。究其原因在于分区存储管理要求把进程必须放置在一块连续的存储区中，而分页式存储管理正是要避开这种连续性的要求。

4.3.1 基本原理>

4.3.1 基本原理 #

  • 分页式存储管理允许把一个进程分配到不相邻的分区中。
  • 将进程的逻辑空间和内存空间划分为同样大小的块，分别称为页和页面（page frame）
4.3.2 数据结构>

4.3.2 数据结构 #

  • 页表是操作系统为每个用户进程建立的，在内存中占有一块固定的区域，用来记录程序页和内存页面的一一对应关系
  • 作业表是操作系统为当前运行的所有作业建立的，用来记录每个作业的页表起址和页表长度，以进行内存分配和地址变化。作业表是整个系统一张。
4.3.3 地址转换和存储保护>

4.3.3 地址转换和存储保护 #

  • 物理地址 = 页面号 × 页表长度 + 页内地址

    分页式存储管理的地址转换

  • 地址越界保护

4.3.4 存储共享>

4.3.4 存储共享 #

  • 数据共享和程序共享
4.3.5 分配算法>

4.3.5 分配算法 #

4.3.6 分页式存储管理的优缺点>

4.3.6 分页式存储管理的优缺点 #

  • 优点：实现了离散存储

  • 缺点：

    1. 消除了外部碎片，但内部碎片仍然存在
    2. 在进行地址转换和存储保护时，需要有相应的硬件支持，增加了机器成本。
4.4 分段式存储管理>

4.4 分段式存储管理 #

在分区存储管理和分页式存储管理中，进程的逻辑地址空间是按线性排列的。虽然，分 区存储管理或分页式存储管理可以把程序划分成区或页，但这些区或页与源程序的公用子程 序和数据毫无逻辑关系，而公用子程序和数据的共享则要求信息在逻辑上是完全的，因而， 这两种方式难以将用户给定的程序名和数据块名与这些被共享进程的程序和数据的区或页对应起来。

4.4.1 基本原理>

4.4.1 基本原理 #

  • 根据逻辑划分段，每个段都有自己的名字
  • 与分页式存储管理相比，分段式存储管理有两个 显著的特征：
    1. 在分页式存储管理中，内存中的页面号递增排列，地址空间属于一维结构，而在分段式存储管理中，段号在内存中的分区之间无任何顺序关系，地址空间属于二维结构；
    2. 在分页式存储管理中，每个页的长度固定，而在分段式存储管理中，为了确保信息在逻辑上是完整的，段的长度可变。分段式存储管理为进程的每一段分配一个连续的内存空间，而各个段之间并不要求一定连续。
4.4.2 地址转换和存储保护>

4.4.2 地址转换和存储保护 #

image-20230326110825467

4.4.3 存储共享>

4.4.3 存储共享 #

段的共享是指在多道程序设计环境下，用户进程需要共享内存中的某段程序或数据时，只要使用相同的段名，在其段表中填入已存在于内存之中的段基址，便可实现逻辑上完整的信息共享

4.4.4 分段式存储管理的优缺点>

4.4.4 分段式存储管理的优缺点 #

  • 优点

    1. 信息共享

      在实现指令和数据的共享时，常常需要以信息的逻辑单位基础，而分页式存储管理中的每一页只是存放信息的物理单位，其本身没有完整的意义，因而不便于实 现信息的共享，而段却是信息的逻辑单位，有利于实现信息的共享；

    2. 动态增长

      在实际的系统中，往往有些数据段会不断地增长，而事先却无法知道 数据段会增长到多大，分段式存储管理可以较好地解决这个问题。

    3. 动态连接

      动态连接是指在进程运行之前，并不把几个目标程序段都连接起来， 而是先将主程序对应的目标程序装入内存并启动运行，当运行过程中又需要调用某段时，再将该段（目标程序）调入内存并连接起来。

    4. 提供了内存和外存统一管理的虚存实现方式。

  • 缺点

    1. 需要有更多的硬件支持，提高了机器成本；
    2. 存在外部碎片
    3. 缺段中断处理以及允许段的动态增长会给系统增加难度和开销。
4.5 段页式存储管理>

4.5 段页式存储管理 #

分段式存储管理是基于用户程序结构的存储管理技术，有利于模块化程序设 计，便于内存信息的共享，但往往会产生碎片问题；

分页式存储管理是基于系统存储器结构的存储管理技术，可以避免产生外部碎片，但不易实现存储共享。

段页式既具有分页式存储管理有效避免产生外部碎片的优点，又具有分段式存储管理能很好实现共享存储的长处

4.5.1 基本原理>

4.5.1 基本原理 #

  1. 先将整个内存划分成大小相等的、位置固定的页面
  2. 再把进程按逻辑关系分为若干个段，并为每个段赋予一个段名
  3. 最后把每段的线性地址空间划分成与页面大小相等的页

image-20230326110950039

作业表整个系统一张，用于记录系 统中所有作业的段表的起始地址；

段表每个作业一张，用于记录该作业的所有段以及每段的页表的起始地址；

页表每个段一张，用户记录该页是否在内存、所对应的内存页面号。

4.5.2 地址转换>

4.5.2 地址转换 #

段页式存储管理的地址变换

4.5.3 段页式存储管理的优缺点>

4.5.3 段页式存储管理的优缺点 #

段页式存储管理具有分页式存储管理和分段式存储管理的优点。但是，反过来说，所需的硬件支持、复杂性和系统开销也会随之增加。在地址转换过程中，如果不采用快表提高地址转换速度，那么 CPU 的执行速度将大大下降。

4.6 虚拟存储管理>

4.6 虚拟存储管理 #

当一个进程在执行过程中，若需要访问的指令和数据在内存中，则继续执行；若不在内存中，则系统将把这部分信息自动调入内存，称为部分装入；若内存中没有足够多的空闲区，则系统需把内存中暂时不用的信息从内存中调出，称为部分对换。

4.6.1 虚拟存储器的概念>

4.6.1 虚拟存储器的概念 #

  • 虚拟存储器是指：具有自动实现部分装入和部分对换功能，能只把进程的 一部分装入内存便可运行，从逻辑上，是对内存容量进行扩充的一种虚拟的存储器系统。

  • 虚拟存储器的逻辑容量由内存和外存容量之和所决定

  • 时两进程P1，P2通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度，进程P1，P2之间的通信满足如下条件：问。（连续存储）

  • 抖动现象：增加内存分配也不能显著减少内存和外存之间的交换次数。或者是，页面在内存与外存之间频繁调度，以至于调度页面所需时间比进程实际运行时间还多，此时系统效率急剧下降，导致系统崩溃。

4.6.2 请求分页式虚拟存储管理>

4.6.2 请求分页式虚拟存储管理 #

image-20230326111307066

image-20230326111318320

4.6.3 请求分段式虚拟存储管理>

4.6.3 请求分段式虚拟存储管理 #

image-20230326111429395

4.6.4 请求段页式虚拟存储管理>

4.6.4 请求段页式虚拟存储管理 #

4.7 页面置换算法>

4.7 页面置换算法 #

4.7.1 最佳置换算法（OPT）>

4.7.1 最佳置换算法（OPT） #

  • 每次选择以后永不使用，或者最长时间内不再被访问的页面
  • 可以保证最低的缺页率，但是实际使用时是无法实现的，因为操作系统无法提前预判各个页面的访问序列
4.7.2 先进先出置换算法（FIFO）>

4.7.2 先进先出置换算法（FIFO） #

  • 淘汰最早进入内存的页面
  • 会产生belady异常
4.7.3 最近最久未使用置换算法（LRU）>

4.7.3 最近最久未使用置换算法（LRU） #

  • 淘汰最近最久未使用的页面
4.7.4 最少使用（LFU）>

4.7.4 最少使用（LFU） #

  • 看前面使用次数
4.8 页面分配策略>

4.8 页面分配策略 #

image-20220702111317440

4.8.1 驻留集>

4.8.1 驻留集 #

  • 驻留集：请求分页存储管理中心给进程分配的物理块的集合

    • 太小：缺页频繁（极端情况：每次调页都会缺页中断）
    • 太大：并发度下降（极端情况：全部页面都在内存中）

  • 分配策略

    image-20220702111936243

    • 固定分配：驻留集大小不变
    • 可变分配：驻留集大小根据进程实际运行情况改变
    • 局部置换：发生缺页时只能选进程自己的物理块进行置换
    • 全局置换：发生缺页时可以将操作系统保留的空闲物理块或者其他进程的物理块分配给缺页进程
    • 可变分配全局置换：只要某进程发生缺页后，都将获得新的物理块，如果这个新的物理块来自其他的进程，则会导致这个被选中的进程的缺页率增加。
    • 可变分配局部置换：操作系统根据该进程的缺页率，适当增减驻留集
4.8.2 调入策略>

4.8.2 调入策略 #

  • 调入页面的时机

    1. 预调页策略

      主要用于进程的首次调入，由程序员指出应该先调入哪些部分

    2. 请求调页策略

      进程运行期间使用，每次只掉一页，IO开销大

  • 从外存中的何处调入页面

    • 对换区（连续分配，速度快，容量小）
      • 进程运行前需要从文件区复制需要的数据到对换区
    • 文件区（离散分配，速度慢，容量大）
      • 不会被修改的数据
4.8.3 抖动、颠簸>

4.8.3 抖动、颠簸 #

  • 现象：刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存

  • 原因：分配给进程的物理块不够

4.8.4 工作集>

4.8.4 工作集 #

  • 指在某段时间间隔内，进程实际访问页面的集合
  • 根据工作集的大小确定驻留集的大小
5. 文件系统>

5. 文件系统 #

它由文件和目录两个部分组成，文件用于存储用户和系统的程序和数据； 目录用于组织系统内的文件，并提供有关文件的信息。对用户而言，文件系统最重要的功能之一就是 通过“按名存取”的方式来实现对文件信息的存储和检索，使得用户能透明地存储和访问文 件，只关心文件操作和逻辑结构，不涉及文件的存储结构。

5.1 文件和文件系统>

5.1 文件和文件系统 #

5.1.1 文件概念>

5.1.1 文件概念 #

  • 逻辑结构：按名存取
  • 物理结构：把用户对文件操作请求转换为对存储介质上信息所在的位置的各种操作
  • 文件是在逻辑上具有完整意义的信息集合
  • 文件是逻辑外存的最小分配单元。数据除非写入文件中，否则不能存储到外存
  • 文件可存储多种不同类型的信息
  • 数据项：描述对象的属性
  • 记录：是一组相关域的集合，是在逻辑上具有独立含义的最小信息单位。
  • 文件：一组相关记录的集合
  • 数据库：相关数据的集合
5.1.2 文件命名>

5.1.2 文件命名 #

  • 文件名.扩展名
  • 通配符：？> 字符串 * > 字符
5.1.3 文件类型>

5.1.3 文件类型 #

  • 在Windows系统中，扩展名表示文件类型
  • 在Linux中，文件的内容决定文件类型
5.1.4 文件属性>

5.1.4 文件属性 #

  • 所有文件的属性信息都保存在目录结构中，但由于目录和文件一样，是易失性的。因此，目录结构必须保存在外存上。
5.1.5 文件系统的概念>

5.1.5 文件系统的概念 #

  • 早期的计算机系统没有文件系统，大容量直接存取的磁盘存储器的问世，导致了文件系统的出现，它是一组系统软件。
  • 功能
    1. 以统一的方式对磁盘等外存进行统一管理；
    2. 目录管理，实现文件的按名存取；
    3. 实现文件从逻辑结构到物理结构的转换；
    4. 实现文件信息的共享，并提供文件的保护和加密措施；
    5. 向用户提供接口，方便使用文件操作。
5.2 文件组织、存取方法和存取设备>

5.2 文件组织、存取方法和存取设备 #

5.2.1 文件的逻辑结构>

5.2.1 文件的逻辑结构 #

  1. 字符流式的无结构文件

    • 如：.txt
    • 通常按长度来读取所需信息，可以使用特殊字符作为分界

  2. 记录式的有结构文件

    • 使用者的每次操作总是以一个逻辑记录为对象
    • image-20220702130120991
    • 常见的记录式的有结构文件有：堆、顺序文件、索引顺序文件、索引文件和直接文件。
5.2.2 文件的物理结构>

5.2.2 文件的物理结构 #

  • 构造文件的物理地址

    • 计算法：根据键和映射函数，计算出物理地址
    • 指针法：设置专门的指针，指明相应记录的物理地址或各记录之间的关联。

  • 文件物理结构和组织方法：顺序文件、连接文件、索引文件和直接文件

    1. 顺序文件

      image-20220702131654210

      • 逻辑上连续的信息物理上也连续
      • 优点
        1. 存取速度快
        2. 当文件是定长记录文件时，还可以随机访问
      • 缺点
        1. 事先确定文件长度，不利于文件动态增长
        2. 要求分配连续的存储空间
        3. 分配的物理块中会产生碎片
        4. 对文件进行增删比较困难
      • 综上，不适合存放用户文件、数据库文件等经常被修改的文件。

    2. 连接文件（串联文件）

      • 文件放在用指针连接的离散的物理块中
      • 优点
        1. 文件长度可动态增长
        2. 增删容易
      • 缺点
        1. 搜索效率低
        2. 不适合随机存取

    3. 索引文件

      image-20220702131927046
      image-20220702132243301

      • 优点：
        1. 动态增长
        2. 增删容易
        3. 随机存取
      • 缺点
        1. 增加存储开销
        2. 访问外存次数多

    4. 直接文件（连接文件）

      直接文件使用散列法或杂凑法（Hash 法），在直接存取存储设备上，把记录的关键字与其地址之间建立某种对应关系，以便实现快速存取。使用 hash 技术需要建立一张 hash 表，一个 hash 表是一个指针数组，数组通过索引访问，数组元素中的指针指向数据记录。

5.2.3 文件的存取方法>

5.2.3 文件的存取方法 #

常用的存取方法有三种：顺序存取、随机存取和索引存取。

  1. 顺序存取
  2. 随机存取
  3. 索引存取
5.2.4 文件的存储设备>

5.2.4 文件的存储设备 #

存储设备的特性决定了文件的组织和存取方法

  1. 存储设备

    1. 顺序存取设备（磁带）

    2. 直接存取设备（磁盘）

      存取设备、物理结构和存取方法间的关系

  2. 卷和块

5.3 文件目录>

5.3 文件目录 #

  1. 文件名
  2. 文件名到文件物理块的转换
  3. 文件名和结构信息的组织结构
  4. 文件说明
  5. 文件控制块
  6. 文件目录和目录文件
5.3.0 文件控制块（FCB）>

5.3.0 文件控制块（FCB） #

  • 文件控制块是按名存取的前提
  • image-20220702144531308
5.3.1 一级目录结构>

5.3.1 一级目录结构 #

image-20220702145102572

5.3.2 二级目录结构>

5.3.2 二级目录结构 #

image-20220702145120566

5.3.3 树形目录结构>

5.3.3 树形目录结构 #

image-20220702145141778

缺点：

  1. 不便于实现文件共享
5.3.4 无环图目录结构>

5.3.4 无环图目录结构 #

image-20220702145627362

5.3.5 索引结点（FCB的改进）>

5.3.5 索引结点（FCB的改进） #

image-20220702145849555

5.4 文件共享与保护>

5.4 文件共享与保护 #

5.4.1 文件共享>

5.4.1 文件共享 #

文件共享的实现方式有：系统目录实现方式、连接实现方式和符号连接方式。

  1. 系统目录实现方式

    • 用户通过全路径名共享地访问共享文件

    • image-20220702150921767

    • 缺点

      无法实现共享文件的动态增长。假设用户 A 和用户 B 通 过系统目录方式实现了对文件 F 的共享。当用户 A 对文件 F 进行修改，使其长度由原来的 20K 增加到 60K 时，对用户 B 而言，自己的目录项中关于文件 F 的长度信息并没有改变， 因而无法实现共享文件的动态增长。也就是说用户 A 对文件 F 增加了新的内容，用户 B 却看不到增加的内容。

  2. 连接实现方式（是基于索引节点的共享方式）

    image-20220702150320240

    缺点：某个用户删除共享文件时，容易造成其他共享用户的指针悬空。

    ※根据王道考研课的讲述：只有在count==0时才会允许删除文件，一般情况下，其中一个用户把文件删除，删的只是指向该索引结点的指针，即删除指向文件的指针。

  3. 符号连接方式

    • 类似于Windows的快捷方式
5.4.2 文件保护>

5.4.2 文件保护 #

一般可以使用以下四种文件保护方式：存取控制矩阵、存取控制表、 密码方式和加密方式。

  1. 存取控制矩阵

    • 在理论上是可行的，但实现上确有困难。当一个系统用户 数和文件数很大时，访问控制矩阵将会变得非常庞大，既占用了大量的内存空间，还会加重 使用文件时对访问控制矩阵扫描所带来的时间开销。
    • image-20220702151512223

  2. 存取控制表

    分组管理

    image-20220702152137088

  3. 口令方式

    • 两种方式：

      1. 是当用户进入系统，为建立终端进程时获得系统使用权的口令。如果用户输入的口令与原来设置的口令不一致的话，该用户将被系统拒绝。
      2. 每个用户在创建文件时，为每一个创建的文件设置一个口令，且将其置于文件说明中。 当任一用户想使用该文件时，都必须提供口令。只有当口令匹配时才能对文件进行存取。

    • 优点：简单，占用的内存空间以及验证口令所需的时间少。

    • 缺点

      1. 用户需要记住的口令数量过大，以致这种方案不可行；
      2. 如果所有文件只使用一个口令，那么它一旦被发现，所有文件都将被访问。

  4. 加密方式

    • 在用户创建源文件并将其写入存储设备时 对文件进行编码加密，在读出文件时对其进行译码解密。
    • 与口令方式相比，加密方式中使用的密钥没有存放在系统中，由用户自己保管，具有 保密性强的优点。
5.5 文件系统其他功能的实现>

5.5 文件系统其他功能的实现 #

5.5.1 文件操作>

5.5.1 文件操作 #

  • 操作命令
    • DOS 系统中的 dir，cd，copy，del，attrib，men
  • 系统调用
    • 增删查改
5.5.2 文件系统的层次结构>

5.5.2 文件系统的层次结构 #

文件系统的层次模型

5.5.3 外存空间管理>

5.5.3 外存空间管理 #

外存空间中空闲块的管理可以采用以下方式：（1）空闲块表；（2）空闲块链表；（3） 成组空闲块链；（4）位示图。

  1. 空闲块表

    • 此表包含两个登记项：该空闲区的第 一个盘块号和盘块总数。
    • 空闲块表的分配算法有最先适应算法、最佳适应算法和最坏适应算法。

  2. 空闲块链表

    • 删除文件时，释放该文件所占用的空闲块，并把这些块挂到空闲块链表上。这种方法效率很低，因为每次申请一块块都要读出空闲块并取得指针，申请多块时要多次读盘
    • 便于文件动态增长和收缩

  3. 成组空闲块链

  4. 位示图

    优点是可以把位示图全部或大部分保存在主存中，再配合计算机具有的位操作指令，可实现高速物理块分配和回收。

5.5.4 虚拟文件系统>

5.5.4 虚拟文件系统 #

  • 虚拟文件系统要实现以下目标：应同时支持多种文件系统；系统中可以安装多个文件系 统，它们应与传统的单一文件系统没有区别，用户的使用接口不变；对网络共享文件提供完 全支持，即访问远程结点上的文件系统应与访问本地结点的文件系统一致；支持开发出新的 文件系统，以模块方式加入到操作系统中
  • 虚拟文件系统并不是一种实际存在的文件系统，它只存在于内存中，不存在 于外存空间，在操作系统启动时建立，在系统关闭时消亡。
6. 设备管理>

6. 设备管理 #

数据传输方式

image-20220703231124698

  1. 程序直接控制方式
  2. 中断控制方式
  3. DMA
  4. 通道
习题>

习题 #

第一章 习题>

第一章 习题 #

1. 判断以下命题是否正确，并说明理由。>

1. 判断以下命题是否正确，并说明理由。 #

  1. 设计操作系统的主要目标是什么？

    1. 方便性：使计算机更易于用户使用。
    2. 有效性：以有效的方式管理计算机系统的资源，合理地组织计算机的工作流程， 以防止对计算机资源的不当或错误使用。这是操作系统可用的关键因素。
    3. 可扩展性：为用户的的开发搭建一个平台，允许修改、并引进新的功能。 操作系统为计算机上所有软件的性能提高提供了平台，另外，操作系统提供了一系列功能用以支持用户程序的运行。

  2. 操作系统的基本功能是什么?

    1. 操作系统是用户和计算机硬件之间的接口。
    2. 操作系统是计算机系统资源的管理者。
    3. 操作系统用作扩充机器，使得裸机功能更强、更方便使用。

  3. 多道批处理系统形成和发展的主要动力是什么？

    计算机体系的不断发展，需要不断提高计算机资源的利用率和系统吞吐量的需要。

  4. 推动分时操作系统形成和发展的主要动力是什么？

    为了满足用户对人机交互的需求，出现了分时系统。

  5. 操作系统的结构大致可分为哪几类？UNIX 的结构有什么特点？

    三类：整体、分层、微内核

    UNIX是分层结构

    • 优点
      • 增加了系统的可读性和可适应性，简化了系统的设计和实现。
      • 易于调试、修改、扩充、维护和保证正确性。
    • 缺点
      • 操作系统的效率不高。
      • 层的定义较为困难。
第二章 习题>

第二章 习题 #

1. 判断以下命题是否正确，并说明理由。>

1. 判断以下命题是否正确，并说明理由。 #

  1. 多道程序设计的目的是为了提高程序员编制程序的效率。

    错。多道程序是为了充分发挥CPU和计算机系统部件并进行工作的能力，从而提高CPU的利用率。

  2. 采用多道程序设计，能充分发挥处理机的使用效率，缩短每个进程的周转时间。

    错。周转时间是指从作业提交到作业完成之间的时间间隔，有一些短进程可能由于进程调度方式，导致其等待时间增加，相比于单独处理它，短进程的周转时间增加了。

    因此只能说是缩短平均周转时间，而不是每个进程的周转时间。

  3. 操作系统的设计必须要保证进程具有可再现性。

    错。可再现性是指：程序只要初始条件相同，运行结果一定相同，即运行结果与执行速度无关。单道程序的顺序执行必须保证可再现性，但是在多道程序并发执行的条件下，可再现性无法保证，取而代之的是不确定性，也许程序的运行结果相同，但是执行速度是不确定的。

  4. 进程控制块是进程存在的唯一标识。

    对。PCB提供了几乎所有管理进程的所需信息，标识了进程的存亡。

  5. 只有在某些条件成立时才可能发生进程调度。

    对。进程调度是指进程由活跃就绪态转换为运行态的过程。在等待的事件得到满足或者处于静止就绪态并且内存空闲已经有大片空闲时，会由其他状态转为活跃就绪态，进而发生进程调度，获得处理机，进入运行态。

  6. 中级调度即从就绪队列中选择一个进程，分配处理机使其运行。

    错。中级调度负责静止态和活跃态的转换，分配处理机是进程调度（低级调度）所需要负责的事

2. 单项选择题>

2. 单项选择题 #

  1. 在单处理机的多进程系统中，进程什么时候占用处理机和能占用多长时间取决于（ ）。

    A、进程相应的程序段的长度 B、进程总共需要运行时间多少

    C、进程自身和进程调度策略 D、进程完成什么功能

  2. 进程自身决定（ ）。

    A、从执行状态到阻塞状态 B、从执行状态到就绪状态

    C、从就绪状态到执行状态 D、从阻塞状态到就绪状态

  3. 下列选项中，导致创建新进程的操作是：（ ）。

    1、用户登录成功

    2、设备分配

    3、启动程序执行

    A、仅 1 和 2 B、仅 2 和 3

    C、仅 1 和 3 D、1、2、3

  4. 在支持多线程的系统中，进程 P 创建的若干个线程不能共享的是（ ）。

    A、进程 P 的代码段 B、进程 P 中打开的文件

    C、进程 P 的全局变量 D、进程 P 中某线程的栈指针

  5. 下列选项中，降低进程优先权级的合理时机是（ ）。

    A、进程的时间片用完 B、进程刚完成 I/O，进入就绪队列

    C、进程长期处于就绪队列 D、进程从就绪态转为执行态

  6. 设有 3 个作业 J1、J2、J3，其运行时间分别是 2、5、3 小时，假定它们同时到达，并 在同一台处理器上以单道方式运行，则平均周转时间最小的执行序列是（ ）。

    A、J1、J2、J3 B、J3、J2、J1 C、J2、J1、J3 D、J1、J3、J2

3. 填空题>

3. 填空题 #

  1. 建立多进程的主要目的是提高 CPU 的利用率。
  2. 在多进程多线程系统中，资源分给 进程，CPU 按 线程 调度。
  3. UNIX 进程控制块由 proc 和 user 构成。
  4. UNIX 进程的上下文由 用户级 、 寄存器 和 系统级 三个层次的内容构成。
  5. UNIX 进程可在 用户态 态和 核心态 态下执行。至于具体处于何种态是由 PCB 中相应位决定的。
  6. 决定 UNIX 进程状态的 proc 数据项有：p_stat 、p_flag 和 p_pri 。
4. 什么是多道程序设计，其主要优点是什么？>

4. 什么是多道程序设计，其主要优点是什么？ #

多道程序设计：指允许让多个计算问题同时装入一个计算机系统的主存储器，并允许它们共享资源、并发执行的程序设计技术。

优点：

  1. 并发：提高CPU和外围设备、外围设备和外围设备间的并行工作能力
  2. 资源共享：提高CPU及其他各种资源的利用率。
5. 程序并发执行时失去程序的封闭性的主要原因是什么？>

5. 程序并发执行时失去程序的封闭性的主要原因是什么？ #

并发执行的程序不再是独占资源，而是资源共享，而这些资源的状态受多个程序影响，进而程序间产生了某种联系，因此失去了封闭性，同时也失去了可再现性

6. 何为进程？系统为了控制进程的运行，都要保护什么？>

6. 何为进程？系统为了控制进程的运行，都要保护什么？ #

进程是一个程序在某个数据集上的一次执行；

保护进程的PCB（PCB的内容）

image-20220427200753099

7. 比较作业和进程的异同。>

7. 比较作业和进程的异同。 #

作业与进程之间的区别

  1. 本质

    作业就是用户要求计算机完成的一项任务；

    进程是系统为了完成作业而设置的动态执行体。

  2. 资源

    作业中的作业说明书事先说好了资源的分配关系，这是静态的；

    进程是操作系统分配资源的基本单位，这是动态的。

  3. 作业和进程的对应关系

    一个进程对应一个作业

    一个作业需要多个进程

8. 比较进程和程序的异同。>

8. 比较进程和程序的异同。 #

  1. 考虑动态性

进程是程序的一次执行过程，进程是一个动态概念；

而程序是完成某个特定功能的指令的有序序列，即程序是一个静态概念。

程序是代码的集合，而进程是程序的执行。

程序可以作为一种软件资源长期保存，可以被复制，可以在不同的计算机上运行；

而进程，是有生命周期的，它动态地被创建，并被调度执行后消亡。

  1. 考虑并发性

进程具有并发特征，而程序没有。由于一个进程可以与其他进程并发执行，即进程具有并发性；而程序并不反映执行过程，所以不具有并发特征。

  1. 考虑资源

进程是系统进行资源分配和调度的一个独立单位，即资源分配是以进程为单位的，而不是以程序为单位的。

  1. 考虑结构

程序的组成是代码，而进程实体的组成包括：程序、数据和 PCB。

  1. 考虑生成性

进程可以生成其他进程，而程序则无法生成新的程序。

  1. 考虑对应关系

一个程序多次执行可以对应多个进程；通过调用关系，一个进程也可以包括多个程序。

9. 在创建和撤销一个进程时所要完成的主要工作是什么？>

9. 在创建和撤销一个进程时所要完成的主要工作是什么？ #

  • 在创建和撤销一个进程时所要完成的主要工作是什么？

    • 进程创建：
      1. 申请空闲PCB
      2. 分配资源
      3. 初始化PCB的信息
      4. 将新进程插入就绪队列
    • 撤销进程：
      1. 修改该进程的状态，设置重新调度标志
      2. 检测子孙进程，递归终止
      3. 递归归还资源
      4. 递归释放PCB
      5. 若重新调度标志位真，调用进程调度程序，重新分配处理机

  • 当进程 A 由于所分配的时间片到，由执行状态转入就绪状态；而进程 B 被调度程序选中由就绪状态转为执行状态时，系统所要做的主要工作是什么？

    将A的状态改为就绪态，并剥夺其CPU，将其放入就绪队列；

    将B的状态改为执行态，将其移出就绪队列，并分配CPU。

11. 处理机调度分为几级？每一级调度的主要任务是什么？>

11. 处理机调度分为几级？每一级调度的主要任务是什么？ #

四级

  1. 作业（高级）调度

    按一定的原则，从输入井中选择一个作业（或一批作业），将其 调入内存、分配必要的资源，并为其建立相应的进程，以使该（批）作业具有竞争 CPU 的 资格；当然，作业执行完毕时，作业调度还需负责回收系统资源。

  2. 交换（中程）调度

    按照一定的原则，将处于外存对换区中具备运行条件的就绪进程调入内存；或者，将处于内存中阻塞状态或者就绪状态的进程换出到外存交换区。

  3. 进程（低级）调度

    是按照一定的策略，选取一个处于活跃就绪状态的进 程占用 CPU 并进行进程的上下文切换。

  4. 线程调度

    对于内核级线程调度，其实质与调度的策略都与进程调度十分类似，因此也有人并不对进程调度与内核级线程调度进行区分，而把内核级线程调度也称为短程调度或低级调度。

13. 列出 3 个引起进程阻塞和唤醒的事件，并写出唤醒原语的执行步骤。>

13. 列出 3 个引起进程阻塞和唤醒的事件，并写出唤醒原语的执行步骤。 #

(1) 向系统请求共享资源失败。 (2) 等待某种操作的完成。 (3) 新数据尚未到达。 (4) 等待新任务的到达。

操作步骤

  1. 找出标识

  2. 从阻塞队列移出

  3. 设置为就绪态

  4. 插入就绪队列

  5. 考虑被唤醒进程和当前运行进程的优先级

    若被唤醒进程优先级更高则需要设置调度标志，并转进程调度程序。

19. 若系统中运行的主要是这 2 类进程，采用什么调度算法更有利于资源的利用率？为什么？>

19. 若系统中运行的主要是这 2 类进程，采用什么调度算法更有利于资源的利用率？为什么？ #

将“I/O 为主”的进程定义为：当此类进程单独运行时，用于 I/O 处理的时间远远多于 处理机的处理时间。将“计算为主”的进程定义为：当此类进程单独运行时，处理机的处理时间远远多于处理的时间。若系统中运行的主要是这 2 类进程，采用什么调度算法更有利于资源的利用率？为什么？

以IO为主的进程可以理解为短进程，因为每次IO处理完之后都会重新排队

以计算为主的进程可以理解为长进程。

多级反馈队列可以有效兼顾长短进程

20. 采用“抢先方式的最高优先级”调度算法，回答以下问题：>

20. 采用“抢先方式的最高优先级”调度算法，回答以下问题： #

某多道程序设计系统中配有一台处理器 CPU 和两台输入输出设备 I/O1 和 I/O2，现有优先级由高到低的三个进程 P1、P2、P3 同时存在，它们使用资源的先后次序和占用时间分别是： 进程 P1：I/O2（30ms），CPU（10ms），I/O1（30ms），CPU（10ms），I/O2（10ms）； 进程 P2：I/O1（20ms），CPU（20ms），I/O2（40ms）； 进程 P3：CPU（30ms），I/O1（20ms）。 若进程调度采用“抢先方式的最高优先级”调度算法，且忽略调度等所需要的时间， 回答以下问题：

  1. 进程 P1、P2、P3 从开始到完成所用的时间分别是多少？（用坐标画出进程 P1、 P2、P3 工作过程，其中横坐标表示时间，纵坐标表示 CPU 和 I/O 设备。）

  2. 三个进程从开始到全部结束完成时 CPU 的利用率是多少？I/O 利用率是多少？

    img

22. 采用最短周期优先调度算法，回答以下问题>

22. 采用最短周期优先调度算法，回答以下问题 #

假定有一组作业（或进程），它们提交时间及要求运行的时间如下表所示（单位为小时， 并以十进制计）

image-20220427194312013

如果采用最短周期优先调度算法，计算出该组作业的平均周转时间 T=1.725 小时和平均带权周转时间 W=6.875 小时。对吗？为什么？

作业号提交时间运行时间等待时间完成时间周转时间代权周转时间
18:002010:0021
39:000.1110:061.111
49:500.216/6010:1828/602.33
28:500.588/6010:48108/603.6
平均值0.7754.4825
23. 求在采用如下算法时进程的平均周转时间和平均带权周转时间。>

23. 求在采用如下算法时进程的平均周转时间和平均带权周转时间。 #

下表列出了五个进程的执行时间和优先数，规定优先数越小优先级越大，在某时刻这五个进程按照 P0、P1、P2、P3、P4 的顺序同时到达，求在采用如下算法时进程的平均周转时间和平均带权周转时间。（调度方式为非抢先方式，且忽略进程调度所花时间。）

image-20220427194438076

  1. 先来先服务调度算法；

    先来先服务
    进程名提交时间运行时间等待时间完成时间周转时间代权周转时间
    P0020020201
    P10152035352.333333333
    P20353570702
    P30257095953.8
    P4040951351353.375
    平均值712.501666667

  2. 最短周期优先调度算法；

    最短周期优先
    进程名提交时间运行时间等待时间完成时间周转时间代权周转时间
    P0020020201
    P10152035352.333333333
    P30253560602.4
    P20356095952.714285714
    P4040951351353.375
    平均值692.36452381

  3. 时间片轮转调度算法（时间片为 5ms）；

    时间片轮转
    进程名提交时间运行时间等待时间完成时间周转时间代权周转时间
    P0020801051051
    P101540352.333333333
    P20353570702
    P30257095953.8
    P4040951351353.375
    平均值712.501666667

  4. 最高优先级优先调度算法。

    优先级优先
    进程名提交时间运行时间等待时间完成时间周转时间代权周转时间
    P1015015151
    P30251540401.6
    P00204060603
    P20356095952.714285714
    P4040951351353.375
    平均值692.337857143
24. 计算平均周转时间>

24. 计算平均周转时间 #

下表给出作业 1、2、3、4 的到达时间和运行时间。请分别给出采用非抢先方式最短周期优先调度算法和先来先服务调度算法时作业调度次序，并计算平均周转时间。（时间单位： 小时，以十进制进行计算）

image-20220427194523549

最短周期优先
作业号提交时间运行时间等待时间完成时间周转时间代权周转时间
12:00204:0021
33:000.114:061.111
43:300.20.64:180.84
22:300.51.84:482.34.6
平均值1.555.15
先来先服务
作业号提交时间运行时间等待时间完成时间周转时间代权周转时间
12:002.004:0021
22:300.526:3048
33:000.13.56:363.636
43:300.23.16:483.316.5
平均值3.22515.375
第三章习题>

第三章习题 #

1. 判断以下命题是否正确，并说明理由。>

1. 判断以下命题是否正确，并说明理由。 #

  1. 如果 CPU 正在执行一个 Down 操作的时候，一个最高级中断到来，那么中断处理进程会抢夺 CPU。

    错。Down是原语操作，不可中断。

  2. 临界区是进程执行程序中对临界资源访问的那一段程序代码。

    对。临界区就是在进程中访问临界资源的那一段程序。

  3. 仅当一个进程退出临界区之后，另一个进程才能进入相应的临界区。

    对。临界区是用于访问临界资源的，临界资源必须是互斥访问的。

  4. 进程 A 与进程 B 共享变量 S1，需要互斥；进程 B 与进程 C 共享变量 S2，需要互斥。 从而，进程 A 与进程 C 也必须互斥。

    错。互斥没有传递性，进程A与进程C并不共享变量。

  5. 系统处于不安全状态必然导致系统死锁。

    错。死锁一定处于不安全状态，但系统处于不安全状态不一定导致系统死锁。

  6. 一个系统的状态如果不是死锁状态那么就一定是安全状态。

    错。不是死锁状态不代表现在不是不安全状态。

    死锁一定处于不安全状态，但系统处于不安全状态不一定导致系统死锁。

2. 单项选择题。>

2. 单项选择题。 #

  1. 在操作系统中，Down、Up 操作是一种（ ）。

    A、机器指令 B、系统调用命令 C、作业控制命令 D、低级进程通信原语

    进程通信类型包括低级通信和高级通信。 进程通信指进程之间的信息交换，进程同步所交换的信息量少，称为低级通信。

    高级进程通信是指用户可直接利用操作系统所提供的一组通信命令，高效传送大量数据的一种通信方式。

  2. 下列选项中，在用户态执行的是（ ）。

    A、命令解释程序 B、缺页处理程序 C、进程调度程序 D 时钟中断处理程序

    缺页处理程序和时钟中断都属于中断，在核心态执行。

    进程调度属于系统调用，在核心态执行。

    命令解释程序属于命令接口，在用户态执行。

  3. 设与某资源相关联的信号量初值为 3，当前值为 1，若 M 表示该资源的可用个数，N 表示等待该资源的进程数，则 M，N 分别是（ ）。

    A、0，1 B、1，0 C、1，2 D、2，0

    信号量表示相关资源的当前可用数量

  4. 某计算机系统中有 8 台打印机，有 K 个进程竞争使用，每个进程最多需要 3 台打印 机，该系统可能会发生死锁的 K 的最小值是（ ）。

    A、2 B、3 C、4 D、5

    每个进程3台，不会产生死锁；对于三个进程，可以有两个进程分别获得3台，使其执行完释放后让第三个进程获得3台，所以也不会产生死锁；对于四个进程，假若每个进程各获得2台而同时需要另外一台，产生了死锁，所以产生死锁的最小值是4。

    类似题型(1)：假设现在有P个进程，每个进程最多需要m个资源，并且有r个资源可用。什么样的条件可以保证死锁不会发生 解：如果一个进程有m个资源它就能够结束，不会使自己陷入死锁中。因此最差情况是每个进程有m-1个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某个进程就能够结束并释放它的所有资源．使其它进程也能够结束。所以避免死锁的条件是： r≥p(m-1)+1。 由此条件解上题：r=8，m=3，带入公式得：2p≤7。即当P小于等于3时才可保证死锁不会发生，所以可能会产生死锁的最小值是4。

    类似题型(2)：某系统中有3个并发进程，都需要同类资源4个，试问该系统不会发生死锁的最少资源数是多少 解：带入上述条件公式：r≥3*(4-1)+1=10。所以答案为10个。

3. 填空题>

3. 填空题 #

  1. 设系统有 10 个并发进程通过 Down、Up 操作原语共享同一临界资源，若该临界资源 互斥信号量为 Mutex，初值设置为 1，则 Mutex 的值域为（-9,1）。

    有m 个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问，则信号量的变化范围是(A )。 A.1 至–(m-1) B.1 至m-1 C.1 至–m D.1 至m

  2. 引起进程相互制约的 2 类原因是：直接制约 和 间接制约。

    image-20220420130940896

    解决临界区问题的一个必要条件是各个进程对于临界资源必须互斥使用，这些只由对临界资源的争用而引起的进程间的关系，构成了进程间的间接制约关系；（进程异步）

    相对应地，由于必须互相合作而呈现的直接的协同关系，则构成了进程间的直接制约关系。（进程同步）

  3. 为实现消息缓冲通信，在 PCB 中应增加 mq、mutex 和 sm 三个数据项。

    image-20220420131415826

  4. 进程通信有直接通信方式和间接通信方式，邮箱机制是一种 间接通信方式。

    邮箱机制是消息传递系统的一种，而且是一种间接通信方式。

  5. 当且仅当 S 状态的资源分配图是 不可化简的，S 为死锁状态。

  6. 对待死锁，一般应考虑死锁的预防、避免、检测和清除四个问题。典型的银行家算法 是属于避免 ，破坏循环等待条件是属于 预防，而抢占资源是 清除 的基本方法。

4. 什么是 Bernstein 条件？若并发执行的程序不满足 Bernstein 条件可能会失去哪些性质？>

4. 什么是 Bernstein 条件？若并发执行的程序不满足 Bernstein 条件可能会失去哪些性质？ #

Bernstein 条件是进程的执行与时间无关的一个充分条件，而非必要条件。

Bernstein 条件指出：如果并发执行的各程序段中语句或指令满足 Bernstein 条件，那么并发执行不会对执行结果的封闭性和可再现性产生影响。

如果不满足，则程序失去封闭性和可再现性

5. 什么是信号量？什么是信号量的 Down、Up 操作？如何利用信号量这两个操作来实施进程间的通信？>

5. 什么是信号量？什么是信号量的 Down、Up 操作？如何利用信号量这两个操作来实施进程间的通信？ #

信号量就是一种特殊的整型变量，该整型变量一般被用于描述资源的个数，因此一个信号量通常被初始化为一个非负整数。

Down、Up 操作是低级进程通信原语，对信号量执行减和加的操作，对应于资源的分配和释放。

每个进程各自有不同的用户地址空间,任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核,在内核中开辟一块缓冲区,进程1把数据从用户空间拷到内核缓冲区,进程2再从内核缓冲区把数据读走,内核提供的这种机制称为进程间通信机制。

信号量用来管理临界资源的。它本身只是一种外部资源的标识，不具有数据交换功能，而是通过控制其他的通信资源实现进程间通信。

就是两个进程共享信号量s，一旦其中一个进程执行了P(s)操作，它将得到信号量，并可以进入临界区，使s减1。而第二个进程将被阻止进入临界区，因为当它试图执行P(s)时，s为0，它会被挂起以等待第一个进程离开临界区域并执行V(s)释放信号量，这时第二个进程就被唤醒恢复执行了。

6. 举例说明若 Down、Up 操作不实现为原语，就不能实现对临界区的互斥。>

6. 举例说明若 Down、Up 操作不实现为原语，就不能实现对临界区的互斥。 #

如果进程P1在执行Down(s)时被中断，P2上处理机，那么P2就会让s=0，并顺利进入临界区，在P2访问临界区还没结束时，P1又上处理机，而此时P1将会继续执行Down操作，然后也顺利进入临界区，此时的临界区就有两个进程在同时运行，因此若 Down、Up 操作不实现为原语，就不能实现对临界区的互斥。

8. 说明同步、互斥的区别与联系。>

8. 说明同步、互斥的区别与联系。 #

区别：

  • 相互互斥的进程在逻辑上是无关的，不具有时间次序的特征，他们是因为对临界资源的争用而产生了间接制约的关系，而互斥便是解决进程间间接制约的手段；

  • 相互同步的进程，具有时间次序的特征，是相互合作而呈现的直接制约关系，同步便是解决进程间直接制约的手段

联系：

  • 互斥是一种特殊的同步。因为同步的进程在执行时间上必须基于某个条件按一定的顺序协调进行，互斥的进程也必须基于某个条件（即对共享资源的互斥访问）按一定的顺序协调进行，只不过是互斥的进程的这种顺序不是固定的，而是可以任意的（只要满足互斥）。
10. 请解释操作系统中“管道”和“管程”这两个名词。>

10. 请解释操作系统中“管道”和“管程”这两个名词。 #

管道，是指能够连接一个写进程和一个读进程、专门用于进程之间的数据通信的共享文件。

管程，是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。

12. 请用Down、Up 操作作为同步机制描述对应于计算进程和打印进程的程序。>

12. 请用Down、Up 操作作为同步机制描述对应于计算进程和打印进程的程序。 #

设有 N 个计算进程和 M 个打印进程共享同一个缓冲区，缓冲区的长度为 8。各计算进程不断地把计算得到的结果送入缓冲区，各打印进程不断地从缓冲区取数并打印。要求，既不漏打，也不重复打印任何一个结果，并且，为了提高工作效率，计算进程在使用缓冲区的同时，运行打印进程从缓冲区中取数，反之亦然。请用Down、Up 操作作为同步机制描述对应于计算进程和打印进程的程序。

int empty = 8;
int full = 0;
computer(){
	while(1){
        prepare a num;//生产数据
        P(empty);//申请空闲缓存空间
        add num to buffer;//将数据放入缓冲区
        V(full);//满缓冲区加一
    }
}
print(){
    while(1){
        P(full);
        remove a num from buffer;
        V(empty);
        print a num;
    }
}
20. 死锁产生的四个必要条件是什么？用于保证系统不会产生死锁的方法有哪些？>

20. 死锁产生的四个必要条件是什么？用于保证系统不会产生死锁的方法有哪些？ #

  1. 互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有，此时若有其他进程请求该资源，则请求进程只能等待
  2. 请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求时，该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放
  3. 不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)
  4. 循环等待条件: 若干进程间形成首尾相接循环等待资源的关系
  • 死锁检测与死锁恢复
  • 死锁预防，破坏4个必要条件
  • 死锁避免，银行家算法
21. 简述“死锁”与“饿死”。>

21. 简述“死锁”与“饿死”。 #

二者都是由于资源的争夺和资源的分配策略而引起的

不同点：

①从进程状态考虑，死锁进程都处于等待态（等待某一不可被剥夺资源被释放）,饿死进程可能处于忙式等待(就绪队列上等待可剥夺处理机资源)。（忙式等待：不进入等待状态的等待实际状态为”运行“或者”就绪“忙式等待空耗处理器资源因而是低效的,进程无法向前推进等待某一事件，但不主动放弃处理器而是不断循环检测资源是否可用）。

②死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源。

③死锁一定发生了循环等待，而饿死则不然，这也表明通过资源分配图可以检测死锁存在与否，但不能检测是否有进程饿死。

④死锁一定涉及多个进程·，而饥饿或被饿死的进程可能只有一个。

23. 某系统有同类资源 m 个，供 n 个进程使用；如果每个进程对资源的最大需求量为 k，>

23. 某系统有同类资源 m 个，供 n 个进程使用；如果每个进程对资源的最大需求量为 k， #

  1. 为使系统不发生死锁，k 的最大值为多少？

    如果一个进程有k个资源它就能够结束，不会使自己陷入死锁中。因此最差情况是每个进程有k-1个资源并且需要另外一个资源。如果留下有一个资源可用，那么其中某个进程就能够结束并释放它的所有资源．使其它进程也能够结束。

    因此，总共只有m个，要分给n个进程，最差的情况是每个进程都有k-1个资源并需要另外的资源，因此m >= n(k-1) + 1，k<=(m-1)/n+1

  2. 按（1）的结果，当 n=3，m 分别取值 2、3、4 时，对应的 k 值是多少，就可以使系统不发生死锁？

​ n=3,m=2 k<1/3+1 k=1

​ n=3,m=3 k<2/3+1 k=1

​ n=3,m=4 k<3/3+1 k=2

26. 请描述用于死锁避免的银行家算法的主要思想并列出其需要使用的数据结构，并简单分析这种算法能解决实际问题中的死锁吗？>

26. 请描述用于死锁避免的银行家算法的主要思想并列出其需要使用的数据结构，并简单分析这种算法能解决实际问题中的死锁吗？ #

  • 主要思想:

    允许进程动态地申请资源，但在系统在进行资源分配之前，应先计算此次资源分配的安全性，若此次分配会导致系统进入不安全状态，则将资源分配给进程；否则，令进程等待。

  • 数据结构共有七种：

    1. 向量 Available = ( V1, V2, …, Vm ) 用于表示系统初始可供使用的资源总数；
    2. 向量 Work = ( W1, W2, …, Wm ) 用于表示系统当前可供使用的资源总数，刚开始初始化为 Available 向量；
    3. 向量 Finish = ( F1, F2, …, Fn ) 用于表示 n 个进程被标记的情况，初始值为false，当某个进程获得所需的全部资源，并能释放全部资源时标记为ture；
    4. 矩阵Max[Mij]，其中矩阵中的元素 Mij表示第 i 号进程对第 j 类资源 的总需求数目；
    5. 矩阵Allocation[Aij]，其中矩阵中的元素 Aij 表示第 i 号进程当前分配的第 j 类资源的数目；
    6. 矩阵Need[Nij]其中矩阵中的元素 Nij 表示第 i 号进程还需要的第 j 类资源的数目；
    7. 向量Request = ( R1, R2, …, Rm ) 用于表示某个进程的某次资源请求，Ri表示该次请求的第 i 类资源的数量。

  • 这种算法能解决实际问题中的死锁吗？

    不能。

    因为假象条件太过理想，比如：预先知道进程需要的最大资源数。

28. 某系统有 4 类资源，有 5 个并发进程。各进程的最大资源请求和已分配的资源矩阵以及当前资源剩余向量如下表所示：>

28. 某系统有 4 类资源，有 5 个并发进程。各进程的最大资源请求和已分配的资源矩阵以及当前资源剩余向量如下表所示： #

image-20220421094557754
image-20220421094613987

image-20220421094650817

按银行家算法回答：

  1. 计算需求矩阵 Need。

    Need = Max - Allocation

    P00000
    P10750
    P21002
    P30020
    P40642

  2. 系统当前处于安全状态吗？

    P0可释放，回收资源 0 0 1 2，则剩余资源1,2,4,6

    分配给P2分配给P3
    回收资源2,3,5,60,6,5,2
    剩余资源3,5,9,121,8,9,8
    剩余P1，P4剩余P1，P4，对比剩余资源，可满足
    R2类资源剩余5分配给P1 分配给P4
    不满足P1和P4回收0,7,5,0 回收0,6,4,2
    不安全剩余1,15,14,8 剩余1,14,13,10
    分配给P4 分配给P1

    安全序列 0,3,1,4 或者 0,3,4,1

  3. 进程 P2 此时发出请求向量 Request(0, 3, 2, 0)，系统能立即满足吗？

    不能，P0释放后还剩余资源1,2,4,6，不满足P2的需求。

易错点>

易错点 #

  1. “访管”指令仅在用户态下使用，执行“访管”指令将用户态转变为核心态。因操作系统不允许用户直接执行某些“危险性高”的指令，因此用户态运行这些指令的结果会转成操作系统的核心态去运行。这个过程就是访管中断。

  2. 中断处理流程的前三个步骤是由硬件直接实现（隐指令）的。地址映射中需要基地址（或页表）寄存器和地址加法器的支持。而在时钟管理中，需要硬件计数器保持时钟的运行。

    中断处理流程：

    1. 中断请求

      1. 每个中断源向CPU发出中断的时机是随机的；
      2. 内中断不能被屏蔽，外中断有可屏蔽和不可屏蔽之分
      3. 为了记录这些中断事件和区分不同的中断源，中断系统为每一个中断源设置了一个中断请求标志触发器。如果某个中断源发出了中断，就将相应的标志触发器置为1；
      4. 对于外中断，CPU统一在每条指令执行阶段结束前向中断控制器发出中断查询信号，去查询是否有中断请求要去处理。

    2. 中断判优先级

      1. 如果有多个中断源发出了中断请求。则需要根据中断优先级选择优先级高的中断请求先进行响应
      2. 中断默认优先级是由一个硬件排队器来实现的
      3. 但是中断屏蔽字可以动态改变中断优先级。

    3. 中断响应

      1. CPU向中断源发出中断响应信号
      2. 关中断
      3. 保存断电（PC）
      4. 找到中断服务的入口地址（中断向量）

    4. 中断服务

      1. 保存现场：通用寄存器和状态寄存器和屏蔽字
      2. 开中断
      3. 中断处理过程
      4. 关中断
      5. 恢复现场
      6. 开中断
      7. 中断返回

    5. 中断返回

      1. 回到断电处
      2. 恢复硬件
      3. 继续执行原程序

  3. 中断程序本身可能是用户程序，但是进入中断的处理程序一定是OS程序。若被中断的是用户程序，则系统将从目态转入管态，在管态下进行中断的处理；若被中断的是低级中断，则仍然保持在管态，而用户程序只能在目态下运行，因此进入中断处理的程序只能是OS程序。

  4. 计算机通过硬件中断机制完成由用户态到核心态的转换，核心态到用户态的转换是由操作系统程序执行后完成的。

  5. 广义指令只能在核心态执行，广义指令就是系统调用。要分清调用和执行的区别，调用可能在用户态，执行一定在核心态。

  6. 特权用户程序能够执行特权指令，这句话是错的，只有操作系统程序可以。

  7. 下列选项中，不可能在用户态发生的事件是（C）。

    • 系统调用

    • 外部中断

    • 进程切换

    • 缺页

      1.系统调用可能在用户态和内核态发生，系统调用把应用程序的请求（用户态的请求）传入内核，由内核（内核态）处理请求并将结果返回给应用程序（用户态） 用户态->核心态

      2.中断的发生与CPU当前的状态无关，既可以发生在用户态，又可以发生在内核态，因为无论系统处于何种状态都需要处理外部设备发来的中断请求。

      3.进程切换在核心态下完成，不能发生在用户态。原因：需要调度处理器和系统资源，为保证系统安全?

      4.缺页（异常）也是用户态->内核态

      ABD（系统调用中断异常）都是用户态转向内核态，而进程切换只能发生在内核态

      所以选C进程切换

  8. 中断处理要保存而子程序不用保存的数据是PSW。因为子程序调用只需保存程序断点，即该指令的下一条指令的地址：中断处理不仅要保存断点(PC的内容)，还要保存程序状态字寄存器(PSW)的内容。在中断处理中，最重要的两个寄存器是PC和PSW。

  9. 整数除以0会触发异常，会使得进程从用户态转向核心态

  10. 外部中断处理过程，PC值由中断隐指令自动保存，而通用寄存器内容由操作系统保存。

  11. 从用户态到内核态，系统调用、中断、异常

  12. 执行系统调用的过程如下：正在运行的进程先传递系统调用参数，然后由焰入(trap)指令负责将用户态转换为内核态，并将返回地址压入堆栈以备后用，接下来CPU执行相应的内核态服务程序，最后返回用户态。

  13. 当CPU检测到中断信号后会做些什么？由硬件自动保存被中断程序的断点(即程序计数器PC)。之后，硬件找到该中断信号对应的中断向量，中断向量指明中断服务程序入口地址(各中断向量统一存放在中断向量表中，该表由操作系统初始化)。接下来开始执行中断服务程序，包括保存PSW、保存中断屏蔽字、保存各通用寄存器的值，并提供与中断信号对应的中断服务，中断服务程序属于操作系统内核。



↑