填空题、判断题、简答题（10）、设计题、编程题（IPC）

引论

操作系统所处的位置

多数计算机由两种运行模式：内核态（管态）和用户态（目态）。软件中最基础的部分是操作系统，它运行在内核态，在这个模式中，操作系统具有对所有硬件的完全访问权，可以执行机器能够运行的任何指令。软件的其余部分运行在用户态下，只使用机器指令中的一个子集。用户接口程序（shell 或 GUI）处于用户态程序中的最低层次，允许用户运行其他程序。操作系统运行在裸机之上，为所有其他软件提供基础的运行环境。操作系统中的程序由硬件进行保护，防止用户试图对其进行修改。

什么是操作系统

操作系统主要有两个方面的重要作用：管理系统中的各种资源，并为用户提供良好的界面。

操作系统有两个基本上独立的任务：为应用程序提供一个资源集的清晰抽象，并管理这些硬件资源。

操作系统是硬件的扩展板，是资源的管理器。

• 作为扩展机器：例如，硬盘驱动。
• 作为资源管理者：资源管理包括用两种不同的方式实现多路复用（共享）资源：时间复用和空间复用。

操作系统的历史

1. 真空管和穿孔卡片
2. 晶体管和批处理系统
3. 集成电路和多道程序设计（SPOOLing）
4. 个人计算机

SPOOLing 假脱机

同时的外部设备联机操作（Simultaneous Peripheral Operation On-Line）

假脱机是多道程序设计系统中处理独占 I/O 设备的一种方法。

SPOOLing 系统的三大组成部分：

1. 输入井和输出井
2. 输入缓冲和输出缓冲
3. 输入进程和输出进程

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

技术特点

1. 提高了I/O速度。从对低速I/O设备进行的I/O操作变为对输入井或输出井的操作，如同脱机操作一样，提高了I/O速度，缓和了CPU与低速I/O设备速度不匹配的矛盾。
2. 设备并没有分配给任何进程。在输入井或输出井中，分配给进程的是一存储区和建立一张I/O请求表。
3. 实现了虚拟设备功能。多个进程同时使用一独享设备，而对每一进程而言，都认为自己独占这一设备，不过，该设备是逻辑上的设备。

工作原理

1、SPOOLing的含义是什么述SPOOLing系统的特点、功能以及控制过程。

答：SPOOLing是Simultaneous Peripheral Operation On-Line（即外部设备联机并行操作）的缩写，它是关于慢速字符设备如何与计算机主机交换信息的一种技术，通常称为”假脱机技术”。SPOOLing技术是在通道技术和多道程序设计基础上产生的，它由主机和相应的通道共同承担作业的输入输出工作，利用磁盘作为后援存储器，实现外围设备同时联机操作。SPOOLing系统由专门负责I/O的常驻内存的进程以及输入井、输出井组成；它将独占设备改造为共享设备，实现了虚拟设备功能。

2、SPOOLing技术如何使一台打印机虚拟成多台打印机/strong>

答：将一台独享打印机改造为可供多个用户共享的打印机，是应用SPOOLing技术的典型实例。具体做法是：系统对于用户的打印输出，但并不真正把打印机分配给该用户进程，而是先在输出井中申请一个空闲盘块区，并将要打印的数据送入其中；然后为用户申请并填写请求打印表，将该表挂到请求打印队列上。若打印机空闲，输出程序从请求打印队首取表，将要打印的数据从输出井传送到内存缓冲区，再进行打印，直到打印队列为空。

计算机硬件简介

• 处理器：从内存中取出指令并执行之。
• 存储器：寄存器、高速缓存、主存、磁盘。
• 磁盘
• I/O设备：CPU 和存储器不是操作系统唯一需要管理的资源。
• 总线
• BIOS（基本输入输出系统，Basic Input Output Stream）

操作系统概念

进程

进程本质上是正在执行的一个程序。与每个进程相关的是地址空间，这是从某个最小值的存储位置（通常是零）到某个最大值的存储位置的列表。

与一个进程有关的所有信息，除了该进程自身地址空间的内容以外，均存放在操作系统的一张表中，称为进程表，进程表是数组或链表结构，当前存在的每个进程都要占用其中的一项。

一个挂起的进程包括：进程的地址空间（磁芯映像，纪念过去使用的磁芯存储器，即主存），以及对应的进程表项（其中包括寄存器以及稍后重启该进程所需要的许多其他信息）。

与进程管理有关的最关键的系统调用是那些进行进程创建和进程终止的系统调用。

一个进程能够创建一个或多个子进程，而这些子进程又可以创建子进程，得到进程树。合作完成某些作业的相关进程经常需要彼此通信以便同步它们的行为，这种通信称为进程间通信。

由于定时器到期，或各种由硬件检测出来的陷阱，如非法指令或使用了无效地址，操作系统会向该进程发送一个警告信 ，此信 引起该进程暂时挂起，系统将其寄存器的值保存到堆栈，并开始运行一个特别的信 处理过程，如重新发送可能丢失的信息。

系统管理器授权每个进程使用一个给定的UID。每个被启动的进程都有一个启动该进程的用户 UID。子进程拥有和父进程一样的 UID。用户可以是某个组的成员，每个组也有一个 GID。在 UNIX 中，有一个 UID 称为超级用户，在 Windows 中为管理员，它具有特殊的权力，可以违背一些保护规则。

地址空间

较复杂的操作系统允许在内存中同时运行多道程序。为了避免它们互相干扰，需要有某种保护机制。虽然这种机制必然是硬件形式的，但是由操作系统掌控。

管理进程的地址空间同样重要，在本质上，操作系统创建了一个地址空间的抽象，作为进程可以引用地址的集合。该地址空间与机器的物理内存解耦，可能大于也可能小于该地址空间，操作系统可以把部分地址空间装入主存，部分留在磁盘上，并且在需要时来回交换它们。对地址空间和物理空间的管理组成了操作系统功能的一个重要部分。

文件

目录层结构中的每一个文件都可以通过从目录的顶部即根目录开始的路径名来确定。

在实例中，每个进程有一个工作目录，对于没有斜线开头给出绝对地址的路径，将在这个工作目录下寻找。进程可以通过使用系统调用指定新的工作目录，从而变更其工作目录。

提供特殊文件是为了使 I/O 设备看起来像文件一般，这样，I/O 设备可以像使用系统调用读写文件一样进行读写。

• 块特殊文件：指那些由可随机存取的块组成的设备，如磁盘等。
• 字符特殊文件：用于打印机、调制解调器和其他接收或输出字符流的设备。

按照惯例，特殊文件保存在/dev目录中。

管道是一种虚文件，它可连接两个进程。这样在 UNIX 中两个进程之间的通信就非常类似于普通文件的读写了。而且若进程想发现它所写入的输出文件不是真正的文件而是管道，则需要特殊的系统调用。

输入/输出

某些 I/O 软件是设备独立的，即这些 I/O软件部分可以同样应用于许多或者全部的 I/O 设备上。

I/O 软件的其他部分，如设备驱动程序，是专门为特定的 I/O 设备设计的。

保护

rwx 位：所有者、其他组成员、其他人。

shell

shell 本身不是操作系统的一部分，但它体现了许多操作系统的特性，并很好地说明了系统调用的具体用法。shell 同时也是终端用户与操作系统之间的接口。现在，很多个人计算机使用 GUI，GUI 与 shell 类似，GUI 只是一个运行在操作系统顶部的程序。

系统调用

任何单 CPU 计算机一次只能执行一条指令。如果一个进程正在用户态运行一个用户程序，并且需要一个系统服务，比如从一个文件读取数据，那么它就必须执行一个陷阱（trap）或系统调用（system call）指令，将控制转移到操作系统。操作系统接着通过参数检查找出所需要的调用进程。然后，它执行系统调用，并把控制返回给在系统调用后面跟随着的指令。在某种意义上，进行系统调用就像进行一个特殊的过程调用，但是只有系统调用可以进入内核，而过程调用则不能。

TRAP 指令实际上与过程调用指令非常类似，它们后面都跟随一个来自远处位置的指令，以及供以后使用的一个保存在栈中的返回地址。然而，TRAP 指令与过程指令存在两个方面的差别：

• TRAP 指令的副作用是切换到内核态，而过程调用指令并不改变模式。
• 不像给定过程所在的相对或绝对地址那样，TRAP 指令不能跳转到任意地址上。根据机器的体系结构，或者跳转到一个单固定地址上，或者指令中有一8位长的字段，它给定了内存中一张表格的索引，这张表格中含有跳转地址。

跟随在 TRAP 指令后的内核代码开始检查系统调用编 ，然后分派给正确的系统调用处理器。

此时，系统调用处理器运行。

一旦系统调用处理器完成其工作，控制可能会在跟随 TRAP 指令后面的指令中返回给用户空间库过程。

这个过程接着以通常的过程调用返回的方式，返回到用户程序。

什么是陷阱指令（TRAP）操作系统中解释它的用途/strong>

答：TRAP 是由于系统调用引起处理机中断的指令。在系统调用中，TRAP 负责由用户模式切换为内核模式，并将返回地址保存至堆栈中以备后用。

读取日期-时钟指令可以在非内核态使用。
读取用户地址空间可以在非内核态使用。

陷阱指令和中断的区别/strong>

答：陷阱指令可以使执行流程从用户态陷入内核；而中断是由外部事件导致并且它发生的时间是不可预测的。外部事件主要是指时钟中断，硬件中断等。所以说中断的主要作用是完成进程间切换，从而支持CPU和设备之间的并行。

系统调用的目的是/strong>

答：操作系统编制了许多不同功能的子程序，供用户程序执行中调用。这些由操作系统提供的子程序称为系统功能调用，简称系统调用。

操作系统特性

• 并发
• 共享
• 虚拟化
• 异步

中断、异常和陷入

• 中断：是为了设备与CPU之间的通信。
• 异常：异常是由当前正在执行的进程产生。

中断的两种方式：外部和陷入：

• interrupt 即外中断，指来自处理机和内存外部的中断，包括 I/O 设备发出的 I/O中断、外部信 中断、各种定时器引起的时钟中断以及调试程序中设置的断点等引起的调试中断等。
• trap 即内中断，主要指在处理机和内存内部产生的中断。它包括程序运算引起的各种错误。软中断是通信进程之间用来模拟硬中断的一种信 通信方式。

中断和陷阱的主要区别：

1. 陷阱通常由处理机正在执行的现行指令引起，而中断则是由与现行指令无关的中断源引起的。
2. 陷阱处理程序提供的服务为当前进程所用，而中断处理程序提供的服务则不是为了当前进程的。
3. CPU 在执行完一条指令之后，下一条指令开始之前响应中断，而在一条指令执行中也可以响应陷阱。
4. 在有的系统中，陷入处理程序被规定在各自的进程上下文中执行，而中断处理程序则在系统上下文中执行。

进程与线程

进程模型

一个进程就是一个正在执行程序的实例，包括程序计数器、寄存器和变量的当前值。

进程和程序的区别：一个进程是某种类型的一个活动，它有程序、输入、输出以及状态。单个处理器可以被若干进程共享，它使用某种调度算法决定何时停止一个进程的工作，并转而为另一个进程提供服务。如果一个程序运行了两遍，则算作两个进程。

进程的创建

4种主要事件会导致进程的创建：

1. 系统初始化：前台进程，后台进程（守护进程，daemon）。
2. 正在运行的程序执行了创建进程的系统调用。
3. 用户请求创建一个新的进程。
4. 一个批处理作业的初始化。

UNIX：只有一个系统调用可以用来创建新进程：fork。这个系统调用会创建一个与调用进程相同的副本。通常，子进程接着执行 execve 或一个类似的系统调用，以修改其内存映像并运行一个新的程序。（之所以要安排两步建立进程，是为了在 fork 之后但在 execve 之前允许孩子进程处理其文件描述符，这样可以完成对标准输入文件、标准输出文件和标准错误文件的重定向。）

文件描述符：UNIX 内核（kernel）利用文件描述符（file descriptor）来访问文件。文件描述符是非负整数。打开现存文件或新建文件时，内核会返回一个文件描述符。读写文件也需要使用文件描述符来指定待读写的文件。

Windows：一个 Win32 函数调用 CreateProcess 既处理进程的创建，也负责把正确的程序装入新的进程。

在 UNIX 和 Windows 中，进程创建之后，父进程和子进程由各自不同的地址空间。在 UNIX 中，子进程的初始地址空间是父进程的一个副本，但是这里涉及两个不同的地址空间，不可写的内存区是共享的。或者，子进程共享父进程的所有内存，但这种情况下内存通过写时复制（copy-on-write）共享，这意味着一单两者之一想要修改部分内存，则这块内存首先被明确地复制，以确保修改发生在私有内存区域。在 Windows 中，从一开始父进程的地址空间和子进程的地址空间就是不同的。

进程的终止

进程的终止通常由下列条件引起：

1. 正常退出（自愿）
2. 出错退出（自愿，进程发现了严重错误）
3. 严重错误（非自愿，由进程引起的错误）
4. 被其他进程杀死（非自愿）

UNIX：kill
Windows：TerminateProcess

进程的层次结构

• UNIX

在 UNIX 中，进程和它的所有子进程以及后裔共同组成一个进程组。当用户从键盘发出一个信 时，该信 被送给当前与键盘相关的进程组中的所有成员（它们通常是在当前窗口创建的所有活动进程）。每个进程可以分别捕获该信 、忽略该信 或采取默认的动作，即被该信 杀死。在 UNIX 的整个系统中，所有的进程都属于以 init 为根的一棵树。

• Windows

在 Windows 中没有进程层次的概念，所有的进程都是地位相同的。唯一类似于进程层次的暗示是在创建进程的时候，父进程得到一个特别的令牌（句柄），该句柄可以用来控制子进程。但是，它有权把这个令牌传送给某个其他进程，这样就不存在进程层次了。在 UNIX 中，进程不能剥夺其子进程的“继承权 ”。

进程的状态

基于进程的操作系统中最底层的是中断和调度处理，在该层之上的是顺序进程。

操作系统的最底层是调度程序，在它上面有许多进程。所以有关于中断处理、启动进程和停止进程的具体细节都隐藏在调度程序中。实际上，调度系统是一段非常短小的程序，操作系统的其他部分被简单地组织成进程的形式。

进程的实现

为实现进程模型，操作系统维护着一张表格（进程表）。每个进程占用一个进程表项（进程控制块），该表项包含了进程状态的重要信息，字段分三类：进程管理、存储管理和文件管理。其中进程的 PID 代表进程的唯一存在。

多道程序设计模型

读者-写者问题（可能考）

读者-写者问题为数据库访问建立了一个模型。多个进程同时读数据库是可以接受的，但是如果一个进程正在更新（写）数据库，则所有的其他进程都不能访问该数据库，即使读操作也不可以。

睡眠的理发师问题（可能考）

有一个理发师，有一个理发椅，5个等候椅，如果没有顾客，则理发师睡觉，如果有顾客，则叫醒理发师；理发师理发时，如果有顾客过来，且有等候椅，则坐下来等候；如果没有等候椅，则离开。

调度程序

当计算机系统是多道程序设计系统时，通常就会有多个进程或线程同时竞争 CPU。只要有两个或更多的进程处于就绪状态，这种情形就会发生。如果只有一个 CPU 可用，那么就必须选择下一个要运行的进程。在操作系统中，完成选择工作的这一部分称为调度程序，该程序使用的算法称为调度算法。

• 调度的三个层次

  • 作业调度：从外存后备队列中选择作业进入内存就绪队列。
  • 存储调度：在内存和外存对换区之间按照给定的策略选择进程对换。
  • 进程和线程调度：从就绪队列中选择一个进程来执行并由分派程序分配处理机。

• 根据如何处理时钟中断，可以把调度算法分为两类：

  • 抢占式
  • 非抢占式

何时调度

1. 在创建一个新进程之后，需要决定是运行父进程还是运行子进程。（任意决定，调度程序可以选择）
2. 在一个进程退出时必须所处调度决策。
3. 当一个进程阻塞在 I/O 和信 量上或由于其他原因阻塞时，必须选择另一个进程运行。
4. 在一个 I/O 中断发生时，必须做出调度决策。

调度算法

批处理系统中的调度

1. 先来先服务
2. 最短作业优先
3. 最短剩余时间优先

交互式系统中的调度

1. 轮转调度
2. 优先级调度：在各个优先级类中使用轮转调度
3. 多级队列：属于最高优先级类的进程运行一个时间片，次高运行2个，再次运行4个。。。
4. 最短进程优先：根据进程过去的行为进程预测，并执行估计运行时间最短的那个，可以和之前的运行时间做加权和来预测
5. 保证调度：确保 n 个进程中每个进程占用 CPU 的时间约为 1/n
6. 彩票调度：反应迅速，所有的进程都是平等的，但是可以给更重要的进程额外的彩票
7. 公平分享调度：以进程的所有者均分 CPU 时间而不论进程数目