[TOC]

1. 操作系统基本特征

1. 并发

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

并行需要硬件支持，如多流水线或者多处理器。

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

2. 共享

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

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

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

3. 虚拟

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

利用多道程序设计技术，让每个用户都觉得有一个计算机专门为他服务。

主要有两种虚拟技术：时分复用技术和空分复用技术。例如多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占有处理器，每次只执行一小个时间片并快速切换。

4. 异步

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

但只要运行环境相同，OS 需要保证程序运行的结果也要相同。

1.2 中断

1. 中断定义

中断（interrupt）是计算机系统中的基本机制之一。即：在计算机运行过程中，当发生某个事件后，CPU 会停止当前程序流，转而去处理该事件，并在处理完毕后继续执行原程序流。

2. 中断的好处

中断机制的好处是 化主动为被动，避免 CPU 轮询等待某条件成立。如果没有中断机制，那么“某个条件成立”就需要 CPU 轮询判断，这样就会增加系统的开销。而使用中断机制，就可以在条件成立之后，向 CPU 发送中断事件，强制中断 CPU 执行程序，转而去执行中断处理程序。

3. 中断分类

硬中断

硬中断由外部设备（例如：磁盘，网卡，键盘，时钟）产生，用来通知操作系统外设状态变化。

时钟中断： 一种硬中断，用于定期打断 CPU 执行的线程，以便切换给其他线程以得到执行机会。

硬中断的处理流程如下：

• 1. 外设 将中断请求发送给中断控制器；
• 2. 中断控制器 根据中断优先级，有序地将中断传递给 CPU；
• 3. CPU 终止执行当前程序流，将 CPU 所有寄存器的数值保存到栈中；
• 4. CPU 根据中断向量，从中断向量表中查找中断处理程序的入口地址，执行中断处理程序；
• 5. CPU 恢复寄存器中的数值，返回原程序流停止位置继续执行。

软中断

软中断是一条 CPU 指令，由当前正在运行的进程产生。

软中断模拟了硬中断的处理过程：

• CPU 终止执行当前程序流，将 CPU 所有寄存器的数值保存到栈中；
• CPU 根据中断向量，从中断向量表中查找中断处理程序的入口地址，执行中断处理程序；
• CPU 恢复寄存器中的数值，返回原程序流停止位置继续执行。

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

系统调用： 是一种软中断处理程序，用于让程序从用户态陷入内核态，以执行相应的操作。

1.3 系统调用

1. 操作系统与应用的边界

• 内核空间

操作系统（Operating System）是管理计算机硬件与软件资源的程序，操作系统内核驻留在受保护的内核空间。

• 用户空间

应用是运行在操作系统上运行的程序，工作在用户空间。

• 隔离

处于安全性和稳定性考虑，用户空间程序无法直接执行内核代码（例如：I/O 读写、创建新进程/线程），也无法访问内核数据，必须通过系统调用。

2. 系统调用的定义

系统调用（Syscall） 是一种软中断处理程序，用于让程序从用户态陷入内核态，以执行相应的操作。

3. 系统调用的作用

当发生系统调用时，会让程序从用户态陷入内核态，以执行相应的操作。

2.4 系统调用中断处理程序的流程

• 1. 程序从用户态陷入内核态
• 2. 根据系统调用号，在系统调用表中查找对应的系统调用函数的内存地址，执行系统调用函数。
• 3. 程序从内核态返回用户态

补充:

什么是堆和栈？说一下堆栈都存储哪些数据？

​ 栈区（stack）— 由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

​ 堆区（heap） — 一般由程序员分配释放， 若程序员不释放，程序结束时可能由 OS 回收 。

如何理解分布式锁？

​ 分布式锁，是控制分布式系统之间同步访问共享资源的一种方式。在分布式系统中，常常需要协调他们的动作。如果不同的系统或是同一个系统的不同主机之间共享了一个或一组资源，那么访问这些资源的时候，往往需要互斥来防止彼此干扰来保证一致性，在这种情况下，便需要使用到分布式锁。

2. 操作系统基本功能:

1. 进程管理

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

2. 内存管理

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

3. 文件管理

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

4. 设备管理

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

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

2.1 进程管理（重要）

1. 进程

进程是资源分配的基本单位，用来管理资源（例如：内存，文件，网络等资源）

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

进程的构成: 代码段（程序）、数据段（数据）、堆栈段（控制块 PCB）

2. 线程

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

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

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

3. 进程和线程的区别

（一）拥有资源

进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

（二）调度

线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。

（三）系统开销

由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

（四）通信方面

进程间通信 (IPC) 需要进程同步和互斥手段的辅助，以保证数据的一致性。而线程间可以通过直接读或写同一进程中的数据段（如全局变量）来进行通信。

只说出上面的即可，下表格帮助理解:

进程	线程	协程
定义	资源分配和拥有的基本单位	程序执行的基本单位	用户态的轻量级线程，线程内部调度的基本单位
切换情况	进程CPU环境(栈、寄存器、页表和文件句柄等)的保存以及新调度的进程CPU环境的设置	保存和设置程序计数器、少量寄存器和栈的内容	先将寄存器上下文和栈保存，等切换回来的时候再进行恢复
切换者	操作系统	操作系统	用户
切换过程	用户态->内核态->用户态	用户态->内核态->用户态	用户态(没有陷入内核)
调用栈	内核栈	内核栈	用户栈
拥有资源	CPU资源、内存资源、文件资源和句柄等	程序计数器、寄存器、栈和状态字	拥有自己的寄存器上下文和栈
并发性	不同进程之间切换实现并发，各自占有CPU实现并行	一个进程内部的多个线程并发执行	同一时间只能执行一个协程，而其他协程处于休眠状态，适合对任务进行分时处理
系统开销	切换虚拟地址空间，切换内核栈和硬件上下文，CPU高速缓存失效、页表切换，开销很大	切换时只需保存和设置少量寄存器内容，因此开销很小	直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快
通信方面	进程间通信需要借助操作系统	线程间可以直接读写进程数据段(如全局变量)来进行通信	共享内存、消息队列

4. 进程状态的切换（生命周期）

就绪状态（ready）：等待被调度

运行状态（running）

阻塞状态（waiting）：等待资源

• 新建态（new）。进程刚建立，还没有被OS提交到可运行进程队列。

• 终止态（exit）。进程已正常或异常结束，被OS从可运行进程队列中释放出来。

• 新建态—就绪态。对一个处于新建态的进程，在就绪队列能够接纳新进程时，将被系统接收并进入就绪队列，此时的进程状态就从新建态转为就绪态

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过进程调度算法 从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后 就会转为就绪状态，等待下一次调度。

• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

• 进程只能自己阻塞自己，因为只有进程自身才知道何时需要等待某种事件的发生

七种状态模型：

• 挂起就绪态（ready suspend）：进程具备运行条件，但目前在辅助存储器中，只有当进程被兑换到主存时才能调度执行。
• 挂起阻塞态（blocked suspend）：进程正在等待某一事件发生且进程在辅助存储器中。

5. 进程调度算法

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 时间分配给队首的进程。

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

• 进程切换都要保存进程的信息并且载入新进程的信息
• 如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间。

2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。

为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列（重点）

​ 如果一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。多级队列是为这种需要连续执行多个时间片的进程考虑。

​ 设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。

​

​ 多级反馈队列调度算法，“多级” 在于有多个不同优先级的队列，“反馈” 在于如果有进程加入优先级高的队列时立即停止当前任务，转去执行优先级高的队列中进程，上述过程循环调度就形成多级反馈队列调度算法。

​ 每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

​ 可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

6. 进程同步

1. 临界区

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

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

2. 同步与互斥

• 同步：多个进程访问同一个资源有一定的先后执行顺序。

• 互斥：多个进程在同一时刻只有一个进程能进入临界区。

3. 信号量

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

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

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

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

补充: 经典同步问题（了解即可）

• 生产者-消费者问题，了解即可

• 读者 - 写者问题

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

• 哲学家进餐问题

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

  为了防止死锁的发生，可以设置两个条件（临界资源）：

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

7. 进程通信

进程同步与进程通信的区别在于：

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

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

7.1 直接通信

发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。

7.2 间接通信 (管命共消信套)

间接通信方式是指进程之间的通信需要通过作为共享数据结构的实体。该实体用来暂存发送进程发给目标进程的消息。

详细说明间接通信：

7.2.1 管道

netstat -tulnp | grep 8080

含义: 其中" |”是管道的意思，它的作用就是把前一条命令 的输出作为后一条命令的输入，在这里就是把 netstat -tulnp 的输出结果作为 grep 8080 这条命令的输 入。

如果两个进程要进行通信的话，就可以用这种管道来进行通信了，并且我们可以知道这条竖线是没有名字的，所以我们把这种通信方式称之为匿名管道。

匿名管道的特点:

• 并且这种通信方式是单向的，只能把第一个命令的输出作为第二个命令的输入
• 如果进程之间想要 互相通信的话，那么需要创建两个管道。

命名管道:

mkfifo test

这条命令创建了了⼀一个名字为 test 的命名管道。

用一个进程向这个管道里⾯写数据，然后有另外一个进程把里⾯的数据读出来

echo "this is a pipe" > test // 写数据

// 这个时候管道的内容没有被读出的话，那么这个命令就会一直停在这里，只有当另外一个进程把 test 里面的内容读
// 出来的时候这条命令才会结束。接下来我们用另外一个进程来读取

cat < test // 读数据

// test 里面的数据被读取出来了。上一 条命令也执行结束了。

从上面的例子可以看出，管道的通知机制类似于缓存，就像一个进程把数据放在某个缓存区域，然后等着另外一个进程去拿，并且是管道是单向传输的, 并且通信方式效率低下;

不过管道通信比较简单，能够保证我们的数据已经真的被其他进程拿走了。

7.2.2 消息队列

那我们能不能把进程的数据放在某个内存之后就马上让进程返回呢?无需等待其他进程来取就返回呢?

当然是可以的，我们可以用消息队列的通信模式来解决这个问题。

例如 a 进程要给 b 进程发送消息， 只需要把消息放在对应的消息队列里就行了，b 进程需要的时候再去对应的消

息队列里取出来。同理，b 进程要个 a 进程发送消息也是一样。这种通信方式类似于缓存吧。

缺点:

• 如果 a 进程发送的数据占的内存比较大，并且两个进程之间的通 信特别频繁的话，消息队列模型就不大适合了。
• 因为 a 发送的数据很大的话，意味发送消息(拷贝) 这个过程需要花很多时间来读内存。

7.2.3 共享内存

共享内存这个通信方式就可以很好着解决发送/拷贝消息所消耗的时间了。

这个可能有人会问了，每个进程不是有自己的独立内存吗?两个进程怎么就可以共享一块内存了?

我们都知道，系统加载一个进程的时候， 分配给进程的内存并不是实际物理内存，而是虚拟内存空间。那么我们

可以让两个进程各自拿出一块虚拟地址空间来，然后映射到相同的物理内存中，这样， 两个进程虽然有着独立的

虚拟内存空间，但有一部分却是映射到相同的物理内存，这就完成了内存 共享机制了。

7.2.4 信号量

共享内存最大的问题是什么?

就是多进程竞争内存的问题。就像类似于我们平时说的线程安全 问题。

如何解决这个问题?

这个时候我们的信号量就上场了。

信号量的本质就是一个计数器， 用来实现进程之间的互斥与同步。例如信号量的初始值是 1,然后 a 进程来访问内存 1 的时候，我们就把信号量的值设为 0,然后进程 b 也要来访问内存 1 的时候，看到 信号量的值为 0 就知道已经有进程在访问内存 1 了，这个时候进程 b 就会访问不了内存 1。所以说， 信号量也是进程之间的一种通信方式。

7.2.5 Socket

上面我们说的共享内存、管道、信号量、消息队列，他们都是多个进程在一台主机之间的通信， 那 两个相隔几千里的进程能够进行通信吗?

答是必须的，这个时候 Socket 这家伙就派上用场了，例如我们平时通过浏览器发起一个 http 请求, 然后服务器给你返回对应的数据，这种就是采用 Socket 的通信方式了。

补充：线程间通信（了解）

• 信号：类似进程间的信号处理
• 锁机制：互斥锁、读写锁和自旋锁
• 条件变量：使用通知的方式解锁，与互斥锁配合使用
• 信号量：包括无名线程信号量和命名线程信号量

3. 死锁（重要）

1. 死锁的定义

​ 死锁是指两个或两个以上的进程在执行过程中，因争夺资源而造成的一种互相等待的现象，若无 外力作用，它们都将无法推进下去。

造成死锁的原因： （1）因为系统资源不足或分配不当等。（2）进程运行推进顺序不合适。如果系 统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则就会因争夺有限的 资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。

2. 产生死锁的必要条件

• （1）互斥条件：一个资源每次只能被一个进程使用。

• （2）占有和等待条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

• （3） 不剥夺条件：进程已获得的资源，在末使用完之前，不能强行剥夺。

• （4） 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

  比如： A，B，C 若干个进程，B 等待 A 释放资源，C 等待 B 释放资源，A 等待 C 释放资源。

​

​ 这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之 一不满足，就不会发生死锁。

3. 解决死锁的方法

解决死锁主要有四种方法：鸵鸟策略，死锁检测与恢复，死锁预防，死锁避免。

1. 鸵鸟策略

鸵鸟策略：把头埋在沙子里，假装根本没发生问题。

为什么用？因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。

什么时候用？当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。

大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

2. 死锁检测与恢复

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

2.1 死锁检测

（1）深度搜索-进程资源图

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

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

该死锁检测算法是 通过检测进程-资源有向图是否存在环来实现:

​ 从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存 在环，也就是检测到 死锁的发生。

进程-资源有向图描述了进程获得了哪些资源，以及资源被哪些进程获取。

（2）标记法

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

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

算法过程:

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

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

**总结：**标记法，标记不会出现死锁的进程。给每一个进程尝试分配其所请求的资源，如果能成功分 配，那么对该

进程进行标记，并且往资源池里边加入该进程所拥有的资源数量，直到遍历完所有进 程，还没被标记的进程就陷

入了死锁。

2.2 死锁恢复

资源剥夺法：剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。

进程回滚法：根据系统保存的检查点让所有的进程回退，直到足以解除死锁，这种措施要求系统建 立保存检查点、回退及重启机制。

**系统重启法：**结束所有进程的执行并重新启动操作系统。这种方法很简单，但先前的工作全部作废，损失很大。

3. 死锁预防

3.1 破坏互斥条件

如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态。

缺点：** 并不是所有的资源都可以改造成可共享使用的资源，并且为了系统安全，很多地方还必须保护这种 互斥性，因此，很多时候都无法破坏互斥条件

3.2 破坏占有和条件

进程在运行前，一次申请完它所需要的全部资源。

缺点： 有些资源可能只需要用很短的时间，因此如果进程的整个运行期间都一致保持着所有资源，就会造 成严重的资源浪费，资源利用率极低。 另外，该策略也有可能导致某些进程饥饿。

3.3 破坏不可剥夺条件

方案一:

​ 当某个进程请求新的资源得不到满足时，它必须立即释放所保持的所有资源，从而破坏了不可剥夺 条件。

方案二:

​ 当某个进程需要的资源被其他进程所占有的时候，可由操作系统协助，将想要的资源强行剥夺， 这种方式一般需要考虑各进程的优先级，比如剥夺调度方式，就是将处理机资源强行剥夺给优先级 更高的进程使用。

缺点:

方案一：释放已获得的资源可能造成前一阶段你工作的失效。

方案二：抢夺别的进程的资源，相当于将别的经常所获得的资源释放，可能会造成别的进程的前一 阶段的工作失效。

3.3 破坏循环等待条件

给资源编号，规定每个进程必须按编号递增的顺序请求资源。

原理分析： 一个进程只有已占有小编号的资源时，才有资格申请更大编号的资源。按此规则，已持有大编号资 源

的进程不能申请小编号的资源，从而就不会产生循环等待的现象。

比如：进程 A 已占有资源 1,3，进程 B 占有资源 2，进程 B 请求资源 3，进程 A 不能请求占有资源 2， 所以不会出现循环等待现象。并且进程 A 还要先获得资源 1。

缺点： 不方便增加新的设备，因为可能需要重新分配所有的编号。 进程实际使用资源的顺序可能和编号递增顺序不一致，会导致资源浪费。 必须按规定次序申请资源，用户编程麻烦。

4. 死锁避免

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

安全状态:

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

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

只要一直是安全状态就能避免死锁

4. 银行家算法

银行家算法会尝试向一个进程分配资源，然后判断分配资源后的状态是否安全，如果安全那么就会 给这个进程分配请求的资源，否则拒绝请求。

案例:

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

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

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

总结： 银行家算法预先给进程分配资源，然后判断当前是否处于安全状态，如果是，那么对这个进程的资源分配有效，否则无效。

**怎么判断是否处于安全状态呢？**查看资源池所剩资源是否能满足 所有进程中所需资源最小的进程的需求，如果能满足，那么释放该进程的资源，放入进程里边。然 后再继续判断下一个所需资源最小的进程，知道遍历完所有进程，如果能满足所有进程的资源请求， 那么证明当前状态是处于安全状态。

4. 内存管理

4.1 虚拟内存（了解）

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

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

​ 从上面的描述中可以看出，虚拟内存允许程序不用将虚拟地址空间（即程序所需地址空间大小）中 的每一页都映射到物理内存，也就是说不需要将一个程序全部调入内存就可以运行，这使得有限的 内存运行大程序成为可能。

​ 例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围 是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

4.2 分页系统地址映射

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

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

案例:

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

4.3 页面置换算法（重点）

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空

闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

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

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

1. 最佳替换（OPT, Optimal replacement algorithm）

**所选择的被换出的页面是未来最长时间内不再被访问的页面，**通常可以保证获得最低的缺页率。

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

案例：

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

7  0  1  2  0  3  0  4  2  3  0  9  2  1  2  0  1  7  0  1

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

2. 最近最久未使用（LRU，Least Recently Used）

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

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

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

案例：

4  7  0  7  1  0  1  2  1  2  6

3. 最近未使用（NRU，Not Recently Used）

每个页面都有两个状态位：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）。

3. 先进先出（FIFO，First In First Out）

选择置换换出的页面是最先进入的页面。

该算法会将那些经常被访问的页面也被换出，从而使缺页率升高。

4. 第二次机会算法

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

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

5. 时钟算法

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

当内存不足需要页面置换时，检查指针指向的页面：

• R=0，则直接替换
• R=1，将 R 设置为 0，并将指针前进。

4.4 分段（了解）

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

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

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

4.5 段页式

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

4.6 分页和分段的比较

共同点：两者都采用离散分配方式，且都地址映射机构来实现地址的转换

不同点：

1. 页是信息的物理单位采用分页存储管理方式是为了实现离散分配方法。提高内存的利用率，采用分段目的主要在于能更好的满足用户的需求
2. 页的大小固定且有系统决定，在采用分页存储管理方式中直接由硬件实现。而段的大小不固定，决定于用户所编写的程序
3. 分页的地址空间是一维的，分页完全是系统完全是行为，分段系统中是二维的。

4.7 快表（掌握）

为了解决虚拟地址到物理地址的转换速度，操作系统在页表方案基础之上引入了 快表 来加速虚拟地址到物理地址

的转换。

我们可以把快表理解为一种特殊的高速缓冲存储器 （Cache），其中的内容是页表的一部分或者全部内容，它的

作用与页表相似，但是提高了访问速率。

由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

使用快表之后的地址转换流程：

1. 根据虚拟地址中的页号查快表；

2. 如果该页在快表中，直接从快表中读取相应的物理地址；

3. 如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；

4. 当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

5. 磁盘管理

5.1 磁盘结构

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

4.2 磁盘调度算法（重点）

读写一个磁盘块（由扇区组成）的时间的影响因素有：

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

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

1. 先来先服务（FCFS， First Come First Served）

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

优点：公平和简单。

缺点：因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先算法（SSTF， Shortest Seek Time First）

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

优点：平均寻道时间比较低。

缺点：但是不够公平。

如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去， 也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

3. 电梯算法（SCAN）

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

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

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

4.3 链接

以下是一个 hello.c 程序：

#include <stdio.h>

int main()
{
    printf("hello, world\n");
    return 0;
}

在 Unix 系统上，由编译器把源文件转换为目标文件:

gcc -o hello hello.c

这个过程大致如下：

• 预处理阶段：处理以 # 开头的预处理命令；
• 编译阶段：翻译成汇编文件；
• 汇编阶段：将汇编文件翻译成可重定位目标文件；
• 链接阶段：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件。

1. 静态链接

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

• 符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
• 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的 引用，使得它们指向这个内存位置。

补充：

目标文件:

• 可执行目标文件：可以直接在内存中执行；
• 可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；
• 共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；

2. 动态链接

静态库有以下两个问题：

• 当静态库更新时那么整个程序都要重新进行链接；
• 对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：

• 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
• 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。

6. 常见问题

系统相关:

1. 操作系统为什么有用户态和内核态，用户级线程与内核级线程如何转换？

（1）操作系统为什么有用户态和内核态：

​ 在计算机系统中，通常运行着两类程序：系统程序和应用程序，为了保证系统程序不被应用程序有 意或无意地破坏，为计算机设置了两种状态：

• 内核态，操作系统程序在内核态运行
• 用户态，应用程序只能在用户态运行

（2）用户态和内核态如何相互转换：

• 用户态切换到内核态的途径——>中断/异常/陷入（系统调用）

• 内核态切换到用户态的途径——>设置程序状态字

2. 操作系统的内核态包括的哪些内容？

1. 时钟管理：向用户提供标准的系统时间，另外通过时钟中断的管理，可以实现进程的切换。 例如时间片轮转算法。
2. 原语：处于操作系统最底层，是最接近硬件的部分、这些程序的运行具有原子性，其操作只 能一气呵成（
3. 中断机制
4. 系统控制的数据结构以及处理：进程控制块。

3. 异常和中断的区别

**中断：**中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，有内核处理中断。

**异常：**异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常；比如CPU处理程序的时候一旦程序不在内存中，会产生缺页异常；当运行除法程序时，当除数为0时，又会产生除0异常。

相同点

• 最后都是由CPU发送给内核，由内核去处理
• 处理程序的流程设计上是相似的

不同点

• 产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的
• 内核需要根据是异常还是中断调用不同的处理程序
• 中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以它是时钟同步的
• 当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中

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

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

4. 请介绍局部性原理，主要有哪两大局部性原理？各自是什么？

主要分为时间局部性和空间局部性。

• 时间局部性:如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行;如果某个数据被访问过，
• 不久之后该数据很可能再次被访问。(因为程序中存在大量的循环)
• 空间局部性:一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。(因为很多数
• 据在内存中都是连续存放的，并且程序的指令也是顺序地在内存中存放的)

5. 系统并发和并行，分得清吗？

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

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

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

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

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

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

7. 同步、异步、阻塞、非阻塞（金典题）

同步与异步 同步和异步关注的是消息通信机制 (synchronous communication/ asynchronous communication) 所谓同步，就是在发出一个调用时，在没有得到结果之前，该调用就不返回。但是一旦调用返回，就得到返回值了。 换句话说，就是由调用者主动等待这个调用的结果。

而异步则是相反，调用在发出之后，这个调用就直接返回了，所以没有返回结果。换句话说，当一个异步过程调用发出后，调用者不会立刻得到结果。而是在调用发出后，被调用者通过状态、通知来通知调用者，或通过回调函数处理这个调用。

阻塞与非阻塞 阻塞和非阻塞关注的是程序在等待调用结果（消息，返回值）时的状态.

阻塞调用是指调用结果返回之前，当前线程会被挂起。调用线程只有在得到结果之后才会返回。 非阻塞调用指在不能立刻得到结果之前，该调用不会阻塞当前线程。

进程相关:

1. 一个进程可以创建多少线程，和什么有关？

理论上，一个进程可用虚拟空间是2G，默认情况下，线程的栈的大小是1MB，所以理论上最多只能创建2048个线程。如果要创建多于2048的话，必须修改编译器的设置。

因此，一个进程可以创建的线程数由可用虚拟空间和线程的栈的大小共同决定，只要虚拟空间足够，那么新线程的建立就会成功。如果需要创建超过2K以上的线程，减小你线程栈的大小就可以实现了。但是过多的线程将会导致大量的时间浪费在线程切换上，给程序运行效率带来负面影响。

2. 介绍几种常见的锁（线程锁）

（1）读写锁

• 多个读者可以同时进行读
• 写者必须互斥（只允许一个写者写，也不能读者写者同时进行）
• 写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）

（2）互斥锁：一次只能一个线程拥有互斥锁，其他线程只有等待

​ 互斥锁是在抢锁失败的情况下主动放弃CPU进入睡眠状态直到锁的状态改变时再唤醒，而操作系统负责线程调度，为了实现锁的状态发生改变时唤醒阻塞的线程或者进程，需要把锁交给操作系统管理，所以互斥锁在加锁操作时涉及上下文的切换。互斥锁实际的效率还是可以让人接受的，加锁的时间大概100ns左右，而实际上互斥锁的一种可能的实现是先自旋一段时间，当自旋的时间超过阀值之后再将线程投入睡眠中，因此在并发运算中使用互斥锁（每次占用锁的时间很短）的效果可能不亚于使用自旋锁。

（3）条件变量 互斥锁一个明显的缺点是他只有两种状态：锁定和非锁定。

​ 而条件变量通过允许线程阻塞和等待另一个线程发送信号的方法弥补了互斥锁的不足，他常和互斥锁一起使用，以免出现竞态条件。当条件不满足时，线程往往解开相应的互斥锁并阻塞线程然后等待条件发生变化。一旦其他的某个线程改变了条件变量，他将通知相应的条件变量唤醒一个或多个正被此条件变量阻塞的线程。总的来说互斥锁是线程间互斥的机制，条件变量则是同步机制。

（4）自旋锁 如果进线程无法取得锁，进线程不会立刻放弃CPU时间片，而是一直循环尝试获取锁，直到获取为止。如果别的线程长时期占有锁，那么自旋就是在浪费CPU做无用功，但是自旋锁一般应用于加锁时间很短的场景，这个时候效率比较高。

3. 怎么回收线程？有哪几种方法？

（1）等待线程结束：int pthread_join(pthread_t tid, void** retval);

（2）主线程调用，等待子线程退出并回收其资源，类似于进程中wait/waitpid回收僵尸进程。

（3）结束线程：pthread_exit(void *retval);

​ 子线程执行，用来结束当前线程并通过retval传递返回值，该返回值可通过pthread_join获得。

（4）分离线程：int pthread_detach(pthread_t tid);

​ 主线程、子线程均可调用。主线程中pthread_detach(tid)，子线程中pthread_detach(pthread_self())，调用后和主线程分离，子线程结束时自己立即回收资源。

4. 进程终止的几种方式

1. main函数的自然返回，return
2. 调用exit函数，属于c的函数库
3. 调用_exit函数，属于系统调用
4. 调用abort函数，异常程序终止，同时发送SIGABRT信号给调用进程。
5. 接受能导致进程终止的信号：ctrl+c (^C)、SIGINT(SIGINT中断进程)

5. 多进程和多线程的区别是什么？换句话说，什么时候该用多线程，什么时候该用多进程？

• 频繁修改：需要频繁创建和销毁的优先使用多线程
• 计算量：需要大量计算的优先使用多线程 因为需要消耗大量CPU资源且切换频繁，所以多线程好一点
• 相关性：任务间相关性比较强的用多线程，相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。
• 多分布：可能要扩展到多机分布的用多进程，多核分布的用多线程。
• 但是实际中更常见的是进程加线程的结合方式，并不是非此即彼的。

内存相关:

1. 内存交换和覆盖有什么区别？ 交换技术主要是在不同进程（或作业）之间进行，而覆盖则用于同一程序或进程中。

内存的覆盖是什么？有什么特点？ 由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成

为一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按照调用关系分段，首先将那些即将要访

问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。

​ 覆盖技术的特点：是打破了必须将一个进程的全部信息装入内存后才能运行的限制，但当同时运行程序的代

码量大于主存时仍不能运行，再而，大家要注意到，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常

驻内存。

内存交换是什么？有什么特点？ 交换(对换)技术的设计思想：内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)。

​ 换入：把准备好竞争CPU运行的程序从辅存移到内存。

​ 换出：把处于等待状态（或CPU调度原则下被剥夺运行权力）的程序从内存移到辅存，把内存空间腾出来。

什么时候会进行内存的交换？ 内存交换通常在许多进程运行且内存吃紧时进行，而系统负荷降低就暂停。例如:在发现许多进程运行时经常

发生缺页，就说明内存紧张，此时可以换出一些进程;如果缺页率明显下降，就可以暂停换出。

2. 动态分区分配算法有哪几种？可以分别说说吗？（了解）

（1）首次适应算法 算法思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区。

如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链( 或空闲分[表)，找到大小能满足要求的第一个空闲分区。

（2）最佳适应算法 算法思想:由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区, 优先使用更小的空闲区。

如何实现:空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

（3）最坏适应算法 又称最大适应算法(Largest Fit)

算法思想:为了解决最佳适应算法的问题-即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。

如何实现:空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

（4）邻近适应算法

首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。

如何实现：空闲分区以地址递增的顺序排列(可排成-一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。

（5）总结 首次适应不仅最简单，通常也是最好最快，不过首次适应算法会使得内存低地址部分出现很多小的空闲分区，而每次查找都要经过这些分区，因此也增加了查找的开销。邻近算法试图解决这个问题，但实际上，它常常会导致在内存的末尾分配空间分裂成小的碎片，它通常比首次适应算法结果要差。

最佳导致大量碎片，最坏导致没有大的空间。

算法	算法思想	分区排列顺序	优点	缺点
首次适应	从头到尾找适合的分区	空闲分区以地址递增次序排列	综合看性能最好。算法开销小，回收分区后一.般不需要对空闲分区队列重新排序
最佳适应	优先使用更小的分区，以保留更多大分区	空闲分区以容量递增次序排列	会有更多的大分区被保留下来，更能满足大进程需求	会产生很多太小的、难以利用的碎片;算法开销大，回收分区后可能需要对空闲分区队列重新排序
最坏适应	优先使用更大的分区，以防止产生太小的不可用的碎片	空闲分区以容量递减次序排列	可以减少难以利用的小碎片	大分区容易被用完，不利于大进程;算法开销大(原因同上)
邻近适应	由首次适应演变而来，每次从上次查找结束位置开始查找	空闲分区以地址递增次序排列(可排列成循环链表)	不用每次都从低地址的小分区开始检索。算法开销小(原因同首次适应算法)	会使高地址的大分区也被用完

3. 介绍虚拟技术

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

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

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

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

4. 操作系统在对内存进行管理的时候需要做些什么?

1. 操作系统负责内存空间的分配与回收。
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充。
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换。
4. 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰

5. 内存分配方式

（1） 从静态存储区域分配。内存在程序编译的时候就已经分配好，这块内存在程序的整个运行期间都存在。例如全局变量，static变量。

（2） 在栈上创建。在执行函数时，函数内局部变量的存储单元都可以在栈上创建，函数执行结束时这些存储单元自动被释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

（3） 从堆上分配，亦称动态内存分配。程序在运行的时候用malloc或new申请任意多少的内存，程序员自己负责在何时用free或delete释放内存。动态内存的生存期由我们决定，使用非常灵活，但问题也最多。

6. 常见内存分配内存错误

（1）内存分配未成功，却使用了它。

（2）内存分配虽然成功，但是尚未初始化就引用它。

（3）内存分配成功并且已经初始化，但操作越过了内存的边界。

（4）忘记了释放内存，造成内存泄露。

（5）释放了内存却继续使用它。

7. 内存交换中，被换出的进程保存在哪里？保存在磁盘中，也就是外存中。

​ 具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件主要用于存放文件，主要追

求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的

进程数据就存放在对换区。

​ 由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式(学过文件管理章节后即可理解)。总之，对换区的I/O速度比文件区的更快。

8. 虚拟内存和共享内存

（1）虚拟内存:

虚拟内存是一种内存管理方式，它通过把程序切成小块，只把目前需要的部分放入物理内存中，其他的部分暂存在磁盘上，也被称为虚拟存储器。

物理存储器和虚拟存储器都被分割为许多大小相同的块，分别称为物理页与虚拟页，二者之间的映射关系用页表记录。

虚拟内存的好处:

• 扩大地址空间：例如虚拟地址空间32位，物理地址空间24位。
• 公平内存分配：每个进程都相当于有同样大小的虚存空间。
• 内存保护：每个进程运行在各自的虚拟内存地址空间，互相不能干扰对方。
• 节省内存：当不同的进程使用同样的代码时（比如库文件中的代码），物理内存中可以只存储一份代码，不同的进程把自己的虚拟内存映射到同一物理内存上。
• 利用碎片：在程序需要分配连续的内存空间的时候，只需要在虚拟内存空间分配连续空间，而不需要实际物理内存的连续空间，可以利用物理空间的碎片。

（2） 共享内存

共享内存是一种进程间通信方式，允许不同进程将自己的虚拟地址映射到同一块物理地址上，从而共享同一段物理内存。

（3）内存映射是什么

内存映射主要是mmap系统调用，是指将一个文件或者其它对象映射到进程地址空间的方法。

内存映射的好处：

• 读文件比普通磁盘I/O要快：普通磁盘I/O读写文件要先把内容拷贝到页缓存（内核空间）中，然后再拷贝到用户空间中供使用，有2次拷贝。 而mmap读写文件是利用缺页异常把文件内容从磁盘换到用户空间中，只有1次拷贝，因此效率较高。
• 实现共享内存：不同进程使用mmap将自身用户空间映射到同一文件或同一匿名区域，实现高效的进程间通信。

磁盘管理相关

1. 一个程序从开始运行到结束的完整过程（了解） 四个过程：

（1）预编译/预处理 主要处理源代码文件中的以“#”开头的预编译指令。

（2）编译 把预编译之后生成的xxx.i或xxx.ii文件，进行一系列词法分析、语法分析、语义分析及优化后，生成相应的汇编代码文件。

（3）汇编

将汇编代码转变成机器可以执行的指令(机器码文件)。 汇编器的汇编过程相对于编译器来说更简单，没有复杂的语法，也没有语义，更不需要做指令优化，只是根据汇编指令和机器指令的对照表一一翻译过来，汇编过程由汇编器完成。经汇编之后，产生目标文件。

（4）链接

将不同的源文件产生的目标文件进行链接，从而形成一个可以执行的程序。链接分为静态链接和动态链接：

1、静态链接： 函数和数据被编译进一个二进制文件。在使用静态库的情况下，在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。 空间浪费：因为每个可执行程序中对所有需要的目标文件都要有一份副本，所以如果多个程序对同一个目标文件都有依赖，会出现同一个目标文件都在内存存在多个副本； 更新困难：每当库函数的代码修改了，这个时候就需要重新进行编译链接形成可执行程序。

运行速度快：但是静态链接的优点就是，在可执行程序中已经具备了所有执行程序所需要的任何东西，在执行的时候运行速度快。

2、动态链接： 动态链接的基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

共享库：就是即使需要每个程序都依赖同一个库，但是该库不会像静态链接那样在内存中存在多份副本，而是这多个程序在执行时共享同一份副本；

更新方便：更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会被自动加载到内存并且链接起来，程序就完成了升级的目标。

性能损耗：因为把链接推迟到了程序运行时，所以每次执行程序都需要进行链接，所以性能会有一定损失。

版权所有

版权归属：cloudinwind

本文链接：/review/z8zwnh1e/

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)