操作系统面试整理

操作系统面试整理

操作系统一些概念

​ 操作系统是指控制和管理整个计算机的硬件与软件资源，合理地组指、调度计算机的工作与资源的分配，进而为用户和其他软件提供方便接口的程序集合。

操作系统的利用

• 操作系统作为计算机资源的管理者

​ 存储管理：提高利用率，方便用户使用，同时提供足够的存储空间，方便进程并发运行，例如存储分配和回收，存储保护，地址映射，存储扩充。

​ 处理机管理：其实就是对进程的管理，例如进程调度（为进程分配处理机），进程控制，进程同步。

​ 设备管理：分配和回收设备，响应IO请求，例如缓冲管理（解决CPU与IO速度不匹配），设备分配与回收（在多用户之间共享IO资源）。

​ 文件管理：解决软件资源之间的存储，共享，保密和保护，例如文件存储空间管理，文件读写和存取控制等等。

​ 用户接口：提供友好的用户访问操作系统，主要包括三种接口，分别是命令接口，程序接口，图形接口。

• 作为用户与计算机硬件系统之间的接口
• 用作扩充机器

操作系统的特征

下面所有特征中，最基本的特征是并发和共享。

并发：指两个或多个事件在同一时间间隔内发生，微观上还是程序在分时地交替执行。

共享：指操作系统中的资源可供内存中多个并发执行的程序共同使用，分为互斥共享（一段时间内只允许一个进程访问该资源，例如打印机）和同时访问（磁盘设备）。

虚拟：指把一个物理上的实体变为若干个逻辑上的对应物，例如虚拟处理器，虚拟内存，虚拟外设。

异步：在多道程序环境下，允许多个程序并发执行，但由于资源有限，进程的执行不是一贯到底，而是走走停停，以不可预知到速度向前推进。

进程

定义：进程是指一个举有独立功能的程序对某个数据集在处理机上的执行过程和分配资源的基本单位。进程是操作系统进行资源分配的基本单位。

进程与程序的区别：

• 进程是动态的，是程序的一次执行过程，具有一定的生命期；程序是静态的，可长期存在。
• 进程具有并发特征，是一个能够独立运行的单位，是作为资源申请和调度的单位存在的，能与其他程序并发执行；程序不能作为一个独立进行的单位而并发执行。
• 一个程序可对应多个进程，一个进程可包括多个程序。

进程的状态：就绪态、阻塞态、、退就绪出态。

• 运行态：进程由就绪态通过调度算法获得CPU，转为运行态。
• 就绪态：运行态的程序，分配给它的CPU时间片用完之后的状态，等待下一次调度。
• 阻塞态：缺少需要的资源从而由运行态转换而来的，但是这里所说的资源不包括CPU，缺少CPU会让进程从运行态转为就绪态。
  

线程

定义：

• 线程是独立调度的基本单位，一个进程可以有多个线程。

• 线程有时被称为轻量级进程（Lightweight Process， LWP），是进程执行流的最小单元。

• 线程共享进程拥有的全部资源，它不 拥有资源，但是它可以访问进程所拥有的系统资源。线程没有自己独立的地址空间，它共享它所属的进程的空间。

进程与线程的区别：

• 资源：进程是资源分配的基本单位；线程不拥有资源，线程可以访问所属进程的资源。
• 调度：线程是独立调度的单位，在同一进程中，线程的切换不会引起进程切换，从一进程内的线程切换到另一个进程内的线程时，会引起进程切换。
• 系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、IO 设备等，因此操作系统所付出的开销远大于创建或撤销线程时的开销。
• 通信：进程间通信需要进程同步和互斥手段的辅助，以保证数据的一致性，而线程间可以通过直接读/写进程数据段（如全局变量）来进行通信。

进程间通信方式：管道（pipe）、有名管道（FIFO）、系统IPC（消息队列(message queue)，信号量(semophore)，共享内存(shared memory)）、信号(signal)、套接字(socket)。

• 管道：他是一个闭环，用读端就关闭写端，用写端口就关闭读端口。
• 有名管道：创建之后直接可以利用write、read，close等等函数进行操作。
• 消息队列：msgget创建、msgsend发送、msgrcv接收、msgctl控制。
• 信号量：semget创建、semop改变信号量的值、semctl控制。
• 共享内存：shmget创建、shmat挂载、shmdt分离、shmctl控制。
• 信号：signal注册、kill发送信号。
• 套接字的使用：
  

调度

调度的层次：

作业调度：又称高级调度。就是内存与辅存之间的调度。

中级调度：又称内存调度。引入中级调度是为了提高内存利用率和系统吞吐量，使那些暂时不能运行的进程，调至外存等待，把此时的进程状态称为挂起状态。当他们具备运行条件且内存又稍有空闲时，由中级调度来决定，把外存上的那些已具备运行条件的就绪进程再重新调入内存。

进程调度：又称为低级调度。按照某种方法和策略从就绪队列中选取一个进程分配 CPU。

调度算法：

先来先服务（FCFS）：调度最先进入就绪队列的作业。有利于长作业，但不利于短作业。

短作业优先调度算法（SJF）：调度估计运行时间最短的作业。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。

短进程优先调度算法（SPF）：从就绪队列中选择一个估计运行时间最短的进程，将处理机分配给它

优先级调度算法：根据能否抢占进程，可将调度算法分为非剥夺式优先级调度算法和剥夺式优先级调度算法；根据进程创建后其优先级是否可以改变，可分为静态优先级（优先级在创建进程时确定，且在进程的整个运行期间保持不变）和动态优先级（可动态调整优先级）

高响应比优先调度算法：把响应比作为优先权，其中响应比 = (等待时间 + 要求服务时间) / 要求服务时间 = 响应时间 / 要求服务时间，主要是为了解决 SJF 中长作业可能会饿死的问题，因为随着等待时间的增长，响应比也会越来越高。

时间片轮转：当某个进程执行的时间片用完时，调度程序便停止该进程的执行，并将它送就绪队列的末尾，等待分配下一时间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。

多级反馈队列：设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。

进程同步：

• 临界区与临界资源：临界资源即一次仅允许一个进程使用的资源，临界区即对临界资源进行访问的代码。
• 同步与互斥：同步即多个进程按一定顺序执行；互斥即多个进程在同一时刻只有一个进程能进入临界区。同步是在对临界区互斥访问的基础上，通过其它机制来实现有序访问的。
• 信号量：它允许多个线程同一时刻访问同一资源，但是需要限制同一时刻访问此资源的最大线程数目。
• 管程：管程是由一组数据以及定义在这组数据之上的对这组数据的操作组成的软件模块，这组操作能初始化并改变管程中的数据和同步进程。事实上，管程是一个抽象类，拥有成员变量，以及对成员变量进行操作的成员函数。

死锁

死锁定义：多个进程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

死锁的原因：资源竞争；进程推进顺序不当。

死锁的必要条件：

• 互斥：一个资源一次只能被一个进程所使用。
• 不剥夺：一个资源仅能被占有它的进程所释放，而不能被别的进程强制剥夺。
• 请求与保持： 指进程占有自身本来拥有的资源并要求其他资源。
• 循环等待： 存在进程资源的循环等待链，链中每一个进程已获得的资源同时被下一个进程所请求。

预防死锁：破坏上面四个必要条件之一

• 破坏互斥条件： 即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等。所以，这种办法并无实用价值。
• 破坏不可剥夺条件：当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难，会降低系统性能。
• 破坏请求与保持条件：可以实行资源预先分配策略。即进程在运行前，一次性地向系统申请它所需要的全部资源。
• 破坏循环等待条件：首先给系统中的资源编号，规定每个进程，必须按编号递增的顺序请求资源，同类资源一次申请完。

避免死锁：

银行家算法：就是为了找一种安全序列，使得系统能按安全序列的顺序推进不会产生死锁，能找到一个安全序列就称系统处于安全状态。

死锁的解除：资源剥夺、撤销进程、进程回退。

存储器管理

程序执行过程：

• 编译：由编译程序将用户源代码编译成若干个目标模块。
• 链接：由链接程序将编译后形成的一组目标模块，以及所需库函数链接在一起，形成一个完整的装入模块。
• 装入：由装入程序将装入模块装入内存运行。

逻辑地址与物理地址：

• 逻辑地址：是指从应用程序角度看到的内存地址，又叫相对地址。编译后，每个目标模块都是从 0 号单元开始编址，称为该目标模块的相对地址或逻辑地址。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。用户和程序员只需要知道逻辑地址。

• 物理地址：它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取，是内存单元真正的地址。

虚拟内存：

• 允许将一个作业分多次调入内存。可以用分页式、分段式、段页式存储管理来实现。

• 基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存，然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间放入将要调入内存的信息。这样，系统就好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

内存分配：

• 单一连续分配：分为系统区和用户区，系统区供给操作系统使用，用户区供给用户使用，内存中永远只有一道程序。
• 固定分区分配：最简单的一种多道程序管理方式，它将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。
• 又称为可变分区分配，是一种动态划分内存的方法。这种分区方法不预先将内存划分，而是在进程装入内存时，根据进程的大小动态的建立分区，并使分区的大小正好适合进程的需要。因此系统中分区的大小和数目是可变的

非连续分配：

• 分页

  用户程序的地址空间被划分为若干固定大小的区域，称为“页”。相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配，由一个页表来维护它们之间的映射关系。

• 分段

  分段的做法是把作业的地址空间被划分为若干个段，每个段是一组完整的逻辑信息。每个段的长度可以不同，可以动态改变。

• 段页式

  在段页式系统中，作业的地址空间首先被分成若干个逻辑段，每段都有自己的段号，然后将每段分成若干固定大小的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。

  分段与分页区别：

  程序员的透明性：分页透明，但是分段需要程序员显示划分每个段 地址空间的维度：分页是一维地址空间，分段是二维的 大小是否可以改变：页的大小不可变，段的大小可以动态改变 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

页面置换算法：

• 最佳置换算法（OPT）：即选择那些永不使用的，或者是在最长时间内不再被访问的页面置换出去。（它是一种理想化的算法，性能最好，但在实际上难于实现）；
• 先进先出置换算法（FIFO）：总是淘汰最先进入内存的页面；
• 最近最久未使用置换算法（LRU）：即选择最近最久未使用的页面予以淘汰。
• 时终置换算法：
• 该算法为每个页面设置一位访问位，将内存中的所有页面都通过链接指针链成一个循环队列。当某页被访问时，其访问位置“1”。在选择一页淘汰时，就检查其访问位，如果是“0”，就选择该页换出；若为“1”，则重新置为“0”，暂不换出该页，在循环队列中检查下一个页面，直到访问位为“0”的页面为止。

局部性原理：

• 时间局部性：如果程序中某条指令一旦执行，不久后该指令可能再次执行；如果某数据被访问过，不久后该数据可能再次被访问。
• 空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。【原因：因为指令通常是顺序存放、顺序执行的；数据也一般是以向量、数组、表等形式簇聚存储的】

中断、系统调用、库函数：

中断：就是指在计算机执行程序的过程中，由于出现了某些特殊事情，使得 CPU 暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类：

• 内部异常中断：由计算机硬件异常或故障引起的中断；

• 软中断：由程序中执行了引起中断的指令而造成的中断；

• 外部中断：由外部设备请求引起的中断；

系统调用：

​ 系统调用是通向操作系统本身的接口，是面向底层硬件的。用户进程需要发生系统调用时，内核将调用内核相关函数来实现用户程序不能直接调用这些函数，这些函数运行在内核态，CPU 通过软中断切换到内核态开始执行内核系统调用函数。

库函数：

​ 库函数是把函数放到库里，供别人使用的一种方式。

文件管理

文件定义：文件是以计算机硬盘为载体存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。

磁盘调度算法：

​ 当多个进程同时请求访问磁盘时，需要进行磁盘调度来控制对磁盘的访问。磁盘调度的主要目标是使磁盘的平均寻道时间最少。

先来先服务（FCFS）：根据进程请求访问磁盘的先后次序来进行调度。公平，简单，但由于未对寻道做任何优化，平均寻道时间可能较长

最短寻道时间优先（SSTF）：根据访问的磁道与当前磁头所在磁道距离最近的优先进行调度。该算法并不能保证平均寻道时间最短，但是比 FCFS 好很多，SSTF 会出现进行饥饿现象。

扫描（SCAN）：考虑了磁头的移动方向，要求所请求访问的磁道在磁头当前移动方向上才能够得到调度。因为考虑了移动方向，那么一个进程请求访问的磁道一定会得到调度。当一个磁头自里向外移动时，移到最外侧会改变移动方向为自外向里，这种移动的规律类似于电梯的运行，因此又常称 SCAN 算法为电梯调度算法。

循环扫描（CSCAN）：CSCAN 对 SCAN 进行了改动，要求磁头始终沿着一个方向移动。

设备管理

SPOOLing技术：虚拟设备技术，利用高速共享设备将低速的独享设备模拟为高速的共享设备，逻辑上，系统为每一个用户都分配了一台独立的高速独享设备。