操作系统

1 操作系统的基本概念

1. 操作系统（Operating System，简称 OS）是管理计算机硬件与软件资源的程序，是计算机的基石。
2. 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬件和软件资源。 举例：运行在你电脑上的所有应用程序都通过操作系统来调用系统内存以及磁盘等等硬件。
3. 操作系统存在屏蔽了硬件层的复杂性。 操作系统就像是硬件使用的负责人，统筹着各种相关事项。
4. 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。 内核是连接应用程序和硬件的桥梁，决定着系统的性能和稳定性。

操作系统的内核（Kernel）

维基百科对于内核的解释： >内核（英语：Kernel，又称核心）在计算机科学中是一个用来管理软件发出的数据 I/O（输入与输出）要求的电脑程序，将这些要求转译为数据处理的指令并交由中央处理器（CPU）及电脑中其他电子组件进行处理，是现代操作系统中最基本的部分。它是为众多应用程序提供对计算机硬件的安全访问的一部分软件，这种访问是有限的，并由内核决定一个程序在什么时候对某部分硬件操作多长时间。 直接对硬件操作是非常复杂的。所以内核通常提供一种硬件抽象的方法，来完成这些操作。有了这个，通过进程间通信机制及系统调用，应用进程可间接控制所需的硬件资源（特别是处理器及 IO 设备）。

早期计算机系统的设计中，还没有操作系统的内核这个概念。随着计算机系统的发展，操作系统内核的概念才渐渐明晰起来了!

简单概括两点：

• 操作系统的内核（Kernel）是操作系统的核心部分，它负责系统的内存管理，硬件设备的管理，文件系统的管理以及应用程序的管理。
• 操作系统的内核是连接应用程序和硬件的桥梁，决定着操作系统的性能和稳定性。

中央处理器（CPU，Central Processing Unit）

关于 CPU 简单概括三点：

• CPU 是一台计算机的运算核心（Core）+控制核心（ Control Unit），可以称得上是计算机的大脑。
• ** CPU 主要包括两个部分：控制器+运算器。**
• CPU 的根本任务就是执行指令，对计算机来说最终都是一串由“0”和“1”组成的序列。

CPU vs Kernel(内核)

可以简单从下面两点来区别：

• 操作系统的内核（Kernel）属于操作系统层面，而 CPU 属于硬件。
• CPU 主要提供运算，处理各种指令的能力。内核（Kernel）主要负责系统管理比如内存管理，它屏蔽了对硬件的操作。

2 操作系统的基本特性

操作系统的基本特性是并发性、共享性、虚拟性、异步性。

并发性

并行性和并发性(Concurrence)是既相似又有区别的两个概念，并行性是指两个或多个事件在同一时刻发生；而并发性是指两个或多个事件在同一时间间隔内发生。在多道程序环境下，并发性是指在一段时间内宏观上有多个程序在同时运行，但在单处理机系统中，每一时刻却仅能有一道程序执行，故微观上这些程序只能是分时地交替执行。（宏观并发微观串行）

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

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

共享性

指系统中的资源可供内存中多个并发执行的进程(线程)共同使用，相应地，把这种资源共同使用称为资源共享，或称为资源复用。目前主要实现资源共享的方式有：

• 互斥共享方式
• 同时访问方式

互斥共享方式

当一个进程 A 要访问某资源时，必须先提出请求。如果此时该资源空闲，系统便可将之分配给请求进程 A 使用。此后若再有其它进程也要访问该资源时(只要 A 未用完)，则必须等待。仅当 A 进程访问完并释放该资源后，才允许另一进程对该资源进行访问。我们把这种资源共享方式称为互斥式共享，而把在一段时间内只允许一个进程访问的资源称为临界资源或独占资源，例如打印机。

同时访问方式

系统中还有另一类资源，允许在一段时间内由多个进程“同时”对它们进行访问。这里所谓的“同时”，在单处理机环境下往往是宏观上的，而在微观上，这些进程可能是交替地对该资源进行访问。典型的可供多个进程“同时”访问的资源是磁盘设备，一些用重入码编写的文件也可以被“同时”共享，即若干个用户同时访问该文件。

虚拟性

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

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

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

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

异步性

在多道程序环境下允许多个进程并发执行，但只有进程在获得所需的资源后方能执行。在单处理机环境下，由于系统中只有一台处理机，因而每次只允许一个进程执行，其余进程只能等待。进程是以人们不可预知的速度向前推进，此即进程的异步性。

3 操作系统的基本功能

操作系统的基本功能包括进程管理、内存管理、文件管理、设备管理。

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

4 什么是系统调用/用户态和系统态是？

根据进程访问资源的特点，可以把进程在系统上的运行分为两个级别：

• ** 用户态(user mode) **: 用户态运行的进程或程序可以直接读取用户程序的数据。
• 系统态(kernel mode):可以简单的理解系统态运行的进程或程序几乎可以访问计算机的任何资源，不受限制。

我们运行的程序基本都是运行在用户态，如果要调用操作系统提供的系统态级别的子功能，那就需要系统调用了！

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

这些系统调用按功能大致可分为如下几类：

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

为什么要有用户态与内核态?

在 cpu 的所有指令中，有些指令是非常危险的，如果使用不当，将会造成系统崩溃等后果。为了避免这种情况发生，cpu 将指令划分为特权级(内核态)指令和非特权级(用户态)指令。

对于那些危险的指令只允许内核及其相关模块调用，对于那些不会造成危险的指令，就允许用户应用程序调用。

• 内核态(核心态,特权态): 内核态是操作系统内核运行的模式。 内核态控制计算机的硬件资源，如硬件设备，文件系统等等，并为上层应用程序提供执行环境。
• 用户态: 用户态是用户应用程序运行的状态。 应用程序必须依托于内核态运行,因此用户态的操作权限比内核态是要低的，如磁盘，文件等，访问操作都是受限的。
• 系统调用: 系统调用是操作系统为应用程序提供能够访问到内核态的资源的接口。

用户态切换到内核态的几种方式

• 系统调用: 系统调用是用户态主动要求切换到内核态的一种方式，用户应用程序通过操作系统调用内核为上层应用程序开放的接口来执行程序。
• 异常: 当 cpu 在执行用户态的应用程序时，发生了某些不可知的异常。于是当前用户态的应用进程切换到处理此异常的内核的程序中去。
• 硬件设备的中断: 当硬件设备完成用户请求后，会向 cpu 发出相应的中断信号，这时 cpu 会暂停执行下一条即将要执行的指令，转而去执行与中断信号对应的应用程序，如果先前执行的指令是用户态下程序的指令，那么这个转换过程也是用户态到内核台的转换。

5 计算机的局部性原理

一个编写良好的计算机程序常常具有良好的局部性，即他们更加倾向于引用邻近于其他最近引用过的数据项的数据项，或者最近引用或的数据项本身，这种特性，常常称为局部性原理。局部性由两种不同的形式：时间局部性和空间局部性

• 时间局部性：被引用过一次的内存位置很有可能在不久的将来再次被多次引用。
• 空间局部性：一个内存被引用过了，那么极有可能在不久的将来会引用器附近的内存位置。在高速缓存中的表现形式是以数据块的形式进行缓存，弥补未命中时的惩罚

我们应该理解局部性原理，因为一般而言，一个良好局部性的程序比局部性差的程序运行得更快，这是由现代计算机系统得设计结构所决定得，在现代计算系统得各个层次之哦你给，都引入了局部性原理：

• 在硬件层，计算机设计者通过引入称为高速缓存存储器这样小而快得快速存储器来保存最近引用得指令和数据项，从而提高对主存得访问速度。
• 在操作系统中，系统使用主存作为虚拟地址空间，来存储最近被引用得数据项，来避免因从磁盘取数据过慢而导致CPU资源的浪费
• 类似的，用主存来缓存磁盘文件中最近被使用的磁盘块。
• 局部性原理在应用程序中也有应用，入Web浏览器将最近引用的文档放在本地磁盘上，利用的就是时间局部性。

6 磁盘调度算法

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

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

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

先来先服务

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

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

最短寻道时间优先

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

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

电梯扫描算法

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

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

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

7 进程、线程和协程的区别和联系

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

1、进程是资源调度的基本单位，运行一个可执行程序会创建一个或多个进程，进程就是运行起来的可执行程序

2、线程是程序执行的基本单位，是轻量级的进程。每个进程中都有唯一的主线程，且只能有一个，主线程和进程是相互依存的关系，主线程结束进程也会结束。多提一句：协程是用户态的轻量级线程，线程内部调度的基本单位

线程和进程的区别？

• 进程：程序是存放在存储介质上的一个可执行文件，而进程是程序执行的过程。进程的状态是变化的，其包括进程的创建、调度和消亡。程序是静态的，进程是动态的。是CPU分配资源的最小单位
• 线程：线程（thread）是操作系统能够进行运算调度的最小单位，它被包含在进程之中，是进程中的实际运作单位。线程是CPU调度的最小单位

关系：

• 一个进程可有多个线程
• 进程间很难共享数据，线程很容易实现数据共享
• 进程比线程消耗更多的计算机资源
• 进程使用的内存地址可以上锁，即一个线程使用某些共享内存时，其他线程必须等它结束，才能使用这一块内存。
• 进程间不会相互影响，一个线程挂掉将导致整个进程挂掉

进程，直观点说，保存在硬盘上的程序运行以后，会在内存空间里形成一个独立的内存体，这个内存体有自己的地址空间，有自己的堆，上级挂靠单位是操作系统。操作系统会以进程为单位，分配系统资源，所以我们也说，进程是CPU分配资源的最小单位。

线程存在与进程当中(进程可以认为是线程的容器)，是操作系统调度执行的最小单位。说通俗点，线程就是干活的，轻量级进程。线程自己基本上不拥有系统资源，只拥有一点在运行中必不可少的资源（如程序计数器，一组寄存器和栈），但是它可与同属一个进程的其他的线程共享进程所拥有的全部资源。（是为避免进程fork()产生写时拷贝的不必要时间和内存支出）

• 调度：线程是调度的基本单位（PC，状态码，通用寄存器，线程栈及栈指针）；进程是拥有资源的基本单位（打开文件，堆，静态区，代码段等）。

• 并发性：一个进程内多个线程可以并发（最好和CPU核数相等）；多个进程可以并发。

• 拥有资源：线程不拥有系统资源，但一个进程的多个线程可以共享隶属进程的资源；进程是拥有资源的独立单位。

• 系统开销：线程创建销毁只需要处理PC值，状态码，通用寄存器值，线程栈及栈指针即可；进程创建和销毁需要重新分配及销毁task_struct结构

协程

协程本质上是一种用户态的轻量级线程，协程的调度完全由用户控制。

传统意思上来说，线程分为内核态线程和用户态线程，用户态线程需要绑定内核态线程，CPU并不能感知用户态线程的存在，它只知道它在运行1个线程，这个线程实际是内核态线程。用户态线程实际有个名字就叫协程（co-routine），为了容易区分，使用协程指用户态线程，使用线程指内核态线程。

协程跟线程是有区别的，线程由 CPU 调度是抢占式的，协程由用户态调度是协作式的，一个协程让出CPU后，才执行下一个协程。

协程和线程有3种映射关系：

• N:1，N个协程绑定1个线程，优点就是协程在用户态线程即完成切换，不会陷入到内核态，这种切换非常的轻量快速。但也有很大的缺点，1个进程的所有协程都绑定在1个线程上，一是某个程序用不了硬件的多核加速能力，二是一旦某协程阻塞，造成线程阻塞，本进程的其他协程都无法执行了，根本就没有并发的能力了。
• 1:1，1个协程绑定1个线程，这种最容易实现。协程的调度都由CPU完成了，不存在N:1缺点，但有一个缺点是协程的创建、删除和切换的代价都由CPU完成，有点略显昂贵了。
• M:N，M个协程绑定N个线程，是N:1和1:1类型的结合，克服了以上2种模型的缺点，但实现起来最为复杂。

协程拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈，直接操作栈则基本没有内核切换的开销，可以不加锁的访问全局变量，所以上下文的切换非常快。

• 协程是属于线程的。协程程序是在线程里面跑的，因此协程又称微线程和纤程等
• ** 协程没有线程的上下文切换消耗**。协程的调度切换是用户(程序员)手动切换的，因此更加灵活,因此又叫用户空间线程.
• 原子操作性。由于协程是用户调度的，所以不会出现执行一半的代码片段被强制中断了，因此无需原子操作锁

• 协程的优点：

• 跨平台,跨体系架构
• 无需线程上下文切换的开销
• 无需原子操作锁定及同步的开销
• 方便切换控制流，简化编程模型

• 高并发+高扩展性+低成本：一个 CPU 支持上万的协程都不是问题。所以很适合用于高并发处理。

缺点：

• 无法利用多核资源：协程的本质是个单线程，它不能同时将单个 CPU 的多个核用上，协程需要和进程配合才能运行在多 CPU 上。当然我们日常所编写的绝大部分应用都没有这个必要，除非是 cpu 密集型应用。
• 进行阻塞（Blocking）操作（如IO时）会阻塞掉整个程序：这一点和事件驱动一样，可以使用异步IO操作来解决

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

这个要分不同系统去看：

• 如果是32 位系统，用户态的虚拟空间只有 3G，如果创建线程时分配的栈空间是 10M，那么一个进程最多只能创建 300 个左右的线程。
• 如果是64 位系统，用户态的虚拟空间大到有 128T，理论上不会受虚拟内存大小的限制，而会受系统的参数或性能限制。

顺便多说一句，过多的线程将会导致大量的时间浪费在线程切换上，给程序运行效率带来负面影响，无用线程要及时销毁

9 线程的调度怎么完成的？

线程调度的完成通常涉及以下几个步骤：

• 1.首先选择调度算法：操作系统可以使用不同的调度算法来决定线程的执行顺序。常见的调度算法包括先来先服务（FCFS）、最短作业优先（SJF）、轮转调度（Round Robin）等。选择适合系统需求的调度算法是很重要的。
• 2.确定优先级：每个线程通常都有一个优先级，优先级决定了线程被调度的顺序。高优先级的线程会被优先执行，而低优先级的线程则可能被延迟执行。操作系统可以根据线程的类型、重要性等因素来确定线程的优先级。
• 3. 创建和管理线程队列：操作系统会维护一个线程队列，用于存储等待执行的线程。当一个线程需要执行时，它会被添加到队列中。调度器会从队列中选择一个线程，并将其分配给可用的处理器执行。
• 4. 上下文切换：当调度器决定切换到另一个线程时，它会进行上下文切换操作。上下文切换包括保存当前线程的上下文信息（如寄存器状态、程序计数器等），并加载下一个线程的上下文信息，以便继续执行。
• 5. 执行线程：一旦调度器选择了一个线程，并完成了上下文切换，该线程就会开始执行。线程执行的时间片通常是有限的，当时间片用完后，调度器会再次选择下一个线程执行

进程切换的过程？

进程切换的过程主要包括以下步骤：

• 保存当前进程状态：当需要进行进程切换时，操作系统会首先保存当前正在运行的进程的状态。这包括程序计数器、寄存器等中间数据，这些数据会被保存在进程控制块（PCB）中。
• 更新PCB信息：接着，操作系统会更新PCB的信息。例如，它会更新进程的状态，如将当前进程的状态从运行状态更改为阻塞状态，并将其加入阻塞队列。
• 选择下一个进程执行：然后，操作系统会选择另一个进程进行执行。这通常涉及到从就绪队列中选择一个进程，并将其状态从就绪转为运行状态。
• 加载新进程上下文：在选择新的进程执行后，操作系统会加载该进程的上下文。这包括从PCB中取出新进程的中间数据，如程序计数器和寄存器的值，以便新进程可以继续执行。

9 操作系统的内存分配设计原理是怎样样的？

操作系统的内存分配设计原理主要基于虚拟内存、内存分页、内存分段以及多种内存分配算法。

• 虚拟内存：操作系统为每个进程分配一个虚拟地址空间，这个空间远大于实际的物理内存。进程在运行时，其所需的代码、数据等被映射到虚拟地址空间中。当进程需要访问某个虚拟地址时，如果该地址对应的物理内存页尚未加载，则发生缺页中断，操作系统负责将该页从磁盘或其他存储介质加载到物理内存中。这种方式有效地扩展了可用内存，使得程序可以像使用大内存一样运行。
• 内存分页：操作系统将物理内存划分为固定大小的页，每页的大小通常是固定的，如4KB。同样，虚拟地址空间也被划分为页。当进程需要访问某个虚拟页时，操作系统通过页表查找该页对应的物理页。如果物理页不存在，则触发缺页中断。
• 内存分段：与分页不同，分段是根据程序的逻辑结构来划分内存的。每个段都有自己的名称和长度，并且可以有不同的访问权限。这种方式可以更好地管理程序的内存使用，但实现起来相对复杂。
• 内存分配算法：操作系统使用多种算法来管理内存分配，包括首次适应算法、最佳适应算法、最坏适应算法等。这些算法在分配内存时考虑不同的因素，如分配速度、内存碎片等。例如，首次适应算法从空闲链表的起始位置开始查找，找到第一个满足需求的空闲分区进行分配；而最佳适应算法则查找最小的满足需求的空闲分区进行分配，以减少内存碎片。

操作系统的内存分配设计原理是为了高效、公平、安全地管理计算机系统的内存资源。通过虚拟内存、内存分页、内存分段以及多种内存分配算法，操作系统能够在有限的物理内存条件下满足多个进程的运行需求，提高系统的整体性能。

10 malloc 是怎么实现的

malloc是C语言中用于动态分配内存的函数。它的实现方式可以因编译器和操作系统而异，下面是一种常见的实现方式：

• 1.首先，malloc函数会接收一个参数，即需要分配的内存大小。
• 2.malloc函数会检查当前的空闲内存块链表，查找是否有足够大小的空闲内存块。
• 3.如果找到了足够大小的空闲内存块，则将其从空闲内存块链表中移除，并返回该内存块的起始地址给调用者。
• 4.如果没有找到足够大小的空闲内存块，则会进行内存分配。这通常涉及到向操作系统请求更多的内存空间。
• 5.操作系统会分配一块连续的内存空间，并将其标记为已使用。
• 6.malloc函数将分配到的内存块的起始地址返回给调用者，并将其添加到已分配内存块链表中，以便后续的内存管理。
• 7.调用者可以使用返回的内存块地址来存储数据。
• 8.当不再需要使用这块内存时，调用者可以使用free函数将其释放，将其重新添加到空闲内存块链表中，以便其他程序可以再次使用。

需要注意的是，malloc函数的实现可能会有一些额外的处理，例如内存对齐、内存池等，以提高内存分配的效率和性能。具体的实现细节可能因编译器和操作系统而异。

9 什么是虚拟内存，虚拟内存的作用？

虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换

通过虚拟内存按需调度页面进主存的机制，不仅大大较少了主存的空间压力，使得在8G主存的计算机上能够运行上百个进程。同样虚拟内存VM还简化了程序的链接、加载，代码和数据共享已经应用程序的内存分配。

• 简化链接：独立的地址空间允许每个进程的内存映像使用相同的格式，且都是相同的虚拟起始地址,只要保证虚拟内存地址的顺序就可以，而不用管代码和数据实际存放在物理内存的何处。
• 简化加载：虚拟内存还使得容易向内存中加载可执行文件和共享对象文件。把目标文件.txt和.data加载到一个进程中，只要Linux加载器为代码和数据段分配对应虚拟页就可。 -** 简化共享：**进程间共享内存更加简便，只要在每个进程得页表维护一个相同得PTE
• 简化内存分配：当一个允许得用户进程想要额外得堆空间时，操作系统通过分配一个适当数字k的连续虚拟内存，并将它们映射到物理内存的K个任意物理页面即可（即虚拟内存上看时连续的，但实际物理上任意）

虚拟内存是硬件异常、硬件地址翻译、主存和磁盘文件和内核软件的完美交互：

10 进程线程模型你知道多少？

对于进程和线程的理解和把握可以说基本奠定了对系统的认知和把控能力。其核心意义绝不仅仅是“线程是调度的基本单位，进程是资源分配的基本单位”这么简单

多线程

我们这里讨论的是用户态的多线程模型，同一个进程内部有多个线程，所有的线程共享同一个进程的内存空间，进程中定义的全局变量会被所有的线程共享，比如有全局变量int i = 10，这一进程中所有并发运行的线程都可以读取和修改这个i的值，而多个线程被CPU调度的顺序又是不可控的，所以对临界资源的访问尤其需要注意安全。

我们必须知道，做一次简单的i = i + 1在计算机中并不是原子操作，涉及内存取数，计算和写入内存几个环节，而线程的切换有可能发生在上述任何一个环节中间，所以不同的操作顺序很有可能带来意想不到的结果。

但是，虽然线程在安全性方面会引入许多新挑战，但是线程带来的好处也是有目共睹的。首先，原先顺序执行的程序（暂时不考虑多进程）可以被拆分成几个独立的逻辑流，这些逻辑流可以独立完成一些任务（最好这些任务是不相关的）。

比如 QQ 可以一个线程处理聊天一个线程处理上传文件，两个线程互不干涉，在用户看来是同步在执行两个任务，试想如果线性完成这个任务的话，在数据传输完成之前用户聊天被一直阻塞会是多么尴尬的情况。

对于线程，我认为弄清以下两点非常重要：

• 线程之间有无先后访问顺序（线程依赖关系）

• 多个线程共享访问同一变量（同步互斥问题）

另外，我们通常只会去说同一进程的多个线程共享进程的资源，但是每个线程特有的部分却很少提及，除了标识线程的tid，每个线程还有自己独立的栈空间，线程彼此之间是无法访问其他线程栈上内容的。

而作为处理机调度的最小单位，线程调度只需要保存线程栈、寄存器数据和PC即可，相比进程切换开销要小很多。

线程相关接口不少，主要需要了解各个参数意义和返回值意义。

1.线程创建和结束

• 背景知识：

在一个文件内的多个函数通常都是按照main函数中出现的顺序来执行，但是在分时系统下，我们可以让每个函数都作为一个逻辑流并发执行，最简单的方式就是采用多线程策略。在main函数中调用多线程接口创建线程，每个线程对应特定的函数（操作），这样就可以不按照main函数中各个函数出现的顺序来执行，避免了忙等的情况。线程基本操作的接口如下。

• 相关接口：

  • 创建线程：int pthread_create(pthread_t *tidp,const pthread_attr_t *attr, void *(start_rtn)(void),void *arg);创建一个新线程，pthread和start_routine不可或缺，分别用于标识线程和执行体入口，其他可以填NULL。

    • pthread：用来返回线程的tid，*pthread值即为tid，类型pthread_t == unsigned long int。

    • attr：指向线程属性结构体的指针，用于改变所创线程的属性，填NULL使用默认值。

    • start_routine：线程执行函数的首地址，传入函数指针。

    • arg：通过地址传递来传递函数参数，这里是无符号类型指针，可以传任意类型变量的地址，在被传入函数中先强制类型转换成所需类型即可。

  • 获得线程ID：pthread_t pthread_self();.。调用时，会打印线程ID。

• 等待线程结束：int pthread_join(pthread_t tid, void** retval);主线程调用，等待子线程退出并回收其资源，类似于进程中wait/waitpid回收僵尸进程，调用pthread_join的线程会被阻塞。

  • tid：创建线程时通过指针得到tid值。

  • retval：指向返回值的指针。

• 结束线程：pthread_exit(void *retval);子线程执行，用来结束当前线程并通过retval传递返回值，该返回值可通过pthread_join获得。

  • retval：同上。

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

  • tid：同上。

2.线程属性值修改

• 背景知识：线程属性对象类型为pthread_attr_t，结构体定义如下：

  typedef struct{
      int detachstate;    // 线程分离的状态
      int schedpolicy;    // 线程调度策略
      struct sched_param schedparam;    // 线程的调度参数
      int inheritsched;    // 线程的继承性
      int scope;    // 线程的作用域
      // 以下为线程栈的设置
      size_t guardsize;    // 线程栈末尾警戒缓冲大小
      int stackaddr_set;    // 线程的栈设置
      void *    stackaddr;    // 线程栈的位置
      size_t stacksize;    // 线程栈大小
  }pthread_attr_t;

• 相关接口：对上述结构体中各参数大多有：pthread_attr_get()和pthread_attr_set()系统调用函数来设置和获取。这里不一一罗列。

多进程

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

进程结构由以下几个部分组成：代码段、堆栈段、数据段。代码段是静态的二进制代码，多个程序可以共享。

实际上在父进程创建子进程之后，父、子进程除了pid外，几乎所有的部分几乎一样。

父、子进程共享全部数据，但并不是说他们就是对同一块数据进行操作，子进程在读写数据时会通过写时复制机制将公共的数据重新拷贝一份，之后在拷贝出的数据上进行操作。

如果子进程想要运行自己的代码段，还可以通过调用execv()函数重新加载新的代码段，之后就和父进程独立开了。

我们在shell中执行程序就是通过shell进程先fork()一个子进程再通过execv()重新加载新的代码段的过程。

1.进程创建与结束

• 背景知识：进程有两种创建方式，一种是操作系统创建的一种是父进程创建的。从计算机启动到终端执行程序的过程为：0号进程 -> 1号内核进程 -> 1号用户进程(init进程) -> getty进程 -> shell进程 -> 命令行执行进程。所以我们在命令行中通过 ./program执行可执行文件时，所有创建的进程都是shell进程的子进程，这也就是为什么shell一关闭，在shell中执行的进程都自动被关闭的原因。从shell进程到创建其他子进程需要通过以下接口。

• 相关接口：
  • 创建进程：pid_t fork(void);
    • 返回值：出错返回-1；父进程中返回pid > 0；子进程中pid == 0
  • 结束进程：void exit(int status);
    • status是退出状态，保存在全局变量中S?，通常0表示正常退出。

  • 获得PID：pid_t getpid(void);返回调用者pid。

  • 获得父进程PID：pid_t getppid(void);返回父进程pid。

• 其他补充：

  • 正常退出方式：exit()、_exit()、return（在main中）。

  • exit()和_exit()区别：exit()是对__exit()的封装，都会终止进程并做相关收尾工作，最主要的区别是_exit()函数关闭全部描述符和清理函数后不会刷新流，但是exit()会在调用_exit()函数前刷新数据流。

  • return和exit()区别：exit()是函数，但有参数，执行完之后控制权交给系统。return若是在调用函数中，执行完之后控制权交给调用进程，若是在main函数中，控制权交给系统。

  • 异常退出方式：abort()、终止信号。

2.Linux进程控制

• 进程地址空间（地址空间） 虚拟存储器为每个进程提供了独占系统地址空间的假象。

  尽管每个进程地址空间内容不尽相同，但是他们的都有相似的结构。X86 Linux进程的地址空间底部是保留给用户程序的，包括文本、数据、堆、栈等，其中文本区和数据区是通过存储器映射方式将磁盘中可执行文件的相应段映射至虚拟存储器地址空间中。

  有一些"敏感"的地址需要注意下，对于32位进程来说，代码段从0x08048000开始。从0xC0000000开始到0xFFFFFFFF是内核地址空间，通常情况下代码运行在用户态（使用0x00000000 ~ 0xC00000000的用户地址空间），当发生系统调用、进程切换等操作时CPU控制寄存器设置模式位，进入内和模式，在该状态（超级用户模式）下进程可以访问全部存储器位置和执行全部指令。

  也就说32位进程的地址空间都是4G，但用户态下只能访问低3G的地址空间，若要访问3G ~ 4G的地址空间则只有进入内核态才行。

• 进程控制块（处理机）进程：的调度实际就是内核选择相应的进程控制块，被选择的进程控制块中包含了一个进程基本的信息。

• 上下文切换 内核管理所有进程控制块，而进程控制块记录了进程全部状态信息。每一次进程调度就是一次上下文切换，所谓的上下文本质上就是当前运行状态，主要包括通用寄存器、浮点寄存器、状态寄存器、程序计数器、用户栈和内核数据结构（页表、进程表、文件表）等。

  进程执行时刻，内核可以决定抢占当前进程并开始新的进程，这个过程由内核调度器完成，当调度器选择了某个进程时称为该进程被调度，该过程通过上下文切换来改变当前状态。

  一次完整的上下文切换通常是进程原先运行于用户态，之后因系统调用或时间片到切换到内核态执行内核指令，完成上下文切换后回到用户态，此时已经切换到进程B。

11 进程调度算法你了解多少？

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

非抢占式的调度算法，按照请求的顺序进行调度。

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

短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。

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

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

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。

如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

时间片轮转

将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。

当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

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

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

优先级调度

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

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

多级反馈队列

一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。

多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。

这种方式下，之前的进程只需要交换 7 次。每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。

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

12 进程状态的切换

进程的三种基本状态

• 就绪状态：当进程已分配到除 CPU 以外的所有必要资源后，只要再获得 CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。
• 执行状态：进程已获得 CPU，其程序正在执行。在单处理机系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。
• 阻塞状态：正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或封锁状态。致使进程阻塞的典型事件有：请求 I/O，申请缓冲空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程排成多个队列。
• 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

13 Linux下进程间通信方式？

• 管道：

  • 无名管道（内存文件）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程之间使用。进程的亲缘关系通常是指父子进程关系。

  • 有名管道（FIFO文件，借助文件系统）：有名管道也是半双工的通信方式，但是允许在没有亲缘关系的进程之间使用，管道是先进先出的通信方式。

• 共享内存：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与信号量，配合使用来实现进程间的同步和通信。

• 消息队列：消息队列是有消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 套接字：适用于不同机器间进程通信，在本地也可作为两个进程通信的方式。

• 信号：用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。

• 信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，实现进程、线程的对临界区的同步及互斥访问

14 Linux下同步机制？

• POSIX信号量：可用于进程同步，也可用于线程同步。

• POSIX互斥锁 + 条件变量：只能用于线程同步

15 如果系统中具有快表(tlb)后，那么地址的转换过程变成什么样了？

块表其实与缓存存储结构的功能是一样的，只不过TLB缓存的是页表条目信息。在没有tlb时，当CPU产生一个虚拟地址，送到内存管理单元后，为能够进行地址转换，必须先向主存内的页表请求对应的页表条目，在主存中找到页表条目后返回给MMU处理，之后MMU通过虚拟地址和相应的页表条目生成物理地址，用该物理地址再次去内存取相应的数据，可见在没有tlb的时候，地址转换过程中要两次访问主存，一次是为了获得页表信息来生成物理地址，另一次是通过生成的物理地址来获得数据

有了tlb缓存后，得益于计算机的局部性设计，将会大大减少从主存中获取页表信息的几率，这样

①CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。

②如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

③如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此,若快表未命中，则访问某个逻辑地址需要两次访存(注意:在找到页表项后，应同时将其存入快表,以便后面可能的再次访问。但若快表已满，则必须按照-定的算法对旧的页表项进行替换)

由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。 因为局部性原理，–般来说快表的命中率可以达到90%以上。

例:某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问- -次快表耗时1us， 访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少?(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100) * 0.9+ (100+100) *0.1=110.9 us 若未采用快表机制，则访问一个逻辑地址需要100+100 = 200us 显然，引入快表机制后，访问一个逻辑地址的速度快多了。

16 动态分区分配算法有哪几种？可以分别说说吗？

1 首次适应算法

算法思想：每次都从低地址开始查找，找到第–个能满足大小的空闲分区。

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

2 最佳适应算法

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

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

3 最坏适应算法

又称最大适应算法(Largest Fit)

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

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

4 邻近适应算法

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

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

5 总结

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

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

进过实验，首次适应比最佳适应要好，他们都比最坏好。

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

17 外部碎片和内部碎片

造成堆利用率低的主要原因是一种称为内存碎片的现象，当虽然有未使用的内存但不能用来满足分配请求时，就会发送这种现象。有两种形式的碎片：内部碎片和外部碎片

• 内部碎片：内部碎片是在一个已分配块比有实际需要的有效载荷大时发生的。比如计算机的内存对齐机制，虽然实际需要1字节存储，但分配器会分配4或者8字节的块来存储。因此，内部碎片是由计算机本身所造成的，我们只能通过改变变量顺序使得内部碎片尽可能小。外部碎片的量化也是极为简单，就是已分配快大小和有效载荷之间的差的和

• 外部碎片：外部碎片是当空闲内存合计起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以满足这个请求块。

18 虚拟技术你了解吗

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

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

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

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

19 一个C/C++程序从开始编译到生成可执行文件的完整过程，你能说出来多少？

四个过程：

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

  • 1、删除所有的#define，展开所有的宏定义。
  • 2、处理所有的条件预编译指令，如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。
  • 3、处理“#include”预编译指令，将文件内容替换到它的位置，这个过程是递归进行的，文件中包含其他 文件。
  • 4、删除所有的注释，“//”和“/**/”。
  • 5、保留所有的#pragma 编译器指令，编译器需要用到他们，如：#pragma once 是为了防止有文件被重 复引用。
  • 6、添加行号和文件标识，便于编译时编译器产生调试用的行号信息，和编译时产生编译错误或警告是 能够显示行号。

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

  • 1、词法分析：利用类似于“有限状态机”的算法，将源代码程序输入到扫描机中，将其中的字符序列分割成一系列的记号。
  • 2、语法分析：语法分析器对由扫描器产生的记号，进行语法分析，产生语法树。由语法分析器输出的语法树是一种以表达式为节点的树。
  • 3、语义分析：语法分析器只是完成了对表达式语法层面的分析，语义分析器则对表达式是否有意义进行判断，其分析的语义是静态语义——在编译期能分期的语义，相对应的动态语义是在运行期才能确定的语义。
  • 4、优化：源代码级别的一个优化过程。
  • 5、目标代码生成：由代码生成器将中间代码转换成目标机器代码，生成一系列的代码序列——汇编语言表示。
  • 6、目标代码优化：目标代码优化器对上述的目标机器代码进行优化：寻找合适的寻址方式、使用位移来替代乘法运算、删除多余的指令等。

• （3）汇编

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

  经汇编之后，产生目标文件(与可执行文件格式几乎一样)xxx.o(Linux下)、xxx.obj(Windows下)。

• （4）链接

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

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

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

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

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

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

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

20 链接器的作用

链接器是开发过程中的一个重要角色，它使得分离编译成为能，有了链接器，我们不用将一个大型应用程序组织为一个巨大的源文件，而是可以分解成更小、更好管理的模块，可以单独修改和编译这些模块，然后使用链接器链接起来即可。链接器主要完成两项工作：

• 符号解析引用：经过编译器和汇编器后每一个函数、全局变量和静态变量都会对应一个符号，生成的可重定位目标文件会维护一个符号表，它包含了这个模块的符号定义和引用，那么链接器符号解析引用的目的就是将每个引用与他输入的可重定位目标文件的符号表中的一个确定的符号定义关联起来。
• 地址重定位：在链接的过程中，我们需要将不同的目标文件中的函数和变量地址进行调整，使得它们在最终的可执行文件中能正确的链接在一起，生成可执行文件。

20.1 符号和符号表

每个可重定位目标文件都会维护一个符号表，包含函数、全局变量的定义或者引用信息，可分为三种不同的符号：

• 全局符号：由该目标文件的定义并且能够被外部文件所引用的符号，为非satic的函数和全局变量。
• 外部符号：由其他可重定位目标文件定义但被本模块所引用的符号，此时链接器就会进行符号解析引用，将这些引用关联到一个确定的符号定义上。
• 局部符号：由本模块定义和引用的局部符号，但不能被其他目标文件所引用，如static函数、static全局变量。

注意：局部变量由堆栈关联，因此链接器不会为局部变量生成符号定义和引用。

20.2 链接器如何解析符号定义和符号引用呢？

首先编译器会向汇编器输出每个全局符号，汇编器这些符号的强弱编码在可重定位目标文件的符号表里，链接器根据符号强弱来识别符号引用和符号定义，Linux对符号强弱规则是这样的：函数定义和以初始化的全局变量是强符号，声明则是弱符号。

• 只允许有一个同名的强符号，（如果有多个则会发送重定义错误）
• 如果有一个强符号和多个弱符合，则选择强符号
• 如果有多个弱符号，则任意选择一个。

20.3 链接器如何使用静态库来解析引用

在符号解析阶段，链接器会按照我们键入的命令行顺序从左到右来扫描可重定位目标文件和静态库存档文件，在这次扫描中，链接器会维护三个集合E、U、D

• E：可重定位目标文件集合，在这个集合的可重定位目标文件最后会被合并起来形成可执行文件
• U：一个未解析符号引用（即应用了但尚未定义的符号）集合，这个集合扫描完成后，应该是空的，否则会程序终止，出现解析错误
• D：已经定义的符号集合

初始化上述的三个集合都为空，执行命令行：

• 对于命令的每个文件f，链接器先判断是一个目标文件还是库存档文件。
  • **若f是目标文件，则会把f添加到E，并且修改U*
  • 若f是静态库存档文件，那么链接器就尝试匹配U中未解析的符号和由存档文件成员定义的符号。如果某个存档文件成员m，定义了一个符号解析U中的一个符号引用，那么九将m加入到E中。对存档文件的成员目标文件依次进行这个过程，直到U。此时，任何不在E中的成员目标文件被丢弃。
• 如果当前链接器完成命令行上输入文件的扫描后，U非空，链接器就会输出一个解析引用的错误终止，否则，就是要E中目标文件构建合并可执行文件。

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

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

21 进程间通信有哪几种方式

Linux几乎支持全部UNIX进程间通信方法，包括管道（有名管道和无名管道）、消息队列、共享内存、信号量和套接字。其中前四个属于同一台机器下进程间的通信，套接字则是用于网络通信。

名称	细节
管道(pipe)	允许一个进程和另一个与它有共同祖先的进程之间进行通信
命名管道(FIFO)	类似于管道，但是它可以用于任何两个进程之间的通信，命名管道在文件系统中有对应的文件名。命名管道通过命令mkfifo或系统调用mkfifo来创建
消息队列(MQ)	消息队列是消息的连接表，包括POSIX消息对和System V消息队列。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号承载信息量少，管道只能成该无格式字节流以及缓冲区大小受限等缺点；
信号量(semaphore)	信号量主要作为进程间以及同进程不同线程之间的同步手段；
共享内存(shared memory)	它使得多个进程可以访问同一块内存空间，是最快的可用IPC形式。这是针对其他通信机制运行效率较低而设计的。它往往与其他通信机制，如信号量结合使用，以达到进程间的同步及互斥
信号(signal)	信号是比较复杂的通信方式，用于通知接收进程有某种事情发生，除了用于进程间通信外，进程还可以发送信号给进程本身
内存映射(mapped memory)	内存映射允许任何多个进程间通信，每一个使用该机制的进程通过把一个共享的文件映射到自己的进程地址空间来实现它
Socket	它是更为通用的进程间通信机制，可用于不同机器之间的进程间通信

进程间通信主要包括管道、系统IPC（包括消息队列、信号量、信号、共享内存等）、以及套接字socket。

1.管道：

管道主要包括无名管道和命名管道:管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信

1.1 普通管道PIPE：

• 1)它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端

• 2)它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）

• 3)它可以看成是一种特殊的文件，对于它的读写也可以使用普通的read、write等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中。

1.2 命名管道FIFO：

• 1)FIFO可以在无关的进程之间交换数据

• 2)FIFO有路径名与之相关联，它以一种特殊设备文件形式存在于文件系统中，严格遵守先进先出原则。

2. 系统IPC：

2.1 消息队列

消息队列，是消息的链接表，存放在内核中。一个消息队列由一个标识符（即队列ID）来标记。 (消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等特点)具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；

特点：

• 1)消息队列是面向记录的，其中的消息具有特定的格式以及特定的优先级。

• 2)消息队列独立于发送与接收进程。进程终止时，消息队列及其内容并不会被删除。

• 3)消息队列可以实现消息的随机查询,消息不一定要以先进先出的次序读取,也可以按消息的类型读取。

2.2 信号量semaphore

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器，可以用来控制多个进程对共享资源的访问。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。

特点：

• 1)信号量用于进程间同步，若要在进程间传递数据需要结合共享内存。

• 2)信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作。

• 3)每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数。

• 4)支持信号量组。

2.3 信号signal

信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

2.4 共享内存（Shared Memory）

它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等

特点：

• 1)共享内存是最快的一种IPC，因为进程是直接对内存进行存取

• 2)因为多个进程可以同时操作，所以需要进行同步

• 3)信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

3.套接字SOCKET：

socket也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同主机之间的进程通信。

22 虚拟内存是什么、作用

在概念上，虚拟内存是指存放在磁盘上的N字节大小的内存区域，每个字节都要相应的虚拟地址，作为寻址索引。和存储结构的缓存一样，磁盘的数据也被分割成块，在这类为做区别称之为虚拟页，每个虚拟页大小由计算机系统决定为\(P=2^p\)，与之对应的是物理页，其大小也应该为P。可以理解它是一种映射，由虚拟内存映射到真实物理内存上，这样在有限的内存上可以运行更多的程序。

在任何时刻，我们都不能实际真实一股脑的为进程分配全部的存储空间，因此虚拟页面分为三个不相交的子集：

• 未分配的：VM系统还没有分配的页，此时未分配的块没有任何数据和它们管理，因此此时不会占有任何磁盘空间
• 缓存的：当前缓存的虚拟页在占有磁盘中的空间，当然由于缓存到内存。内存当中也会占有一定内存空间
• 维缓存的：在磁盘中占用空间，但并未缓存在内存中，当然不占用内存(此时当CPU要寻址该页当中一个数据时，由于未缓存在内存中，就会造成缺页异常。)

作用

• 虚拟内存是作为缓存的工具，如L1\L2\L3作为主存的缓存，那么虚拟内存是作为主存与磁盘之间缓存的工具

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

• 更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。

• 简化了链接，独立的地址空间允许每个进程的内存映像使用相同的格式，且都是相同的虚拟起始地址,只要保证虚拟内存地址得顺序就可以，而不用管代码和数据实际存放在物理内存的何处。

• 当程序引用到不在物理内存中的页时，产生缺页中断，将缺失的部分装入物理内存并重新执行失败的指令。可以看出，虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

• 提供了内存保护功能，每个进程的必须在自己的存储空间运行，虚拟内存起到了这个作用，虽然在逻辑地址上它们运行是在同一位置上，但通过地址转换成物理地址后，每个进程都有自己的真实物理地址。

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

23 几种典型的锁

读写锁

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

互斥锁

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

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

条件变量

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

自旋锁

自旋锁属于busy-waiting类型的锁，如果线程A是使用pthread_spin_lock操作去请求锁，如果自旋锁已经被线程B所持有，那么线程A就会一直在core 0上进行忙等待并不停的进行锁请求，检查该自旋锁是否已经被线程B释放，直到得到这个锁为止。因为自旋锁不会引起调用者睡眠，所以自旋锁的效率远高于互斥锁。

虽然它的效率比互斥锁高，但是它也有些不足之处：

• 自旋锁一直占用CPU，在未获得锁的情况下，一直进行自旋，所以占用着CPU，如果不能在很短的时间内获得锁，无疑会使CPU效率降低。

• 在用自旋锁时有可能造成死锁，当递归调用时有可能造成死锁。

• 自旋锁只有在内核可抢占式或SMP的情况下才真正需要，在单CPU且不可抢占式的内核下，自旋锁的操作为空操作。自旋锁适用于锁使用者保持锁时间比较短的情况下。

24 死锁产生的必要条件

• 互斥条件：指进程对所分配到的资源进行排它性使用，即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求该资源，则请求者只能等待，直至占有该资源的进程用毕释放。
• 请求和保持条件：指进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又已被其它进程占有，此时请求进程阻塞，但又对自己已获得的其它资源保持不放。
• 不可抢占条件：指进程已获得的资源，在未使用完之前，不能被剥夺抢占，只能在使用完时由自己释放。
• 循环等待条件：指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P0，P1，P2，…，Pn}中的P0正在等待一个P1占用的资源；P1正在等待 P2占用的资源，……，Pn正在等待已被P0占用的资源。

处理死锁的基本方法

主要有以下五种方法：

• 鸵鸟策略
• 预防死锁：该方法是通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而可能会导致系统资源利用率和系统吞吐量降低。
• 避免死锁：是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。这种方法只需事先施加较弱的限制条件，便可获得较高的资源利用率及系统吞吐量，但实现难度较高。
• 检测死锁：是允许系统在运行过程中发生死锁，但可通过系统所设置的检测机构，及时地检测出死锁的发生，并精确地确定与死锁有关的进程和资源； 然后，采取适当措施，从系统中将已发生的死锁清除掉。
• ** 解除死锁**：与检测死锁相配套的一种措施。当检测到系统中已发生死锁时，须将进程从死锁状态中解脱出来。常用的实施方法是撤消或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程，使之转为就绪状态，以继续运行。死锁的检测和解除措施有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

鸵鸟策略

把头埋在沙子里，假装根本没发生问题。

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

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

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

预防死锁

预防死锁的方法是使四个必要条件中的第2、3、4个条件之一不能成立，来避免发生死锁。至于必要条件 1，因为它是由设备的固有特性所决定的，不仅不能改变，还应加以保证。

摒弃“请求和保持”条件

在采用这种方法时，系统规定所有进程在开始运行之前，都必须一次性地申请其在整个运行过程所需的全部资源。

• 优点：简单、易于实现且很安全
• 缺点：资源严重浪费，恶化了系统资源的利用率；造成使进程延迟运行

摒弃不可抢占条件

在采用这种方法时系统规定，进程是逐个地提出对资源的要求的。当一个已经保持了某些资源的进程，再提出新的资源请求而不能立即得到满足时，必须释放它已经保持了的所有资源，待以后需要时再重新申请。这意味着某一进程已经占有的资源，在运行过程中会被暂时地释放掉，也可认为是被剥夺了，从而摒弃了“不剥夺”条件。

• 缺点：实现起来比较复杂且要付出很大的代价。一个资源在使用一 段时间后，它的被迫释放可能会造成前段工作的失效，即使是采取了某些防范措施，也还会使进程前后两次运行的信息不连续。此外，这种策略还可能因为反复地申请和释放资源，致使进程的执行被无限地推迟，这不仅延长了进程的周转时间，而且也增加了系统开销，降低了系统吞吐量。

摒弃“环路等待”条件

这种方法中规定，系统将所有资源按类型进行线性排队，并赋予不同的序号。所有进程对资源的请求必须严格按照资源序号递增的次序提出，这样，在所形成的资源分配图中，不可能再出现环路，因而摒弃了“环路等待”条件。

• 缺点：是为系统中各类资源所分配(确定)的序号必须相对稳定，这就限制了新类型设备的增加；作业(进程)使用各类资源的顺序与系统规定的顺序不同，造成对资源的浪费；这种按规定次序申请的方法，必然会限制用户简单、自主地编程。

避免死锁

所谓安全状态，是指系统能按某种进程顺序(P1，P2，…，Pn)(称〈P1，P2，…，Pn〉序列为安全序列)，来为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺利地完成。如果系统无法找到这样一个安全序列，则称系统处于不安全状态。

并非所有的不安全状态都必然会转为死锁状态，但当系统进入不安全状态后，便有可能进而进入死锁状态；反之，只要系统处于安全状态，系统便可避免进入死锁状态。因此，避免死锁的实质在于：系统在进行资源分配时，如何使系统不进入不安全状态。 图 a 的第二列 Has表示已拥有的资源数，第三列Max表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时Free 变为 5（图 c）；接着以同样的方式运行 C和A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。

预防死锁和避免死锁这两种方法实质上都是通过施加某些限制条件，来预防发生死锁。两者的主要差别在于：为预防死锁所施加的限制条件较严格，这往往会影响进程的并发执行；而为避免死锁所施加的限制条件则较宽松，这给进程的运行提供了较宽松的环境，有利于进程的并发执行。

利用银行家算法避免死锁

基本思想：

• 在每个新进程进入系统时，他必须声明在运行过程中，可能需要的每种资源类型的最大单元数目（数目不超过系统拥有的资源总量）。
• 当进程请求一组资源时，系统必须首先在确定是否有足够的资源分配给该进程。
• 若有，在进一步计算将这些资源分配给进程后，是否会使系统处于不安全状态。如果处于安全状态，才将资源分配给他；否则，让进程等待。

银行家算法中的数据结构:

• 可利用资源向量Available：是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j]=K，则表示系统中现有Rj类资源K个。
• 最大需求矩阵Max：是一个 n×m的矩阵，它定义了系统中 n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
• 分配矩阵Allocation：是一个 n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
• 需求矩阵Need：是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K 个，方能完成其任务。

Need[i, j]=Max[i, j]-Allocation[i, j]

银行家算法:

设Request i是进程Pi的请求向量，如果Request i[j]=K，表示进程Pi需要K 个 R j类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：

1. 如果Request i[j]≤Need[i,j]，便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
2. 如果Requesti[j]≤Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
3. 系统试探着把资源分配给进程 P i，并修改下面数据结构中的数值：

   Available[j]= Available[j]-Request i[j];
   Allocation[i,j] = Allocation[i,j]+Request i[j];
   Need[i,j] = Need[i,j]-Request i[j];

• 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程 Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。

安全性算法: 系统所执行的安全性算法可描述如下：

1. 设置两个向量：
   • 工作向量work：它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available。
   • Finish：它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做Finish[i]=false；当有足够资源分配给进程时，再令Finish[i]=true。
2. 从进程集合中找到一个能满足下述条件的进程：
   • Finish[i]=false;
   • Need[i,j]≤Work[j];若找到，执行步骤3，否则，执行步骤4。
3. 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行：

   Work[j] = Work[j]+Allocation[i,j];
   Finish[i] = true;
   go to step 2;

4. 如果所有进程的Finish[i]=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

缺点：每一次分配都要执行安全性算法，得到所有的Finish都是true，效率会有一定牺牲，但牺牲<效益

检测死锁

不试图阻止死锁，而是当检测到死锁发生时，采取措施进行恢复。 上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。

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

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

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

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

• 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. 如果没有这样一个进程，算法终止。

就是拓扑排序思想

死锁解除

当发现有进程死锁时，便应立即把它们从死锁状态中解脱出来。常采用解除死锁的两种方法是：

• 剥夺资源。从其它进程剥夺足够数量的资源给死锁进程，以解除死锁状态。
• 撤消进程。最简单的撤消进程的方法是使全部死锁进程都夭折掉；稍微温和一点的方法是按照某种顺序逐个地撤消进程，直至有足够的资源可用，使死锁状态消除为止。

25 内存的覆盖是什么？有什么特点？

由于程序运行时并非任何时候都要访问程序及数据的各个部分（尤其是大程序），因此可以把用户空间分成为一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按照调用关系分段，首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。

覆盖技术的特点：是打破了必须将一个进程的全部信息装入内存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行，再而，大家要注意到，内存中能够更新的地方只有覆盖区的段，不在覆盖区的段会常驻内存。

26 内存交换是什么？有什么特点？

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

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

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

27 操作系统的页表寻址

虚拟内存系统必须以某种方法来判断一个虚拟页是否在主存DRAM上，如果在，还必须确定在DRAM的哪个位置。若不命中，触发缺页异常，还必须知道它在磁盘的哪个位置，同时还必须用页调度算法在物理内存中牺牲一个页进行替换。

上述的功能由软硬件共同结合作用，包括操作系统软件、MMU和重要的数据结构——页表。页表上是虚拟地址和物理页的关系，它常驻在主存上。每次地址翻译硬件将一个虚拟地址转为物理地址时，都会读取页表。页表的结构如下，页表就是页表条目PTE数组。简而言之，页表是为了配合计算机的虚拟内存而设计出来的数据结构。

页表寻址命中过程：

• 当CPU为了获取内存当中位于某个页面内某个位置的数据，它会产生一个虚拟地址VA，把它送给MMU
• 第二步：MMU用VA去高速缓存/主存获得PTE页表条目
• 第三步：高速缓存/主存向MMU返回一个PTE
• 第四步：MMU利用PTE和VA构造物理地址，并把它传送给主存
• 第五步：高数缓存/主存返回所请求的的数据给处理器

其中的物理地址构造如图所示，虚拟地址的后p位作为该页偏移地址，PTE内存储相应的物理页号，因此将它们拼接就可以得到真正的物理地址。

28 页表未命中，缺页会发生什么？

此时若CPU要使用VP3该页中某块的某个数据，由于主存并没有缓存该物理页，因此页表的PTE有效位为0，就会触发缺页异常，执行缺页处理程序，进行页面调度替换后再返回原来执行的指令\(I_{cur}\)重新执行该虚拟的地址上的数据请求。在缺页异常处理程序，该程序会选择一个牺牲页作为替换VP3,假如选择了VP4作为替换页，若VP4修改了，那么内核执行写回操作，将他复制回磁盘。

• 步骤：
  • 第一步和第三步：与上述一样
  • 第四步：PTE的有效位是零，所以MMU回触发缺页异常，传递给CPU中的控制到操作系统内核中的缺页异常处理程序。
  • 第五步：缺页异常处理程序确定物理内存的牺牲页，如果这个页面已经被修改，则把它换出到磁盘
  • 第六步：缺页异常处理程序调入新的页面，并且更新页表对应的PTE
  • 第七步：缺页异常处理程序返回到原来的进程，再次执行导致缺页的指令。

29 页表也会占用内存，计算机是怎么设计。

上面讨论的都是单级页表的情况，对于单级页表，无论是否分配，我们都要维护PTE,试想一下32位系统，页面大小是4KB和一个4字节的PTE，那么在内存中总需要用\(4GB/4KB*4byte=4MB\)的页表，对于64位来说更加复杂。内存是计算机很稀缺的资源，我们当然不希望内存因为存储页表而耗费太多的内存，虚拟内存并不是所有都会分配使用，因此多级页表利用这个特性解决这个问题的。

多级页表中，第一级页表正常分配1024个PTE，但其中许多PTE都是未分配的即null，那么二级页表就不会去生成它们的二级页表，这样就大大节约了空间。 上图中只占用了内存\(1024*4Byte*4=16KB\)

30 页面置换算法

1 最佳置换法(OPT)

最佳置换算法(OPT，Optimal) :每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。 最佳置换算法可以保证最低的缺页率，但实际上，只有在进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面访问序列。因此，最佳置换算法是无法实现的

2 先进先出置换算法(FIFO)

先进先出置换算法(FIFO) :每次选择淘汰的页面是最早进入内存的页面 实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面队列的最大长度取决于系统为进程分配了多少个内存块 - Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

只有FIFO算法会产生Belady异常，而LRU和OPT算法永远不会出现Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

3最近最久未使用置换算法(LRU)

• 最近最久未使用置换算法(LRU，least recently used) :每次淘汰的页面是最近最久未使用的页面
• 实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t(该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大)。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。 LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。

4 时钟置换算法(CLOCK)

最佳置换算法性OPT能最好，但无法实现；先进先出置换算法实现简单，但算法性能差；最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。

所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体，因为算法要循环扫描缓冲区像时钟一样转动。所以叫clock算法。

时钟置换算法是一种性能和开销较均衡的算法，又称CLOCK算法，或最近未用算法(NRU，Not Recently Used)

• 简单的CLOCK算法实现方法:为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰-一个页面时，只需检查页的访问位。如果是0，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第1轮扫描中所有页面都是1，则将这些页面的访问位依次置为0后，再进行第二轮扫描(第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择–个淘汰页面最多会经过两轮扫描)

5 改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。

为方便讨论，用(访问位，修改位)的形式表示各页面状态。如(1, 1)表示一个页面近期被访问过，且被修改过。

改进型的Clock算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中，同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成一下四种类型的页面。

算法规则：将所有可能被置换的页面排成一个循环队列

• 第一轮：从当前位置开始扫描到第一个(A =0, M = 0)的页用于替换。表示该页面最近既未被访问，又未被修改，是最佳淘汰页（第一优先级）

• 第二轮：若第一轮扫描失败，则重新扫描，查找第一个(A =0, M = 1)的帧用于替换。本轮扫描会将访问位置0。本轮目的是寻找表示该页面最近未被访问，但被修改的页面，并不是很好的淘汰页。（第二）

• 第三轮：若第二轮扫描失败，则重新扫描，查找第一个(A =0, M = 0)的帧用于替换。本轮扫描不修改任何标志位。表示该页面最近被访问，但未修改。（第三优先级）

• 第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0, 1)的帧用于替换。表示最近被访问，且已被修改的页面（最坏情况）

6 总结

	算法规则	优缺点
OPT	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好;但无法实现
FIFO	优先淘汰最先进入内存的页面	实现简单;但性能很差，可能出现Belady异常
LRU	优先淘汰最近最久没访问的页面	性能很好;但需要硬件支持，算法开销大
CLOCK (NRU)	最多两轮	实现简单，算法开销小;但未考虑页面是否被修改过。
改进型CLOCK (改进型NRU)	若用(访问位，修改位)的形式表述，最多四轮	算法开销较小，性能也不错

31 Linux中异常和中断的区别

中断

大家都知道，当我们在敲击键盘的同时就会产生中断，当硬盘读写完数据之后也会产生中断，所以，我们需要知道，中断是由硬件设备产生的，而它们从物理上说就是电信号，之后，它们通过中断控制器发送给CPU，接着CPU判断收到的中断来自于哪个硬件设备（这定义在内核中），最后，由CPU发送给内核，有内核处理中断。下面这张图显示了中断处理的流程：

异常

CPU处理程序的时候一旦程序不在内存中，会产生缺页异常；当运行除法程序时，当除数为0时，又会产生除0异常。所以，大家也需要记住的是，异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常，下面这张图显示了异常处理的流程：

• 相同点

  • 最后都是由CPU发送给内核，由内核去处理

  • 处理程序的流程设计上是相似的

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

32 上下文切换是什么

上下文切换（Context Switch）是操作系统中的一种机制，用于在多任务环境下，从一个任务（进程或线程）切换到另一个任务时保存和恢复任务的执行环境和状态。

在多任务操作系统中，同时存在多个任务需要并发执行。每个任务都有自己的执行上下文，包括寄存器状态、程序计数器（PC）值、栈指针、打开的文件、内存映射等。当操作系统需要切换当前正在执行的任务到另一个任务时，就需要进行上下文切换。

上下文切换的过程包括以下步骤：

• 保存当前任务的上下文：操作系统会保存当前任务的寄存器状态、PC值、堆栈指针等信息，并将其保存在任务的上下文数据结构中，以便在之后能够正确地恢复任务的执行状态。

• 恢复目标任务的上下文：操作系统会从目标任务的上下文数据结构中读取保存的上下文信息，并将寄存器状态、PC值、堆栈指针等恢复到目标任务的执行状态。

• 切换执行：一旦目标任务的上下文恢复完毕，操作系统会将控制权切换到目标任务，开始执行目标任务的代码。

上下文切换的目的是实现任务的并发执行和共享CPU资源。通过在任务之间进行快速而有效的上下文切换，操作系统可以在有限的处理器资源下，实现多任务的轮转调度或优先级调度，以满足不同任务的执行需求。

上下文切换的开销是一个重要的考量因素。切换过程中，需要保存和恢复大量的寄存器状态和其他执行环境，还可能涉及内存管理和页表切换等操作，这会带来一定的开销。因此，在设计操作系统调度算法时需要综合考虑上下文切换的成本和任务切换的频率，以实现高效的任务调度和系统性能。

33 中断上下文和异常上下文

中断上下文（Interrupt Context）和异常上下文（Exception Context）是指在处理中断和异常时所处的执行环境和状态。

• 中断上下文是指在处理硬件中断时保存的处理器状态和相关信息。当硬件设备触发中断时，处理器会立即中断当前执行的程序，保存当前的上下文信息，包括寄存器状态、程序计数器（PC）值、栈指针等。然后，处理器会切换到中断处理程序，执行相应的中断处理逻辑。中断上下文通常是由硬件和操作系统共同管理的，以确保在中断处理程序执行期间，中断不会干扰到正在运行的程序或任务。

• 异常上下文是指在处理异常时保存的处理器状态和相关信息。当程序执行过程中发生异常（如除零错误、非法内存访问等），处理器会立即中断当前执行的程序，保存当前的上下文信息，包括寄存器状态、程序计数器（PC）值、栈指针等。然后，处理器会将控制转移到异常处理程序，根据异常类型执行相应的处理逻辑。异常上下文通常是由操作系统提供的异常处理机制管理的，以确保在异常处理程序执行期间能够正确处理异常情况，并继续执行程序或采取适当的措施。

区别在于触发机制和处理方式：

• 中断是由外部设备或信号触发，可以是硬件中断或软件中断。中断上下文用于处理设备的输入输出操作或请求系统服务。
• 异常是由程序执行过程中的错误或特殊情况触发，可以是硬件异常或软件异常。异常上下文用于处理程序执行过程中的错误或异常情况

34 内核抢占和非内核抢占

内核抢占（Kernel Preemption）和非内核抢占（Non-Kernel Preemption）是操作系统中的两种不同的调度机制。

• 内核抢占指的是当一个进程或线程正在执行内核态（kernel mode）代码时，如果有更高优先级的任务需要执行，操作系统会强制暂停当前内核态的执行，切换到更高优先级的任务执行。这种机制允许操作系统及时响应紧急的任务或事件，保证系统的可靠性和实时性。内核抢占通常需要硬件支持，例如通过定时器中断或外部中断信号来触发内核抢占。

• 非内核抢占是指当一个进程或线程正在执行用户态（user mode）代码时，如果有更高优先级的任务需要执行，操作系统会暂停当前用户态的执行，切换到更高优先级的任务。非内核抢占是由操作系统自身实现的，通常基于时间片轮转或优先级调度等算法来决定任务的切换时机。非内核抢占可以提高系统的响应性能，但也可能导致一些问题，如上下文切换开销过大、竞争条件等。

总的来说，内核抢占和非内核抢占都是为了实现多任务调度和提高系统的性能和可靠性。内核抢占在内核态代码执行期间也能被中断，而非内核抢占只在用户态代码执行期间进行切换。

35 守护进程、孤儿进程和僵尸进程

守护进程

指在后台运行的，没有控制终端与之相连的进程。它独立于控制终端，周期性地执行某种任务。Linux的大多数服务器就是用守护进程的方式实现的，如web服务器进程http等

孤儿进程

如果父进程先退出，子进程还没退出，那么子进程此时就成为孤儿进程，孤儿进程的父进程将变为init进程。（注：任何一个进程都必须有父进程）。

一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作

僵尸进程

如果子进程先退出，父进程还没退出，那么子进程必须等到父进程捕获到了子进程的退出状态才真正结束，否则这个时候子进程就成为僵尸进程。

设置僵尸进程的目的是维护子进程的信息，以便父进程在以后某个时候获取。这些信息至少包括进程ID，进程的终止状态，以及该进程使用的CPU时间，所以当终止子进程的父进程调用wait或waitpid时就可以得到这些信息。

因此对于僵尸进程，父进程必须进行回收，否则会消耗系统资源，比如进程ID

36 如何避免僵尸进程?

• 通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心，由内核回收,此时子进程是由init()进程管理和回收。

• 父进程调用wait/waitpid等函数等待子进程结束，如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。

• 如果父进程很忙不要阻塞，可以用signal注册信号处理函数，在信号处理函数调用wait/waitpid等待子进程退出。

• 通过两次调用fork。父进程首先调用fork创建一个子进程然后waitpid等待子进程退出，子进程再fork一个孙进程后退出。这样子进程退出后会被父进程等待回收，而对于孙子进程其父进程已经退出所以孙进程成为一个孤儿进程，孤儿进程由init进程接管，孙进程结束后，init会等待回收。

37 计算机大小端

对于跨域多字节的程序对象，必须有两个规则：

• 这个对象的地址是什么：在几乎所有的机器上，多字节对象都被存储为连续的字节序列，对象的地址为所使用字节中最小的地址。
• 这个对象在内存中是如何排列这些字节的：排列ijie有两个通用的规则，一个是大端(网络字节序)，一个是小端(主机序);大端字节序在内存中按从最高有效位到最低有效位存储；而小端字节序在内存中按照从最低有效位到最高有效位存储
  • 现有一个int型变量，位于初始地址为0x100，它的十六进制值为0x01234567，则大小端存储如下：

如何区分计算机是大端存储还是小端存储：

typedef unsigned char* byte_pointer;
void show_bytes(byte_pointer start,size_tlen){
	size_t i;
	for(i=0;i<len;i++)
		printf("%2.x ",start[i]);	//%2.x表示整数必须用两个16进制输出
	printf("\n");
}
//调用
int a=0x123456;
show_bytes((byte_pointer)&a,seziof(int));

输出

56 34 12 00

观察输出可知本计算机使用小端法存储数据

38 线程回收方式

• pthread_join阻塞方式回收：主线程调用，等待子线程退出并回收其资源，类似于进程中wait/waitpid回收僵尸进程，调用的线程会被阻塞。
• pthread_detach非阻塞形式回收：主线程、子线程均可调用。主线程中pthread_detach(tid)，子线程中pthread_detach(pthread_self())，调用后和主线程分离，子线程结束时自己立即回收资源。

39 Linux环境下的内存分布

过这张图你可以看到，用户空间内存，从低到高分别是 7 种不同的内存段：

• 代码段.txt：程序文件段，包括二进制可执行代码；
• 已初始化数据段.data：又细分为只读数据段和读写数据段，存储全局变量、静态变量；
• 未初始化数据段.bss：它存储所有被初始化为0或者未初始化的静态变量，这些为初始化的变量在程序启动时被自动初始化为0。
• 堆段：包括动态分配的内存，从低地址开始向上增长；
• 文件映射段：包括动态库、共享内存等，从低地址开始向上增长（跟硬件和内核版本有关）
• 栈段：包括局部变量和函数调用的上下文等。栈的大小是固定的，一般是 8 MB。当然系统也提供了参数，以便我们自定义大小；

40 在Linux/windows平台下栈空间的大小

• Linux环境下有操作系统决定，一般是8MB，8192KB，通过ulimit -a命令查看,通过ulimit -s修改

  trluper@DESKTOP-67ADUGH:~$ ulimit -a
  real-time non-blocking time  (microseconds, -R) unlimited
  core file size              (blocks, -c) 0
  data seg size               (kbytes, -d) unlimited
  scheduling priority                 (-e) 0
  file size                   (blocks, -f) unlimited
  pending signals                     (-i) 15393
  max locked memory           (kbytes, -l) 64
  max memory size             (kbytes, -m) unlimited
  open files                          (-n) 1024
  pipe size                (512 bytes, -p) 8
  POSIX message queues         (bytes, -q) 819200
  real-time priority                  (-r) 0
  stack size                  (kbytes, -s) 8192
  cpu time                   (seconds, -t) unlimited
  max user processes                  (-u) 15393
  virtual memory              (kbytes, -v) unlimited
  file locks                          (-x) unlimited

• Windows环境下由编译器决定，VC++6.0一般是1M

41 程序从堆中动态分配内存时，虚拟内存上怎么操作的

页表：是一个存放在物理内存中的数据结构，它记录了虚拟页与物理页的映射关系

在进行动态内存分配时，例如malloc()函数或者其他高级语言中的new关键字，操作系统会在硬盘中创建或申请一段虚拟内存空间，并更新到页表（分配一个页表条目（PTE），使该PTE指向硬盘上这个新创建的虚拟页），通过PTE建立虚拟页和物理页的映射关系。

42 抖动你知道是什么吗？它也叫颠簸现象

刚刚换出的页面马上又要换入内存，刚刚换入的页面马上又要换出外存，这种频繁的页面调度行为称为抖动，或颠簸。产生抖动的主要原因是进程频繁访问的页面数目高于可用的物理块数(分配给进程的实际内存物理块不够)

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率 为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程工作集” 的概念

43 什么是进程工作集

进程的工作集（Working Set of a Process）是指在特定时间内，进程正在使用的物理内存页面的集合。这个概念通常与虚拟内存系统相关，因为在虚拟内存系统中，物理内存的分配是动态的，进程不一定会一直占用相同的物理内存页。

工作集的大小会随着进程的内存访问模式和运行时间而变化。如果一个进程正在访问的页面较多，那么它的工作集就会相应增大；反之，如果进程不再使用某些页面，那么这些页面可能会被操作系统从进程的工作集中移除，以释放内存资源供其他进程使用。

维护合适的工作集对于系统性能非常重要。如果一个进程的工作集太小，那么它可能会频繁地发生页面错误（Page Fault），导致性能下降；而如果一个进程的工作集太大，那么它可能会占用过多的内存资源，导致其他进程的性能受到影响。

44 从堆和栈上建立对象哪个快？

栈比较快，从两方面来考虑：

• 分配和释放，堆在分配和释放时都要调用函数（malloc,free)，比如分配时会到堆空间去寻找足够大小的空间（因为多次分配释放后会造成内存碎片），这些都会花费一定的时间，具体可以看看malloc和free的源代码，函数做了很多额外的工作，而栈却不需要这些。

• 访问时间，访问堆的一个具体单元，需要两次访问内存，第一次得取得指针，第二次才是真正的数据，而栈只需访问一次，栈常驻内存中。另外，堆的内容被操作系统交换到外存的概率比栈大，栈一般是不会被交换出去的

45 常见的内存错误

• 内存分配未成功，却使用了它。

  编程新手常犯这种错误，因为他们没有意识到内存分配会不成功。常用解决办法是，在使用内存之前检查指针是否为NULL。如果指针p是函数的参数，那么在函数的入口处用assert(p!=NULL)进行检查。如果是用malloc或new来申请内存，应该用if(p==NULL) 或if(p!=NULL)进行防错处理。

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

  犯这种错误主要有两个起因：一是没有初始化的观念；二是误以为内存的缺省初值全为零，导致引用初值错误（例如数组）。内存的缺省初值究竟是什么并没有统一的标准，尽管有些时候为零值，我们宁可信其无不可信其有。所以无论用何种方式创建数组，都别忘了赋初值，即便是赋零值也不可省略，不要嫌麻烦。

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

  例如在使用数组时经常发生下标“多1”或者“少1”的操作。特别是在for循环语句中，循环次数很容易搞错，导致数组操作越界。

• 忘记了释放内存，造成内存泄露。

  含有这种错误的函数每被调用一次就丢失一块内存。刚开始时系统的内存充足，你看不到错误。终有一次程序突然挂掉，系统出现提示：内存耗尽。动态内存的申请与释放必须配对，程序中malloc与free的使用次数一定要相同，否则肯定有错误（new/delete同理）。

• 释放了内存却继续使用它。常见于以下有三种情况：

  • 程序中的对象调用关系过于复杂，实在难以搞清楚某个对象究竟是否已经释放了内存，此时应该重新设计数据结构，从根本上解决对象管理的混乱局面。

  • 函数的return语句写错了，注意不要返回指向“栈内存”的“指针”或者“引用”，因为该内存在函数体结束时被自动销毁。

  • 使用free或delete释放了内存后，没有将指针设置为NULL。导致产生“野指针”。

46 内存交换中，被换出的进程保存在哪里？

保存在磁盘中，也就是外存中。具有对换功能的操作系统中，通常把磁盘空间分为文件区和对换区两部分。文件区主要用于存放文件，主要追求存储空间的利用率，因此对文件区空间的管理采用离散分配方式;对换区空间只占磁盘空间的小部分，被换出的进程数据就存放在对换区。由于对换的速度直接影响到系统的整体速度，因此对换区空间的管理主要追求换入换出速度，因此通常对换区采用连续分配方式(学过文件管理章节后即可理解)。总之，对换区的I/O速度比文件区的更快。

47 五种IO模型

• 阻塞 I/O 模型（Blocking I/O）：当应用程序执行 I/O 操作时，程序会被阻塞，直到 I/O 操作完成。如read和write函数

• 非阻塞 I/O 模型（Non-blocking I/O）：在进行 I/O 操作时，如果没有数据可读写应用程序会立即返回，非阻塞 I/O 模型通常需要程序进行循环查询，会造成 CPU 的资源浪费。

• 多路复用 I/O 模型（Multiplexing I/O）：使用多路复用 I/O 模型时，应用程序通过调用一个函数（如 select()、poll() 或 epoll()）将多个 I/O 操作注册到一个监视器中。当其中任何一个 I/O 操作准备就绪时，应用程序被通知并可以执行相应的操作。这种模型避免了不断轮询的资源浪费，但仍然需要应用程序主动等待通知。

• 信号驱动 I/O 模型（Signal-driven I/O）：在这种模型中，应用程序通过注册信号处理函数来处理 I/O 操作。当 I/O 操作完成时，操作系统会发送一个信号给应用程序，触发相应的信号处理函数。这种模型通常用于处理异步事件，但在某些环境下可能会受到信号处理的限制。

• 异步 I/O 模型（Asynchronous I/O）：在异步 I/O 模型中，应用程序发起一个 I/O 请求后立即返回，而不需要等待操作完成。当 I/O 操作完成时，操作系统会通知应用程序，应用程序可以继续执行其他任务，而不需要等待 I/O 操作完成。异步 I/O 模型通常需要使用操作系统提供的特殊 API（如 POSIX 的 aio_* 系列函数）来实现。

48 fork操作原理

"fork" 操作的基本原理如下：

• 调用系统调用fork函数： 程序通过系统调用来请求操作系统创建一个新的进程。

• 复制父进程： 操作系统在接收到 fork() 调用后，会写时复制当前的父进程。这包括父进程的代码、数据和堆栈等内存信息。这样，子进程就拥有了和父进程相同的执行环境。

• 分配新资源： 操作系统为子进程分配新的进程标识符（PID），确保子进程有自己的独立标识。此外，操作系统可能会分配新的资源给子进程，例如内存空间、文件描述符等。

• 返回值： 在父进程中，fork() 调用返回新创建子进程的PID，而在子进程中，fork() 调用返回0。这样，父进程和子进程可以通过返回值来区分彼此。

• 执行： 父进程和子进程在 fork() 调用之后的代码行开始并行执行。它们之间的区别通常在于返回值，父进程返回子进程的PID，而子进程返回0。基于这个返回值，程序可以采取不同的行为。

49 Linux常用命令

见Linux常用命令

49.1 Linux 服务器当中如何查看负载情况？通过什么指标进行查看？

• 1.top命令 top命令提供了实时的系统状态监视，包括CPU使用率、内存使用情况、正在运行的进程等信息。你可以通过top命令查看各个进程的CPU和内存占用情况，以及系统的总体负载。

• 2 htop命令 htop是top命令的一个增强版本，提供了一个彩色的界面和更多的交互功能。它可以更直观地显示CPU各个核心的使用率、内存、交换空间的使用情况，以及各个进程的详细信息，功能比top更加强大。

• 3.vmstat命令:vmstat [选项] [刷新时间间隔] [刷新次数] vmstat命令报告关于进程、内存、分页、块IO、中断和CPU活动的信息。它可以帮助你查看系统的内存使用情况、进程状态以及IO等待时间等。

  trluper@Trluper:~$ vmstat 1 3
  procs -----------memory---------- ---swap-- -----io---- -system-- ------cpu-----
   r  b   swpd   free   buff  cache   si   so    bi    bo   in   cs us sy id wa st
   1  0      0 1945816 210828 1105608    0    0     1     6    7   16  0  0 100  0  0
   0  0      0 1945212 210828 1105612    0    0     0     0   39  171  0  0 100  0  0
   0  0      0 1945212 210828 1105612    0    0     0    12   25  124  0  0 100  0  0
  procs：
  	r：运行或等待CPU时间片的进程数。
  memory：
  	swpd：被换出到交换空间的内存大小（单位：KB）。
  	free：空闲内存大小（单位：KB）。
  	buff：用作缓冲区的内存大小（单位：KB）。
  	cache：用作缓存的内存大小（单位：KB）。
  swap：
  	si：每秒从磁盘读入交换区的数据量（单位：KB）。
  I/O：
  	bi：每秒从块设备读入的数据量（单位：块，一般为512字节）。
  	bo：每秒向块设备写入的数据量（单位：块，一般为512字节）。
  system：
  	in：每秒产生的中断数。
  	cs：每秒上下文切换的次数。
  cpu：
  	us：用户空间占用CPU时间的百分比。
  	sy：内核空间占用CPU时间的百分比。
  	id：空闲CPU时间的百分比。
  	wa：等待I/O的CPU时间百分比。
  	st：被虚拟机偷走的CPU时间的百分比。

• 4.iostat命令 iostat命令主要用于监视系统输入/输出设备加载情况，可以显示CPU统计信息和所有物理设备的磁盘活动统计信息。这对于检查磁盘IO瓶颈非常有用。

利用上面的命令能够判断Linux服务器的性能瓶颈是否由CPU造成还是内存不足导致的磁盘IO造成

对于网络IO性能瓶颈，可以使用sar命令：

#-n表示选择网络入口和出口，DEV表示网络设备，1表示每秒更新一次。
trluper@Trluper:~$ sar -n DEV 1
Linux 5.10.102.1-microsoft-standard-WSL2 (Trluper)      04/12/24        _x86_64_        (8 CPU)

22:19:06        IFACE   rxpck/s   txpck/s    rxkB/s    txkB/s   rxcmp/s   txcmp/s  rxmcst/s   %ifutil
22:19:07           lo      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
22:19:07        bond0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
22:19:07       dummy0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
22:19:07        tunl0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
22:19:07         sit0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00
22:19:07         eth0      0.00      0.00      0.00      0.00      0.00      0.00      0.00      0.00

IFACE: 网络接口的名称。例如，lo是回环接口，bond0可能是一个绑定接口，dummy0是虚拟接口，tunl0和sit0是隧道接口，eth0是以太网接口。
rxpck/s: 每秒接收的数据包数量。
txpck/s: 每秒发送的数据包数量。
rxkB/s: 每秒接收的千字节数。
txkB/s: 每秒发送的千字节数。
rxcmp/s: 每秒接收的压缩数据包数量（这个字段可能不常见，取决于具体的监控工具）。
txcmp/s: 每秒发送的压缩数据包数量（同上）。
rxmcst/s: 每秒接收的多播数据包数量。
%ifutil: 网络接口的利用率百分比。

• 判断网络IO是否为性能瓶颈，可由以下标准尝试确定：
  • 查看网络接口的带宽利用率：如果网络接口的带宽利用率接近或达到100%，那么网络IO可能是一个性能瓶颈。
    
  • 比较网络IO与其他资源的利用率：例如，如果CPU和内存的利用率都很低，但网络IO很高，那么网络IO很可能是一个瓶颈。
    
  • 观察应用的响应时间：如果应用的响应时间随着网络流量的增加而显著增加，那么网络IO可能是一个问题。

解决方法：

• 网络硬件升级：首先，可以考虑升级服务器的网络接口卡（NIC）和交换机等硬件设备，使用支持更高带宽和更低延迟的设备。例如，从1Gbps升级到10Gbps或更高速度的NIC，或者升级到支持更先进网络协议（如RoCE、SPB等）的设备。
• 网络拓扑优化：优化网络拓扑结构，减少网络跳数，降低网络延迟。例如，可以通过合理的路由设置、VLAN划分等方式，将流量有效地引导到目标服务器，避免不必要的网络拥堵。
• 负载均衡：使用负载均衡技术，将网络流量分散到多个服务器上，避免单一服务器承受过大的网络IO压力。这可以通过硬件负载均衡器或软件负载均衡解决方案（如Nginx、HAProxy等）来实现。
• 网络协议优化：选择和使用更适合业务场景的网络协议，比如对于低延迟敏感的应用，可以选择UDP协议；对于需要可靠传输的应用，可以选择TCP协议，并调整其相关参数（如拥塞控制算法、窗口大小等）以优化性能。
• TCP参数调优：调整TCP相关的系统参数，如发送缓冲区大小、接收缓冲区大小、超时重传时间等，以适应不同的网络环境和业务需求。
• 压缩传输数据：对于大量数据的传输，可以考虑使用数据压缩技术，减少网络带宽的占用，提高传输效率。
• 应用层优化：在应用层进行优化，如减少不必要的数据传输、合并小数据包、使用长连接等，都可以有效降低网络IO的压力。

49.2 查看进程内存的使用情况

可以使用free或者top命令来查看

• 使用free命令来获取当前系统的总体内存使用情况：

  free -h

• 如果想要动态地监视内存使用情况并持续更新，则可以使用top命令：

49.2 查看进程端口使用情况

查看端口使用清理可以用netstat命令，

• -u:udp
• -t:tcp
• l:仅显示监听状态的连接
• -n：（以数字形式显示端口和IP地址）

49.3 Linux的搜索命令

• 在指定目录及其子目录下查找所有txt文件并输出路径 find /path/to -name "*.txt"
• 在指定目录下递归地查找包含特定字符串的文件并输出路径 grep -r "keyword" /path/to/directory

50 分段和分页存储的区别

首先，页和段是不同的两个概念，页是指由操作系统所定义的，我们常说的页表、页面置换都指的页。而段通常是由编译器对源程序编译依据其

• 分页存储：将程序的逻辑地址空间划分为固定大小的页(page)，而物理内存划分为同样大小的页框(page frame)。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。
• 分段存储：将程序的地址空间划分为若干个段(segment)，这样每个进程有一个二维的地址空间。每个段分配一个连续的分区，而进程中的各个段可以不连续地存放在内存的不同分区中。程序加载时，操作系统为所有段分配其所需内存，这些段不必连续。

相同点：

• 分页机制和分段机制都是为了提高内存利用率，产生较少的内存碎片。
• 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是每个页和段中的内存是连续的。

区别：

• 页的大小是固定的，由操作系统决定，而段的大小不固定，取决于我们当前运行的程序。
• 分页是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，它含有一组其意义相对完整的信息，在程序中可以体现为代码段，数据段，是为了满足用户的需要。
• 段一般比页大，因而段表比页表短，可以缩短查找时间，提高访问速度

51.cpu常见的寄存器有哪些?

CPU中常见的寄存器主要包括以下几类：

• 指令寄存器（IR）：用于保存当前正在执行的一条指令。指令寄存器中操作码字段的输出就是指令译码器的输入。
• 程序计数器（PC）：用来指出下一条指令在主存储器中的地址。在程序执行之前，首先必须将程序的首地址，即程序第一条指令所在主存单元的地址送入PC，因此PC的内容即是从主存提取的第一条指令的地址。
• 地址寄存器（AR）：用于存放操作数地址。
• 数据寄存器（DR）：又称数据缓冲寄存器，其主要功能是作为CPU和主存、外设之间信息传输的中转站，用以弥补CPU和主存、外设之间操作速度上的差异。
• 累加寄存器（AC）：用于暂时存放算术或逻辑运算的中间结果等。
• 程序状态字寄存器（PSW）：用于存放程序状态信息，如指令执行后的结果状态。

此外，还有一些通用寄存器（如Rbx~Rn）和特定功能寄存器，它们根据CPU的架构和设计有所不同，用于存放操作数、返回地址等。

50 计算机系统中cache和buffer的区别

在计算机系统中，Cache（缓存）和Buffer（缓冲区）都扮演着重要的角色，但它们的功能和用途存在明显的区别。

• 首先，Cache主要用于提高数据访问速度。它是一种高速缓冲存储器，通常位于CPU和主存之间，用于存储经常访问的数据。当CPU需要读取或写入数据时，会首先检查Cache中是否已有该数据。如果Cache中已有该数据（命中），则CPU可以直接从Cache中获取数据，而无需访问主存，从而减少了访问延迟。Cache的存取速度比主存快，因此使用Cache可以显著提高程序的执行速度。

• 相比之下，Buffer主要用于存储临时数据，并在数据传输过程中起到缓冲作用。当数据从一个设备或组件传输到另一个设备或组件时，由于两者的速度可能不匹配，就需要使用Buffer来平衡这种差异。Buffer可以暂时存储数据，以便后续处理或传输，从而确保数据的连续性和稳定性。此外，Buffer还可以用于平滑数据传输速率的变化，防止数据丢失或损坏。

总结来说，Cache和Buffer的主要区别在于它们的目标和用途。Cache主要是为了提高数据访问速度，而Buffer则是为了存储临时数据并平衡数据传输速率。在实际应用中，它们各自发挥着不可替代的作用，共同为计算机系统的高效运行提供支持。 ### 50 生成者-消费者模型

51 经典同步问题

读者—写者问题

哲学家进餐问题

文章参考来源 >InterviewGuide