操作系统

xujiaojiao2024-12-272024-12-27

操作系统

概述

计算机系统由两部分组成：

硬件
软件

通常把未配置软件的计算机称为裸机。

操作系统目的是：为了填补人与机器之间的鸿沟，即建立用户与计算机之间的接口，而为裸机配置的一种系统软件。

操作系统也包括了系统软件。

操作系统在计算机系统中的地位：

操作系统是用户与计算机之间的接口，它在计算机系统中占据重要而特殊的地位，所有其他软件，如编辑程序、汇编程序、编译程序、数据库管理系统等系统软件，以及大量的应用软件都是建立在操作系统基础上的，并得到它的支持和取得它的服务。

程序与进程

程序顺序执行时的主要特征包括：顺序性、封闭性和可再现性。

程序并发执行时的主要特征包括：失去了程序的封闭性、程序和机器的执行程序的活动不再一一对应、并发程序之间的相互制约性。

三态模型

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

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

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

进程间的通信

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

同步和互斥

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

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

例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。
互斥：申请临界资源进程间的间接制约问题。

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

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

临界区管理的原则：

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

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

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

信号量机制

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

信号量机制主要有：

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

整型信号量：

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

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

信号量 S 的物理意义：

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

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操作实现进程的互斥：

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

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

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

信号量的值：

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

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

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

死锁

当有 n 个进程，m个资源，且每个进程所需要的资源数为k，并且系统采用的分配策略是轮流地为每个进程分配资源时，判断是否发生死锁的公式如下：
$$
m >= n * (k-1)+1
$$
死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

进程资源图

做题方法：先分配，再申请

线程

传统进程有两个基本属性：

可拥有资源的独立单位；

可独立调度和分配的基本单位。

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

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

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

线程的特点：

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

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

线程分为：

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

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

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

存储管理

程序局部性原理

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

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

时间局限性：
- 如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；
- 如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。
产生时间局限性的典型原因是在程序中存在着大量的循环操作。
空间局限性：指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。

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

分页存储管理

分页原理：

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

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

地址结构：

其中，页内地址是同一页（页号）中的偏移量。

分页的过程是由操作系统完成的，对用户是透明的，所以用户不必关心分页的过程，其优点是能有效地提高主存利用率，其缺点是不易实现共享。

段页式存储管理

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

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

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

段页式地址空间的结构：

设备管理

缓冲技术

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

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

单缓冲

单缓冲工作过程图：

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

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

磁盘调度算法

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。
- 优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。
- 缺点：此算法由于未对寻道进行优化，致使平均寻道时间可能较长。
最短寻道时间优先（SSTF，最短移臂算法）：该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，使得每次的寻道时间最短。
- 优点：可能会出现饥饿现象。
- 缺点：不能保证平均寻道时间最短。
扫描算法（SCAN，电梯调度算法）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。

在这种调度方法下磁头的移动类似于电梯的调度，所以它也称为电梯调度算法。
- 优点：避免了饥饿现象的出现。
- 缺点：当磁头刚从里向外移动过某一磁道时，恰有一进程请求访问此磁道，这时该进程必须等待，待磁头从里向外，再从外向里扫描完所有要访问的磁道后才处理该进程的请求，致使该进程的请求被严重地推迟。
单向扫描算法（CSCAN，循环扫描算法）：为了减少上述SCAN缺点中存在的这种延迟，算法规定磁头只做单向移动。

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

总结：

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

文件管理

双缓冲

双缓冲进一步加快I/O的速度，提高了设备的利用率。其工作基本过程是在设备输入时，先将数据输入到缓冲区1，装满后便转向缓冲2。

双缓冲工作过程图：

双缓冲的工作特点是，可以实现对缓冲中数据的输入T和提取M，与CPU的计算C，三者并行工作：

$$
（前提是M +c ＜T）计算公式为：T * n + M + c
$$

多级索引结构

文件目录

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

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

文件控制块也称为文件的说明或文件目录项（简称目录项）。
文件目录：文件控制块的有序集合。

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

文件控制块

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

基本信息类：例如文件名、文件的物理地址、文件长度和文件块数等。
存取控制信息类：文件的存取权限。

UNIX中，用户分成三类：
- 文件主用户
- 同组用户
- 一般用户
以上三类用户对文件的权限为：
- 读
- 写
- 执行
使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。

目录结构

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

常见的目录结构有：

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

优点：结构简单；

缺点：查找速度慢，不允许重名和不便于实现文件共享等。

主要用在单用户环境中。
二级目录结构：为了克服一级目录结构存在的缺点引入了二级目录结构。

二级目录结构的组成为：
- 主文件目录（MFD）：每个用户文件目录都占有一个目录项，其目录项中包括用户名和指向该用户目录文件的指针；
- 用户目录（UFD）：由用户所有文件的目录项组成的。
优点：提高了检索目录的速度，较好地解决了重名问题。

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

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

在采用多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名：
- 路径名：从某个目录开始到该文件的通路上所有各级目录名拼起来得到的。
  
  在各目录名之间、目录名与文件名之间需要用分隔符隔开。
- 绝对路径名：指从根目录开始的完整路径。
  
  全文件名：指绝对路径名加上该文件的文件名。
- 相对路径名：从当前所在目录开始到其他目录或文件的路径。

位示图

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

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

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

例如：

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

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

做题技巧：

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