Operating System

操作系统

Linux

用户态到内核态的切换

  • 系统调用

这是用户态进程主动要求切换到内核态的一种方式，**用户态进程通过系统调用申请使用操作系统提供的服务程序完成工作。**比如前例中fork()实际上就是执行了一个创建新进程的系统调用。

用户程序通常调用库函数，由库函数再调用系统调用，因此有的库函数会使用户程序进入内核态（只要库函数中某处调用了系统调用），有的则不会。

  • 异常

当CPU在执行运行在用户态下的程序时，发生了某些事先不可知的异常，这时会触发由当前运行进程切换到处理此异常的内核相关程序中，也就转到了内核态，比如缺页异常。

  • 外围设备的中断

当外围设备完成用户请求的操作后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条即将要执行的指令转而去执行与中断信号对应的处理程序，

如果先前执行的指令是用户态下的程序，那么这个转换的过程自然也就发生了由用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等。

用户态和内核态区别

两者最大的区别就是特权级不同。用户态拥有最低的特权级，内核态拥有较高的特权级。运行在用户态的程序不能直接访问操作系统内核数据结构和程序。内核态和用户态之间的转换方式主要包括：系统调用，异常和中断。

为什么要分用户态和内核态

为了安全性。在cpu的一些指令中，有的指令如果用错，将会导致整个系统崩溃。 分了内核态和用户态后，当用户需要操作这些指令时候，内核为其提供了API，可 以通过系统调用陷入内核，让内核去执行这些操作。

系统调用

系统调用是操作系统提供给用户（应用程序）的一组接口，每个系统调用都有一个对应的系统调用函数来完成相应的工作。用户通过这个接口向操作系统申请服务，如访问硬件，管理进程等等。但是因为用户程序运行在用户空间，而系统调用运行在内核空间，因此用户程序不能直接调用系统调用函数，我们经常看到的比如fork、open、write 等等函数实际上并不是真正的系统调用函数，他们都只是c库，在这些函数里将执行一个软中断 swi 指令，产生一个软中断，使CPU 陷入内核态，接着在内核中进行一系列的判断，判断出是哪个系统调用，再转到真正的系统调用函数，完成相应的功能。

系统调用与普通函数库调用区别

函数库的API是相同的，系统调用的API取决于操作系统

函数库调用的是函数库里面的一段程序，系统调用调用的是内核的服务

函数库调用在用户态，系统调用在内核态

函数库调用不用上下文切换，系统调用需要切换到内核态

进程 & 线程

父子进程

创建进程：pid_t fork(void)

返回值：创建失败返回-1，创建成功返回0给创建的子进程，返回子进程号给父进程

子进程将父进程地址空间拷贝一份（出于内存管理原因可能一开始不会拷贝成两份），父子进程从fork的下一行开始执行

结束进程：exit()

等待子进程：pit_t wait(int *status_ptr) / pid_t waitpid(pid_t pid, int *status_ptr, int options)，等待直到子进程状态码可用，然后将子进程状态码拷贝到 *status_ptr

返回值：不成功时返回-1，子进程状态码可用时返回子进程号

执行程序：execve(const char *filename, const char *arg0, char *const env[]…)

不会再创建新进程，pid不变，机器码，数据，堆，栈替换为新程序的数据

返回值：不成功返回-1，成功不返回值（代码已被替换）

僵尸进程，孤儿进程

僵尸进程：子进程退出但父进程没有wait获取其状态信息，子进程进程描述符仍保存在系统中；会占用进程号最终导致系统没有可用的进程号而不能产生新的进程；kill掉父进程后变为孤儿进程以解决问题

孤儿进程：父进程退出但子进程还在运行，孤儿进程会被init进程收养；init进程会wait孤儿进程故危害不大

守护进程

守护进程：Linux Daemon（守护进程）是运行在后台的一种特殊进程。它独立于控制终端并且周期性地执行某种任务或等待处理某些发生的事件。它不需要用户输入就能运行而且提供某种服务，不是对整个系统就是对某个用户程序提供服务。Linux系统的大多数服务器就是通过守护进程实现的。常见的守护进程包括系统日志进程syslogd、 web服务器httpd、邮件服务器sendmail和数据库服务器mysqld等。

守护进程一般在系统启动时开始运行，除非强行终止，否则直到系统关机都保持运行。守护进程经常以超级用户（root）权限运行，因为它们要使用特殊的端口（1-1024）或访问某些特殊的资源。

一个守护进程的父进程是init进程，因为它真正的父进程在fork出子进程后就先于子进程exit退出了，所以它是一个由init继承的孤儿进程

进程线程区别

调度：线程作为调度和分配的基本单位，进程作为资源分配的独立单元

并发性：不仅进程之间可以并发执行，同一个进程的多个线程之间也可并发执行

拥有资源：进程是拥有资源的一个独立单位，线程不拥有系统资源，但可以访问隶属于进程的资源.

系统开销：在创建或撤消进程时，由于系统都要为之分配和回收资源，导致系统的开销明显大于创建或撤消线程时的开销。

切换：进程切换与线程切换的一个最主要区别就在于进程切换涉及到虚拟地址空间的切换而线程切换则不会（所以进程切换慢）

上下文切换

  • 系统调用（内核态用户态切换）

从用户态到内核态的转变，需要通过系统调用来完成。比如，当我们查看文件内容时，就需要多次系统调用来完成：首先调用 open() 打开文件，然后调用 read() 读取文件内容，并调用 write() 将内容写到标准输出，最后再调用 close() 关闭文件。

在这个过程中就发生了 CPU 上下文切换，整个过程是这样的： 1、保存 CPU 寄存器里原来用户态的指令位 2、为了执行内核态代码，CPU 寄存器需要更新为内核态指令的新位置。 3、跳转到内核态运行内核任务。 4、当系统调用结束后，CPU 寄存器需要恢复原来保存的用户态，然后再切换到用户空间，继续运行进程。

所以，一次系统调用的过程，其实是发生了两次 CPU 上下文切换。（用户态-内核态-用户态）

不过，需要注意的是，系统调用过程中，并不会涉及到虚拟内存等进程用户态的资源，也不会切换进程。这跟我们通常所说的进程上下文切换是不一样的：进程上下文切换，是指从一个进程切换到另一个进程运行；而系统调用过程中一直是同一个进程在运行。

所以，系统调用过程通常称为特权模式切换，而不是上下文切换。系统调用属于同进程内的 CPU 上下文切换。

  • 进程上下文切换

首先，进程是由内核来管理和调度的，进程的切换只能发生在内核态。所以，进程的上下文不仅包括了虚拟内存、栈、全局变量等用户空间的资源，还包括了内核堆栈、寄存器等内核空间的状态。

因此，进程的上下文切换就比系统调用时多了一步：在保存内核态资源（当前进程的内核状态和 CPU 寄存器）之前，需要先把该进程的用户态资源（虚拟内存、栈等）保存下来；而加载了下一进程的内核态后，还需要刷新进程的虚拟内存和用户栈。

  • 线程上下文切换

同一个进程的线程间切换时，因为虚拟内存是共享的，所以在切换时，虚拟内存这些资源就保持不动，只需要切换线程的私有数据、寄存器等不共享的数据

为什么进程切换慢

每个进程都有自己的虚拟地址空间，那么显然每个进程都有自己的页表，那么当进程切换后页表也要进行切换，页表切换后会导致TLB失效（TLB就是当前页表的缓存），cache失效导致命中率降低，那么虚拟地址转换为物理地址就会变慢，表现出来的就是程序运行会变慢，而线程切换不会导致TLB失效，因为线程无需切换地址空间，因此我们通常说线程切换比进程切换快，原因就在这里。

IPC

管道：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程（父子进程）之间使用，缓冲区有限

有名管道（FIFO）：有名管道也是半双工的通信方式，但是允许在没有亲缘关系的进程之间使用，管道是先进先出的通信方式，缓冲区有限

（管道的实质是一个内核缓冲区，进程以先进先出的方式从缓冲区存取数据：管道一端的进程顺序地将进程数据写入缓冲区，另一端的进程则顺序地读取数据，该缓冲区可以看做一个循环队列，读和写的位置都是自动增加的，一个数据只能被读一次，读出以后再缓冲区都不复存在了）

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

信号量：信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

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

共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问；效率最高，但没有提供同步机制，需要使用锁等其他机制进行同步。

套接字( socket ) ：套接字也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。

同一个进程内的线程会共享什么资源？

  • 该进程的地址空间
  • 全局变量
  • 堆空间

进程调度算法

  • 先来先服务（FCFS）：简单但效率低，适合CPU密集任务

优点是公平，实现简单；缺点是不利于短作业

  • 时间片轮转调度法（RR）：时间片短则开销大，时间片长则退化为先来先服务

优点是兼顾长短作业；缺点是平均等待时间较长，上下文切换较费时。适用于分时系统。

  • 最短作业优先（SJF）：平均等待时间最少，但作业时间长短只能靠由历史长度预测（指数平均）

  • 最短剩余时间（SRF）：最短进程优先的抢占机制版本，选择预期剩余时间最短的进程（即使是新加入的进程）

  • 优先级调度算法（Priority）：抢占/非抢占，导致饥饿（低优先级一直不被执行），通过衰老（随时间增大优先级）解决

  • 多级队列算法（Multilevel）：队列内调度（RR/FCFS） / 队列间调度（固定优先级/时间片）

什么时候用多线程什么时候用多进程？

对比维度 多进程 多线程 优势
数据共享、同步 数据共享复杂，需要用IPC；数据是分开的，同步简单 因为共享进程数据，数据共享简单，但也是因为这个原因导致同步复杂 各有优势
内存、CPU 占用内存多，切换复杂，CPU利用率低 占用内存少，切换简单，CPU利用率高 线程占优
创建销毁切换 创建销毁切换复杂，速度慢 创建销毁切换简单，速度很快 线程占优
可靠性 进程间不会互相影响 一个线程挂掉将导致整个进程挂掉 进程占优
分布式 适应于多核、多机分布式如果一台机器不够，扩展到多台机器比较简单 适应于多核分布式 进程占优

同步异步，阻塞非阻塞

同步按一定响应时间进行IO；异步响应时间无规则或不可预测

阻塞在IO执行时挂起进程（waiting）；非阻塞不挂起进程而是立即返回，IO执行多少返回多少

IO复用

I/O多路复用，I/O就是指的我们网络I/O，多路指多个TCP连接(或多个Channel)，复用指复用一个或少量进程。串起来理解就是很多个网络I/O复用一个或少量的进程来处理这些连接，让单个进程具有处理多个 I/O 事件的能力

Epoll的ET模式和LT模式

  • ET是边缘触发模式，在这种模式下，只有当描述符从未就绪变成就绪时，内核才会通过epoll进行通知。然后直到下一次变成就绪之前，不会再次重复通知。也就是说，如果一次就绪通知之后不对这个描述符进行IO操作导致它变成未就绪，内核也不会再次发送就绪通知。优点就是只通知一次，减少内核资源浪费，效率高。缺点就是不能保证数据的完整，有些数据来不及读可能就会无法取出。
  • LT是水平触发模式，在这个模式下，如果文件描述符IO就绪，内核就会进行通知，如果不对它进行IO操作，只要还有未操作的数据，内核都会一直进行通知。优点就是可以确保数据可以完整输出。缺点就是由于内核会一直通知，会不停从内核空间切换到用户空间，资源浪费严重。

并行&并发

并行：支持同时执行多于一个任务；并发：支持多于一个任务一起取得进展（不一定同时运行）

pthread

创建线程：int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(start_routine)(void *), voidd *arg)

thread：新创建的线程ID指向的内存单元，start_routine是线程开始执行的函数地址，arg是这个函数的参数

返回值：错误返回错误码，成功返回0

退出线程：void pthread_exit(void *retval)

main() 执行完时如果线程没执行完会继续执行

阻塞线程：int pthread_join(pthread_t thread, void **retval)

阻塞调用线程，直到指定的线程（参数thread）终止

互斥锁：pthread_mutex_t

上锁：

int pthread_mutex_lock(pthread_mutex *mutex)

上锁，如果已经被锁则阻塞线程

int pthread_mutex_trylock(pthread_mutex *mutex)

试图上锁，如果已经上锁则返回错误码

int pthread_mutex_unlock(pthread_mutex *mutex)

解锁，只能解锁自己上的锁；已经被解锁或被其它线程上锁时返回错误码

条件变量：pthread_cond_t

int pthread_cond_wait(pthread_cont_t *t, pthread_mutex_t *mutex)

阻塞调用线程直到条件变量被发信号

int pthread_cond_signal(pthread_cond_t *t)

给条件变量发信号从而唤醒另一个等待中的线程

int pthread_cond_broadcast(pthread_cond_t *t)

当多于一个线程在等待条件变量时使用

协程

协程，英文Coroutines，是一种基于线程之上，但又比线程更加轻量级的存在，这种由程序员自己写程序来管理的轻量级线程叫做『用户空间线程』，具有对内核来说不可见的特性。正如一个进程可以拥有多个线程一样，一个线程也可以拥有多个协程。

  1. 线程的切换由操作系统负责调度，协程由用户自己进行调度，因此减少了上下文切换，提高了效率。
  2. 线程的默认Stack大小是1M，而协程更轻量，接近1K。因此可以在相同的内存中开启更多的协程。
  3. 由于在同一个线程上，因此可以避免竞争关系而使用锁。
  4. 适用于被阻塞的，且需要大量并发的场景。但不适用于大量计算的多线程，遇到此种情况，更好实用线程去解决。

中断

中断是什么

早期的CPU处理外设的事件(比如接收键盘输入)，往往采用“轮询”的方式。即CPU像个查岗的一样轮番对外设顺序访问，比如它先看看键盘有没被按下，有的话就处理，没的话继续往下看鼠标有没有移动，再看看打印机……这种方式使CPU的执行效率很低，且CPU与外设不能同时工作（因为要等待CPU来“巡查”）。

中断模式时就是说CPU不主动访问这些设备，只管处理自己的任务。如果有设备要与CPU联系，或要CPU处理一些事情，它会给CPU发一个中断请求信号。这时CPU就会放下正在进行的工作而去处理这个外设的请求。处理完中断后，CPU返回去继续执行中断以前的工作。

中断类型

  • 硬件中断

硬件中断又称外部中断，主要分为两种：可屏蔽中断、非屏蔽中断。

可屏蔽中断：

常由计算机的外设或一些接口功能产生，如键盘、打印机、串行口等；这种类型的中断可以在CPU要处理其它紧急操作时，被软件屏蔽或忽略

典型的可屏蔽中断的例子是打印机中断，CPU对打印机中断请求的响应可以快一些，也可以慢一些，因为让打印机稍等待一会也是完全合理的。

非屏蔽中断：

由意外事件导致，如电源断电、内存校验错误等；对于这种类型的中断事件，无法通过软件进行屏蔽，CPU必须无条件响应

典型的非屏蔽中断的例子是电源断电，一旦出现此中断请求，必须立即无条件地响应，否则进行其他任何工作都是没有意义的。

  • 软件中断

软件中断又称内部中断，是指在程序中调用INTR中断指令引起的中断

中断过程

中断请求

中断请求是由中断源向CPU发出中断请求信号。外部设备发出中断请求信号要具备以下两个条件：

  1. 外部设备的工作已经告一段落。例如输入设备只有在启动后，将要输入的数据送到接口电路的数据寄存器（即准备好要输入的数据）之后，才可以向CPU发出中断请求。

  2. 系统允许该外设发出中断请求。如果系统不允许该外设发出中断请求，可以将这个外设的请求屏蔽。当这个外设中断请求被屏蔽，虽然这个外设准备工作已经完成，也不能发出中断请求。

中断响应、处理和返回

当满足了中断的条件后，CPU就会响应中断，转入中断程序处理。具体的工作过程如下：

  1. 关闭中断信号接收器

  2. 保存现场(context)

  3. 给出中断入口，转入相应的中断服务程序

  4. 处理完成，返回并恢复现场(context)

  5. 开启中断信号接收器

中断排队和中断判优

  1. 中断申请是随机的，有时会出现多个中断源同时提出中断申请。

  2. CPU每次只能响应一个中断源的请求。

  3. CPU不可能对所有中断请求一视同仁，它会根据各中断源工作性质的轻重缓急，预先安排一个优先级顺序。当多个中断源同时申请中断时，即按此优先级顺序进行排队，等候CPU处理。

为什么在中断过程中不能进行睡眠

运行在中断中的代码不能进行睡眠，或者阻塞！因为代码是运行在中断上下文中，并非进程上下文中，如果将中断进行睡眠的话，调度器无从得知下一个应该调度的进程，系统无法继续进行！

锁

死锁原因

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

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

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

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

死锁预防

破坏互斥条件：取决于资源本身

破坏请求条件：申请一个资源时不能占有其它资源

破坏不可剥夺条件：申请一个不能立即分配的资源时已占有的资源都可抢占

破坏环路等待条件：资源有序分配，系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反

死锁避免（银行家算法）

m：资源数量；n：进程数量

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]

  • 安全性算法：检测目前计算机的资源是不是足够这些进程完成任务

Work：长度为m的向量，初始等于Allocation，表示当前能提供的资源数量；当一个进程目前分配的资源有能力完成任务时，会将已经分配给此进程的资源Allocation_i加到work上（进程完成任务，不需要继续持有资源）

Finish：长度为n的向量，初始全为false，表示进程有没有完成任务；当进程有足够资源完成任务时变为true

进程如果有能力完成任务（Need_i<Work_i），则Finish_i变为true，并且Work=Work+Allocation_i

当没有有能力完成任务且未完成的进程时，检查是不是所有进程都完成了任务，如果是则系统处于安全状态

  • 资源请求算法

Request_i：进程i请求的资源数量

  1. 检查Request_i小于等于Need_i，否则出错（请求的太多了）
  2. 检查Request_i小于等于Available，否则必须等待（现在给不了你这么多，但是后面可能可以）
  3. 将Allocation的资源按Request_i的量分给进程i，如果产生的新状态是安全的，则进程i可以拿到其所需要资源，否则必须等待

安全性算法保证系统一定能找到一种调度方式保证死锁不产生；资源请求算法保证进程请求资源不会让系统进入不安全状态

解决死锁

  • 阻塞住占据资源的一个进程并剥夺它占有的资源，让它把资源先分给需要这个资源的进程
  • 直接kill一个

有互斥锁为什么还要条件变量？

条件变量是某个条件被满足时会发出信号告诉别的线程；互斥锁是保证同一时间只有一个线程拥有资源

假如我们没有“条件变量”这个概念，如果一个线程要等待某个“自定义的条件”满足而继续执行，而这个条件只能由另一个线程来满足，比如 T1不断给一个全局变量 x +1， T2检测到x 大于100时，将x 置0，如果我们没有条件变量只通过互斥锁实现

//thread 1:
while(true){
    pthread_mutex_lock(&mutex);
    iCount++;
    pthread_mutex_unlock(&mutex);
}

//thread 2:
while(true){
    pthread_mutex_lock(&mutex);
    if(iCount >= 100){
        iCount = 0;
    }
    pthread_mutex_unlock(&mutex);
}

此时就算 lock 空闲，thread2也需要不断重复<加锁，判断，解锁>这个流程，会给系统带来不必要的开销。有没有一种办法让 thread2先被 block，等条件满足的时候再唤醒 thread2？这样 thread2 就不用不断进行重复的加解锁操作了？这就要用到条件变量了

//thread1 :
while(true){
    pthread_mutex_lock(&mutex);
    iCount++;
    pthread_mutex_unlock(&mutex);

    pthread_mutex_lock(&mutex);
    if(iCount >= 100){
        pthread_cond_signal(&cond);
    }
    pthread_mutex_unlock(&mutex);
}

//thread2:
while(1){
    pthread_mutex_lock(&mutex);
    while(iCount < 100){
        pthread_cond_wait(&cond, &mutex);
    }
    printf("iCount >= 100\r\n");
    iCount = 0;
    pthread_mutex_unlock(&mutex);
}

为什么条件变量里还要传入一个互斥锁

还是上面那个例子，T2会在iCount小于100时等待条件变量唤醒，如何线程1里iCount大于100了，则T2被唤醒；但是如果此时T2没有在被唤醒的一瞬间锁住iCount这个变量的话，其它线程可以在很短的时间内再次将iCount变为小于100的值，这样T2就又会被锁住（没来得及跳出while循环），要想做到T2醒来这段时间iCount这个条件不再发生改变，就需要让条件变量和互斥锁绑定，条件变量进行唤醒的同时加互斥锁防止条件被再次改变，从而避免上面这种情况的发生

自旋锁与互斥锁

自旋锁无法拿到锁时不阻塞线程而是不停循环检测锁状态（耗CPU），线程不休眠所以不需条件变量，适合加锁时间短暂的情况下使用（耗费CPU资源不多，并且没有上下文切换损耗）

互斥锁无法拿到锁时阻塞线程，线程进入休眠，一般与条件变量一起使用以发出信号唤醒线程适合加锁时间较长情况下使用

独占锁与共享锁（读写锁）

独占锁概念

独占锁也叫排他锁，是指该锁一次只能被一个线程所持有。如果线程T对数据A加上排他锁后，则其他线程不能再对A加任何类型的锁。获得排它锁的线程即能读数据又能修改数据

共享锁概念

共享锁是指该锁可被多个线程所持有。如果线程T对数据A加上共享锁后，则其他线程只能对A再加共享锁，不能加排它锁。获得共享锁的线程只能读数据，不能修改数据。 独享锁与共享锁也是通过AQS来实现的，通过实现不同的方法，来实现独享或者共享。

悲观锁与乐观锁

乐观锁：乐观锁在操作数据时非常乐观，认为别人不会同时修改数据。因此乐观锁不会上锁，只是在执行更新的时候判断一下在此期间别人是否修改了数据：如果别人修改了数据则放弃操作，否则执行操作。

悲观锁：悲观锁在操作数据时比较悲观，认为别人会同时修改数据。因此操作数据时直接把数据锁住，直到操作完成后才会释放锁；上锁期间其他人不能修改数据。

CAS机制

CAS是英文单词Compare And Swap的缩写，翻译过来就是比较并替换。

CAS机制当中使用了3个基本操作数：内存地址V，旧的预期值A，要修改的新值B。

更新一个变量的时候，只有当变量的预期值A和内存地址V当中的实际值相同时，才会将内存地址V对应的值修改为B。如果不同，则回去重新执行整个操作（乐观锁）

递归锁

例如bar函数和foo函数都获取了同一个锁，并且bar函数会调用foo函数，那么如果这个锁不是可递归锁时，程序会发生死锁

可以通过设置pthread_mutex_recursive属性将互斥锁设置为可递归的

在系统不支持递归锁，而又必须要使用时,就需要自己构造一个递归锁。通常，递归锁是在非递归互斥锁加引用计数器来实现的。简单的说，在加锁前，先判断上一个加锁的线程和当前加锁的线程是否为同一个。如果是同一个线程，则仅仅引用计数器加1； 如果不是的话，则引用计数器设为1，则记录当前线程号，并加锁。

内存管理

堆栈区别

栈中分配局部变量、临时变量的内存空间，内存相对较少，所以开辟太多会导致栈溢出（例如使用递归的时候，递归层数太深或是没有递归终止的条件都可能导致栈溢出）；是一块连续的内存的区域；由系统自动分配，速度较快

堆区是向上增长的用于分配程序员申请的内存空间，如malloc和new出来的空间都是放在堆区，手动申请释放，没能及时释放可能会导致内存泄漏的问题；是不连续的内存区域，用链表来存储的空闲内存地址；是程序员分配的内存，一般速度比较慢，分配的空间大于需要的空间时有内存碎片

共享内存和虚拟内存

共享内存：进程在运行过程中，会加载许多操作系统的动态库，比如 libc.so、libld.so等。这些库对于每个进程而言都是公用的，它们在内存中实际只会加载一份，这部分称为共享内存。如上图中的A4和B3部分即为共享内存，实际都映射到同一块物理内存。

虚拟内存：由于成本的限制，物理内存往往无法做的很大，但是进程运行阶段所需申请的内存可能远远超过物理内存，并且系统不可能只跑一个进程，会有多个进程一起申请使用内存，如果都直接向物理内存进行申请使用肯定无法满足。通过引入虚拟内存，每个进程都有自己独立的虚拟地址空间，这个空间理论上可以无限大，因为它并不要钱。一个进程同一时刻不可能所有变量数据都会访问到，只需要在访问某部分数据时，把这一块虚拟内存映射到物理内存，其他没有实际访问过的虚拟地址空间并不会占用到物理内存，这样对物理内存的消耗就大大减少了

换页算法

FIFO：置换时选择离调入时间最久的页

LRU：置换时选择最长时间没有用到的页，计数器/栈实现

近似LRU：二次机会，引用位0时置换，引用位1时变成0并重新选一个页；时钟算法，使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

image-20201030212646730

LFU / MFU：置换被引用次数最少 / 最多的页

分段 & 分页

分页：

  • 逻辑地址道物理地址变化原理：CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址。
  • 优点：没有外碎片，提高内存的利用率。一个程序不必连续存放。便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。
  • 缺点：无论数据有多少，都只能按照页面大小分配，容易产生内部碎片。无法体现程序逻辑。页长与程序的逻辑大小不相关。不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。 分段存储

分段：

  • 地址映射: 在分段存储中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。
  • 优点：分段对程序员可见。段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。方便编程，分段共享，分段保护，动态链接，动态增长。
  • 缺点：主存空间分配比较麻烦。外部碎片。由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。

对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。

地址空间的维度：分页是一维地址空间，分段是二维的。

大小是否可以改变：页的大小不可变，段的大小可以动态改变。

出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

段页式存储

image-20201030211232454

为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块

它首先将程序按其逻辑结构划分为若干个大小不等的逻辑段，然后再将每个逻辑段划分为若干个大小相等的逻辑页。主存空间也划分为若干个同样大小的物理页。辅存和主存之间的信息调度以页为基本传送单位，每个程序段对应一个段表，每页对应一个页表。

段页式系统中，作业的地址结构包含三部分的内容：段号，页号，页内位移量

CPU访问时，段表指示每段对应的页表地址，每一段的页表确定页所在的主存空间的位置，最后与页表内地址拼接，确定CPU要访问单元的物理地址。

段页存储管理方式综合了段式管理和页式管理的优点，但需要经过两级查表才能完成地址转换，消耗时间多。

  • 过程：检查是否越界。利用段表始址和段号来求出该段所对应的段表项在段表中的位置，得到该段的页表始址。读出该页所在的物理块号b。构建物理地址。
  • 优点：提供了大量的虚拟存储空间。有效地利用主存，为组织多道程序运行提供了方便。
  • 缺点：增加了硬件成本、系统的复杂性和管理上的开销。存在系统抖动的风险。存在内碎片。各种表占用更多的空间。