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

宏内核与微内核

1）宏内核宏内核是将操作系统功能作为一个紧密结合的整体放到内核。

由于各模块共享信息，因此有很高的性能。

2）微内核由于操作系统不断复杂，因此将一部分操作系统功能移出内核，从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务，相互独立。

在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

因为需要频繁地在用户态和核心态之间进行切换，所以会有一定的性能损失。

中断分类

1）外中断由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。 2）异常由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。 3）陷入在用户程序中使用系统调用。

硬件结构

内存，作用？

内存使用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理。

问题:在多道程序环境下，系统中会有多个程序并发执行，也就是说会有多个程序的数据需要同时放到内存中。那么，如何区分各个程序的数据放在什么地方？

方法：给内存的存储单元编地址

**逻辑地址vs物理地址：**编译时只需确定变量x存放的相对地址是100 ( 也就是说相对于进程在内存中的起始地址而言的地址)。CPU想要找到x在内存中的实际存放位置，只需要用进程的起始地址+100即可。相对地址又称逻辑地址，绝对地址又称物理地址。

中断和异常的区别

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

例子：当我们在敲击键盘的同时就会产生中断，当硬盘读写完数据之后也会产生中断。

异常：由CPU产生的，同时，它会发送给内核，要求内核处理这些异常，下面这张图显示了异常处理的流程：

例子：非法操作码、地址越界、算术溢出等。

相同点：

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

不同点：

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

系统并发和并行

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

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

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

共享

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

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

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

虚拟技术

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

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

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

进程管理

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

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

总结（进程和线程的区别和联系）：

区别：
- 进程是资源分配和拥有（（打开文件，堆，静态区，代码段等）的基本单位，而线程是CPU调度（（PC，状态码，通用寄存器，线程栈及栈指针）的基本单位，是轻量级的进程。
- 进程有独立的地址空间。线程没有独立的地址空间，多个线程共享进程的地址空间。
- 拥有资源：线程不拥有系统资源，但一个进程的多个线程可以共享隶属进程的资源，也有各自维护的资源（如程序计数器、一些寄存器、栈）；进程是拥有资源的独立单位。
- 进程的创建需要系统分配内存和CPU，文件句柄等资源，销毁时也要进行相应的回收，所以进程的管理开销很大；但是线程的管理开销则很小，创建销毁只需要处理PC值，状态码，通用寄存器值，线程栈及栈指针即可。(进程创建和销毁需要重新分配及销毁task_struct结构。)
- 在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
- 进程之间不会相互影响；而一个线程崩溃会导致进程崩溃，从而影响同个进程里面的其他线程。
联系
- 进程与线程之间的关系：线程是存在进程的内部，一个进程中可以有多个线程，一个线程只能存在一个进程中。

Notes:

进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。运行一个可执行程序会创建一个或多个进程，进程就是运行起来的可执行程序。
每个进程中都有唯一的主线程，且只能有一个，主线程和进程是相互依存的关系，主线程结束进程也会结束。
在一个进程的线程共享堆区、全局变量、静态变量、指针，引用、文件等，而进程中的线程各自维持自己的堆栈。
并发性：一个进程内多个线程可以并发（最好和CPU核数相等）；多个进程可以并发。
线程使用有一定难度，需要处理数据一致性问题。
举例：QQ 和浏览器是两个进程，浏览器进程里面有很多线程，例如 HTTP 请求线程、事件响应线程、渲染线程等等，线程的并发执行使得在浏览器中点击一个新链接从而发起 HTTP 请求时，浏览器还可以响应用户的其它事件。

Linux理论上最多可以创建多少个进程？一个进程可以创建多少线程，和什么有关

最多可以创建32768个进程，因为进程的pid是用pid_t来表示的，pid_t的最大值是32768.所以理论上最多有32768个进程。

关于一个进程可以创建多少线程，这个要分不同系统去看：

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

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

进程状态切换

一个进程的活动期间至少具备三种基本状态：运行态、就绪态、阻塞态（等待态或睡眠态）

就绪态（ready)：等待被调用
运行态（running）:该时刻进程占用CPU
阻塞状态（waiting)：等待资源

Note：

就绪态和运行态可以相互转换，其余都是单向转换。处于就绪态的进程通过进程调度算法获得CPU时间，变为运行态；处于运行态的进程将分配给它的CPU时间片用完就转为就绪态，等待下一次调度。
阻塞状态是由于缺少除CPU之外的资源从而从运行态转换而来，缺少CPU时间会从运行态转为就绪态。

进程还有两种基本状态：

创建状态（new)：进程正在被创建时的状态；
结束状态(exit)：进程正在从系统中消失时的状态。

进程的状态变迁：

NULL->创建状态：一个新进程被创建时的第一个状态；
创建状态->就绪状态：当进程被创建完成并初始化后，一切就绪准备运行时，变为就绪状态，这个过程是很快的；
就绪态->运行态：处于就绪态的进程被操作系统的进程调度器选中后，就分配给CPU正式运行该进程；
运行态->结束态：当进程已经运行完成或出错时，会被操作系统作结束状态处理；
运行态->就绪态：处于运行态的进程在运行过程中，由于分配给它的运行时间片用完，操作系统把该进程变为就绪态，接着从就绪态中选另一个进程运行；
运行态->阻塞态：当进程请求某个事件且必须等待时，例如请求I/O事件；
阻塞态->就绪态：当进程要等待的事件完成时，它从阻塞态变为就绪态。

当有大量处于阻塞态的进程，进程可能会占用着物理内存空间，但是物理内存空间有限，被阻塞态的进程占用着物理内存就是一种浪费物理内存的行为。所以，在虚拟内存管理的操作系统中，通常把阻塞态的进程的物理内存空间换出到硬盘，等需要再次运行的时候，再从磁盘换出到物理内存。

那么，就需要一个新的状态，来描述进程没有占用实际的物理内存空间的情况，这个状态就是挂起状态。这跟阻塞态不同，阻塞态是等待某个事件的返回。挂起态可以分为两种：

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

导致挂起的原因不只是因为进程所使用的内存空间不在物理内存，还包括如下情况：

通过sleep让进程间歇性挂起，其工作原理是设置一个定时器，到期后唤醒进程。
用户希望挂起一个程序的执行，比如在Linux中用ctrl + Z挂起进程；

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

1）守护进程

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

2）僵尸进程

在类UNIX系统中，僵尸进程是指完成执行（通过 exit 系统调用，或运行时发生致命错误或收到终止信号所致），但在操作系统的进程表中仍然存在其进程控制块，处于"终止状态"的进程。

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

设置僵尸进程的目的是维护子进程的信息，以便父进程在以后某个时候获取。这些信息至少包括进程ID，进程的终止状态，以及该进程使用的CPU时间，所以当终止子进程的父进程调用wait或waitpid时就可以得到这些信息。如果一个进程终止，而该进程有子进程处于僵尸状态，那么它的所有僵尸子进程的父进程ID将被重置为1（init进程）。继承这些子进程的init进程将清理它们（也就是说init进程将wait它们，从而去除它们的僵尸状态）。

3）孤儿进程

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

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

如何避免僵尸进程

通过signal(SIGCHLD, SIG_IGN)通知内核对子进程的结束不关心，由内核回收。如果不想让父进程挂起，可以在父进程中加入一条语句：signal(SIGCHLD,SIG_IGN);表示父进程忽略SIGCHLD信号，该信号是子进程退出的时候向父进程发送的。
父进程调用wait/waitpid等函数等待子进程结束，如果尚无子进程退出wait会导致父进程阻塞。waitpid可以通过传递WNOHANG使父进程不阻塞立即返回。
如果父进程很忙可以用signal注册信号处理函数，在信号处理函数调用wait/waitpid等待子进程退出。
通过两次调用fork。父进程首先调用fork创建一个子进程然后waitpid等待子进程退出，子进程再fork一个孙进程后退出。这样子进程退出后会被父进程等待回收，而对于孙子进程其父进程已经退出所以孙进程成为一个孤儿进程，孤儿进程由init进程接管，孙进程结束后，init会等待回收。

第一种方法忽略SIGCHLD信号，这常用于并发服务器的性能的一个技巧因为并发服务器常常fork很多子进程，子进程终结之后需要服务器进程去wait清理资源。如果将此信号的处理方式设为忽略，可让内核把僵尸子进程转交给init进程去处理，省去了大量僵尸进程占用系统资源。

父进程、子进程、进程组、作业和会话

1）父进程

已创建一个或多个子进程的进程

2）子进程

由fork创建的新进程被称为子进程（child process）。该函数被调用一次，但返回两次。两次返回的区别是子进程的返回值是0，而父进程的返回值则是新进程（子进程）的进程 id。将子进程id返回给父进程的理由是：因为一个进程的子进程可以多于一个，没有一个函数使一个进程可以获得其所有子进程的进程id。对子进程来说，之所以fork返回0给它，是因为它随时可以调用getpid()来获取自己的pid；也可以调用getppid()来获取父进程的id。(进程id 0总是由交换进程使用，所以一个子进程的进程id不可能为0 )。

fork之后，操作系统会复制一个与父进程完全相同的子进程，这2个进程共享代码空间，但是数据空间是互相独立的，子进程数据空间中的内容是父进程的完整拷贝，指令指针也完全相同，子进程拥有父进程当前运行到的位置（两进程的程序计数器pc值相同，也就是说，子进程是从fork返回处开始执行的），但有一点不同，如果fork成功，子进程中fork的返回值是0，父进程中fork的返回值是子进程的进程号，如果fork不成功，父进程会返回错误。

子进程从父进程继承的有：

1.进程的资格(真实(real)/有效(effective)/已保存(saved)用户号(UIDs)和组号(GIDs))

2.环境(environment)

3.堆栈

4.内存

5.进程组号

独有：

1.进程号；

2.不同的父进程号(译者注：即子进程的父进程号与父进程的父进程号不同，父进程号可由getppid函数得到)；

3.资源使用(resource utilizations)设定为0

3）进程组

进程组就是多个进程的集合，其中肯定有一个组长，其进程PID等于进程组的PGID。只要在某个进程组中一个进程存在，该进程组就存在，这与其组长进程是否终止无关。

4）作业

shell分前后台来控制的不是进程而是作业（job）或者进程组（Process Group）。

一个前台作业可以由多个进程组成，一个后台也可以由多个进程组成，shell可以运行一个前台作业和任意多个后台作业，这称为作业控制。

**为什么只能运行一个前台作业？**当我们在前台新起了一个作业，shell就被提到了后台，因此shell就没有办法再继续接受我们的指令并且解析运行了。但是如果前台进程退出了，shell就会有被提到前台来，就可以继续接受我们的命令并且解析运行。

作业与进程组的区别：如果作业中的某个进程有创建了子进程，则该子进程是不属于该作业的。一旦作业运行结束，shell就把自己提到前台（子进程还存在，但是子进程不属于作业），如果原来的前台进程还存在（这个子进程还没有终止），他将自动变为后台进程组

5）会话

会话（Session）是一个或多个进程组的集合。一个会话可以有一个控制终端。在xshell或者WinSCP中打开一个窗口就是新建一个会话。

进程终止的几种方式

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

exit和_exit的区别

进程线程模型

多线程

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

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

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

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

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

线程之间有无先后访问顺序（线程依赖关系）
多个线程共享访问同一变量（同步互斥问题）

同一进程的多个线程共享进程的资源，但是每个线程特有的部分，除了标识线程的tid，每个线程还有自己独立的栈空间，线程彼此之间是无法访问其他线程栈上内容的。

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

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

线程创建和结束
- 背景知识：
  在一个文件内的多个函数通常都是按照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：同上。

线程属性值修改

背景知识：

线程属性对象类型为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()重新加载新的代码段的过程。

进程创建与结束
- 背景知识：
  进程有两种创建方式，一种是操作系统创建的一种是父进程创建的。从计算机启动到终端执行程序的过程为：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()、终止信号。
Linux进程控制

进程地址空间（地址空间）
虚拟存储器为每个进程提供了独占系统地址空间的假象。尽管每个进程地址空间内容不尽相同，但是他们的都有相似的结构。X86 Linux进程的地址空间底部是保留给用户程序的，包括文本、数据、堆、栈等，其中文本区和数据区是通过存储器映射方式将磁盘中可执行文件的相应段映射至虚拟存储器地址空间中。
有一些"敏感"的地址需要注意下，对于32位进程来说，代码段从0x08048000开始。从0xC0000000开始到0xFFFFFFFF是内核地址空间，通常情况下代码运行在用户态（使用0x00000000 ~ 0xC00000000的用户地址空间），当发生系统调用、进程切换等操作时CPU控制寄存器设置模式位，进入内和模式，在该状态（超级用户模式）下进程可以访问全部存储器位置和执行全部指令。
也就说32位进程的地址空间都是4G，但用户态下只能访问低3G的地址空间，若要访问3G ~ 4G的地址空间则只有进入内核态才行。
进程控制块（处理机）
进程的调度实际就是内核选择相应的进程控制块，被选择的进程控制块中包含了一个进程基本的信息。
上下文切换
内核管理所有进程控制块，而进程控制块记录了进程全部状态信息。每一次进程调度就是一次上下文切换，所谓的上下文本质上就是当前运行状态，主要包括通用寄存器、浮点寄存器、状态寄存器、程序计数器、用户栈和内核数据结构（页表、进程表、文件表）等。
进程执行时刻，内核可以决定抢占当前进程并开始新的进程，这个过程由内核调度器完成，当调度器选择了某个进程时称为该进程被调度，该过程通过上下文切换来改变当前状态。
一次完整的上下文切换通常是进程原先运行于用户态，之后因系统调用或时间片到切换到内核态执行内核指令，完成上下文切换后回到用户态，此时已经切换到进程B。

进程调度算法

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

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

有利于长作业（CPU繁忙型），但不利于短作业(I/O繁忙型），因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

2）短作业优先 shortest job first（SJF）

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

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

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

最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程，否则新的进程等待。

4）高响应比有点调度算法 Highest Reponse Ratio First（HRRF）

非抢占式的，主要用于作业调度。基本思想：每次进行作业调度时，先计算后备作业队列中每个作业的响应比，挑选最高的作业投入系统运行。响应比 = （等待时间 + 服务时间） / 服务时间 = 等待时间 / 服务时间 + 1。因为每次都需要计算响应比，所以比较耗费系统资源。

5）时间片轮转

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

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

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

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

6）优先级调度

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

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

7）多级反馈队列

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

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

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

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

进程同步的四种方法

1）临界区Critical Section

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

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

// entry section
// critical section;
// exit section

2）同步与互斥 Synchronization and Mutex

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
互斥：多个进程在同一时刻只有一个进程能进入临界区。

3）信号量

信号量是操作系统提供的一种协调共享资源访问的方法。

信号量（Semaphore）是一个整型变量，表示资源的数量，还有两个原子操作的系统调用函数来控制信号量的（原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断）。

P：表示申请资源，对信号量执行 - 1 操作，如果信号量小于 0 ，则进程/线程进入阻塞等待，否则继续，表明P操作可能会阻塞；
V：表示释放资源，对信号量执行 +1 操作，如果信号量<=0，唤醒一个等待中的进程/线程，表明V操作不会阻塞；

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

typedef int semaphore;
semaphore mutex = 1;
void P1() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

void P2() {
    down(&mutex);
    // 临界区
    up(&mutex);
}

使用信号量实现生产者-消费者问题

问题描述：使用一个缓冲区来保存物品，只有缓冲区没有满，生产者才可以放入物品；只有缓冲区不为空，消费者才可以拿走物品。

因为缓冲区属于临界资源，因此需要使用一个互斥量 mutex 来控制对缓冲区的互斥访问。

为了同步生产者和消费者的行为，需要记录缓冲区中物品的数量。数量可以使用信号量来进行统计，这里需要使用两个信号量：empty 记录空缓冲区的数量，full 记录满缓冲区的数量。其中，empty 信号量是在生产者进程中使用，当 empty 不为 0 时，生产者才可以放入物品；full 信号量是在消费者进程中使用，当 full 信号量不为 0 时，消费者才可以取走物品。

注意，不能先对缓冲区进行加锁，再测试信号量。也就是说，不能先执行 down(mutex) 再执行 down(empty)。如果这么做了，那么可能会出现这种情况：生产者对缓冲区加锁后，执行 down(empty) 操作，发现 empty = 0，此时生产者睡眠。消费者不能进入临界区，因为生产者对缓冲区加锁了，消费者就无法执行 up(empty) 操作，empty 永远都为 0，导致生产者永远等待下，不会释放锁，消费者因此也会永远等待下去。

#define N 100
typedef int semaphore;
semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

void producer() {
    while(TRUE) {
        int item = produce_item();
        down(&empty);
        down(&mutex);
        insert_item(item);
        up(&mutex);
        up(&full);
    }
}

void consumer() {
    while(TRUE) {
        down(&full);
        down(&mutex);
        int item = remove_item();
        consume_item(item);
        up(&mutex);
        up(&empty);
    }
}

4）管程 Monitor

使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

c 语言不支持管程，下面的示例代码使用了类 Pascal 语言来描述管程。示例代码的管程提供了 insert() 和 remove() 方法，客户端代码通过调用这两个方法来解决生产者-消费者问题

monitor ProducerConsumer
    integer i;
    condition c;

    procedure insert();
    begin
        // ...
    end;

    procedure remove();
    begin
        // ...
    end;
end monitor;

管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。

管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

使用管程实现生产者-消费者问题

// 管程
monitor ProducerConsumer
    condition full, empty;
    integer count := 0;
    condition c;

    procedure insert(item: integer);
    begin
        if count = N then wait(full);
        insert_item(item);
        count := count + 1;
        if count = 1 then signal(empty);
    end;

    function remove: integer;
    begin
        if count = 0 then wait(empty);
        remove = remove_item;
        count := count - 1;
        if count = N -1 then signal(full);
    end;
end monitor;

// 生产者客户端
procedure producer
begin
    while true do
    begin
        item = produce_item;
        ProducerConsumer.insert(item);
    end
end;

// 消费者客户端
procedure consumer
begin
    while true do
    begin
        item = ProducerConsumer.remove;
        consume_item(item);
    end
end;

经典同步问题

1）哲学家进餐问题

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

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

#define N 5
semaphore chop[5];//信号量初值为1，筷子的个数
void philosopher(int i) {
    while(TRUE) {
        think();
        P(chop[i]);       // 拿起左边的筷子
        P(chop[(i+1)%N]); // 拿起右边的筷子
        eat();
        V(chop[i]);
        V(chop[(i+1)%N]);
    }
}

**方案二：**既然方案一会发生同时竞争左边筷子导致死锁的现象，那么在拿筷子前，加一个互斥信号量。

#define N 5
semaphore chop[5];//信号量初值为1，筷子的个数
semaphore mutex;//互斥信号量，初值为1
void philosopher(int i) {
    while(TRUE) {
        think();
        P(mutex);
        P(chop[i]);       // 拿起左边的筷子
        P(chop[(i+1)%N]); // 拿起右边的筷子
        eat();
        V(chop[i]);
        V(chop[(i+1)%N]);
        V(mutex);//退出临界区
    }
}

互斥信号量的作用：只要有一个哲学家进入临界区，只有这位哲学家用完筷子，才能轮到下一个哲学家进餐。但是每次进餐只有一个哲学家，从效率上看，这不是最好的解决方法。

方案三：⽅案⼀的问题在于，会出现所有哲学家同时拿左边筷子的可能性，那我们就避免哲学家可以同时拿左边的筷子，采⽤分⽀结构，根据哲学家的编号的不同，⽽采取不同的动作。

即让偶数编号的哲学家「先拿左边的筷子后拿右边的筷子」，奇数编号的哲学家「先拿右边的筷子后拿左边的筷子」。

#define N 5
semaphore chop[5];//信号量初值为1，筷子的个数

void philosopher(int i) {
    while(TRUE) {
        think();
        if(i % 2 == 0){
            P(chop[i]);       // 拿起左边的筷子
            P(chop[(i+1)%N]); // 拿起右边的筷子
        }
        else{
            P(chop[(i+1)%N]); // 拿起右边的筷子
            P(chop[i]);       // 拿起左边的筷子
        }
        eat();
        V(chop[i]);
        V(chop[(i+1)%N]);
    }
}

方案三既不会出现死锁，也可以两人同时进餐。

方案四：

再提出一种可行的解决方案，用一个数组state记录每一位哲学家在进餐、思考还是饥饿状态（正在试图拿筷子）。那么，一个哲学家只有在两个邻居都没有进餐时，才可以进入就餐状态。

第i个哲学家的左邻右舍，由宏LEFT和RIGHT定义：

LEFT：（i + 5 - 1）%5
RIGHT：（i + 1）% 5

#define THINKING 0    //思考状态
#define HUNGRY   1    //饥饿状态
#define EATING   2    //进餐状态
typedef int semaphore;
int state[N];                // 记录每个哲学家的状态
semaphore mutex = 1;         // 临界区的互斥，临界区是 state 数组，对其修改需要互斥
semaphore s[N];              // 每个哲学家一个信号量

//哲学家主代码
void philosopher(int i) {
    while(TRUE) {
        think(i);
        take_two(i);//准备拿筷子吃饭
        eat(i);
        put_two(i);   //吃完饭回筷子
    }
}

//功能：要么拿到两把筷子，要么被阻塞起来
void take_two(int i) {
    P(mutex);//进入临界区
    state[i] = HUNGRY;//标记哲学家处于饥饿状态
    check(i); //尝试获取两只筷子
    V(mutex);
    P(s[i]); // 只有收到通知之后才可以开始吃，否则会一直等下去
}

//功能：把两把筷子放回原处，在需要的时候，幻想左邻右舍
void put_two(i) {
    P(mutex);
    state[i] = THINKING; //吃完了，交出筷子，标记思考状态
    check(LEFT); // 尝试通知左右邻居，自己吃完了，你们可以开始吃了
    check(RIGHT);
    V(mutex);
}

void eat(int i) {
    P(mutex);
    state[i] = EATING;
    V(mutex);
}

// 检查两个邻居是否都没有用餐，
void check(i) {         
    //如果i号的邻居哲学家不是进餐状态，把i号哲学家标记为进餐状态
    if(state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] !=EATING) {
        state[i] = EATING;//进餐状态
        V(s[i]);//通知第i哲学家可以进餐了
    }
}

上⾯的程序使⽤了⼀个信号量数组，每个信号量对应⼀位哲学家，这样在所需的筷子被占⽤时，想进餐的哲学家就被阻塞。

2）读者-写者问题

读者只会读取数据，不会修改数据，而写者既可以读数据也可以修改数据。

读者-写者问题描述：

「读-读」允许：同⼀时刻，允许多个读者同时读
「读-写」互斥：没有写者时读者才能读，没有读者时写者才能写
「写-写」互斥：没有其他写者时，写者才能

方案一：

使用信号量的方式尝试解决：

信号量 wMutex ：控制写操作的互斥信号量，初始值为 1 ；
读者计数 rCount ：正在进⾏读操作的读者个数，初始化为 0；
信号量 rCountMutex ：控制对 rCount 读者计数器的互斥修改，初始值为 1；

semaphore wMutex; 
semaphore rCountMutex;
int rCount = 0;
//写者进程/线程执行的函数
void writer()
{
    while(TRUE)
    {
        P(wMutex);
        write();
        V(wMutex);
    }
}
//读者进程/线程执行的函数
void reader()
{
    while(TRUE)
    {
        P(rCountMutex);
        if(rCount == 0)
        {
            P(wMutex);  //如果有写者，阻塞写者
        }
        rCount++;   //读者计数加1
        V(rCountMutex);
        
        read();
        
        P(rCountMutex);
        rCount--;   //读完数据，准备离开
        if(rCount == 0)
        {
            V(wMutex);   //最后一个读者离开了，唤醒写者
        }
        V(rCountMutex);
    }
}

上面这种实现是读者优先的策略，只要有读者正在读的状态，后面的读者可以直接进入，如果读者不断进入，写者会处于饥饿状态。

方案二：

写者优先策略：

只要有写者准备要写⼊，写者应尽快执⾏写操作，后来的读者就必须阻塞；
如果有写者持续不断写⼊，则读者就处于饥饿；

在方案一的基础上新增如下信号量：

信号量 rMutex ：控制读者进⼊的互斥信号量，初始值为 1；
信号量 wDataMutex ：控制写者写操作的互斥信号量，初始值为 1；
写者计数 wCount ：记录写者数量，初始值为 0；
信号量 wCountMutex ：控制 wCount 互斥修改，初始值为 1

semaphore rMutex; 
semaphore rCountMutex;  //控制对Rcount的互斥修改，初始值为1
semaphore wCountMutex;
semaphore wDataMutex; //控制写者写操作的互斥信号量
int rCount = 0;
int wCount = 0;
//写者进程/线程执行的函数
void writer()
{
    while(TRUE)
    {
       P(wCountMutex);//进入临界区
        if(wCount == 0)
        {
            P(rMutex); //当第一个写着进入，如果有读者阻塞读者
        }
        wCount++;
        V(wCountMutex);//退出临界区
        
        P(wDataMutex);
        write();  //写数据
        V(wDataMutex);
        
        P(wCountMutex);
        wCount--;
        if(wCount == 0);
        {
            V(rMutex);//最后一个写者离开，唤醒读者
        }
        V(wCountMutex);
    }
}
//读者进程/线程执行的函数
void reader()
{
    while(TRUE)
    {
        P(rMutex);
        P(rCountMutex);
        if(rCount == 0)
        {
            P(wDataMutex);  //如果有写者，阻塞写者
        }
        rCount++;   //读者计数加1
        V(rCountMutex);
        V(rMutex);
        
        read();
        
        P(rCountMutex);
        rCount--;   //读完数据，准备离开
        if(rCount == 0)
        {
            V(wDataMutex);   //最后一个读者离开了，唤醒写者
        }
        V(rCountMutex);
    }
}

这里rMutex的作用，开始有多个读者读数据，全部进入读者队列，此时来了一个写者，执行了P(rMutex)后，和后续的读者由于堵塞在rMutex上，都不能再进入读者队列，而写者到来，则全部进入写者队列，保证了写者优先。

第一个写者执行了P(rMutex)之后，也不能马上写，要等到所有进入读者队列的读者都执行完读操作，通过V(wDataMutex)唤醒写者的写操作。

方案三：

公平策略：

优先级相同；
写者、读者互斥访问；
只能⼀个写者访问临界区；
可以有多个读者同时访问临界资源

semaphore rCountMutex;  //控制对Rcount的互斥修改，初始值为1
semaphore wDataMutex; //控制写者写操作的互斥信号量，初始值为1
semaphore flag;   //用于实现公平竞争，初始值为1
int rCount = 0;
//写者进程/线程执行的函数
void writer()
{
    while(TRUE)
    {
        P(flag);
        P(wDataMutex);
        write();  //写数据
        V(wDataMutex);
        V(flag);
    }
}
//读者进程/线程执行的函数
void reader()
{
    while(TRUE)
    {
        P(flag);
        P(rCountMutex);
        if(rCount == 0)
        {
            P(wDataMutex);  //当第一个读者进入，如果有写者则阻塞写者写操作
        }
        rCount++;   //读者计数加1
        V(rCountMutex);
        V(flag);
        
        read();
        
        P(rCountMutex);
        rCount--;   //读完数据，准备离开
        if(rCount == 0)
        {
            V(wDataMutex);   //最后一个读者离开了，唤醒阻塞中写者的写操作
        }
        V(rCountMutex);
    }
}

对⽐⽅案⼀的读者优先策略，可以发现，读者优先中只要后续有读者到达，读者就可以进⼊读者队列，⽽写者必须等待，直到没有读者到达。没有读者到达会导致读者队列为空，即 rCount==0 ，此时写者才可以进⼊临界区执⾏写操作。

⽽这⾥ flag 的作⽤就是阻⽌读者的这种特殊权限（特殊权限是只要读者到达，就可以进入读者队列）。

开始来了⼀些读者读数据，它们全部进⼊读者队列，此时来了⼀个写者，执⾏ P(falg) 操作，使得后续到来的读者都阻塞在 flag 上，不能进⼊读者队列，这会使得读者队列逐渐为空，即 rCount 减为 0。这个写者也不能立马开始写（因为此时读者队列不为空），会阻塞在信号量 wDataMutex 上，读者队列中的读者全部读取结束后，最后⼀个读者进程执⾏ V(wDataMutex) ，唤醒刚才的写者，写者则继续开始进⾏写操作。

Linux进程间通信方式

(186条消息) Linux多线程间通信和多进程间通信的方式_landishu的博客-CSDN博客_linux线程间通信的几种方法

[整理] Linux 进程间通信的方式、应用场景及优缺点 - 哆啦梦乐园 - 博客园

(194条消息) 进程间的7种通信方式（含例程代码）_馋学习的身子的博客-CSDN博客_进程间通信的七种方式

进程同步与进程通信很容易混淆，它们的区别在于：

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

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

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

1）管道

无名管道（内存文件）PIPE：
- 特点
  - 无名管道是一种特殊的文件，这种文件只存在于内存中。
  - 管道是一种半双工的通信方式，数据只能单向流动，如果双方需要同时收发数据需要两个管道。
  - 由于匿名管道没有名字：只能在具有亲缘关系（指父子进程关系）的进程之间使用。
- 相关接口
  - 通过调用pipe函数创建，fd[0]用于读，df[1]用于写。通信双方的进程中写数据的一方需要把fd[0]先close掉，读的一方需要先把fd[1]给close掉。
```
#include <unistd.h>
int pipe(int fd[2]);
```
使用：ps auf | grep mysql;其中 |表示的管道称为匿名管道；
命名管道（FIFO文件，借助文件系统）：
- 特定
  - 有名管道是FIFO文件，存在于文件系统中，可以通过文件路径名来指出。命名管道也是半双工的通信方式，是一种先进先出的通信方式。
  - 允许在没有亲缘关系的进程之间使用。
  - FIFO 常用于客户-服务器应用程序中，FIFO 用作汇聚点，在客户进程和服务器进程之间传递数据。
- 相关接口：命名管道通过命令mkfifo或系统调用mkfifo来创建
```
#include <sys/stat.h>
int mkfifo(const char *pathname, mode_t mode);//pathname为即将创建的FIFO文件路径，如果文件存在需要先删除；mode和open()中参数相同 
int mkfifoat(int fd, const char *pathname, mode_t mode);
```

2）共享内存

进程可以将同一段共享内存映射到自己的进程地址空间，所有进程都可以访问共享内存中的地址，如果某个进程向共享内存内写入数据，所做的改动将立即影响到可以访问该共享内存的其他所有进程。这段共享内存由一个进程创建，但多个进程都可以访问。因为数据不需要在进程之间复制，共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往配合信号量一起实现进程间的同步和通信。

其余补充：

共享内存的方式像极了多线程中线程对全局变量的访问，大家都对等地有权去修改这块内存的值，这就导致在多进程并发下，最终结果是不可预期的。所以对这块临界区的访问需要通过信号量来进行进程同步。
但共享内存的优势也很明显，首先可以通过共享内存进行通信的进程不需要像无名管道一样需要通信的进程间有亲缘关系。其次内存共享的速度也比较快，不存在读取文件、消息传递等过程，只需要到相应映射到的内存地址直接读写数据即可。

3）消息队列

消息队列是消息的链表，包括POSIX消息队列和System V消息队列，存放在内核中并由消息队列标识符标识。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读队列中的消息。与管道（无名管道：只存在于内存中的文件；命名管道：存在于实际的磁盘介质或者文件系统）不同的是消息队列存放在内核中，只有在内核重启(即，操作系统重启)或者显式地删除一个消息队列时，该消息队列才会被真正的删除。消息队列可以实现消息的随机查询，消息不一定要以先进先出的次序读取，也可以按消息的类型读取，比 FIFO 更有优势。消息队列克服了信号承载信息量少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

相比于 FIFO，消息队列具有以下优点：

消息队列可以独立于读写进程存在，从而避免了 FIFO 中同步管道的打开和关闭时可能产生的困难；
避免了 FIFO 的同步阻塞问题，不需要进程自己提供同步方法；
读进程可以根据消息类型有选择地接收消息，而不像 FIFO 那样只能默认地接收。

4）套接字

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

5）信号

用于通知接收进程某个事件已经发生，比如按下ctrl + C就是信号。除了用于进程间通信外，进程还可以发送信号给进程本身。信号可以在任何时候发送给某一进程，而无须知道该进程的状态。如果该进程并未处于执行状态，则该信号就由内核保存起来，直到该进程恢复执行并传递给它为止。如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程。信号是开销最小的

6）信号量

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

多线程同步的信号量是POSIX信号量，而在进程里使用SYSTEM V信号量。

辅助命令：
ipcs命令用于报告共享内存、信号量和消息队列信息。
ipcs -a：列出共享内存、信号量和消息队列信息。
ipcs -l：列出系统限额。
ipcs -u：列出当前使用情况。

线程间同步的方式

线程同步是两个或多个共享关键资源的线程的并发执行。应该同步线程以避免关键的资源使用冲突。操作系统一般有下面三种线程同步的方式：

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

Linux线程间通信方式

1）锁机制：包括互斥锁、自旋锁、读写锁

2）信号量机制Semaphore

包括无名线程信号量和命名线程信号量

3）信号机制

类似进程间的信号处理；

4）条件变量：使用通知的方式解锁，与互斥锁配合使用

多进程和多线程的区别是什么？什么时候用多线程，什么时候用多进程？

频繁修改：需要频繁创建和销毁的优先使用多线程
计算量：需要大量计算的优先使用多线程 因为需要消耗大量CPU资源且切换频繁，所以多线程好一点
相关性：任务间相关性比较强的用多线程，相关性比较弱的用多进程。因为线程之间的数据共享和同步比较简单。
多分布：可能要扩展到多机分布的用多进程，多核分布的用多线程。

但是实际中更常见的是进程加线程的结合方式，并不是非此即彼的。

单线程和多线程各自的优缺点

单线程和多线程的区别_wx5ba0c87f1984b的技术博客_51CTO博客

单线程的好处就是易于编程，不需要考虑太多状况，缺点是效率低。

多线程的好处是效率高，性能高，但是不是所有的运算都可以被并行化，而且容易出现各种意外的稀奇古怪的bug。

多线程的产生并不是因为多线程CPU运行效率比单线程高。单从CPU的运行效率上考虑，单任务进程及单线程效率是最高的，因为CPU没有任何进程及线程的切换开销。 多线程的出现主要为了解决IO设备的读写速度往往比CPU的处理速度慢造成的单线程程序运行阻塞问题。多线程能提高因程序由于等待某个资源阻塞时其他资源的利用率（是利用率不是效率）。

因此多线程与单线程的最大区别，多线程程序能在等待某个IO操作时，继续完成非这个IO的其他工作，有利于提高资源利用率，提高完成整个任务的效果和速度。此外，多线程程序需要考虑对静态变量等资源的操作互锁及程序执行的同步问题。

几种典型的锁

读写锁

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

互斥锁mutex

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

互斥锁属于sleep-waiting类型的锁。例如在一个双核的机器上有两个线程A和B，它们分别运行在core 0和core 1上。假设线程A想要通过pthread_mutex_lock操作去得到一个临界区的锁，而此时这个锁正被线程B所持有，那么线程A就会被阻塞，此时会通过上下文切换将线程A置于等待队列中，此时core 0就可以运行其他的任务（如线程C）。

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

条件变量cond

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

自旋锁spin

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

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

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

自旋锁一直占用CPU，在未获得锁的情况下，一直进行自旋，所以占用着CPU，如果不能在很短的时间内获得锁，无疑会使CPU效率降低。
在用自旋锁时有可能造成死锁，当递归调用时有可能造成死锁。
自旋锁只有在内核可抢占式或SMP的情况下才真正需要，在单CPU且不可抢占式的内核下，自旋锁的操作为空操作。自旋锁适用于锁使用者保持锁时间比较短的情况下。

多线程有哪些锁，特点

互斥锁，自旋锁，读写锁，乐观锁，悲观锁

互斥锁与自旋锁

加锁的目的是保证共享资源在任意时间里，只有一个线程访问，这样就可以避免多线程导致共享数据错乱的问题

当已经有一个线程加锁后，其他线程加锁则就会失败，互斥锁和自旋锁对于加锁失败后的处理方式是不一样的：

互斥锁加锁失败后，线程会释放 CPU ，给其他线程；

自旋锁加锁失败后，线程会忙等待，直到它拿到锁；

互斥锁是一种「独占锁」，比如当线程 A 加锁成功后，此时互斥锁已经被线程 A 独占了，只要线程 A 没有释放手中的锁，线程 B 加锁就会失败，于是就会释放 CPU 让给其他线程，既然线程 B 释放掉了 CPU，自然线程 B 加锁的代码就会被阻塞。

对于互斥锁加锁失败而阻塞的现象，是由操作系统内核实现的。当加锁失败时，内核会将线程置为「睡眠」状态，等到锁被释放后，内核会在合适的时机唤醒线程，当这个线程成功获取到锁后，于是就可以继续执行。如下图：

所以，互斥锁加锁失败时，会从用户态陷入到内核态，让内核帮我们切换线程，虽然简化了使用锁的难度，但是存在一定的性能开销成本。

那这个开销成本是什么呢？会有两次线程上下文切换的成本：

当线程加锁失败时，内核会把线程的状态从「运行」状态设置为「睡眠」状态，然后把 CPU 切换给其他线程运行；
接着，当锁被释放时，之前「睡眠」状态的线程会变为「就绪」状态，然后内核会在合适的时间，把 CPU 切换给该线程运行。

线程的上下文切换的是什么？当两个线程是属于同一个进程，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据。

上下切换的耗时有大佬统计过，大概在几十纳秒到几微秒之间，如果你锁住的代码执行时间比较短，那可能上下文切换的时间都比你锁住的代码执行时间还要长。

所以，如果你能确定被锁住的代码执行时间很短，就不应该用互斥锁，而应该选用自旋锁，否则使用互斥锁。

自旋锁是通过CPU提供的CAS（Compare And Swap）函数，在用户态完成加锁和解锁的操作，不会主动产生线程上下文切换，所以相比互斥锁，会快一点，开销也小一点

一般加锁的过程，包含两个步骤：

第一步，查看锁的状态，如果锁是空闲的，则执行第二步；
第二步，将锁设置为当前线程持有；

CAS 函数就把这两个步骤合并成一条硬件级指令，形成原子指令，这样就保证了这两个步骤是不可分割的，要么一次性执行完两个步骤，要么两个步骤都不执行。

比如，设锁为变量 lock，整数 0 表示锁是空闲状态，整数 pid 表示线程 ID，那么 CAS(lock, 0, pid) 就表示自旋锁的加锁操作，CAS(lock, pid, 0) 则表示解锁操作。

使用自旋锁的时候，当发生多线程竞争锁的情况，加锁失败的线程会「忙等待」，直到它拿到锁。这里的「忙等待」可以用 while 循环等待实现，不过最好是使用 CPU 提供的 PAUSE 指令来实现「忙等待」，因为可以减少循环等待时的耗电量。

自旋锁是最比较简单的一种锁，一直自旋，利用 CPU 周期，直到锁可用。需要注意，在单核 CPU 上，需要抢占式的调度器（即不断通过时钟中断一个线程，运行其他线程）。否则，自旋锁在单 CPU 上无法使用，因为一个自旋的线程永远不会放弃 CPU。

自旋锁开销少，在多核系统下一般不会主动产生线程切换，适合异步、协程等在用户态切换请求的编程方式，但如果被锁住的代码执行时间过长，自旋的线程会长时间占用 CPU 资源，所以自旋的时间和被锁住的代码执行的时间是成「正比」的关系，我们需要清楚的知道这一点。

自旋锁与互斥锁使用层面比较相似，但实现层面上完全不同：当加锁失败时，互斥锁用「线程切换」来应对，自旋锁则用「忙等待」来应对。

读写锁

读写锁由【读锁】和【写锁】组成，只读取共享资源1用【读锁】加锁，如果要修改共享资源则用【写锁】加锁。

读写锁的工作原理是：

当【写锁】没有被线程占用时，【读锁】可以多线程并发持有

当【写锁】被线程占用时，读线程的获取读锁的操作会被阻塞，其他写线程的获取写锁的操作也会被阻塞

乐观锁和悲观锁

悲观锁做事比较悲观，它认为多线程同时修改共享资源的概率比较高，于是很容易出现冲突，所以访问共享资源前，先要上锁。

那相反的，如果多线程同时修改共享资源的概率比较低，就可以采用乐观锁。

乐观锁做事比较乐观，它假定冲突的概率很低，它的工作方式是：先修改完共享资源，再验证这段时间内有没有发生冲突，如果没有其他线程在修改资源，那么操作完成，如果发现有其他线程已经修改过这个资源，就放弃本次操作。

死锁

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

1）死锁产生的原因（必要条件）

理论上认为死锁产生有以下四个必要条件，缺一不可：

互斥条件：进程对所获得的资源具有排他性，若有其他进程请求该资源，请求进程只能等待。
不剥夺条件：进程在所获得的资源未释放前，不能被其他进程强行夺走，只能自己释放。
请求和保持条件：进程当前所拥有的资源在进程请求其他新资源时，由该进程继续占有。
循环等待条件：存在一种进程资源循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。

产生死锁的原因主要是：

系统资源不足；
进程运行推进的顺序不合适；
资源分配不当；

死锁演示：

#include <iostream>
#include <vector>
#include <list>
#include <thread>
#include <mutex>  //引入互斥量头文件
using namespace std;

class A {
public:
	//插入消息，模拟消息不断产生
	void insertMsg() {
		for (int i = 0; i < 100; i++) {
			cout << "插入一条消息:" << i << endl;
			my_mutex1.lock(); //语句1
			my_mutex2.lock(); //语句2
			Msg.push_back(i);
			my_mutex2.unlock();
			my_mutex1.unlock();
		}
	}
	//读取消息
	void readMsg() {
		int MsgCom;
		for (int i = 0; i < 100; i++) {
			MsgCom = MsgLULProc(i);
			if (MsgLULProc(MsgCom)) {
				//读出消息了
				cout << "消息已读出" << MsgCom << endl;
			}
			else {
				//消息暂时为空
				cout << "消息为空" << endl;
			}
		}
	}
	//加解锁代码
	bool MsgLULProc(int &command) {
		int curMsg;
		my_mutex2.lock();   //语句3
		my_mutex1.lock();   //语句4
		if (!Msg.empty()) {
			//读取消息，读完删除
			command = Msg.front();
			Msg.pop_front();
			
			my_mutex1.unlock();
			my_mutex2.unlock();
			return true;
		}
		my_mutex1.unlock();
		my_mutex2.unlock();
		return false;
	}
private:
	std::list<int> Msg;  //消息变量
	std::mutex my_mutex1; //互斥量对象1
	std::mutex my_mutex2; //互斥量对象2
};

int main() {
	A a;
	//创建一个插入消息线程
	std::thread insertTd(&A::insertMsg, &a); //这里要传入引用保证是同一个对象
	//创建一个读取消息线程
	std::thread readTd(&A::readMsg, &a); //这里要传入引用保证是同一个对象
	insertTd.join();
	readTd.join();
	return 0;
}

语句1和语句2表示线程A先锁资源1，再锁资源2，语句3和语句4表示线程B先锁资源2再锁资源1，具备死锁产生的条件。

**死锁的解决方案：**保证上锁的顺序一致

2）处理方式

主要有以下四种方法：

鸵鸟策略
死锁检测与死锁恢复：检测是指系统设有专门的机构，当死锁发生时，该机构能够检测死锁的发生，并精确地确定与死锁有关的进程和资源。恢复是将进程从死锁状态下解脱出来
死锁预防：采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间上都不满足。
死锁避免：系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生

3）鸵鸟策略

假装无事发生。因为解决死锁问题的代价很高，因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。当发生死锁时不会对用户造成多大影响，或发生死锁的概率很低，可以采用鸵鸟策略。大多数操作系统，包括 Unix，Linux 和 Windows，处理死锁问题的办法仅仅是忽略它。

4）死锁检测

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

每种类型一个资源的死锁检测
img
上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。
图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
每种类型多个资源的死锁检测
image-20220829114251683
上图中，有三个进程四个资源，每个数据代表的含义如下：
- E 向量：资源总量
- A 向量：资源剩余量
- C 矩阵：每个进程所拥有的资源数量，每一行都代表一个进程拥有资源的数量
- R 矩阵：每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足，只有进程 P3 可以，让 P3 执行，之后释放 P3 拥有的资源，此时 A = (2 2 2 0)。P2 可以执行，执行后释放 P2 拥有的资源，A = (4 2 2 1) 。P1 也可以执行。所有进程都可以顺利执行，没有死锁。
算法总结如下：
每个进程最开始时都不被标记，执行过程有可能被标记。当算法结束时，任何没有被标记的进程都是死锁进程。
- 寻找一个没有标记的进程 Pi，它所请求的资源小于等于 A。
- 如果找到了这样一个进程，那么将 C 矩阵的第 i 行向量加到 A 中，标记该进程，并转回 1。
- 如果没有这样一个进程，算法终止。

5）死锁恢复

利用抢占恢复：死锁发生的必要条件，其中一个就是不可抢占。如果允许抢占，那么就可以破坏死锁条件。
利用回滚恢复：周期性对进程进行检查点检查，一旦发现了死锁，就回滚到一个较早的检查点上。
通过杀死进程恢复：杀死一个进程可以释放它占有的资源，如果仍然不行就继续杀死其他进程直到打破死锁。

6）死锁预防

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

破坏互斥条件：尽量使得资源不被某个进程独占。例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
破坏请求和保持条件：一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
破坏不剥夺条件：允许抢占资源
破坏循环请求等待：一种方法是对资源进行编号，进程在任何时候都可以请求资源，但是所有的请求必须按照资源编号的顺序（升序）提出。

7）死锁避免

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

安全状态
img
图 a 的第二列 Has 表示已拥有的资源数，第三列 Max 表示总共需要的资源数，Free 表示还有可以使用的资源数。从图 a 开始出发，先让 B 拥有所需的所有资源（图 b），运行结束后释放 B，此时 Free 变为 5（图 c）；接着以同样的方式运行 C 和 A，使得所有进程都能成功运行，因此可以称图 a 所示的状态时安全的。
定义：如果没有死锁发生，并且即使所有进程突然请求对资源的最大需求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。
安全状态的检测与死锁的检测类似，因为安全状态必须要求不能发生死锁。下面的银行家算法与死锁检测算法非常类似，可以结合着做参考对比。
单个资源的银行家算法
一个小城镇的银行家，他向一群客户分别承诺了一定的贷款额度，算法要做的是判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求；否则予以分配。
img
上图 c 为不安全状态，因此算法会拒绝之前的请求，从而避免进入图 c 中的状态。
多个资源的银行家算法
img
图中有五个进程，四个资源。左边的图表示已经分配的资源，右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示：总资源、已分配资源以及可用资源，注意这三个为向量，而不是具体数值，例如 A=(1020)，表示 4 个资源分别还剩下 1/0/2/0。
检查一个状态是否安全的算法如下：
- 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行，那么系统将会发生死锁，状态是不安全的。
- 假若找到这样一行，将该进程标记为终止，并将其已分配资源加到 A 中。
- 重复以上两步，直到所有进程都标记为终止，则状态时安全的。
如果一个状态不是安全的，需要拒绝进入这个状态。

Note：饥饿的概念，其实与死锁和活锁差别比较大。考虑进程调度，基于优先级的调度中，如果总是有高优先级的进程就绪，那么一个低优先级的进程可能长时间无法上CPU运行。这就是饥饿现象，可以考虑通过动态优先级机制，可以动态提高长时间得不到运行的进程的优先级，从而使它可以运行。

**饥饿：**饥饿是由于资源分配策略不公引起的，当进程或线程无法访问它所需要的资源而不能继续执行时，就会发生饥饿现象。

内存管理

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

**快表TLB：**是一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

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

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

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

在执行malloc申请内存的时候，操作系统是怎么做的？

进程分配内存的两种方式--brk() 和mmap()（不设计共享内存）_鱼思故渊的博客-CSDN博客

从操作系统层面上看，malloc是通过两个系统调用来实现的： brk和mmap

brk是将进程数据段(.data)的最高地址指针向高处移动，这一步可以扩大进程在运行时的堆大小
mmap是在进程的虚拟地址空间中寻找一块空闲的虚拟内存，这一步可以获得一块可以操作的堆内存。

通常，分配的内存小于128k时，使用brk调用来获得虚拟内存，大于128k时就使用mmap来获得虚拟内存。

进程先通过这两个系统调用获取或者扩大进程的虚拟内存，获得相应的虚拟地址，在访问这些虚拟地址的时候，通过缺页中断，让内核分配相应的物理内存，这样内存分配才算完成。

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

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

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

内存交换和覆盖有什么区别？

交换技术主要是在不同进程（或作业）之间进行，而覆盖则用于同一程序或进程中。

**内存交换：**内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存(进程在内存与磁盘间动态调度)。**内存交换的时机：**许多进程运行且内存紧张时进行，系统负荷降低就停止，如频繁出现缺页，

**内存覆盖：**由于程序运行时并非任何时候都要访问程序及数据的各个部分，因此可以把用户空间分成为一个固定区和若干个覆盖区。将经常活跃的部分放在固定区，其余部分按照调用关系分段，首先将那些即将要访问的段放入覆盖区，其他段放在外存中，在需要调用前，系统将其调入覆盖区，替换覆盖区中原有的段。**特点：**打破了必须将一个进程的全部信息装入内存后才能运行的限制，但当同时运行程序的代码量大于主存时仍不能运行。

动态分区分配算法有哪些？

1)首次适应算法

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

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

2）最佳适应算法

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

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

3）最坏适应算法

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

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

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

4）临近适应算法

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

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

总结：

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

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

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

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

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

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

内存管理技术

简单分为连续分配管理方式和非连续分配管理方式这两种。连续分配管理方式是指为一个用户程序分配一个连续的内存空间，常见的如 块式管理 。同样地，非连续分配管理方式允许一个程序使用的内存分布在离散或者说不相邻的内存中，常见的如页式管理 、段式管理、段页式管理。

连续分配方式

单一连续分配：是指主存中只有一个用户作业，把程序装入主存之后，占据全部存储空间和资源。
分区分配
- 固定式分区：将内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。
- 可变式分区：在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。存在以上几种动态分区的分配策略。
- 可重定位分区：紧凑技术

离散分配方式

分页存储

操作系统学习笔记（四）內存分页管理方式 | Origin of Ray

1）页面和页面大小

进程中的块称为页（Page），内存中的块称为页框（Page Frame，或者页帧）。外存也以同样的单位进行划分，直接称为块（Block）。进程在执行时需要申请主存空间，即要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

为了方便进行地址转换，页面大小应该是2的整数幂。

2）页表

为了方便在内存中找到每个进程中每个页面对应的物理块，系统为每个进程建立一张页表，它记录页面在内存中对应的物理块号，页表一般保存在内存中。

页表是由页表项组成的，第一部分是页号，页表项第二部分是该页号对应的物理地址块号。

3）逻辑地址转换为物理地址的基本过程：

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

可以借助进程的页表将逻辑地址转换为物理地址。

通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M。进程未执行时，页表的始址和页表长度放在进程控制块(PCB) 中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。

注意:页面大小是2的整数幂设页面大小为L，逻辑地址A到物理地址E的变换过程如下:

设页面大小为L，逻辑地址A到物理地址E的过程如下：

计算页号P = A / L，和页内偏移量W = A % L
比较页号P和页表长度M的关系，如果P >= M，则产生越界中断，否则继续执行
页表中页号P对应的页表项地址 = F + P * 页表项长度，然后取出该页表项的内容b，即物理块号。（要注意区分页表长度和页表项长度，页表长度指的是一共有多少页，页表项长度指的是页地址占多大空间，也就是物理块号的地址长度）
E = b * L + W

页式管理只需要给出一个整数就可以确定对应物理地址，因为页面大小L是确定的，所以页式管理的地址空间是一维的。

总结：

把主存分为大小相等且固定的一页一页的形式，页较小，相比于块式管理的划分粒度更小，提高了内存利用率，减少了碎片。页式管理通过页表对应逻辑地址和物理地址。

分页存储会产生内存碎片，不会产生外存碎片；

分段存储

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

下图为一个编译器在编译过程中建立的多个表，有 4 个表是动态增长的，如果使用分页系统的一维地址空间，动态增长的特点会导致覆盖问题的出现。 分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

总结：

页式管理虽然提高了内存利用率，但是页式管理其中的页并无任何实际意义。段式管理把主存分为一段段的，段是有实际意义的，每个段定义了一组逻辑信息，例如,有主程序段 MAIN、子程序段 X、数据段 D 及栈段 S 等。段式管理通过段表对应逻辑地址和物理地址。

分段存储不会产生内存碎片，会产生外存碎片。

**为什么分段式存储管理有外部碎片而无内部碎片？为什么固定分区分配有内部碎片而不会有外部碎片？**分段式分配是按需分配，而固定式分配是固定分配的方式。

段页式存储

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

总结：

段页式管理机制结合了段式管理和页式管理的优点。简单来说段页式管理机制就是把主存先分成若干段，每个段又分成若干页，也就是说 段页式管理机制 中段与段之间以及段的内部的都是离散的。需要访问三次内存

简单来说：页是物理单位，段是逻辑单位。分页可以有效提高内存利用率，分段可以更好满足用户需求。

内部碎片与外部碎片

内碎片：分配给某些进程的内存区域中有些部分没用上，常见于固定分配方式

内存总量相同，100M

固定分配，将100M分割成10块，每块10M，一个程序需要45M，那么需要分配5块，第五块只用了5M，剩下的5M就是内部碎片；
分段式分配，按需分配，一个程序需要45M，就给分片45MB，剩下的55M供其它程序使用，不存在内部碎片。

外碎片：内存中某些空闲区因为比较小，而难以利用上，一般出现在内存动态分配方式中

分段式分配：内存总量相同，100M，比如，内存分配依次5M，15M，50M，25M，程序运行一段时间之后，5M，15M的程序运行完毕，释放内存，其他程序还在运行，再次分配一个10M的内存供其它程序使用，只能从头开始分片，这样，就会存在10M+5M的外部碎片

如何消除碎片文件

对于外部碎片，通过紧凑技术消除，就是操作系统不时地对进程进行移动和整理。但是这需要动态重定位寄存器地支持，且相对费时。

解决外部内存碎片的问题就是内存交换。

可以把程序占用的内存写到硬盘上，然后再从硬盘上读回来到内存里。不过再读回的时候，我们不能装载回原来的位置，这样就能空缺出连续的空间，于是新的程序就可以装载进来。

回收内存时要尽可能地将相邻的空闲空间合并。

交换空间与虚拟内存的关系

虚拟内存 = 物理内存 + 交换空间

使用磁盘来作为物理内存的扩展，这样可用的内存就会增加，其中被指定的磁盘空间即为交换空间，扩展后的总内存大小即为虚拟内存大小。

交换空间对应着虚存中的用来临时存储物理内存中内容的磁盘空间。当系统的物理内存不够时，我们才使用交换空间。CPU会将暂时不用的数据内容存到交换空间内，等到需要用到时，会再将其加载进内存中。

读写硬盘的速度要慢于内存读写速度数千倍。

内存交换中，被换出到进程保存在哪里

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

在发生内存交换时，有些进程是被优先考虑的？

可优先换出阻塞进程;可换出优先级低的进程;为了防止优先级低的进程在被调入内存后很快又被换出，有的系统还会考虑进程在内存的驻留时间… (注意: PCB 会常驻内存，不会被换出外存)

抖动（颠簸现象）是什么

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

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低资源的利用率。

块表和多级页表

页表管理机制中有两个很重要的概念：快表和多级页表，这两个东西分别解决了页表管理中很重要的两个问题。

虚拟地址到物理地址的转换要快。
解决虚拟地址空间大，页表也会很大的问题。

快表

为了提高虚拟地址到物理地址的转换速度，操作系统在 页表方案 基础之上引入了快表来加速虚拟地址到物理地址的转换。我们可以把快表理解为一种特殊的高速缓冲存储器（Cache），其中的内容是页表的一部分或者全部内容。作为页表的 Cache，它的作用与页表相似，但是提高了访问速率。由于采用页表做地址转换，读写内存数据时 CPU 要访问两次主存。有了快表，有时只要访问一次高速缓冲存储器，一次主存，这样可加速查找并提高指令执行速度。

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

根据虚拟地址中的页号查快表；
如果该页在快表中，直接从快表中读取相应的物理地址；
如果该页不在快表中，就访问内存中的页表，再从页表中得到物理地址，同时将页表中的该映射表项添加到快表中；
当快表填满后，又要登记新页时，就按照一定的淘汰策略淘汰掉快表中的一个页。

看完了之后你会发现快表和我们平时经常在我们开发的系统使用的缓存（比如 Redis）很像，的确是这样的，操作系统中的很多思想、很多经典的算法，你都可以在我们日常开发使用的各种工具或者框架中找到它们的影子

多级页表：

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

多级页表属于时间换空间的典型场景。

为了提高内存的空间性能，提出了多级页表的概念；但是提到空间性能是以浪费时间性能为基础的，因此为了补充损失的时间性能，提出了快表（即 TLB）的概念。不论是快表还是多级页表实际上都利用到了程序的局部性原理，局部性原理在后面的虚拟内存这部分会介绍到。

分页机制和分段机制的共同点和区别

共同点
- 分页机制和分段机制都是为了提高内存利用率，减少内存碎片。
- 页和段都是离散存储的，所以两者都是离散分配内存的方式。但是，每个页和段中的内存是连续的。
区别
- 页的大小是固定的，由操作系统决定；而段的大小不固定，取决于我们当前运行的程序。
- 分页仅仅是为了满足操作系统内存管理的需求，而段是逻辑信息的单位，在程序中可以体现为代码段，数据段，能够更好满足用户的需要。

其它说法：

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

逻辑（虚拟）地址和物理地址

我们编程一般只有可能和逻辑地址打交道，比如在 C 语言中，指针里面存储的数值就可以理解成为内存里的一个地址，这个地址也就是我们说的逻辑地址，逻辑地址由操作系统决定。物理地址指的是真实物理内存中地址，更具体一点来说就是内存地址寄存器中的地址。物理地址是内存单元真正的地址。

CPU寻址，为什么需要虚拟地址

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

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

先从没有虚拟地址空间的时候说起吧！没有虚拟地址空间的时候，程序直接访问和操作的都是物理内存 。但是这样有什么问题呢？

用户程序可以访问任意内存，寻址内存的每个字节，这样就很容易（有意或者无意）破坏操作系统，造成操作系统崩溃。
想要同时运行多个程序特别困难，比如你想同时运行一个微信和一个 QQ 音乐都不行。为什么呢？举个简单的例子：微信在运行的时候给内存地址 1xxx 赋值后，QQ 音乐也同样给内存地址 1xxx 赋值，那么 QQ 音乐对内存的赋值就会覆盖微信之前所赋的值，这就造成了微信这个程序就会崩溃。

总结来说：如果直接把物理地址暴露出来的话会带来严重问题，比如可能对操作系统造成伤害以及给同时运行多个程序造成困难。

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

程序可以使用一系列相邻的虚拟地址来访问物理内存中不相邻的大内存缓冲区。
程序可以使用一系列虚拟地址来访问大于可用物理内存的内存缓冲区。当物理内存的供应量变小时，内存管理器会将物理内存页（通常大小为 4 KB）保存到磁盘文件。数据或代码页会根据需要在物理内存与磁盘之间移动。
不同进程使用的虚拟地址彼此隔离。一个进程中的代码无法更改正在由另一进程或操作系统使用的物理内存。

虚拟内存

什么是虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，让程序可以拥有超过系统物理内存大小的可用内存空间。

为了更好的管理内存，操作系统将内存抽象成地址空间，虚拟内存为每个进程提供了一个一致的、私有的地址空间，它让每个进程产生了一种自己在独享主存的错觉（每个进程拥有一片连续完整的内存空间）。

每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。说明虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。

局部性原理

局部性原理是虚拟内存技术的基础，正是因为程序运行具有局部性原理，才可以只装入部分程序到内存就开始运行。

局部性原理表现在以下两个方面：

时间局部性 ：如果程序中的某条指令一旦执行，不久以后该指令可能再次执行；如果某数据被访问过，不久以后该数据可能再次被访问。产生时间局部性的典型原因，是由于在程序中存在着大量的循环操作。
空间局部性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内，这是因为指令通常是顺序存放、顺序执行的，数据也一般是以向量、数组、表等形式簇聚存储的。

时间局部性是通过将近来使用的指令和数据保存到高速缓存存储器中，并使用高速缓存的层次结构实现。空间局部性通常是使用较大的高速缓存，并将预取机制集成到高速缓存控制逻辑中实现。虚拟内存技术实际上就是建立了 “内存一外存”的两级存储器的结构，利用局部性原理实现髙速缓存。

虚拟内存的实现技术

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

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

这里多说一下？很多人容易搞混请求分页与分页存储管理，两者有何不同呢？

请求分页存储管理建立在分页管理之上。他们的根本区别是是否将程序全部所需的全部地址空间都装入主存，这也是请求分页存储管理可以提供虚拟内存的原因，我们在上面已经分析过了。

它们之间的根本区别在于是否将一作业的全部地址空间同时装入主存。请求分页存储管理不要求将作业全部地址空间同时装入主存。基于这一点，请求分页存储管理可以提供虚存，而分页存储管理却不能提供虚存。

不管是上面那种实现方式，我们一般都需要：

一定容量的内存和外存：在载入程序的时候，只需要将程序的一部分装入内存，而将其他部分留在外存，然后程序就可以执行了；
缺页中断：如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统将相应的页面或段调入到内存，然后继续执行程序；
虚拟地址空间 ：逻辑地址到物理地址的变换。

内存页面置换算法

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

当CPU访问的页面不在物理内存时，就会产生一个缺页中断，请求操作系统将所缺页调入到物理内存，它与一般中断的主要区别在于：

缺页中断在指令执行期间产生和处理中断信号，而一般中断在一条指令执行完成后检查和处理中断信号。
缺页中断返回到该指令的开始重新执行该指令，而一般中断返回回到该指令的下一个指令执行。

缺页中断的处理流程：

在 CPU ⾥访问⼀条 Load M 指令，然后 CPU 会去找 M 所对应的⻚表项。
如果该⻚表项的状态位是「有效的」，那 CPU 就可以直接去访问物理内存了，如果状态位是「⽆效的」，则 CPU 则会发送缺⻚中断请求。
操作系统收到了缺⻚中断，则会执⾏缺⻚中断处理函数，先会查找该⻚⾯在磁盘中的⻚⾯的位置。
找到磁盘中对应的⻚⾯后，需要把该⻚⾯换⼊到物理内存中，但是在换⼊前，需要在物理内存中找空闲⻚，如果找到空闲⻚，就把⻚⾯换⼊到物理内存中。
⻚⾯从磁盘换⼊到物理内存完成后，则把⻚表项中的状态位修改为「有效的」。
最后，CPU 重新执⾏导致缺⻚异常的指令。

第4步中如果在物理内存中找不到空闲页呢？

找不到空闲页面，说明此时内存满了，需要页面置换算法选择一个物理页，如果该物理页有被修改过（脏页），则将它换出到磁盘，然后将该被置换出去的页表项的状态改为「无效的」，最后把正在访问的页面装入到这个物理页中。

页表项的字段：

状态位：用于表示该页是否有效，即是否在物理内存中，供程序访问时参考。
访问字段：用于记录该页再一段时间被访问的次数，供页面置换算法选择页面时参考。
修改位：表示该页在调用内存后是否有被修改过，由于内存中的每一页都在磁盘上保留一份副本，因此，如果没有修改，在置换该页时就不需要将该页写回到磁盘上，以减少系统开销；如果已经被修改，则将该页重写到磁盘上，以保证磁盘中所保留的始终时最新的副本。
硬盘地址：用于指出该页在硬盘上的地址，通常是物理块号，供调入该页时使用。

管理虚拟内存的整个流程：

页面置换算法的功能：当出现缺页异常，需要调入新页面而内存已满时，选择被置换的物理页面，也就是选择一个物理页面换出到磁盘，然后把需要访问的页面换入到物理页。

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

最佳页面置换算法OPT
先进先出置换算法FIFO
最近最久未使用置换算法LRU
时钟页面置换算法Lock
最不常用置换算法LFU

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）先进先出

基本思路：选择换出的页面是最先进入的页面。

实现方法:把调入内存的页面根据调入的先后顺序排成一个队列，需要换出页面时选择队头页面队列的最大长度取决于系统为进程分配了多少个内存块。

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

在这个请求的页面序列中，缺页共发生了10次，页面置换共发生了7次，和最佳置换算法比较起来，性能明显差了很多。

Belady异常—当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

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

3）最近最久未使用LRU

基本思想：发生缺页时，将最长时间没有被访问的页面换出。该算法假设已经很久没有使用的页面可能在未来较长的一段时间内仍然不被使用。

OPT算法是通过未来的使用情况推测要淘汰的页面，而LRU通过历史的使用情况推测要淘汰的页面。

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

因为每次访问内存时都需要更新链表，在链表中找到一个页面，删除它，然后将它移动到表头是一个非常耗时的操作，因此这种方式实现的 LRU 代价很高。

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

4）时钟页面置换算法

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

时钟页面置换算法：既能优化置换的次数，也能方便实现，它跟LRU近似，又是对FIFO的一种改进。

该算法的思路是，把所有的页面保存在一个类似钟面的环形链表中，一个表针指向最老的页面。

当发生缺页中断时，算法首先检查表针指向的页面：

如果它的访问位位是 0 就淘汰该⻚⾯，并把新的⻚⾯插⼊这个位置，然后把表针前移⼀个位置；
如果访问位是 1 就清除访问位，并把表针前移⼀个位置，重复这个过程直到找到了⼀个访问位为 0 的⻚⾯为⽌。

工作流程：

5）最不常用算法

最不常用LFU算法：当发生缺页中断时，选择访问次数最少的那个页面进行淘汰。

实现方式是，对每个页面设置一个访问计数器，每当一个页面被访问时，该页面的访问计数器就累加1。在发生缺页中断时，淘汰计数器最小的哪个页面。

虽然看起来简单，但是在操作系统实现的时候，需要考虑效率和硬件成本。

要增加一个计数器来实现，这个硬件成本比较高，另外如果要对这个计数器查找哪个页面访问次数最小，查找链表本身，如果链表长度很长，是非常耗时的。

但还有个问题，LFU 算法只考虑了频率问题，没考虑时间的问题，⽐如有些⻚⾯在过去时间⾥访问的频率很⾼，但是现在已经没有访问了，⽽当前频繁访问的⻚⾯由于没有这些⻚⾯访问的次数⾼，在发⽣缺⻚中断时，就会可能会误伤当前刚开始频繁访问，但访问次数还不⾼的⻚⾯。

那这个问题的解决的办法还是有的，可以定期减少访问的次数，⽐如当发⽣时间中断时，把过去时间访问的⻚⾯的访问次数除以 2，也就说，随着时间的流失，以前的⾼访问次数的⻚⾯会慢慢减少，相当于加⼤了被置换的概率。

总结

	算法规则	优缺点
OPT	优先淘汰最长时间内不会被访问的页面	缺页率最小，性能最好;但无法实现
FIFO	优先淘汰最先进入内存的页面	实现简单;但性能很差，可能出现Belady异常
LRU	优先淘汰最近最久没访问的页面	性能很好;但需要硬件支持，算法开销大
CLOCK (NRU)	循环扫描各页面第一轮淘汰访问位=0的，并将扫描过的页面访问位改为1。若第-轮没选中，则进行第二轮扫描。	实现简单，算法开销小;但未考虑页面是否被修改过。
改进型CLOCK (改进型NRU)	若用(访问位，修改位)的形式表述，则第一轮:淘汰(0,0) 第二轮:淘汰(O,1)，并将扫描过的页面访问位都置为0 第三轮:淘汰(O, 0) 第四轮:淘汰(0, 1)	算法开销较小，性能也不错

文件系统

设备管理

磁盘结构

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

磁盘调度算法

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

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

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短，一般是通过优化磁盘的访问请求顺序做到的。

假设有个请求序列，每个数字代表磁道的位置：98，163，37，122，14，124，65，67,初始磁头当前的位置是在第53磁道。

常见的磁盘调度算法有：

1）先来先服务算法

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

比如，按照序列98，163，37，122，14，124，65，67，磁盘的写入顺序是从左到右，FCFS算法总共移动了640个磁道的距离。

优点：公平和简单。

缺点：如果大量进程竞争使用磁盘，请求访问的磁道可能会很分散，那么FCFS算法在性能上就会显得很差，因为未对寻道做任何优化，使平均寻道时间可能较长。

2）最短寻道时间优先算法

工作方式：优先调度从当前磁头所在磁道所需寻道时间最短的请求。

比如，按照序列98，163，37，122，14，124，65，67。根据距离磁头（53位置）最近的请求的算法，具体的请求会是下列从左到右顺序：65，67，37，14，98，122，124，183。

磁头移动的总距离是236磁道，相比FCFS算法性能提高不少。

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

产生饥饿的原因是磁头在一小块区域来回移动。

3）扫描算法（电梯算法-SCAN）

最短寻道时间优先算法会产生饥饿的原因在于：磁头可能会在一个小区域内来回移动。

为了防止这个问题，可以规定：磁头在一个方向上移动，访问所有未完成的请求，直到磁头到达该方向上最后的磁道，才调换方向，这就是扫描SCAN算法（电梯算法，比如电梯保持按一个方向移动，直到在那个方向上没有请求为止，然后改变方向）。

比如，磁头的初始位置是53，请求序列：98，163，37，122，14，124，65，67。假设SCAN算法先朝磁道号减少的方向移动，具体请求则是下列从左到右的顺序：37，14，0，65，67，98，122，124，183。

磁头先响应左边的请求，直到到达最左端（0磁道）后，才开始反向移动，响应右边的请求。

SCAN算法不会产生饥饿现象，但是中间部分的磁道相比其他部分响应的频率会比较多，即每个磁道的响应频率存在差异。

4）循环扫描算法

扫描算法存在每个磁道的响应频率存在差异，如果要优化这个问题，可以总是按相同的方向进行扫描，使每个磁道的响应频率基本一致。

循环扫描CSCAN算法规定：只有磁头朝某个特定方向移动时，才处理磁道访问请求，而返回时直接移动到最边缘的磁道，即复位磁头，这个过程很快，同时返回中途不处理任何请求。

该算法的特点：磁道只响应一个方向上的请求。

比如，磁头的初始位置是53，请求序列：98，163，37，122，14，124，65，67。假设CSCAN算法先朝磁道增加的方向移动，具体请求则是下列从左到右的顺序：65，67，98，122，124，183，199，0，14，37。

磁头先响应右边的请求，直到碰到了最右边的磁道199，就立即回到磁盘的开始处（磁道0），但返回的过程中不会响应任何请求，直到到达最开始的磁道后，才继续顺序响应右边的请求。

循环扫描算法相比扫描算法，对于各个位置的磁道响应频率相对比较平均。

5）LOOK与C-LOOK算法

CSCAN与CAN算法都是磁头移动到磁盘最始端或最末端才开始调换方向。

优化思路：磁头在移动到最远的请求位置，然后就反向移动。

针对SCAN算法的优化叫LOOK算法，工作方式：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中会响应请求。

磁头的初始位置是53，请求序列：98，163，37，122，14，124，65，67。假设SCAN算法先朝磁道号减少的方向移动，具体请求则是下列从左到右的顺序：37，14，65，67，98，122，124，183。

针对CSCAN算法的优化叫C-LOOK算法，工作方式：磁头在每个方向上仅仅移动到最远的请求位置，然后立即反向移动，而不需要移动到磁盘的最始端或最末端，反向移动的途中不会响应请求。

磁头的初始位置是53，请求序列：98，163，37，122，14，124，65，67。假设SCAN算法先朝磁道号增加的方向移动，具体请求则是下列从左到右的顺序：65，67，98，122，124，183，199，14，37。

其他

系统调用

系统调用是指操作系统向应用程序提供的操作和访问底层硬件资源的接口。用户空间发生请求，内核空间负责执行，系统调用作为中间层，是连接用户态和内核态的桥梁。

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

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

程序的编译过程？动态链接库与静态链接库

hello.c程序

#include <stdio.h>

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

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

gcc -o hello hello.c

过程：

源代码－－>预处理－－>编译－－>优化－－>汇编－－>链接-->可执行文件

预处理：处理以 # 开头的预处理命令；读取c源程序，对其中的伪指令（以#开头的指令）和特殊符号进行处理。包括宏定义替换、条件编译指令、头文件包含指令、特殊符号。预编译程序所完成的基本上是对源程序的“替代”工作。经过此种替代，生成一个没有宏定义、没有条件编译指令、没有特殊符号的输出文件。.i预处理后的c文件，.ii预处理后的C++文件。
编译：代码优化和生成汇编代码；通过词法分析和语法分析，在确认所有的指令都符合语法规则之后，将其翻译成等价的中间代码表示或汇编代码。.s文件
汇编：将汇编文件翻译成可重定位目标文件；把汇编语言代码翻译成目标机器指令的过程。对于被翻译系统处理的每一个C语言源程序，都将最终经过这一处理而得到相应的目标文件。目标文件中所存放的也就是与源程序等效的目标的机器语言代码。.o目标文件
链接：将可重定位目标文件和 printf.o 等单独预编译好的目标文件进行链接，得到最终的可执行目标文件。将有关的目标文件彼此相连接，也即将在一个文件中引用的符号同该符号在另外一个文件中的定义连接起来，使得所有的这些目标文件成为一个能够让操作系统装入执行的统一整体。

静态链接：

对于静态库，程序在链接阶段中，将引用的库和目标文件.o一起链接打包到可执行文件中，程序运行时不再需要静态库。

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

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

目标文件：

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

动态链接库：

静态库有以下两个问题：

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

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

动态库在程序编译时并不会被连接到目标代码中，而是在程序运行时才被载入。不同的应用程序如果调用相同的库，那么在内存里只需要有一份该共享库的实例。

它具有以下特点：

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

动态库的调用又分为显示和隐式两种方式：

隐式调用(静态加载)	显式调用（动态加载）
需要调用代码少	调用时指明动态库的名称和函数名称
调用起来和使用当前项目下的函数一样直接	自己加载和卸载（更合理，大项目都用显式）
makefile中链接命令需要加入参数-l命令指明包含的动态库头文件位置	更加灵活，必须加头文件dlfcn.h

隐式调用就是编译程序的时候，包含动态库的头文件，并且指明动态库的名字和位置。
显示调用就是在程序运行过程中dlopen动态库，然后通过dlsym获取动态库里函数的地址。（动态库的动态链接、打开、调用：dlopen、dlsym和dlclose)
区别
- 隐式调用需要调用者写的代码量少，调用起来和使用当前项目下的函数一样直接；而显式调用则要求程序员在调用时，指明要加载的动态库的名称和要调用的函数名称。
- 隐式调用由系统加载完成；显式调用由程序员在需要使用时自己加载，不再使用时，自己负责卸载。因此显式调用对内存的使用更加合理，大型项目中应使用显示调用。
- 当动态链接库中只提供函数接口，而该函数没有封装到类里面时，如果使用显式调用的方式，调用方甚至不需要包含动态链接库的头文件（需要调用的函数名是通过dlsym函数的参数指明的），而使用隐式调用时，则调用方不可避免要加上动态库中的头文件，g++编译时还需要要用参数-I指明包含的头文件的位置。需要注意的是，当动态链接库中的接口函数是作为成员函数封装在类里面时，即使使用显式调用的方式，调用方也必须包含动态库中的相应头文件。
- 显式调用更加灵活，可以模拟多态效果。

总结-静态链接和动态链接的区别：

静态链接实在编译链接时直接将需要的执行代码拷贝到调用处；
优点：程序在发布时不需要依赖库，可以独立执行；
缺点：程序体积会相对较大，而且如果静态库更新之后，所有可执行文件需要重新链接；
动态链接是在编译时不直接拷贝执行代码，⽽是通过记录⼀系列符号和参数，在程序运行或加载时将这些信息传递给操作系统，操作系统负责将需要的动态库加载到内存中，然后程序在运行到指定代码时，在共享执行内存中寻找已经加载的动态库可执行代码，实现运行时链接；
优点在于多个程序可以共享同⼀个动态库，节省资源；
缺点在于由于运行时加载，可能影响程序的前期执⾏性能

buffer缓冲和cache缓存区别

buffer和cache的区别-阿里云开发者社区

**buffer缓冲是为了提高内存和硬盘（或其他I/O设备）之间的数据交换的速度而设计的。**缓冲（buffers）是根据磁盘的读写设计的，把分散的写操作集中进行，减少磁盘碎片和硬盘的反复寻道，从而提高系统性能。
**cache（缓存）是为了提高cpu和内存之间的数据交换速度而设计的，**也就是平常见到的一级缓存、二级缓存、三级缓存。cpu在执行程序所用的指令和读数据都是针对内存的，也就是从内存中取得的。由于内存读写速度慢，为了提高cpu和内存之间数据交换的速度，在cpu和内存之间增加了cache，它的速度比内存快，但是造价高。cache是根据程序的局部性原理而设计的，就是cpu执行的指令和访问的数据往往在集中的某一块，所以把这块内容放入cache后，cpu就不用在访问内存了，这就提高了访问速度。若cache中没有cpu所需要的内容，还是要访问内存的。

总结：

数据写入内存空间，这段空间就是缓冲区buffer，写入缓冲区
把数据从内存空间读出，这段空间就是缓存器cache，读取缓存区

创建时，需要完成的主要工作是给定一个指定进程标识符，形成该进程的PCB并放入系统队列中，调用者必须提供形成PCB的有关参数，以便在创建时填入，对于较复杂的PCB结构，还需要提供资源清单等。
在撤销一个进程时，需完成的主要工作是必须把该进程的PCB从系统队列中溢出，释放并归还所有系统资源，同时审查该进程是否有子进程，若有则一起撤销。

参考资料

计算机操作系统 - 概述 | CS-Notes