操作系统

Narcissus 收录于操作系统

2022-10-15 约 8146 字预计阅读 17 分钟

1. 操作系统基础

1.1 什么是操作系统？

操作系统是管理计算机硬件与软件资源的程序，是计算机的基石。
操作系统本质上是一个运行在计算机上的程序，用于管理计算机硬件和软件资源。
操作系统的存在屏蔽了硬件层的复杂性。
操作系统的内核是操作系统的核心部分，负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。

1.2 系统调用

先了解一下用户态和系统态。根据进程访问资源的特点，可以把进程在系统上的运行分为两个级别：

用户态：用户态运行的进程可以直接读取用户程序的数据。
系统态：又称为内核态，可以简单理解为系统态运行的进程或程序，几乎可以访问计算机的任何资源。

我们运行的程序基本都运行在用户态，凡是与系统级别的资源有关的操作（如文件管理、进程控制、内存管理等）都必须通过系统调用的方式向操作系统提出服务请求，并由操作系统代为完成。

三种情况导致用户态到系统态的切换：

系统调用、异常（如缺页异常）、外围设备中断。

系统调用按功能可分为：

设备管理：完成设备的请求或释放，以及设备启动等功能。
文件管理：完成文件的读、写、创建及删除等。
进程控制：完成进程的创建、撤销、阻塞及唤醒等功能。
进程通信：完成进程之间的消息传递或信号传递等功能。
内存管理：完成内存分配、回收以及获取作业占用内存大小及地址等功能。

2. 进程与线程

2.1 进程与线程的区别

进程是资源分配的基本单位，线程是CPU调度的基本单位。
一个进程可以有多个线程，线程的切换不一定会引起进程的切换，但进程的切换一定会引起线程的切换。
每个进程都有独立的地址空间，进程间的切换开销较大；同一个进程中的线程共享地址空间，但每个线程都有自己独立的寄存器和栈。

协程，是一种比线程更加轻量级的存在，协程不被操作系统内核管理，而完全是由程序所控制（也就是在用户态执行），线程的切换由操作系统负责调度，协程由用户自己进行调度，因此减少了上下文切换，提高了效率。

2.2 进程的状态

创建状态(new) ：进程正在被创建，尚未到就绪状态。
就绪状态(ready) ：进程已处于准备运行状态，即进程获得了除了处理器之外的一切所需资源，一旦得到处理器资源(处理器分配的时间片)即可运行。
运行状态(running) ：进程正在处理器上上运行(单核 CPU 下任意时刻只有一个进程处于运行状态)。
阻塞状态(waiting) ：又称为等待状态，进程正在等待某一事件而暂停运行如等待某资源为可用或等待 IO 操作完成。即使处理器空闲，该进程也不能运行。
结束状态(terminated) ：进程正在从系统中消失。可能是进程正常结束或其他原因中断退出运行。

另外还有一个状态叫挂起状态，表示进程没有占用内存空间。挂起状态可以分为两种：

阻塞挂起状态：进程在外存（硬盘）并等待某个事件的出现；
就绪挂起状态：进程在外存（硬盘），但只要进入内存，即刻立刻运行；

挂起状态与阻塞状态的区别：

是否释放CPU：阻塞（pend）就是任务释放CPU，其他任务可以运行，一般在等待某种资源或信号量的时候出现。挂起（suspend）不释放CPU，如果任务优先级高就永远轮不到其他任务运行。

是否主动：阻塞是一种被动行为，其发生在磁盘，网络IO，wait，lock等要等待某种事件的发生的操作之后。挂起是主动的，因为挂起后还要受到CPU的监督（等待着激活），所以挂起不释放CPU，比如sleep函数，站着CPU不使用。

与调度器是否相关：任务调度是操作系统来实现的，任务调度时，直接忽略挂起状态的任务。

2.3 进程间通信

概念

每个进程各自有不同的用户地址空间，任何一个进程的全局变量在另一个进程中都看不到，所以进程之间要交换数据必须通过内核，在内核中开辟一块缓冲区，进程1把数据从用户空间拷到内核缓冲区，进程2再从内核缓冲区把数据读走，内核提供的这种机制称为进程间通信（IPC，InterProcess Communication）

进程间通信的七种方式

管道/匿名管道(pipes)

用于具有亲缘关系的父子进程间或者兄弟进程之间的单向通信。

有名管道(Names pipes)

匿名管道由于没有名字，只能用于亲缘关系的进程间通信。为了克服这个缺点，提出了有名管道。有名管道严格遵循先进先出(first in first out)。有名管道以磁盘文件的方式存在，可以实现本机任意两个进程通信。

信号(signal)

信号是Linux系统中用于进程间互相通信或者操作的一种机制，信号可以在任何时候发给某一进程，而无需知道该进程的状态。

消息队列

消息队列是存放在内核中的消息链表，允许一个或多个进程向它写入与读取消息；消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取，比FIFO更有优势；消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

信号量

信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。

共享内存(Shared memory)

使得多个进程可以可以直接读写同一块内存空间，是最快的可用IPC形式。由于多个进程共享一段内存，因此需要依靠某种同步机制（如信号量）来达到进程间的同步及互斥。

套接字(Sockets)

主要用于在客户端和服务器之间通过网络进行通信。

2.4 进程调度算法

先到先服务(FCFS)调度算法 : 从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
短作业优先(SJF)的调度算法 : 从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。
时间片轮转调度算法 : 时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法，又称 RR(Round robin)调度。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。
多级反馈队列调度算法 ：前面介绍的几种进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程 。多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。，因而它是目前被公认的一种较好的进程调度算法，UNIX 操作系统采取的便是这种调度算法。
优先级调度为每个流程分配优先级，首先执行具有最高优先级的进程，依此类推。具有相同优先级的进程以 FCFS 方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

2.5 线程间同步的方式？

操作系统一般采用三种线程同步方式：

互斥量(Mutex)：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个线程同时访问。
信号量(Semphares) ：它允许同一时刻多个线程访问同一资源，但是需要控制同一时刻访问此资源的最大线程数量。
事件(Event) :Wait/Notify：通过通知操作的方式来保持多线程同步，还可以方便的实现多线程优先级的比较操作。

2.6 死锁

多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况称为死锁。

产生死锁的四个必要条件，必须同时满足，死锁才会出现：

互斥：资源必须处于非共享模式，即一次只有一个进程可以使用。如果另一进程申请该资源，那么必须等待直到该资源被释放为止。
占有并等待：一个进程至少应该占有一个资源，并等待另一资源，而该资源被其他进程所占有。
非抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资源才会被释放。
循环等待：有一组等待进程 {P0, P1,..., Pn}， P0 等待的资源被 P1 占有，P1 等待的资源被 P2 占有，……，Pn-1 等待的资源被 Pn 占有，Pn 等待的资源被 P0 占有。

2.7 解决死锁的办法

解决死锁的方法可以从多个角度去分析，一般有：预防、避免、检测和解除四种。

死锁的预防

破坏死锁产生的四个条件之一就可以。破坏互斥条件，使得资源可以被同时访问，这种做法简单，但是很多资源往往不能同时访问，这种做法在大多数时候行不通。破坏非抢占，即采用剥夺式调度算法，会导致资源利用率下降。

静态分配策略

通过破坏第二个条件（占有并等待），指一个进程必须在执行前就申请到它所需要的全部资源才能执行。会降低资源利用率，可能造成一个进程占有了一些几乎不用的资源而使其他需要该资源的进程产生等待。

层次分配策略

破坏了产生死锁的第四个条件（循环等待），所有的资源被分成了多个层次，一个进程得到某一层的一个资源后，它只能再申请较高一层的资源；当一个进程要释放某层的一个资源时，必须先释放所占用的较高层的资源。

死锁的避免

允许系统中同时存在四个必要条件，只要掌握并发进程中与每个进程有关的资源动态申请情况，做出明智和合理的选择，仍然可以避免死锁。

我们将系统分为安全状态和不安全状态，使用银行家算法通过先试探分配给该进程资源，然后通过安全性算法判断是否处于安全状态，若不安全则试探分配作废；若能进入安全状态，则真的分配资源。

银行家算法改善了资源利用率低的问题，但要不断地检测每个进程对各类资源的占用和申请情况，以及做安全检测，需要花费较多的时间

例子：

利用应行家算法，可以找到一个安全序列{p0、p3、p4、p1、p2}：

3. 死锁检测和解除

死锁的预防和避免都不利于各进程对系统资源的充分共享，解决死锁问题的另一个途径就是死锁检测和解除。(检测和解除更像是乐观锁，等到发生死锁后再解决，死锁的预防和避免像悲观锁，觉得死锁会出现，分配时更谨慎)

分配资源时不加任何限制，但系统定时运行一个“死锁检测”程序，判断系统内是否发生死锁，检测到死锁发生，就解除它。

进程-资源分配图

操作系统中每一时刻的系统状态都可以用进程-资源分配图表示，这是一种描述进程和资源申请及分配关系的一种有向图，可用于检测系统是否处于死锁状态。

注意：进程-资源分配图中存在环并不一定就发生了死锁。

死锁检测步骤

如果进程-资源分配图中无环，则没有死锁；
如果进程-资源分配图有环，且没有资源类仅一个资源，则发生了死锁
如果进程-资源分配图有环，且涉及资源类有多个，未必死锁。如果能在进程-资源分配图中找出一个 既不阻塞又非独立的进程 ，该进程能够在有限的时间内归还占有的资源，也就是把边给消除掉了，重复此过程，直到能在有限的时间内 消除所有的边 ，则不会发生死锁，否则会发生死锁。

死锁的解除

常用死锁解除方法有四种：

立即结束所有进程的执行，重新启动操作系统：简单但是损失很大。
撤销涉及死锁的所有进程，解除死锁后继续运行：付出代价大
逐步撤销涉及死锁的进程，回收资源直到死锁解除
抢占资源：从涉及死锁的一个或几个进程中抢占资源，把夺得的资源再分配给涉及死锁的进程直至死锁解除。

3. 内存管理

操作系统的内存管理主要负责内存的分配与回收，另外地址转换（将逻辑地址转换成相应的物理地址）等功能也是操作系统内存管理负责。

3.1 常见内存管理机制

简单分为连续分配管理方式和非连续分配管理方式两种。连续分配管理方式指为用户程序分配一个连续的内存空间，如块式管理。分连续分配管理方式允许一个程序使用的内存分配不连续，如页式管理、段式管理。

块式管理：将内存分为几个固定大小的块，每个块中只包含一个进程。如果程序运行需要内存的话，操作系统就分配给它一块，如果程序运行只需要很小的空间的话，分配的这块内存很大一部分几乎被浪费了。这些在每个块中未被利用的空间，我们称之为碎片。
页式管理：把主存分为大小相等且固定的一页一页的形式，页较小，相比于块式管理的划分力度更大，提高了内存利用率，减少了碎片。
段式管理：页式管理虽然提高了内存利用率，但是页式管理其中的页实际并无任何实际意义。段式管理把主存分为一段段的，段是有实际意义的，每个段定义了一组逻辑信息，例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。段式管理通过段表对应逻辑地址和物理地址。
段页式管理：结合了段式管理和页式管理的优点，段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。

分页管理与分段管理的区别？

相同点

分页机制和分段机制都是为了提高内存利用率，减少内存碎片。

页和段都是离散存储的，两者都是离散分配内存的方式。但每个页和段中内存是连续的。

区别

页大小固定，有操作系统决定；段大小不固定，取决于当前运行的程序。

分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段、数据段，能够更好满足用户需求。

3.2 快表与多级页表

页式管理中有两个重要概念：快表与多级页表

快表

快表是为了解决虚拟地址到物理地址的转换速度问题，操作系统在页表基础上引入快表来加速虚拟地址到物理地址的转换。可以把快表理解为一种高速缓存，其中的内容是页表的一部分，使用快表后地址转换流程如下：

根据虚拟地址中页号查询快表
如果该页在快表中，直接从快表中读取相应物理地址
如果该页不在快表中，就访问内存中的页表，再从页表中读取对应物理地址，同时将映射项添加到快表中
当快表填满后，是由淘汰策略淘汰掉快表中的一项

多级页表

引入多级页表的主要目的是为了避免把全部页表一直放在内存中占用过多空间，特别是那些根本就不需要的页表就不需要保留在内存中。多级页表属于时间换空间的典型场景。

3.3 CPU寻址？为什么需要虚拟地址空间？

现代处理器使用的是一种虚拟寻址的寻址方式。使用虚拟寻址，CPU 需要将虚拟地址翻译成物理地址，这样才能访问到真实的物理内存。 实际上完成虚拟地址转换为物理地址转换的硬件是 CPU 中含有一个被称为 内存管理单元（Memory Management Unit, MMU） 的硬件。

为什么要有虚拟地址空间呢？

没有虚拟地址空间的时候，程序都是直接访问和操作物理内存。可能对操作系统造成伤害以及给同时运行多个程序造成困难。

通过虚拟地址访问内存有以下优势：

程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。

程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动

不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

4. 虚拟内存

虚拟内存 可以让程序可以拥有超过系统物理内存大小的可用内存空间。另外，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。这样会更加有效地管理内存并减少出错。

为什么需要虚拟内存？

虚拟内存是操作系统物理内存和进程之间的中间层，它为进程隐藏了物理内存这一概念，为进程提供了更加简洁和易用的接口以及更加复杂的功能。

早期的操作系统进程会直接使用物理地址直接访问内存中的内容，现在引入了虚拟内存，进程持有虚拟地址经过内存管理单元(Memory Mangament Unit)的转换变成物理地址，然后再访问内存。

虚拟内存是充分利用内存的随机访问速度改善程序执行效率的有效方式，操作系统以页的方式管理内存，当进程发现需要访问的数据不在内存时，会将数据以页的方式加载到内存中。虚拟内存起到三个非常关键的作用：

虚拟内存可以结合磁盘和物理内存的优势为进程提供看起来速度足够快并且容量足够大的存储。
虚拟内存可以为进程提供独立的内存空间并引入多层的页表结构将虚拟内存翻译成物理内存，进程之间可以共享物理内存减少开销，也能简化程序的链接、装载以及内存分配过程。
虚拟内存可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性。

作用一：缓存

虚拟内存利用空间较大的磁盘存储作为『内存』并使用主存储缓存进行加速。虚拟页有三种状态：未分配、为缓存和已缓存。

当用户程序访问未被缓存的虚拟页时，硬件会触发缺页中断，在部分情况下，被访问的页面已经加载到了物理内存中，但是用户程序的页表（Page Table）并不存在该对应关系，这时我们只需要在页表中建立虚拟内存到物理内存的关系；在其他情况下，操作系统需要将磁盘上未被缓存的虚拟页加载到物理内存中。

因为主内存的空间有限，所以有了缺页中断和页面替换技术。

作用二：内存管理

因为有多层的页表结构可以用来转换虚拟地址，所以多个进程可以通过虚拟内存共享物理内存。

除了能够共享内存之外，独立的虚拟内存空间也会简化内存的分配过程，当用户程序向操作系统申请堆内存时，操作系统可以分配几个连续的虚拟页，但是这些虚拟页可以对应到物理内存中不连续的页中。

作用三：内存保护

内存管理单元可以决定当前进程是否有权限访问目标的物理内存，这样我们就最终将权限管理的功能全部收敛到虚拟内存系统中。

4.1 局部性原理

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。（在某个较短的时间段内，程序执行局限于某一小部分，程序访问的存储空间也局限于某个区域。）

4.2 虚拟内存的技术实现

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上。有以下三种方式：

请求分页存储管理：建立在分页管理之上，为了支持虚拟存储器功能而增加了请求调页功能和页面置换功能。请求分页存储管理系统中，在作业开始运行之前，仅装入当前要执行的部分段即可运行。假如在作业运行的过程中发现要访问的页面不在内存，则由处理器通知操作系统按照对应的页面置换算法将相应的页面调入到主存，同时操作系统也可以将暂时不用的页面置换到外存中。
请求分段存储管理：建立在分段存储管理之上，增加了请求调段功能、分段置换功能。在作业开始运行之前，仅装入当前要执行的部分段即可运行；在执行过程中，可使用请求调入中断动态装入要访问但又不在内存的程序段；当内存空间已满，而又需要装入新的段时，根据置换功能适当调出某个段，以便腾出空间而装入新的段。
请求段页式存储管理

4.3 页面置换算法

地址映射过程中，若在页面中发现所要访问的页面不在内存中，则发生缺页中断。当发生缺页中断时，如果当前内存中并没有空闲的页面，操作系统就必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。

OPT页面置换算法（最佳页面置换算法）：所选择淘汰的页面将是以后永不使用的，或者是在最长时间内不再被访问的页面。但该算法无法被实现，一般作为衡量其他算法的方法。
FIFO页面置换算法（先进先出）：总是淘汰最先进入内存的页面。
LRU页面置换算法（最近最久未使用页面置换算法）：LRU算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间T，当需要淘汰一个页面时，选择现有页面中T值最大的淘汰。
LFU页面置换算法（最少使用页面置换算法）：选择之前使用最少次数的页面进行淘汰。

5. 五中IO模型

Linux系统为我们提供了五种IO模型：阻塞式IO模型、非阻塞式IO模型、IO多路复用模型、信号驱动IO模型和异步IO模型。

5.1 阻塞式IO模型

应用进程从发起 IO 系统调用，至内核返回成功标识，这整个期间是处于阻塞状态的。

5.2 非阻塞式IO模型

进程发起IO系统调用后，如果内核缓冲区没有数据，需要到IO设备中读取，进程返回一个错误而不会被阻塞；进程发起IO系统调用后，如果内核缓冲区有数据，内核就会把数据返回进程。

5.3 IO多路复用模型

多个的进程的IO可以注册到一个复用器（select）上，然后用一个进程调用该select， select会监听所有注册进来的IO；如果select监听的IO在内核缓冲区都没有可读数据，select调用进程会被阻塞；而当任一IO在内核缓冲区中有可数据时，select调用就会返回；而后select调用进程可以自己或通知另外的进程（注册进程）来再次发起读取IO，读取内核中准备好的数据。

5.4 信号驱动IO模型

当进程发起一个IO操作，会向内核注册一个信号处理函数，然后进程返回不阻塞；当内核数据就绪时会发送一个信号给进程，进程便在信号处理函数中调用IO读取数据。

5.5 异步IO模型

当进程发起一个IO操作，进程返回（不阻塞），但也不能返回果结；内核把整个IO处理完后，会通知进程结果。如果IO操作成功则进程直接获取到数据。

目录