进程管理、存储管理、文件管理、设备管理

PCB：Process Control Block，进程控制块

FIFO：First-In, First-Out，先进先出

LRU：Least Recently Used，最近最少使用

OPT：Optimal，最优的

DMA：Direct Memory Access，直接内存访问

SPOOLING：Simultaneous Peripheral Operation On-Line

操作系统考点概述

• 进程管理

  • 进程的状态
  • 前趋图
  • PV操作
  • 进程调度
  • 死锁
  • 线程

• 存储管理

  • 分区存储
  • 页式存储
  • 段式存储
  • 段页式存储

• 文件管理

  • 索引文件
  • 树形目录
  • 空闲存储管理

• 设备管理

  • I/O软件
  • 输入输出技术
  • SPOOLING技术

操作系统概述

操作系统

• 操作系统的作用：通过资源管理提高计算机系统的效率：改善人机界面向用户提供友好的工作环境。

• 操作系统的特征：并发性、共享性、虚拟性、不确定性。

• 操作系统的功能：进程管理、存储管理、文件管理、设备管理、作业管理。

• 操作系统的分类：批处理操作系统、分时操作系统（轮流使用CPU工作片）、实时操作系统（快速响应）、网络操作系统、分布式操作系统（物理分散的计算机互联系统）、微机操作系统（Windows）、嵌入式操作系统。

• 计算机启动的基本流程为：BIOS->主引导记录->操作系统

进程管理

进程的组成和状态

• 进程的组成：进程控制块PCB（唯一标志）、程序（描述进程要做什么）、数据（存放进程执行时所需数据）。

• 进程基础的状态是下左图中的三态图，这是系统自动控制时只有三种状态，而下右图中的五态，是多了两种状态：静止就绪和静止阻塞，需要人为的操作才会进入对应状态，活跃就绪即就绪，活跃阻塞即等待。

  

  • 三态：进程等待资源。有了资源就进入就绪状态，等待CPU调度

  • 五态：是三态的扩展，一般是认为操作才会进入相应状态

• 可知，当人为干预后，进程将被挂起，进入静止状态，此时，需要人为激活，才能恢复到活跃状态，之后的本质还是三态图

前趋图

前趋图：用来表示哪些任务可以并行执行，哪些任务之间有顺序关系，具体如下图

可知，ABC可以并行执行，但是必须ABC都执行完后，才能执行D，这就确定了两点：任务间的并行、任务间的先后顺序。

进程资源图

进程资源图：用来表示进程和资源之间的分配和请求关系，如下图所示

图形解释：

• P代表进程，R代表资源，R方框中有几个圆球就表示有几个这种资源。

• 进来的箭头表示占有资源，比如R1指向P1，表示P1占有一个R1资源。出去的箭头表示需要资源，比如P1指向R2，表示P1还需要一个R2资源

• 在图中，R1指向P1，表示R1有一个资源已经分配给了P1，P1指向R2，表示P1还需要请求一个R2资源才能执行。

阻塞节点与非阻塞节点：

• 阻塞节点：某进程所请求的资源已经全部分配完毕，无法获取所需资源，该进程被阻塞了无法继续。如上图中P2。

• 非阻塞节点：某进程所请求的资源还有剩余，可以分配给该进程继续运行。如上图中P1、P3。

• 当一个进程资源图中所有进程都是阻塞节点时，即陷入死锁状态。

同步和互斥

基本概念：

• 互斥：某资源（即临界资源）在同一时间内只能由一个任务单独使用，使用时需要加锁，使用完后解锁才能被其他任务使用：如打印机。

• 同步：多个任务可以并发执行，只不过有速度上的差异，在一定情况下停下等待，不存在资源是否单独或共享的问题；如自行车和汽车。

• 临界资源：各进程间需要以互斥方式对其进行访问的资源。

• 临界区：指进程中对临界资源实施操作的那段程序。本质是一段程序代码。

• 互斥信号量：对临界资源采用互斥访问，使用互斥信号量后其他进程无法访问，初值为1。

  • 就是对互斥资源加一个锁，保证一次只能有一个资源占用

• 同步信号量：对共享资源的访问控制，初值一般是共享资源的数量。

信号量操作

• P操作：申请资源。S=S-1，若S>=0，则执行P操作的进程继续执行：若S<0，则置该进程为阻塞状态（因为无可用资源），并将具插入阻塞队列。

• V操作：释放资源。S=S+1，若S>0，则执行V操作的进程继续执行：若S<=0，则从阻塞状态唤醒一个进程，并将其插入就绪队列（此时因为缺少资源被P操作阻塞的进程可以继续执行），然后执行V操作的进程继续。

  

  • 图说明：

    • 当S>=0时，表示资源的个数
    • 当S<0时，表示在等待该资源的进程的个数

• 经典问题：生产者和消费者问题

  三个信号量：互斥信号量S0（仓库独立使用权），同步信号量S1（仓库空闲个数），同步信号量S2（仓库商品个数）

  

• 例题1：

  

  

  • 我们做这种题的时候可以大胆假设，小心求证。一般是从先假设S1，S2开始的。

• 例题2：

  

  • 我们做这种题的时候，可以把值都列出来。当资源Sn的值小于0时，进程就阻塞了同时另一个进程继续执行。当另一个线程将Sn释放后，Sn不小于0，也要等此线程执行完或者阻塞才能继续执行原有线程。

死锁

• 什么是死锁：

  • 当一个进程在等待永远不可能发生的事件时，就会产生死锁，若系统中有多个进程处死锁状态，就会造成系统死锁。

• 死锁产生的四个必要条件：

  • 资源互斥
  • 每个进程占有资源并等待其他资源
  • 系统不能剥夺进程资源
  • 进程资源图是一个环路

• 死锁的解决措施：

  • 死锁预防：采用某种策略限制并发进程对于资源的请求，破坏死锁产生的四个条件之一，使系统任何时刻都不满足死锁的条件。
  • 死锁避免：一般采用银行家算法来避免，银行家算法，就是提前计算出一条不会死锁的资源分配方法，才分配资源，否则不分配资源，相当于借贷，考虑对方还得起才借钱，提前考虑好以后，就可以避免死锁。
  • 死锁检测：充许死锁产生，但系统定时运行一个检测死锁的程序，若检测到系统中发生死锁，则设法加以解除。
  • 死锁解除：即死锁发生后的解除方法，如强制剥夺资源，撤销进程等。

• 死锁计算问题：

  • 系统内有n个进程，每个进程都需要R个资源，那么其发生死锁的最大资源数为n*（R-1）。其不发生死锁的最小资源数为n*（R-1）+1。
  • 如何理解：
    • 每个进程都需要R个资源，如果每个都刚好只差一个资源才能解锁，那么系统将会死锁，同时资源被占有数是最大的，也就是n*(R-1)
    • 当我们向上述死锁的环境中再增加一个资源，那么就会有一个进程将其获得，同时能够完成进程，便释放资源。后续其他进程也能够获得资源。

• 例题：

  

  • 本题直接计算即可

  

  • 本题中，你需要先计算可用资源数，使用总共的 减去 已分配的 即可

    执行顺序计算方式：将剩下的资源尝试按照一定的顺序分配给进程，看如何才能不阻塞

线程

• 传统的进程有两个属性：可拥有资源的独立单位：可独立调度和分配的基本单位。

• 引入线程后，线程是独立调度的最小单位，进程是拥有资源的最小单位，线程可以共享进程的公共数据、全局变量、代码、文件等资源，但不能共享线程独有的资源，如线程的栈指针等标识数据。

存储管理

页式存储管理

• 什么是页式存储：

  • 将进程空间分为一个个页，假设每个页大小为4K，同样的将系统的物理空间也分为一个个4K大小的物理块（页帧号），这样，每次将需要运行的逻辑页装入物理块中，运行完再装入其他需要运行的页，就可以分批次运行完进程，而无需将整块逻辑空间全部装入物理内存中。

  

• 页式存储的特点

  • 优点：利用率高、碎片小（只在最后一个页中有）、分配及管理简单。
    • 碎片：分配一个内存，这个内存没有装满，就是碎片。
  • 缺点：增加了系统开销，可能产生抖动现象。

• 例题：

  • 逻辑地址和物理地址的转换

    

    

页面置换算法

• 基本概念

  • 有时候，进程空间分为100个页面，而系统内存只有10个物理块，无法全部满足分配，就需要将马上要执行的页面先分配进去，而后根据算法进行淘汰，使100个页面能够按执行顺序调入物理块中执行完。

  • 缺页表示需要执行的页不在内存物理块中，需要从外部调入内存，会增加执行时间，因此缺页数越多，系统效率越低。

• 算法：

  • 最优算法：OPT，理论上的算法，无法实现，是在进程执行完后进行的最佳效率计算，用来让其他算法比较差距。原理是选择未来最长时间内不被访问的页面置换，这样可以保证未来执行的都是马上要访问的。

  • 先进先出算法：FIFO，先调入内存的页先被置换淘汰，会产生抖动现象，即分配的帧数越多，缺页率可能越高（即效率越低）。

  • 最近最少使用：LRU，在最近的过去，进程执行过程中，过去最少使用的页面被置换淘汰，根据局部性原理，这种方式效率高，且不会产生抖动现象。

• 例题：

  

快表

• 基本概念

  • 是一块小容量的相联存储器，由快速存储器组成，按内容访问，速度快，并且可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号。

  • 快表是将页表存于Cache中；慢表是将页表存于内存上。

  • 因此慢表需要访问两次内存才能取出页，而快表是访问一次cache和一次内存，因此更快。

段式存储管理

• 基本概念

  • 将进程空间分为一个个段，每段也有段号和段内地址，与页式存储不同的是，每段物理大小不同，分段是根据逻辑整体分段的

  • 地址表示：（段号，段内偏移）：其中段内偏移不能超过该段号对应的段长，否则越界错误，而此地址对应的真正内存地址应该是：段号对应的基地址+段内偏移。

  

  • 这幅图中，段长30K，基址40K，表示的是40K-70K的地址

• 段式存储的特点

  • 优点：程序逻辑完整，修改互不影响
  • 缺点：内存利用率低，内存碎片浪费大

• 例题

  • 下述逻辑地址为：（段号，段内地址），段内地址为需要的地址长度。所以只需要段内地址小于段表中的段长即可

  

段页式存储系统

• 基本概念

  

• 段页式存储系统的特点

  • 对进程空间先分段，后分页，具体原理图和优缺点如下：
    • 优点：空间浪费小、存储共享容易、能动态连接。
    • 缺点：由于管理软件的增加，复杂性和开销也增加，执行速度下降

文件管理

基本概念

• 计算机系统中采用的索引文件结构如下图所示：

  

  • 系统中有13个索引节点，0-9为直接索引，即每个索引节点存放的是内容，假设每个物理盘小为4KB，共可存4KB*10=10KB数据：

  • 10号索引节点为一级间接索引节点，大小为4KB，存放的并非直接数据，而是链接到直接物盘块的地址，假设每个地址占4B，则共有1024个地址，对应1024个物理盘，可存1024*4KB=4098KB数据

  • 二级索引节点类似，直接盘存放一级地址

    一级地址再存放物理盘快地址，而后链接到存放数据的物理盘块，容量又扩大了一个数量级，为1024*1024*4KB数据。

真题

树形文件目录

• 相对路径：是从当前路径开始的路径。

• 绝对路径：是从根目录升始的路径

• 全文件名=绝对路径+文件名。要注意，绝对路径和相对路径是不加最后的文件名的，只是单纯的路径序列。

• 树形结构主要是区分相对路径和绝对路径，如下图所示：

  

空闲存储空间管理

• 基本概念：

  • 空闲区表法：将所有空闲空间整合成一张表，即空闲文件自录

  • 空闲链表法：将所有空闲空间链接成一个链表，根据需要分配。

  • 成组链接法：既分组，每组内文链接成链表，是上述两种方法的综合。

  • 位示图法：对每个物理空间用一位标识，为1则使用，为0则空闲，形成一张位示图

• 例题：

  

  

  

设备管理

设备分类的方式

• 按数据组织分类：块设备、字符设备。

• 资源分配角度分类：独占设备、共享设备和虚拟设备。

• 数据传输速率分类：低速设备、中速设备、高速设备。

I/O软件层次结构

输入输出技术

• 程序控制方式：CPU主动查询外设，效率低。

• 程序中断方式：外设完成传输后，发出中断请求，CPU响应并处理数据，效率较高。适用于需要实时响应的场景，如键盘输入。

  • 中断响应时间指的是从发出中断请求到开始进入中断处理程序；

    中断处理时间指的是从中断处理开始到中断处理结束；

    中断向量提供中断服务程序的入口地址。

    多级中断嵌套，使用堆栈来保护断点和现场。

• DMA方式（直接主存存取）：DMA控制器负责整个数据传输过程，在主存和外设之间建立直接的数据通路，CPU只需完成必要的初始化等工作，效率高。适用于高速设备，如硬盘。

  • 在一个总线周期结束后，CPU会响应DMA请求开始读取数据；CPU响应程序中断方式请求是在一条指令执行结束时；区分指令执行结束和总线周期结束。

虚设备和SPOOLING技术

传统情况下，一台实际的物理设备，比如打印机，一次只能被一个进程使用，其他进程必须等待，但无法确定何时会空闲，这会导致外设的工作效率极低。

为了解决这个问题，引入了SPOOLING（Simultaneous Peripheral Operation On-Line）技术。这项技术在外设上创建了两个数据缓冲区，分别称为输入井和输出井。一个用于输入（输入缓冲区），另一个用于输出（输出缓冲区）。现在，多个进程可以共享同一台打印机，它们只需将打印任务发送给设备，数据将按照顺序存储在缓冲区中，并由打印机自动按顺序打印。这样一来，每个进程都感觉自己独占了一个打印机，实现了对物理设备的虚拟化。

这种虚拟化技术提高了外设的利用率，使多个进程能够有效地共享物理设备，而不会相互干扰。这个过程的示意图如下所示：

磁盘结构

• 磁盘存储结构：

  • 磁盘由正反两个盘面构成，每个盘面分为多个同心圆，每个同心圆是一个磁道，一个磁道又被划分为多个扇区，数据存储在这些扇区中。

• 读取数据过程：

  1. 磁头首先要寻找到目标磁道。
  2. 等待磁盘进行周期旋转，旋转到指定的扇区。
  3. 才能读取到对应的数据。

  这个过程包括了寻道时间（将磁头移动到磁道所需的时间）和等待时间（等待读写的扇区转到磁头下方所需的时间）。其中，寻道时间通常是最耗时的。

• 磁盘调度算法：

  1. 先来先服务（FCFS）：按照进程请求访问磁盘的顺序进行调度。

  2. 最短寻道时间优先（SSTF）：优先调度离当前磁道最近的请求，以最小化寻道时间。但可能导致某些远处请求永远无法满足（"饥饿"现象）。

  3. 扫描算法（SCAN）：也称为“电梯算法”，磁头在磁盘上双向移动，选择最近的请求磁道，并朝着磁头移动方向前进，直到最后一个请求，然后改变方向继续。

  4. 单向扫描调度算法（CSCAN）：类似SCAN，但只能从一端向另一端单向移动，然后返回。通常只能从内向外或者从外向内移动。

特殊的操作系统

微内核操作系统

微内核，顾名思义，就是尽可能的将内核做的很小，只将最为核心必要的东西放入内核中，其他能独立的东西都放入用户进程中，这样，系统就被分为了用户态和内核态，如下图所示：

嵌入式操作系统

• 嵌入式操作系统特点：

  • 微型化：体积小，适用于资源有限的嵌入式系统。

  • 代码质量高：稳定可靠，不容易出错。

  • 专业化：针对特定应用场景进行优化。

  • 实时性强：能够满足对实时性要求高的应用。

  • 可裁剪可配置：可以根据需要选择性地裁剪和配置功能。

• 实时嵌入式操作系统的内核服务：

  • 异常和中断处理：处理硬件异常和中断请求。

  • 计时器服务：提供时间管理和延时功能。

  • I/O管理：管理输入和输出设备。

• 常见的嵌入式RTOS（实时操作系统）：

  • VxWorks

  • RT-Linux

  • QNX

  • pSOS

• 嵌入式系统初始化过程（自底向上，从硬件到软件）：

  1. 片级初始化：初始化微处理器。
  2. 板级初始化：初始化其他硬件设备。
  3. 系统初始化：进行软件和操作系统的初始化。