软考备考——三、操作系统

三、操作系统

1、操作系统基础知识

计算机软件通常分为系统软件和应用软件两大类。系统软件是计算机系统的一部分，用来支持应用软件的运行。应用软件是指计算机用户利用计算机的软件、硬件资源为某一专门的应用目的而开发的软件。例如，科学计算、工程设计、数据处理、事务处理和过程控制等方面的程序，以及文字处理软件、表格处理软件、辅助设计软件(CAD)和实时处理软件等。常用的系统软件有操作系统、语言处理程序、链接程序、诊断程序和数据库管理系统等。操作系统是计算机系统中必不可少的核心系统软件，其他软件是建立在操作系统的基础上，并在操作系统的统一管理和支持下运行的，是用户与计算机之间的接口。

1.1 操作系统的定义

操作系统（OS）是计算机中的一个系统软件，它管理和控制计算机系统的硬件和软件资源，合理地组织计算机的工作流程，控制程序的执行，并且向用户提供一个良好的工作环境和友好的接口

1.2 操作系统的作用

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

1.3 操作系统的特征

操作系统主要有并发性、共享性、虚拟性和不确定性4个基本特征。

1.4 操作系统的功能

• 处理机管理。处理机管理实际上是指对处理机执行"时间"的管理，采用多道程序等技术将CPU真正合理地分配给每个任务。常用的资源管理单位有进程和线程。
• 文件管理。文件管理（信息管理）包括文件存储空间管理、目录管理、文件的读写管理和存取控制、软件管理等。
• 存储管理。存储管理主要是对主存空间进行管理。
• 设备管理。设备管理的目标是方便设备使用，提高CPU与I/O设备的利用率。
• 作业管理。作业管理暴扣任务管理、界面管理、人机交互等。

2、 操作系统类型

1. 批处理操作系统
   • 分为单道批处理系统和多道批处理系统
2. 分时操作系统
3. 实时操作系统
4. 网络操作系统
5. 分布式操作系统
6. 微机操作系统
7. 嵌入式操作系统

3、进程管理

进程管理也称处理机管理。在多道程序批处理系统和分时系统中有多个并发执行的程序，为了描述系统中程序执行时动态变化的过程引入了进程。进程是资源分配和独立运行的基本单位。进程管理重点需要研究诸进程之间的并发特性，以及进程之间相互合作与资源竞争产生的问题。

3.1 程序与进程

1. 程序顺序执行的特征

   前趋图是一个有向无循环图，由结点和有向边组成，结点代表各程序段的操作，而结点间的有向边表示两个程序段操作之间存在的前趋关系(→)。程序段Pi和Pj的前趋关系表示成Pi→Pj,其中，Pi是Pj的前趋，Pj是Pi的后继，其含义是Pi执行结束后Pj才能执行。例如，为3个程序段，其中输入是计算的前驱(计算是输入的后继),输入结束才能进行计算；计算是输出的前驱，计算结束才能进行输出。
   程序顺序执行时的主要特征包括顺序性、封闭性和可再现性。

   

2. 程序并发执行的特征
   若在计算机系统中采用多道程序设计技术，则主存中的多道程序可处于并发执行状态。对于上述有3个程序段的作业类，虽然每个作业有前趋关系的各程序段不能在CPU和输入/输出各部件并行执行，但是同一个作业内没有前趋关系的程序段或不同作业的程序段可以分别在CPU和各输入/输出部件上并行执行。例如，某系统中有一个CPU、一台输入设备和一台输出设备，每个作业具有3个程序段输入I,计算C;和输出P(i=1,2,3)。下图为3个作业的各程序段并发执行的前驱图。

   从图中可以看出，I₂与C₁并行执行；I₃、C₂与P₁并行执行；C₃与P₂并行执行。其中，I₂、I₃受到I₁的间接制约，C₂、C₃受到C₁的间接制约，P₂、P₃受到P₁的间接制约，而C₁、P₁受到I₁的直接制约，等等。

   

3.2 三态模型

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。

运行：当一个进程在处理机上运行时。
就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行（还未得到）。
阻塞（等待或睡眠）：一个进程正在等待某一事件发生而暂时停止运行，这时即使把处理机分配给进程也无法运行。

进程	CPU	资源
运行	√	√
就绪	×	√
阻塞	×	×

3.3 进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

3.4 同步和互斥

• 同步：合作进程间的直接制约问题。

  进程间的同步：是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

  例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

• 互斥：申请临界资源进程间的间接制约问题。

  进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。

  临界资源：在多道程序系统环境中，那些一次只能供一个进程使用的资源。如打印机、共享变量和表格等。

临界区管理的原则：

临界区：是进程中对临界资源实施操作的那段程序。

对互斥临界区管理的4条原则如下：

有空即进：当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限 的时间。
无空则等：当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。
有限等待：对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入“饥饿”状态。
让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态

3.5 信号量机制

信号量机制是一种有效的进程同步与互斥工具。

信号量机制主要有：

• 整型信号量
• 记录型信号量
• 信号量集机制

整型信号量：

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类：

• 公用信号量：实现进程间的互斥，初值为1或资源的数目。
• 私用信号量：实现进程间的同步，初值为0或某个正整数。

信号量 S 的物理意义：

• S ≥ 0：表示某资源的可用数，此时有可用资源；
• S＜0：则其绝对值表示阻塞队列中等待该资源的进程数，此时无可用资源，并且有进程被阻塞。

3.6 PV操作

PV操作：实现进程同步与互斥的常用方法。

P操作和V操作是低级通信原语，在执行期间不可分割。其中：

• P操作（减）：表示申请一个资源；

  定义：S := S−1（S表示信号量）

  • S ≥ 0：执行P操作的进程继续执行；
  • S＜0：无可用资源，置该进程为阻塞状态，并将其插入阻塞队列。

• V操作（加）：表示释放一个资源。

  定义：S := S+1

  • S ≥ 0：执行V操作的进程继续执行；
  • S＜0：表示释放前有程序被阻塞，从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

  P减V加，P进V出。

利用PV操作实现进程的互斥：

1. 令信号量mutex的初始值为1；
2. 进入临界区：执行P操作；
3. 推出临界区：执行V操作。

利用PV操作实现进程的同步：

实现进程的同步可用一个信号量与消息联系起来。

信号量的值：

• 为0：表示希望的消息未产生；
• 非0：表示希望的消息已经存在。

假定信号量S表示某条消息，进程可以：

• 调用P操作：测试消息是否到达；
• 调用V操作：通知消息已经准备好。

3.7 死锁

当有 n 个进程，m个资源，且每个进程所需要的资源数为k，并且系统采用的分配策略是轮流地为每个进程分配资源时，判断是否发生死锁的公式如下：
m>=n∗(k−1)+1

死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

3.8 线程

引入线程的原因是，进程的系统必须付出较大的时空开销。引入线程后，将传统进程的两个基本属性分开：

• 线程：作为调度和分配的基本单位；
• 进程：作为独立分配资源的单位。

线程是进程中的一个实体，是被系统独立分配和调度的基本单位。

线程的特点：

• 线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。
• 线程也具有就绪、运行和阻塞3种基本状态。
• 线程可创建另一个线程。
• 同一个进程中的多个线程可并发执行。

线程因其具有许多传统进程所具有的特性，故称为"轻型进程"；而传统进程称为"重型进程"。

线程分为：

• 用户级线程（User-Level Threads）：不依赖于内核，该类线程的创建、撤销和切换都不利用系统调用来实现；
• 内核支持线程（Kernel-Supported Threads）：依赖于内核，即无论是在用户进程中的线程，还是在系统中的线程，它们的创建、撤销和切换都利用系统调用来实现。

某些系统同时实现了两种类型的线程。

与线程不同的是，不论是系统进程还是用户进程，在进行切换时，都要依赖于内核中的进程调度。因此，不论是什么进程都是与内核有关的，是在内核支持下进行切换的。

4、存储管理

4.1 程序局部性原理

程序在执行时将呈现出局部性规律，即在一段时间内，程序的执行仅局限于某个部分。相应地，它所访问的存储空间也局限于某个区域内。

程序的局限性表现在以下两个方面：

• 时间局限性：

  • 如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；
  • 如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。

  产生时间局限性的典型原因是在程序中存在着大量的循环操作。

• 空间局限性：指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。

  即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型原因为程序是顺序执行。

4.2 分页存储管理

分页原理：

• 页：将一个进程的地址空间划分成若干个大小相等的区域，称为页。
• 块（页框）：将主存空间划分成与页相同大小的若干个物理块，称为块或页框。

在为进程分配主存时，将进程中若干页分别装入多个不相邻接的块中。

地址结构：

分页系统的地址结构如图所示，它由两部分组成:前一部分为页号 P;后一部分为偏移量 W，即页内地址。图中的地址长度为 32 位，其中，0~11 位为页内地址(每页的大小为4kb)，12~31位为页号，所以允许地址空间的大小最多为1Mb 个页。

页表：

当进程的多个页面离散地分配到主存的多个物理块时，系统应能保证在主存中找到进程要访问的页面所对应的物理块。为此，系统为每个进程建立了一张页面映射表，简称页表。每个页在页表中占一个表项，记录该页在主存中对应的物理块号。

4.3段页式存储管理

结合分页和分段存储管理方式，形成一种新的存储管理方式，即段页式存储管理。段页式系统有两种系统的优点。

段页式系统的基本原理是：

1. 将整个主存划分成大小相等的存储块（页框）。
2. 将用户程序按程序的逻辑关系分为若干个段，并为每个段赋予一个段名。
3. 将每个段划分成若干页，以页框为单位离散分配。

段页式地址空间的结构：

5、设备管理

5.1 缓冲技术

缓冲技术可提高外设利用率，尽可能使外设处于忙状态。缓冲技术可以采用两种方式：

• 硬件缓冲：利用专门的硬件寄存器作为缓冲；
• 软件缓冲：通过操作系统来管理的。

单缓冲

单缓冲工作过程图：

当第1块数据送入用户工作区后（进行数据处理），缓冲区是空闲的，可以传送第2块数据（输入）。即第1块数据的处理C1与第2块数据的输入T2是可以并行的，以此类推：

（前提是c要小于T）计算公式为：（T+M）∗n+c

5.2 磁盘调度算法

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。

• 优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。
• 缺点：此算法由于未对寻道进行优化，致使平均寻道时间可能较长。

最短寻道时间优先（SSTF，最短移臂算法）：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。

• 优点：可能会出现饥饿现象。
• 缺点：不能保证平均寻道时间最短。

**扫描算法（**SCAN，电梯调度算法）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。

在这种调度方法下磁头的移动类似于电梯的调度，所以它也称为电梯调度算法。

• 优点：避免了饥饿现象的出现。
• 缺点：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，再从外向里扫描完所有要访问的磁道后才处理该进程的请求，致使该进程的请求被严重地推迟。

单向扫描算法（CSCAN，循环扫描算法）：为了减少上述SCAN缺点中存在的这种延迟，算法规定磁头只做单向移动。

例如，只是自里向外移动，从当前位置开始沿磁头的移动方向去选择离当前磁头最近的那个柱面访问，如果沿磁头的方向无请求访问时，磁头立即返回到最里面的欲访问的柱面，再亦即将最小柱面号紧接着最大柱面号构成循环，进行循环扫描。

总结：

1. 先来先服务（FCFS） ：根据进程请求访问磁盘的先后次序进行调度。
2. 最短寻道时间优先(SSTF)：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
3. 扫描算法/电梯调度算法（SCAN）：扫描算法不仅考虑到要访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。
4. 单向扫描调度算法（CSCAN）：为了减少这种延迟，算法规定磁头只做单向移动。

6、文件管理

6.1 文件目录

• 文件控制块（FCB）：用于文件的描述和控制的数据结构，实现了文件的“按名存取”。

  文件控制块至少要包括文件名和存放文件的物理地址。

  文件控制块也称为文件的说明或文件目录项（简称目录项）。

• 文件目录：文件控制块的有序集合。

  即文件目录是由文件控制块组成的，专门用于文件的检索。

6.2 文件控制块

文件控制块中包含以下信息：

• 基本信息类：例如文件名、文件的物理地址、文件长度和文件块数等。

• 存取控制信息类：文件的存取权限。

  UNIX中，用户分成三类：

  • 文件主用户
  • 同组用户
  • 一般用户

  以上三类用户对文件的权限为：

  • 读
  • 写
  • 执行

• 使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的 信息（如打开文件的进程数、在文件上的等待队列）等。

6.3 目录结构

组织好文件的目录是设计文件系统的重要环节，文件目录结构的组织方式直接影响到文件的存取速度，关系到文件的共享性和安全性。

常见的目录结构有：

• 一级目录结构：一级目录的整个目录组织是一个线性结构，在整个系统中只需建立一张目录表，系统为每个文件分配一个目录项。

  • 优点：结构简单；
  • 缺点：查找速度慢，不允许重名和不便于实现文件共享等。

  主要用在单用户环境中。

• 二级目录结构：为了克服一级目录结构存在的缺点引入了二级目录结构。

  二级目录结构的组成为：

  • 主文件目录（MFD）：每个用户文件目录都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针；
  • 用户目录（UFD）：由用户所有文件的目录项组成的。

  优点：提高了检索目录的速度，较好地解决了重名问题。

  缺点：该结构虽然能有效地将多个用户隔离开（这种隔离在各个用户之间完全无关时是一个优点），但当多个用户之间要相互合作去共同完成一个大任务，且一个用户又需要去访问其他用户的文件时，这种隔离便成为一个缺点，因为这种隔离使诸用户之间不便于共享文件。

• 多级目录结构：在多道程序设计系统中常采用多级目录结构。

  多级目录结构是树型目录结构。从根结点向下，每一个结点是一个目录，叶结点是文件。

  在采用多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名：

  • 路径名：从某个目录开始到该文件的通路上所有各级目录名拼起来得到的。
  • 在各目录名之间、目录名与文件名之间需要用分隔符隔开。
  • 绝对路径名：指从根目录开始的完整路径。
  • 全文件名：指绝对路径名加上该文件的文件名。
  • 相对路径名：从当前所在目录开始到其他目录或文件的路径。

6.3 位示图

位示图是一种空闲空间管理方法。通过在外存上建立一张位示图，记录文件存储器的使用情况。

位示图用二进制的一位来表示一个物理块的使用情况：

• 0：表示空闲；
• 1：表示占用。

位示图的大小由磁盘空间的大小（物理块总数）决定。

位示图的描述能力强，适合各种物理结构。

做题技巧：

块号从0开始，字号从1开始，公式：
(n−1)∗32～～～n∗32−1 (n-1)32 ～～～ n32-1
(n−1)∗32～～～n∗32−1

块号从0开始，字号从0开始，公式：
n∗32～～～(n+1)∗32−1 n*32 ～～～(n+1)*32-1
n∗32～～～(n+1)∗32−1