在复试时，很少问及计算题，大多数都是的问题都是和概念直接相关，所以要深刻理解操作系统各个组成部分的概念。

本篇主要归纳操作系统的基本概念以及进程相关概念和算法

操作系统基本概念

首先需要知道操作系统在整个计算机系统中的定位：

​ 计算机系统大致可以分为四个部分（自底向上）：计算机硬件 -> 操作系统 -> 应用程序软件 -> 用户。

从上述结构可以轻易看到，操作系统管理着计算机的各个硬件，具体表现为对资源的合理调度，分配等，同时也为上层应用程序软件提供抽象出来的硬件功能。

综上所述，操作系统可以定义为控制和管理整个计算机的硬件和软件资源，并合理地组织，分配资源、调度工作，进而为用户和其它软件提供方便接口与环境的程序集合。 提炼一下，操作系统就是一系列程序的集合，不过这些程序有着上述管理功能。

特征（四大特征）

  1. 并发 => 注意并发和并行的区别。
  2. 共享 （两种共享方式，也对应着后续会提到的资源共享形式）
    1. 互斥共享
    2. 同时访问
  3. 虚拟 => 用逻辑的对应物去映射实际的物理设备，让用户在使用时感觉是在真正使用物理设备。
    • 经典例子: 请求分页系统，SPOOLing技术
  4. 异步 => 进程以不可预知的速度向前执行（进程的异步性）
    • 异步也是操作系统中需要进程控制的原因之一，因为要保证怎么个异步法，各个进程的最终结果都一样。

其中，**并发和共享是其它特性的基础，**它们两也相互依存。

管理的计算机资源（包括硬件和软件）分类

  1. 处理机管理 => 进程的调度与分配
  2. 存储器管理 => 内存管理
  3. 文件管理 => 文件的存储形式：逻辑存储和物理存储
  4. I/O设备管理 => 外存相关概念以及相关管理

运行环境

  • CPU的状态分为两类：用户态（目态）和核心态（管态）
  • 用户的程序运行在目态，而操作系统的内核运行在管态。有一些特殊的特权指令，只有在CPU处于管态时才能调用。
    • 特权指令 -> 操作系统不允许用户直接调用的指令，比如I/O指令，置中断指令等等。
  • 如果说用户程序必须使用特权指令的功能，则需要通过中断或异常操作来达到目的，即发生中断或异常时，CPU状态会从用户态转向核心态。

中断和异常

操作系统的发展过程大体上就是一个想法设法不断提高资源利用率的过程，而提高资源利用率就需要在程序并未使用某种资源时，把它对那种资源释放，而这一行为就需要通过中断来实现。

中断（外中断）：CPU执行指令以外的事情发生而引起的中断，即外中断不是由指令本身引起的（比如访问数组越界等），而是外界因素导致的（比如I/O中断，时间片中断），它和当前处理机正在运行的程序有关。

异常（内中断，陷入trap）：CPU执行指令时发生的错误异常事件。比如地址越界，请求分页系统的缺页以及专门的陷入指令（这个也是上述用户能够主动进入核心态的办法，也称为系统调用）。

​ 系统调用的本质是用户把CPU的使用权交给了操作系统内核的程序，然后让内核程序去执行对应的特权指令，等执行完毕后，再把使用权返回。即关键指令的调用实质还是内核调用而不是用户直接调用。

进程管理

基本概念

  • 在多道程序运行的系统中，由于程序直接“暴露在内存里”，所以导致程序没有封闭性，它们能够彼此看见对方内部的结构，甚至调用，这显然是不行的。于是为了方便描述程序和控制程序的并发，体现操作系统的并发性和共享性，所以引入了进程的概念。
  • 进程（动态的）：是程序的一次执行过程（进程实体的运行过程），是CPU资源分配和调度的基本单位（引入线程之前）
    • PCB（Process Control Block）
    • 程序段
    • 相关数据段

状态

  1. 创建态
  2. 就绪态
  3. 运行态
  4. 终止态
  5. 阻塞态
  • 它们各自的定义这里不再描述。
  • 需要说明的是，当进程从运行态变换到阻塞态时，是一个主动的行为（即自己需要去请求某个外设资源或等待某一事件发生而引起的阻塞），这是一种特殊的，由运行的用户态程序去调用操作系统内核过程的形式。
  • 而从阻塞态转移到就绪态，这是一个被动过程，因为它需要外界信号进行触发。例如请求的外设已经完成了对应的任务，或是请求的某个资源已经空闲出来等。

进程通信

  1. 共享存储空间通信 -> 多个进程共享内存中的某块空间，当需要通信时，在内存中进行读写即可。
  2. 消息传递 -> 调用操作系统提供的消息传递方法进行进程通信，即通过发送消息和接受消息两个原语进行通信。
    1. 直接通信，即发送进程直接把消息发送给接收消息进程。
    2. 间接通信，即发送进程把消息发送给某个中间实体，使其成为一个信箱，而接受进程直接从实体中取消息即可，反之亦然。
  3. 管道通信 -> 由pipe文件来连接发消息进程和接受消息进程从而达到通信的目的。（消息查看2022王道考研操作系统P35）

线程

由于进程的切换会有较大的时空开销，于是考虑引入线程，从而提高系统的并发性能（因为线程切换所引起的时空开销要远远小于进程）。

  • 线程是轻量级的进程，它是CPU的执行单位。需要值得注意的是，**线程本身不占有资源，它共享它所在的进程的资源，**即进程的资源被它拥有的线程所共享。
  • 在引入线程的系统里，进程仅仅作为系统资源分配的基本单位，而线程则成为了处理机的分配单元。

实现方式

  1. 用户级线程（User-Level Thread: ULT）
    • 线程的管理全部由用户程序来实现，内核意识不到线程的存在。
  2. 内核级线程（Kernel-Level Thread: KLT)
    • 线程的管理工作全部由内核实现，内核为每个线程维护乡下问信息，应用程序不能直接管理线程，只能通过内核级线程接口来进行相关操作。

处理机调度

在系统中，进程的数量绝大多数时候都大于处理机的数量，所以如何分配处理机给进程使用成为了一大难点，如果分配不合理，不仅会极大影响系统的运行效率和资源利用率，严重情况下甚至会造成死锁。

而处理机的调度则是对处理机进行合理的分配，它执行某种公平的算法从而使得处理机能够合理分配给各个进程，以实现进程的并发执行。

调度的层次

  1. 高级调度 -> 作业调度，即把作业从外存调入内存中。
  2. 中级调度 -> 内存调度，作用是提高内存的利用率，当某些进程不能运行时，可以暂时将其调至外存，从而实现资源的释放（此时，该进程的状态也称为挂起态）
  3. 低级调度（进程调度）。按照某种方法或策略从就绪队列中选择对应的进程，并将处理机分配给它。

调度方式（注意和后面的算法区别）

  1. 非剥夺式调度（非抢占调度）
  2. 剥夺式调度（抢占式调度） => 剥夺不是任意性行为，而需要遵循某种原则，这种原则就是后面要提到的调度算法。

调度的衡量标准

这里不一一列举全部标准，只说明几个简单准则

  1. 周转时间：作业从提交到完成的全过程时间
    • 带权周转时间：周转时间 / 作业实际运行时间 。 => 因为在整个周转时间里，作业除了运行时间，还有等待时间。
  2. 等待时间：作业处于等处理机状态的时间总和（创建，就绪，阻塞）。
    • 这里等待时间和上述周转时间中提到的等待时间是同一回事，同时该指标也是衡量算法优劣的重要标准。
  3. 响应时间：作业从提交到系统首次响应所经历的时间。

调度算法（重点）

  1. 先到先服务（FCFS：First Come First Serve）
  2. 短作业优先（SJF：Short Job First）
  3. 优先级调度算法
    • 为每个作业进程设置优先级，根据优先级高级来进行调度。
    • 优先度有静态优先级和动态优先级两种分类。注意把这里的动态优先级和下述的高响应比做对比
  4. 高响应比有限调度算法
    • 响应比计算 R = (等待时间 + 要求服务时间) / 要求服务时间
    • 从上述公示可以看出：对于短作业，要求服务时间小，R比较大，优先级一开始较高；对于长作业，虽然一开始R较低，随着时间的推迟，等待时间变大，R随之增大。所以它对于短，长作业都是相对公平的。
  5. 时间片轮转调度算法
  6. 多级反馈队列调度算法
    • 设置多个时间片队列，每个队列内的分配的时间片相同，每个队列之间从第一队列到第n队列分配的时间片依次增大，作业从第一队列开始执行，如果没执行完，则放置下一队列继续执行，依此类推，直到最后一个队列。
    • 需要注意的是，第1 - 第n-1队列对内调度算法为FCFS，第n队列调度算法为时间片轮转算法。

进程同步

相关概念

在多道程序系统中，进程是并发执行的，不同进程之间存在着不同的制约关系，为了能够较好的协调这种制约关系，从而引入了进程同步的概念

临界资源
  • 同一段时间内只能被一个进程访问的资源。
临界区
  • 访问临界资源的代码区。
同步（直接制约关系）
  • 共同完成同一个任务的多个进程之间，在执行任务的某个阶段，需要某种制约关系让它们相互等待，相互传递消息从而使得多个进程能够按照一定速度，并以正确顺序去完成该作业，这种制约关系就称为同步。
互斥（间接制约关系）
  • 一个进程进入到临界区使用临界资源时，另一个进程必须等待，直到前一个进程退出临界区。
  • 四大准则：
    1. 空闲让进
    2. 忙则等待
    3. 有限等待
    4. 让权等待

实现临界区互斥的方法

  1. 软件实现方法（王道考研P76）
  2. 硬件实现方法
    1. 中断屏蔽方法（开关中断）
    2. 硬件指令方法（即设置原子操作去访问临界区）

信号量

  • 信号量是一种功能较强的机制，它能够用来解决互斥和同步的问题，它只能被wait(S)和signal(S)两个原语访问。

管程

计算机中的软件资源或硬件资源，都可以用某种数据结构的特性抽象地描述其特性。即用少量的信息和对对资源的操作来表征某种资源。

  • 管程：代表共享数据的数据结构，以及对共享数据结构实施操作的一组过程所组成的资源管理程序，称为管程。 => 相当于把共享数据的数据结构以及对它的一系列操作抽象出来，抽象成一组管理程序，而这组管理程序就叫做管程，它能够保持进程互斥，无序程序员手动实现互斥。

死锁

当有多个进程持有一定资源时又去争夺其它进程持有的不可剥夺资源，此时便发生了死锁。

  • 死锁：多个进程因争夺资源而造成的一种僵局（互相等待），若无外力作用，则程序无法继续执行下去。

死锁产生的必要条件

  1. 互斥条件：资源的互斥性。
  2. 不可剥夺条件：不可剥夺资源。
  3. 请求并保持条件：每个进程在持有资源的同时又去请求别的进程持有的资源。
  4. 循环等待条件。

死锁处理的策略

  1. 预防死锁
    • 关于死锁的预防，只要打破上述四个必要条件之一，便可以预防死锁。 => 王道P124
  2. 死锁避免
    • 和预防死锁不同的是，预防死锁是在进程执行之前进行一系列操作，而死锁避免是在进程运行过程中（资源动态分配过程中），防止系统进入不安全状态。
    • 解决方法：银行家算法
  3. 死锁检测和解除
    • 检测采用资源分配图辅助分析。
    • 死锁的接触有以下方法可以参考。
      1. 资源剥夺法 => 剥夺死锁进程的资源，把它挂起
      2. 撤销进程法 => 强制撤销部分或全部死锁进程，释放资源
      3. 进程回退法 => 将一个（或多个）死锁进程回退到发生死锁之前。

进程部分结束