复试 — 操作系统

一、概述

什么是操作系统r> 操作系统（Operating System，简称 OS）是管理和控制计算机硬件与软件资源的计算机程序，任何其他软件都必须在操作系统的支持下才能运行。

操作系统是用户和计算机的接口，同时也是计算机硬件和其他软件的接口。

操作系统的功能包括管理计算机系统的硬件、软件及数据资源，控制程序运行，改善人机界面，为其它应用软件提供支持等，使计算机系统所有资源最大限度地发挥作用，提供了各种形式的用户界面，使用户有一个好的工作环境，为其它软件的开发提供必要的服务和相应的接口。

基本特征

1. 并发

并发是指宏观上在一段时间内能同时运行多个程序，而并行则指同一时刻能运行多个指令。

并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。

操作系统通过引入进程和线程，使得程序能够并发运行。

2. 共享

共享是指系统中的资源可以被多个并发进程共同使用。

有两种共享方式：互斥共享和同时共享。

互斥共享的资源称为临界资源，例如打印机等，在同一时间只允许一个进程访问，需要用同步机制来实现对临界资源的访问。

3. 虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。

主要有两种虚拟技术：时分复用技术和空分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换。

虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

4. 异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

基本功能

1. 进程管理

进程控制、进程同步、进程通信、死锁处理、处理机调度等。

2. 内存管理

内存分配、地址映射、内存保护与共享、虚拟内存等。

3. 文件管理

文件存储空间的管理、目录管理、文件读写管理和保护等。

4. 设备管理

完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。

主要包括缓冲管理、设备分配、设备处理、虛拟设备等。

系统调用

如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

什么是微内核：

什么是微内核操作系统到现在没有一致公认的定义，但是可以从四个方面对微内核操作系统进行描述：

① 足够小的内核：在微内核操作系统中，内核是指精心设计的，能实现现代 OS 最基本核心功能的部分，并非是一个完整的 OS，而只是 OS 中最基本的部分。
② 基于 C/S 模式：将操作系统中最基本的部分放入内核中，而把操作系统的绝大部分功能都放于微内核外面的一组服务器中实现。
③ 应用“极致与策略分离”原理：在传统 OS 中，讲极致放在 OS 的内核的较低层，把策略放在内核的较高层中。而在微内核 OS 中，通常把机制放在 OS 的微内核中，这样才有可能将内核做得很小。
④ 采用面向对象技术。

优点：
① 提高了系统的可扩展性
② 增强系统的可靠性
③ 可移植性
④ 提供了对分布式系统的支持
⑤ 融入了面向对象技术

中断分类

1. 外中断

由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

2. 异常

由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。

3. 陷入

在用户程序中使用系统调用。

硬中断和软中断是什么是什么r> 软中断：
1、编程异常通常叫做软中断
2、软中断是通讯进程之间用来模拟硬中断的一种信 通讯方式。
3、中断源发中断请求或软中断信 后,CPU 或接收进程在适当的时机自动进行中断处理或完成软中断信 对应的功能
4、软中断是软件实现的中断,也就是程序运行时其他程序对它的中断;而硬中断是硬件实现的中断,是程序运行时设备对它的中断。
硬中断：
1、硬中断是由外部事件引起的因此具有随机性和突发性；软中断是执行中断指令产生的，无外部施加中断请求信 ，因此中断的发生不是随机的而是由程序安排好的。
2、硬中断的中断 是由中断控制器提供的；软中断的中断 由指令直接给出，无需使用中断控制器。
3、硬中断是可屏蔽的，软中断不可屏蔽。
区别：
1、软中断发生的时间是由程序控制的,而硬中断发生的时间是随机的
2、软中断是由程序调用发生的,而硬中断是由外设引发的
3、硬件中断处理程序要确保它能快速地完成它的任务,这样程序执行时才不会等待较长时间。

二、进程管理

进程与线程

1. 进程

进程是资源分配的基本单位。

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

2. 线程

线程是独立调度的基本单位。

一个进程中可以有多个线程，它们共享进程资源。

QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。

• 就绪状态（ready）：等待被调度
• 运行状态（running）
• 阻塞状态（waiting）：等待资源

应该注意以下内容：

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程调度算法

不同环境的调度算法目标不同，因此需要针对不同环境来讨论调度算法。

1. 批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-serverd（FCFS）

按照请求的顺序进行调度。

有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

1.2 短作业优先 shortest job first（SJF）

按估计运行时间最短的顺序进行调度。

长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next（SRTN）

按估计剩余时间最短的顺序进行调度。

2. 交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

时间片轮转算法的效率和时间片的大小有很大关系：

• 因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。
• 而如果时间片过长，那么实时性就不能得到保证。

3. 实时系统

实时系统要求一个请求在一个确定时间内得到响应。

分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程同步

1. 临界区

对临界资源进行访问的那段代码称为临界区。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。

2. 同步与互斥

• 同步：多个进程按一定顺序执行；
• 互斥：多个进程在同一时刻只有一个进程能进入临界区。

3. 信 量

信 量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

• down : 如果信 量大于 0 ，执行 -1 操作；如果信 量等于 0，进程睡眠，等待信 量大于 0；
• up ：对信 量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

如果信 量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

操作系统中的信 量：

信 量分类：
① 整型信 量：所谓整型信 量就是一个用于表示资源个数的整型量
② 记录型信 量（资源信 量）：就是用一个结构体实现，里面包含了表示资源个数的整型量和一个等待
队列。
信 量的应用：
① 实现进程同步
② 实现进程互斥

整型变量 s 表示系统中某类资源的数目，当其值大于 0 时，表示系统中当前可用资源的数目；当其值小于 0 时，其绝对值表示系统中因请求该类资源而被阻塞的进程数目。

4. 管程

什么是管程：

管程可以看作一个软件模块，它是将共享变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制。

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否者其它进程永远不能使用管程。

进程通信

进程同步与进程通信很容易混淆，它们的区别在于：

• 进程同步：控制多个进程按一定顺序执行；
• 进程通信：进程间传输信息。

进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

它具有以下限制：

• 只支持半双工通信（单向交替传输）；
• 只能在父子进程中使用。

分段

虚拟内存采用的是分页技术，也就是将地址空间划分成固定大小的页，每一页再与内存进行映射。

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

• 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
• 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
• 实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务

FCFS, First Come First Served

按照磁盘请求的顺序进行调度。

优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先

SSTF, Shortest Seek Time First

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

4. 循环扫描算法

CSCAN

规定磁头单向移动，如自里向外移动，当磁头移动到最外的磁道时立即返回到最里磁道，如此循环进行扫描。兼顾较好的寻道性能，防止饥饿现象，同时解决了一个请求等待时间过长的问题。

六、链接

程序的装入方式有哪些p>

应用程序从用户编写的源文件到内内存中执行的进程大致分为三个阶段：

• 经过编译程序将源代码编译为若干个目标模块；
• 在通过链接程序将编译好的目标模块以及所需的库函数链接到一起，形成完整的装
  入模块；
• 最后通过装入程序将这些装入模块装入内存并执行。（编译，链接，装入）

装入方式：
① 绝对装入：在编译时就知道程序将要驻留在内存的物理地址，编译程序产生含有物理地址的目标代码，不适合多道程序设计。
② 可重定位装入：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称静态重定位。当操作系统为程序分配一个以某地址为起始地址的连续主存区域后，重定位时将程序中指令或操作数的逻辑地址加上这个起始地址就得到了物理地址。
③ 动态运行装入：允许程序运行时在内存中移动位置，把装入模块装入到内存后的所有地址都是相对地址，在程序执行过程中每当访问到相应指令或数据时，才将要访问的程序或数据的相对地址转换为物理地址。动态重定位的实现要依靠硬件地址变换机构。

程序的链接方式有哪些p>

① 静态链接：在程序运行之前，先把各个目标模块及所需库链接为一个完整的可执行程序，以后不再拆开。
② 装入时动态链接：将应用程序编译后所得到的一组目标模块在装入内存时采用边装入边链接的链接方式。
③ 运行时动态链接：知道程序运行过程中需要一些模块时，才对这些模块进行链接。

七、补充

交换技术，覆盖技术，以及两者的区别。

覆盖技术：把一个大的程序划分为一系列覆盖，每个覆盖是一个相对独立的程序单位，把程序执行时并不要求同时装入内存的覆盖组成一组，成为覆盖段，这个覆盖段分配到同一个存储区域，这个存储区域成为覆盖区，它与覆盖段一一对应。覆盖段的大小由覆盖段中最大的覆盖来确定。（为了解决内存容量太小的问题，打破了必须将一个程序全部信息装入内存后才能运行的限制）
交换技术：把暂时不用的某个程序及数据部分从内存移到外存中去，以便腾出必要的内存空间；或者把指定的程序或数据从外存读到相应的内存中，并将控制权交给他，让其在系统上运行的一种内存扩充技术。处理器的中级调度就是采用交换技术。

区别：
① 与覆盖技术相比，交换技术不要求程序员给出的程序段之间的覆盖结构；
② 交换技术主要在进程和作业之间进行，覆盖技术主要在同一个进程或作业中进行；
③ 覆盖技术只能覆盖于覆盖程序段无关的程序段，交换进程由换出和换入两个过程组成。

内存连续分配管理方式有哪些r> ① 单一连续分配（静态分配）
② 固定分区分配（分区大小可以不等，但事先必须确定，运行时不能改变）
③ 动态分区分配

动态分区分配的算法有哪些r> ① 首次适应算法 First Fit
② 循环首次适应算法 Next Fit
③ 最佳适应算法 Best Fit
④ 最差适应算法 Worst Fit

什么叫拼接技术r> 在分区管理方式下，系统运行一段时间后，内存中会出现相当一部分的碎片，拼接技术是解决碎片问题的方法。
即将存储器中所有已分配分区移动到主存的一端，使本来分散的多个小空闲区连成一个大的空闲区，这种通过移动把多个分散的小分区拼接成一个大分区的方法即为拼接技术。

内部碎片和外部碎片
内部碎片：分配给作业的存储空间中未被利用的部分。
外部碎片：系统中无法利用的小存储块，比如通过动态内存分配技术从空闲内存区上分配内存后剩下的那部分内存块。

常用的存储保护方法
（1）界限寄存器
上下界寄存器方法
基址、限长寄存器方法
（2）存储保护键：给每个存储块分配一个单独的存储键，它相当于一把锁。

什么是页表么作用。
为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页面映射表。
页表由页表项组成，页表项有页 和块 组成，根据页表项就可以找到每个页 对于物理内存中物理块的块 。

参考资料

• CS-Note https://cyc2018.github.io/CS-Notes/#/README
• Tanenbaum A S, Bos H. Modern operating systems[M]. Prentice Hall Press, 2014.
• 汤子瀛, 哲凤屏, 汤小丹. 计算机操作系统[M]. 西安电子科技大学出版 , 2001.
• Bryant, R. E., & O’Hallaron, D. R. (2004). 深入理解计算机系统.
• 史蒂文斯. UNIX 环境高级编程 [M]. 人民邮电出版 , 2014.
• Operating System Notes
• Operating-System Structures
• Processes
• Inter Process Communication Presentation[1]
• Decoding UCS Invicta – Part 1