面试整理——操作系统

操作系统

第一节 基本特征

问：并发与并行？

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

• 并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。
• 操作系统通过引入进程和线程，使得程序能够并发运行。

问：虚拟技术？

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

主要有两种虚拟技术：

• 时（时间）分复用技术
• 空（空间）分复用技术

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

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

问：什么是同步？什么是异步？

同步分为进程/线程同步和数据同步，进程同步指多个进程在特定点会和使操作序列有序，数据同步则指一份数据集的多份拷贝保持一致以维护完整性。（一般通过进程同步来实现数据同步）

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

---

第二节 基本功能

问：说一下操作系统的基本功能包括？

1. 进程管理
   • 进程控制、进程同步、进程通信、死锁处理、处理机调度等
2. 内存管理
   • 内存分配、地址映射、内存保护与共享、虚拟内存等。
3. 文件管理
   • 文件存储空间的管理、目录管理、文件读写管理和保护等。
4. 设备管理：完成用户的 I/O 请求，方便用户使用各种设备，并提高设备的利用率。
   • 主要包括缓冲管理、设备分配、设备处理、虛拟设备等。

1.1 进程管理

问：什么是进程？什么是线程？

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

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。

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

问：线程和进程的区别？

• 拥有资源：进程是资源分配的基本单位，线程本身并不拥有资源但可以访问所属进程资源。进程可以包含多个线程，线程是一个进程中的不同执行路径，是比进程更小的单位。进程有独立的地址空间，进程间相互隔离。进程比较安全，但开销大、切换慢。线程间则使用相同的地址空间，共享大部分数据，虽然有自己的堆栈和局部变量。线程开销小，切换快。
• 调度：线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
• 系统开销：由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。
• 通信：线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。因为进程间相互独立，所以通信机制比较复杂，譬如管道，信号，消息队列，共享内存，套接字等通信机制，而线程由于共享数据段所以通信机制很方便。

问：进程的数据段和内存？进程和线程的内存有什么区别？

问：进程、线程间的通信方式？

进程间的通信方式（IPC）：

• 管道：一种半双工的通信方式，数据只能单向流动，且只能在具有亲缘关系的进程间使用（通常指父子进程）。在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
• 命名管道（FIFO）：有路径名关联，允许无亲缘关系进程间进行通信。
• 消息队列：即消息的链接表，存放在内核中并由消息队列标识符（队列ID）标识，有写权限的进程向队列添加消息，有读权限的进程则可以读走。消息队列解决了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。相比于管道的优点：
  • 消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
  • 避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
  • 读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。
• 信号机制：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 信号量机制：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。常作为一种锁机制，防止某进程访问共享资源时被其他进程访问。信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作：
  • down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
  • up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。
  • 如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
• 共享内存：即映射一段能被其他进程所访问的内存，由一个进程创建，但多个线程都可访问。因为数据不需要在进程之间复制，这种IPC方式效率最高，往往与其他通信机制配合使用（需要使用信号量用来同步对共享存储的访问）。
• 套接字：套接字也是一种进程间通信机制，可用于不同机器的进程间通信。

线程间的通信方式：（线程间通信主要用于同步，所以没有进程那种用于数据交换的通信机制）

• 锁机制：
  • 互斥锁：确保同一时间只能有一个线程访问共享资源。
  • 读写锁：写锁获取时阻塞所有尝试获取锁的线程，读锁获取时只阻塞写锁。读模式共享，写模式互斥。
  • 条件变量：以原子的方式阻塞线程，直到某个特定的条件为真。条件变量一直与互斥锁配套使用。
  • 自旋锁：获取锁失败并不阻塞，而是循环轮询尝试，因为没有线程切换所以没有相关开销，但因为占用CPU所以可能造成资源浪费。适用于并行结构或锁占用时间较短切换频繁的场景。
• 信号量机制：包括无名和命名信号量。类似于进程的信号量，可以高效完成基于线程的资源计数，是一个整数计数器，每当公共资源增加或减少就相应变化，当信号量大于0时可以访问其所代表的资源。
• 信号机制：类似进程的信号处理。
• volatile共享内存：TODO
• 阻塞唤醒机制：TODO

问：生产者消费者问题？进程间的同步方式有用过哪些？

生产者消费者问题，又叫有限缓冲区问题，是多进程同步的经典案例。指一个共享固定大小的缓冲区，有生产者进程向缓冲区添加数据，消费者进程则消耗缓冲区的数据。问题的关键就是保证生产者不会在缓冲区满时加入数据，消费者不会在缓冲区空时消耗数据。

解决方法：进程间通信即IPC来进行同步，常用信号量实现来解决生产者消费者问题：

• 因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。
• 为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。
• 注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

问：哲学家进餐问题？

五个哲学家围着一张圆桌，每个哲学家面前放着食物。哲学家的生活有两种交替活动：吃饭以及思考。当一个哲学家吃饭时，需要先拿起自己左右两边的两根筷子，并且一次只能拿起一根筷子。

如果所有哲学家同时拿起左手边的筷子，那么所有哲学家都在等待其它哲学家吃完并释放自己手中的筷子，导致死锁。

为了防止死锁的发生，可以设置两个条件：

• 必须同时拿起左右两根筷子；
• 只有在两个邻居都没有进餐的情况下才允许进餐。

问：读者写者问题？

允许多个进程同时对数据进行读操作，但是不允许读和写以及写和写操作同时发生。

一个整型变量 count 记录在对数据进行读操作的进程数量，一个互斥量 count_mutex 用于对 count 加锁，一个互斥量 data_mutex 用于对读写的数据加锁。

问：进程调度算法？

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

1. 批处理系统：批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。
   • 先来先服务（FCFS）：非抢占式的调度算法，按照请求的顺序进行调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。
   • 短作业优先（SJF）：非抢占式的调度算法，按估计运行时间最短的顺序进行调度。长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。
   • 最短剩余时间优先（SRTN）：最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。
2. 交互式系统：交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。
   • 时间片轮转：将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。时间片轮转算法的效率和时间片的大小有很大关系：因为进程切换都要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。而如果时间片过长，那么实时性就不能得到保证。
   • 优先级调度：为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。
   • 多级反馈队列：一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
3. 实时系统：实时系统要求一个请求在一个确定时间内得到响应。分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

问：进程中的响应时间指？

到达时间和进程首次获取CPU的时间之间的差异称为响应时间。

问：fork和exec有深入了解吗？

问：父进程有多个线程在运行，调用fork后，产生的子进程中有多少个线程？

答：只有一个线程

为什会只fork一个线程？会带来什么问题？

答：扯了一下unix设计fork接口那会还没有多线程的概念，所以就没考虑复制多个线程，会带来线程安全性问题，略去。

问：死锁的必要条件？

• 互斥：每个资源要么已经分配给了一个进程，要么就是可用的。
• 占有和等待：已经得到了某个资源的进程可以再请求新的资源。
• 不可抢占：已经分配给一个进程的资源不能强制性地被抢占，它只能被占有它的进程显式地释放。
• 环路等待：有两个或者两个以上的进程组成一条环路，该环路中的每个进程都在等待下一个进程所占有的资源。

问：死锁的处理方法？

主要有以下四种方法：

• 鸵鸟策略：把头埋在沙子里，假装根本没发生问题。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。
• 死锁检测与死锁恢复：下题。
• 死锁预防：下题。
• 死锁避免：下题。

问：死锁的检测和恢复？

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。

1.每种类型一个资源的死锁检测：

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

2.每种类型多个资源的死锁检测：

上图中，有三个进程四个资源，每个数据代表的含义如下：

• E 向量：资源总量
• A 向量：资源剩余量
• C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
• R 矩阵：每个进程请求的资源数量

进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。

算法总结如下：

每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。

1. 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
2. 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
3. 如果没有这样一个进程，算法终止。

死锁恢复：

• 利用抢占恢复
• 利用回滚恢复
• 通过杀死进程恢复

问：死锁的预防？

在程序运行之前预防发生死锁：

1. 破坏互斥条件：例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
2. 破坏占有和等待条件：一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
3. 破坏不可抢占条件：TODO
4. 破坏环路等待：给资源统一编号，进程只能按编号顺序来请求资源。

问：死锁的避免？

在程序运行时避免发生死锁：

1.安全状态

图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。

安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。

2.单个资源的银行家算法

一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。

上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。

3.多个资源的银行家算法

上图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。

检查一个状态是否安全的算法如下：

• 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
• 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
• 重复以上两步，直到所有进程都标记为终止，则状态时安全的。

如果一个状态不是安全的，需要拒绝进入这个状态。

1.2 内存管理

问：说一下操作系统的内存管理机制？

内存管理机制包括：内存分配、地址映射、内存保护与共享、虚拟内存等。

问：虚拟内存？

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

从上面的描述中可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

问：分页系统地址映射？

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

下图的页表存放着 16 个页，这 16 个页需要用 4 个比特位来进行索引定位。例如对于虚拟地址（0010 000000000100），前 4 位是存储页面号 2，读取表项内容为（110 1），页表项最后一位表示是否存在于内存中，1 表示存在。后 12 位存储偏移量。这个页对应的页框的地址为 （110 000000000100）。

问：页面置换算法有哪些，介绍一下？

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

1. 最佳（OPT）：所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

   是一种理论上的算法，因为无法知道一个页面多长时间不再被访问。

   举例：一个系统为某进程分配了三个物理块，并有如下页面引用序列：

   7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

   开始运行时，先将 7, 0, 1 三个页面装入内存。当进程要访问页面 2 时，产生缺页中断，会将页面 7 换出，因为页面 7 再次被访问的时间最长。

2. 最近最久未使用（LRU）：虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。

   为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。

   因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

   4，7，0，7，1，0，1，2，1，2，6

   

3. 最近未使用（NRU）：每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。可以将页面分成以下四类：

   • R=0，M=0
   • R=0，M=1
   • R=1，M=0
   • R=1，M=1

   当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。

   NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

4. 先进先出（FIFO）：选择换出的页面是最先进入的页面。

   该算法会将那些经常被访问的页面换出，导致缺页率升高。

5. 第二次机会算法：FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

   当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

   

6. 时钟：第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

   

问：分页和分段？

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

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。

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

段页式：程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分页和分段区别：

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

1.3 文件管理

1.4 设备管理

问：磁盘结构？

• 盘面（Platter）：一个磁盘有多个盘面；
• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
• 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
• 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
• 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
• 主轴（Spindle）：使整个盘面转动。

问：磁盘调度算法？

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

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

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

1. 先来先服务

FCFS, First Come First Served

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

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

2. 最短寻道时间优先

SSTF, Shortest Seek Time First

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

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

3. 电梯算法

SCAN

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

---

第三节 系统调用

问：讲讲Linux你知道的系统调用？

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

Linux 的系统调用主要有以下这些：

Task	Commands
进程控制	fork(); exit(); wait();
进程通信	pipe(); shmget(); mmap();
文件操作	open(); read(); write();
设备操作	ioctl(); read(); write();
信息维护	getpid(); alarm(); sleep();
安全	chmod(); umask(); chown();

---

第四节 中断

---

第五节 Linux

5.1 基础操作

问：linux中有哪些常见的指令？

• 关机：

  • who：先用 who 命令查看有没有其它用户在线。
  • sync：为了加快对磁盘文件的读写速度，位于内存中的文件数据不会立即同步到磁盘，因此关机之前需要先进行 sync 同步操作。
  • shutdown：shutdown [-krhc] 时间 [信息] 。

• sudo：允许一般用户使用 root 可执行的命令，不过只有在 /etc/sudoers 配置文件中添加的用户才能使用该指令

• ls：列出文件或者目录的信息，目录的信息就是其中包含的文件。

• cd：更换目录。

• mkdir：创建目录。

• rmdir：删除目录。

• rm：删除文件。

• mv：移动文件。

• cat：获取文件内容

• grep：正则表达式

  • ```bash
    $ grep [-acinv] [–color=auto] 搜寻字符串 filename
    -c ： 统计匹配到行的个数
    -i ： 忽略大小写
    -n ： 输出行号
    -v ： 反向选择，也就是显示出没有 搜寻字符串 内容的那一行
    –color=auto ：找到的关键字加颜色显示

    * ```bash
      $ grep -n 'the' regular_express.txt
      8:I can't finish the test.
      12:the symbol '*' is represented as start.
      15:You are the best is mean you are the no. 1.
      16:The world Happy is the same with "glad".
      18:google is the best tools for search keyword

• cut：对数据进行切分，取出想要的部分。

  • $ cut
    -d ：分隔符
    -f ：经过 -d 分隔后，使用 -f n 取出第 n 个区间
    -c ：以字符为单位取出区间
    

  • 切分过程一行一行地进行

• TODO

问：说一下Linux的启动方式？

1. 开机BIOS自检
2. MBR引导
3. grub引导菜单
4. 加载内核
5. 启动init进程
6. 读取inittab文件
7. 启动mingetty进程
8. 登录系统

问：select、poll、epoll有没有了解过，讲解一下？区别？

问：如何查看Linux系统运行状态？

1. CPU状态：
   • 查看CPU信息：$ cat /proc/cpuinfo
   • 统计CPU使用状态：$ mpstat -P ALL # 列出每个CPU的信息
2. 内存状态：
   • 查看内存信息: $ cat /proc/meminfo
   • 统计已用和空闲的内存: $ free -h
   • 统计CPU，内存及虚拟内存使用状态: $ vmstat 5 # 每隔5秒刷新
3. 进程状态：
   • 列出进程信息: $ ps [OPTION]
   • 显示进程树信息: $ pstree [OPTION]
   • 显示每个进程的内存映射信息: $ pmap [OPTION] [PID]
   • 动态显示进程列表: $ top [OPTION]
4. 网络状态：
   • 查看网络接口信息: $ ifconfig
   • 查看网络连接，端口，监听等信息: $ netstat [OPTION]
   • 查看Socket信息: $ ss [OPTION]
5. 磁盘状态：
   • 查看磁盘空间使用状态: $ df [OPTION]
   • 查看指定目录下各子目录及文件的大小: $ du [OPTION] [DIR]
   • 统计CPU及IO操作信息: $ iostat [OPTION] [INTERVAL]

问：说一下Linux如何查找CPU故障？

5.2 磁盘

5.3 分区

5.4 文件系统

问：Linux文件系统有哪些？

问：文件系统的组成？inode 和 block ？

最主要的几个组成部分如下：

• inode：一个文件占用一个 inode，记录文件的属性，同时记录此文件的内容所在的 block 编号；
• block：记录文件的内容，文件太大时，会占用多个 block。

除此之外还包括：

• superblock：记录文件系统的整体信息，包括 inode 和 block 的总量、使用量、剩余量，以及文件系统的格式与相关信息等；
• block bitmap：记录 block 是否被使用的位图。

对于 Ext2 文件系统，当要读取一个文件的内容时，先在 inode 中查找文件内容所在的所有 block，然后把所有 block 的内容读出来。

而对于 FAT 文件系统，它没有 inode，每个 block 中存储着下一个 block 的编号。

问：如何进行数据恢复？

5.5 文件

问：Linux文件类型有哪些？

常见的文件类型及其含义有：

• d：目录
• -：文件
• l：链接文件

问：说一下Linux软链接以及和硬链接的区别？

Linux的文件链接分：

• 硬链接：通过索引节点（inode）来识别文件。在 Linux 中，多个文件名指向同一索引节点是存在的，所以硬连接指通过索引节点来进行的连接，即每一个硬链接都是一个指向对应区域的文件。
• 软链接：软链接又叫符号链接，这个文件包含了另一个文件的路径名，软连接可以是任意文件或目录，可以链接不同文件系统的文件，在对符号文件进行读或写操作的时候，系统会自动把该操作转换为对源文件的操作，但删除链接文件时，系统仅仅删除链接文件，而不删除源文件本身，这一点类似于 Windows 操作系统下的快捷方式。

	软链接	硬链接
inode	原文件&链接文件拥有不同的inode号，表明是不同文件	原文件和链接文件共用一个inode号，表示是同一个文件
文件属性	明确写出是链接文件	未写出，因为本质上硬链接文件和原文件相同
跨越文件系统建立	支持	不支持
链接数目	链接数目不会增加，文件大小不一样	显示的大小与原文件相同

5.6 压缩与打包

5.7 Bash

5.8 管道指令

问：说一下命名管道和匿名管道的特点和区别？

5.9 正则表达式

5.10 进程管理

进程管理相关，僵尸进程与孤儿进程，SIGCHLD 。

问：说一下Linux进程间通信的方式？

答：管道，信号量，消息队列，共享内存，套接字。

中断与系统调用的概念

问：用户态和内核态？为什么要有用户态和内核态？

通过系统调用将Linux整个体系分为用户态和内核态（或者说内核空间和用户空间）。那内核态到底是什么呢？其实从本质上说就是我们所说的内核，它是一种特殊的软件程序，特殊在哪儿呢？控制计算机的硬件资源，例如协调CPU资源，分配内存资源，并且提供稳定的环境供应用程序运行。

用户态就是提供应用程序运行的空间，为了使应用程序访问到内核管理的资源例如CPU，内存，I/O。内核必须提供一组通用的访问接口，这些接口就叫系统调用。

内核态：cpu可以访问内存的所有数据，包括外围设备，例如硬盘，网卡，cpu也可以将自己从一个程序切换到另一个程序。

用户态：只能受限的访问内存，且不允许访问外围设备，占用cpu的能力被剥夺，cpu资源可以被其他程序获取。

为什么要有用户态和内核态？由于需要限制不同的程序之间的访问能力, 防止他们获取别的程序的内存数据, 或者获取外围设备的数据, 并发送到网络, CPU划分出两个权限等级 – 用户态和内核态。

---

CS-Notes-操作系统

查看Linux系统运行状态

参考内容均来自网络分享、开源项目、书籍、博客等，若内容涉及侵权请及时告知，我会尽快修改和删除相关内容