操作系统

• 程序的局部性原理
• 跨平台技术实现原理
• 库函数和系统调用的区别
• 并行和并发
• 计算密集任务和IO密集任务
• 单核CPU/多核CPU/多CPU
• 什么时候使用多线程和多进程
• 进程与PCB
• fork、v_fork、clone
• 进程间通信
• 共享内存底层原理
• 进程异常退出共享内存会销毁吗
• 进程调度算法
• 进程调度时机
• 僵尸进程和孤儿进程
• 进程状态转移
• 进程间共享和私有资源
• 线程
• 协程
• 线程间同步及系统调用
• 线程间共享和私有资源
• 进程与线程的区别
• 用户态和内核态
• 什么是虚拟内存
• 缺页中断
• 虚拟内存置换算法
• 虚拟内存页表寻址
• 说一下LINUX系统中的锁
• 自旋锁发生死锁
• 死锁产生的条件
• 如何避免死锁
• 死锁检测和死锁恢复
• 信号处理机制
• 哪两个信号不能忽略
• 原子操作和锁机制

程序的局部性原理

基本概念

程序倾向于引用临近于其他最近引用过的数据项的数据项，或最近引用过的数据项本身，这种倾向性被称为局部性原理。

• 时间局部性
  • 良好时间局部性的程序中，被引用过一次的内存位置很可能在不远的将来再被多次引用
• 空间局部性
  • 良好空间局部性的程序中，一个内存位置被引用，程序很可能在不远的将来引用其附近的一个内存位置

从硬件和操作系统层面看如何利用局部性

• 硬件层
  • 局部性原理允许硬件引入高速缓存存储器这种小而快速的存储器来存储最近被引用的指令和数据，从而提高对主存的访问速度
• 操作系统
  • 允许系统使用主存作为虚拟地址空间作为最近被引用块的高速缓存

从存储结构看如何利用局部性

存储器层次结构的中心思想是，对于每个 k，位于 k 层的更快更小的存储设备作为位于 k + 1 层的更大更慢的存储设备的缓存。

• 时间局部性
  • 同一数据对象可能被多次使用。一旦一个数据对象在第一次不命中时被复制到缓存中，我们就会期望后面对目标有一系列的访问命中。因为缓存比低一层的存储设备更快，对后面的命中的服务会比最开始的不命中的快很多。
• 空间局部性
  • 块通常包含多个数据对象。我们会期望后面对该块中其他对象的访问能补偿不命中后复制该块的花费。

库函数和系统调用的区别

概念

• 库函数调用是语言或应用程序的一部分，而系统调用是操作系统的一部分，跨平台技术的原理就是通过库函数实现的，库函数可以理解为是对系统调用的一层封装，但库函数不是必须包含系统调用。
• 库函数有可能包含有一个系统调用，有可能有好几个系统调用，当然也有可能没有系统调用，比如有些操作不需要涉及内核的功能。

区别

• 所有 C 函数库是相同的，而各个操作系统的系统调用是不同的。
• 函数库调用是调用函数库中的一个程序，而系统调用是调用系统内核的服务。
• 函数库调用是与用户程序相联系，而系统调用是操作系统的一个进入点
• 函数库调用是在用户地址空间执行，而系统调用是在内核地址空间执行
• 函数库调用的运行时间属于「用户」时间，而系统调用的运行时间属于「系统」时间
• 函数库调用属于过程调用，开销较小，而系统调用需要切换到内核上下文环境然后切换回来，开销较大
• 在C函数库libc中大约 300 个程序，在 UNIX 中大约有 90 个系统调用
• 函数库典型的 C 函数：system, fprintf, malloc，而典型的系统调用：chdir, fork, write, brk

为什么不直接用函数调用

• 因为读写文件通常是大量的数据（相对于底层驱动的系统调用所实现的数据操作单位），这时，使用库函数可以大大减少系统调用的次数。这是因为**缓冲区技术**，在用户空间和内核空间对文件操作都使用了缓冲区。当用户空间缓冲区满或者写操作结束时，才将用户缓冲区的内容写到内核缓存区。同理，内核缓冲区满或写结束时，才将内核缓冲区内容写到文件对应的硬件媒介。
• 为了保证可移植性

库函数的缓冲区

• 对于库函数，如果标准输出连到终端设备(直接输出到屏幕)，则它是行缓冲的（遇到回车换行符或者是缓冲区满了才输出）；否则（输出到文件）是全缓冲的（缓冲区填满或者是程序运行结束了才输出）。
• 程序运行结束时，会刷新所有的缓冲区。

由于上面的缓冲机制，也给我们编写程序时带来了一些奇怪的问题。解决办法有如下两种：

• 任何时候我们都可以使用fflush(stdout)来刷新标准输出缓冲区。
• 使用不带缓冲的系统调用write替代printf输出。

系统调用底层原理

• 每个系统调用函数都有一个系统调用号
• 首先找到系统调用对应的中断号（Linux下是int 0x80），然后在中断向量表中找到对应的中断处理函数，再根据系统调用号，在中断处理函数找到对应系统调用函数进行执行。

跨平台技术实现原理

现有跨平台技术就是通过库函数调用实现的，不使用系统函数调用。

• Qt如何识别不同系统
  • Qt各个操作系统都有特定的宏，然后代码里面根据不同的宏调用不同平台的API

并行和并发

• 并发

  • 在同一时刻只能有一条指令执行，但多个进程指令被快速轮换执行，使得在宏观上具有多个进程同时执行的效果。

• 并行

  • 在同一时刻，有多条指令在多个处理器上同时执行。

计算密集任务和IO密集任务

• 计算密集型任务

  • 特点是要进行大量的计算，消耗CPU资源，比如计算圆周率、对视频进行高清解码等等，全靠CPU的运算能力。
  • 虽然可以用多任务完成，但是任务越多，花在任务切换的时间就越多，CPU执行任务的效率就越低，所以，要最高效地利用CPU，计算密集型任务同时进行的数量应当等于CPU的核心数。

• IO密集型任务

  • 涉及到网络、磁盘IO的任务都是IO密集型任务，这类任务的特点是CPU消耗很少，任务的大部分时间都在等待IO操作完成（因为IO的速度远远低于CPU和内存的速度）。
  • 对于IO密集型任务，任务越多，CPU效率越高，但也有一个限度。常见的大部分任务都是IO密集型任务，比如Web应用。

单核CPU/多核CPU/多CPU

• 都是一个CPU，不同的是每个CPU上的核心数。
• 多核CPU是多个CPU的替代方案，同时也减少了功耗。
• 一个核心只能同时执行一个线程。

• 单核CPU
  • 一个CPU中只有一个核心处理器
• 多核CPU
  • 一个CPU有多个核心处理器，处理器之间通过**CPU内部总线**进行通讯
• 多CPU
  • 简单的多个CPU工作在同一个系统上，多个CPU之间通过**主板上的总线**进行通讯

深入理解进程和线程

• 进程的调度和资源分配是操作系统负责

• 线程的调度和资源分配是CPU负责

• 进程是操作系统资源分配(包括cpu、内存、磁盘IO等)的基本单位，一个CPU同时刻只能执行一个进程

  • 单核CPU实现多进程，并发。 通过操作系统的进程调度算法，单核CPU进行进程调度的时候，需要读取上下文+执行程序+保存上下文，即进程切换。
  • 多CPU实现多进程，并行。 不同的进程运行在不同的CPU上。

• 线程是CPU调度和资源分配的基本单位，一个CPU核心同时刻只能执行一个线程

  • 单核CPU实现多线程，并发。 不同线程为了使用CPU核心，则会进行线程切换，但是由于共享了程序执行环境，这个线程切换比进程切换开销少了很多。
  • 多核CPU实现多线程，并行。 CPU可以将不同线程分配到不同的CPU核心处理器中。

• 单CPU中进程只能是并发，多CPU计算机中进程可以并行。
• 单CPU单核中线程只能并发，单CPU多核中线程可以并行。
• 并行有上限，进程与CPU个数，线程与CPU核心个数有关，并不是所有线程和所有进程都能同时运行

什么时候使用多进程和多线程

• 多核CPU——计算密集型任务。此时要尽量使用多线程，可以提高任务执行效率，例如加密解密，数据压缩解压缩（视频、音频、普通数据），否则只能使一个核心满载，而其他核心闲置.
• 单核CPU——计算密集型任务。此时的任务已经把CPU资源100%消耗了，就没必要也不可能使用多线程来提高计算效率了；相反，如果要做人机交互，最好还是要用多线程，避免用户没法对计算机进行操作。
• 单核CPU——IO密集型任务，使用多线程还是为了人机交互方便.
• 多核CPU——IO密集型任务，这就更不用说了，跟单核时候原因一样。

进程与PCB

进程

• 进程是操作系统的资源分配单位，实现操作系统的并发，对于一个进程，它在被执行前其实是一个可执行程序。这个程序是被放在磁盘上的，当它要被执行的时候，它先被加载到内存当中，然后再放入到寄存器中，最后再让cpu执行该程序，这个时候一个静态的程序就变成了进程
• 进程创建时会分配4G的内存，其中0-3G是用户空间，3-4G是内核空间，PCB存在于内核空间
• 进程的用户空间是不同的，内核空间也是不同的。比如每个进程的不同系统调用，是陷入自己独立的内核空间里面，所以每个进程内核的堆栈肯定是不一样的

PCB

• 每个进程的PCB都是存在所有进程共享的内核空间中，操作系统管理进程，也就是在内核空间中管理的，在内核空间中通过链表管理所有进程的PCB，如果有一个进程要被创建，实际上多分配了这么一个4G的虚拟内存，并在共享的内核空间中的双向链表中加入了自己的PCB。
• PCB(Process Control Block)进程控制块，描述进程的基本信息和运行状态，进程的创建和销毁都是对PCB进行操作，PCB的具体内容如下
  • 标识相关：pid，ppid等等
  • 文件相关：进程需要记录打开的文件信息，于是需要文件描述符表
  • 内存相关：内存指针，指向进程的虚拟地址空间（用户空间）信息
  • 优先级相关：进程相对于其他进程的调度优先级
  • 上下文信息相关：CPU的所有寄存器中的值、进程的状态以及堆栈上的内容，当内核需要切换到另一个进程时，需要保存当前进程的所有状态，即保存当前进程的进程上下文，以便再次执行该进程时，能够恢复切换时的状态，继续执行。
  • 状态相关：进程当前的状态，说明该进程处于什么状态
  • 信号相关：进程的信号处理函数，以及记录当前进程是否还有待处理的信号
  • I/O相关：记录进程与各种I/O设备之间的交互
• 每个进程的内核空间中都有PCB，但真正的PCB是存储在物理内存上的，当进程创建和销毁时，会由操作系统操作PCB，每个进程只是虚拟地址空间，并不会存储实际数据，数据存储在物理内存中，只有一份。

进程间同步

信号量

forkvforkclone

fork、v_fork、clone底层都是do_fork，追踪发现底层使用的是sys_clone

• fork
  • 父进程fork之后创建子进程，子进程复制父进程的所有资源，子进程的代码段、数据段、堆栈都是指向父进程的物理空间，但此时仅仅是子进程的虚拟地址空间和父进程指向的物理地址空间建立了映射关系，并没有真正复制
  • 由于fork()后会产生一个和父进程完全相同的子进程，但子进程在此后多会exec系统调用，处于效率考虑，linux中引入了“写时复制技术-Copy-On-Write”
  • 若两个进程一直只是读数据，则子进程一直不会复制，直到任一进程进行写操作
  • 父进程和子进程执行顺序没有规定，可以乱序执行
  • 读时共享，写时复制
• vfork
  • vfork也是创建一个子进程，但是子进程共享父进程的空间。在vfork创建子进程之后，父进程阻塞，直到子进程执行了exec()或者exit()。
  • 规定必须子进程先执行
  • 严格意义上讲，vfork产生的不叫进程，因为他没有独立的地址空间，和父进程共享同一个

进程间通信

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

• 管道(缓冲区有限)
  • 无名管道PIPE
    • 一种半双工的通信方式，只能在具有亲缘关系的进程间使用（父子进程或兄弟进程）
  • 有名管道FIFO
    • 一种半双工的通信方式，可以在非亲缘关系的进程间使用
• 消息队列
  • 消息队列是消息的链接表，存放在内核中并由消息队列标识符标识
  • 消息队列克服了信号传递信息少，管道缓冲区大小受限的缺点
  • 一个消息队列由一个标识符（即队列ID）来标记
• 信号
  • 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存
  • 它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。多个进程可以同时操作，所以需要进行同步 ，一般与信号量配合使用。
  • shm
  • mmap
• 套接字
  • 本地套接字用于本机不同进程间通信，另外普通套接字可以用于不同主机间的进程间通信

共享内存底层原理

共享内存有两个，一个mmap，一个systemV的shmget

• 虚拟内存在硬盘上

不同进程如何访问共享内存？

进程异常退出共享内存会销毁吗

进程调度算法

批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

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

  • 非抢占式的调度算法，按照请求的顺序进行调度。
  • 有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

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

  • 非抢占式的调度算法，按估计运行时间最短的顺序进行调度。
  • 长作业有可能会饿死，处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

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

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

交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

• 时间片轮转

  • 将所有就绪进程按 FCFS 的原则排成一个队列，每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。
  • 当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。

• 优先级调度

  • 为每个进程分配一个优先级，按优先级进行调度。
  • 为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

• 多级反馈队列

  • 一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
  • 多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次。
  • 每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
  • 可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

实时系统

• 实时系统要求一个请求在一个确定时间内得到响应。
• 分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

进程调度时机

• 进程状态转换的时刻：进程终止、进程睡眠；
• 当前进程的时间片用完时（current->counter=0）；
• 设备驱动程序
• 进程从中断、异常及系统调用返回到用户态时；

僵尸进程和孤儿进程

• 当父进程先结束，子进程此时就会变成孤儿进程，孤儿进程会自动向上被init进程收养，init进程完成对状态收集工作。而且这种过继的方式也是守护进程能够实现的因素。
• 如果子进程先结束，父进程并未调用wait或者waitpid获取进程状态信息，回收进程资源，那么子进程描述符就会一直保存在系统中，这种进程称为僵尸进程。
  • 僵尸进程是每个子进程退出时必然经历的过程
  • 僵尸进程的危害
    • 在每个进程退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存等。但是仍然为其保留一定的信息（包括进程号the process ID，退出状态the termination status of the process，运行时间the amount of CPU time taken by the process等）。直到父进程通过wait / waitpid来取时才释放.
    • 如果进程不调用wait / waitpid的话， 那么保留的那段信息就不会释放，其进程号就会一直被占用，但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程。
  • 如何消除僵尸进程
    • kill发送SIGTERM或者SIGKILL信号消灭产生僵尸进程的进程，它产生的僵死进程就变成了孤儿进程，这些孤儿进程会被init进程接管
    • 子进程退出时向父进程发送SIGCHILD信号，父进程处理SIGCHILD信号。在信号处理函数中调用wait进行处理僵尸进程。

进程状态转移

• 就绪状态（ready）：等待被调度
• 运行状态（running）
• 阻塞状态（waiting）：等待资源

  • 就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
  • 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

进程间共享和私有资源

• 私有：地址空间、堆、全局变量、栈、寄存器（0-3G的用户空间）
• 共享：3-4G的内核空间

线程

线程是CPU调度的基本单位

协程

协程学习笔记

协程概述

• 协程是轻量级线程，拥有自己的寄存器上下文和栈。协程调度切换时，将寄存器上下文和栈保存到其他地方，在切回来的时候，恢复先前保存的寄存器上下文和栈。
• 协程能保留上一次调用时的状态，即所有局部状态的一个特定组合，每次过程重入时，就相当于进入上一次调用的状态。

协程和线程的区别

• 协程最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制，因此，没有线程切换的开销，和多线程比，线程数量越多，协程的性能优势就越明显。
• 不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突，在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

应用场景

• I/O 密集型任务。

• 这一点与多线程有些类似，但协程调用是在一个线程内进行的，是单线程，切换的开销小，因此效率上略高于多线程。
• 当程序在执行 I/O 时操作时，CPU 是空闲的，此时可以充分利用 CPU 的时间片来处理其他任务。在单线程中，一个函数调用，一般是从函数的第一行代码开始执行，结束于 return 语句、异常或者函数执行（也可以认为是隐式地返回了 None ）。
• 有了协程，我们在函数的执行过程中，如果遇到了耗时的 I/O 操作，函数可以临时让出控制权，让 CPU 执行其他函数，等 I/O 操作执行完毕以后再收回控制权。

线程间同步及系统调用

信号量

信号量是一种特殊的变量，可用于线程同步。它只取自然数值，并且只支持两种操作：

• P(SV):如果信号量SV大于0，将它减一；如果SV值为0，则挂起该线程。
• V(SV)：如果有其他进程因为等待SV而挂起，则唤醒，然后将SV+1；否则直接将SV+1。

• 系统调用
  • sem_wait（sem_t *sem）：以原子操作的方式将信号量减1，如果信号量值为0，则sem_wait将被阻塞，直到这个信号量具有非0值。
  • sem_post（sem_t *sem)：以原子操作将信号量值+1。当信号量大于0时，其他正在调用sem_wait等待信号量的线程将被唤醒。

互斥量

互斥量又称互斥锁，主要用于线程互斥，不能保证按序访问，可以和条件锁一起实现同步。当进入临界区 时，需要获得互斥锁并且加锁；当离开临界区时，需要对互斥锁解锁，以唤醒其他等待该互斥锁的线程。

• 系统调用
  • pthread_mutex_init:初始化互斥锁
  • pthread_mutex_destroy：销毁互斥锁
  • pthread_mutex_lock：以原子操作的方式给一个互斥锁加锁，如果目标互斥锁已经被上锁，pthread_mutex_lock调用将阻塞，直到该互斥锁的占有者将其解锁。
  • pthread_mutex_unlock:以一个原子操作的方式给一个互斥锁解锁。

条件变量

条件变量，用于在线程之间同步共享数据的值。条件变量提供一种线程间通信机制：当某个共享数据达到某个值时，唤醒等待这个共享数据的一个/多个线程。即，当某个共享变量等于某个值时，调用 signal/broadcast。此时操作共享变量时需要加锁。

• 系统调用
  • pthread_cond_init:初始化条件变量
  • pthread_cond_destroy：销毁条件变量
  • pthread_cond_signal：唤醒一个等待目标条件变量的线程。哪个线程被唤醒取决于调度策略和优先级。
  • pthread_cond_wait：等待目标条件变量。需要一个加锁的互斥锁确保操作的原子性。该函数中在进入wait状态前首先进行解锁，然后接收到信号后会再加锁，保证该线程对共享资源正确访问。

线程间共享和私有资源

• 私有：线程栈，寄存器，程序寄存器，线程ID，错误返回码，信号屏蔽字，调度优先级
• 共享：文件描述符表，堆，地址空间，全局变量，静态变量，进程代码段，进程的当前目录和进程用户ID与进程组ID

进程与线程的区别

• 进程是cpu资源分配的最小单位，线程是cpu调度的最小单位。
• 进程有独立的系统资源或地址空间，而同一进程内的线程共享进程的大部分系统资源,包括堆、代码段、数据段，每个线程只拥有一些在运行中必不可少的私有属性，比如线程Id,栈、寄存器、程序计数器PC(或者说IP)。
• 一个进程崩溃，不会对其他进程产生影响；而一个线程崩溃，会让同一进程内的其他线程也宕掉。
• 进程在创建、销毁时开销比较大，而线程比较小。进程创建的时候需要分配虚拟地址空间等系统资源，而销毁的的时候需要释放系统资源；线程只需要创建栈，栈指针，程序计数器，通用目的寄存器和条件码等，不需要创建独立的虚拟地址空间。
• 进程切换开销比较打，线程比较小。进程切换需要分两步：切换页目录、刷新TLB以使用新的地址空间；切换内核栈和硬件上下文（寄存器）；而同一进程的线程间逻辑地址空间是一样的，不需要切换页目录、刷新TLB。
• 进程间通信比较复杂，而同一进程的线程由于共享代码段和数据段，所以通信比较容易。

TLB

TLB( Translation Look- aside buffer)专门用于缓存内存中的页表项,一般在MMU单元内部，页表一般存储在屋里内存中。当处理器要访问一个虚拟地址时,首先会在TLB中查询。如果TLB表项中没有相应的表项,称为TLB Miss,那么就需要访问页表来计算出相应的物理地址。如果TLB表项中有相应的表项,那么直接从TLB表项中获取物理地址,称为TLB命中。

程序计数器PC和指令指针寄存器IP(http://blog.sina.com.cn/s/blog_5ede281a0100sn4w.html)

• 程序计数器PC
  • 用指令事先编好的程序连续存放在内存程序区中，靠地址+1的方法连续取指执行”。在八位机8080CPU中是采用先取指后执行的串行操作的原理，而其中执行地址+1指令寻址的部件就是程序计数器PC。那么在程序的执行过程中，PC始终是指向下一条要执行的指令。
  • 结论：PC中的地址就是需要转移、循环、调用子程序和中断子程序等操作时的断点。
• 指令指针寄存器IP
  • 在向上兼容的十六位机8086CPU中首先分为两个功能部件，即总线接口部件BIU和执行部件EU，BIU负责取指令，EU负责译码执行。并且当BIU执行指令排队栈中的六个字节装满后，（8088CPU是4个字节），EU开始从指令排队栈的出栈口，取指令进行译码执行，同时BIU并行操作向入栈口补充一条取指令命令。
  • 指令指针IP则是指向下个条要取指的指令，而不是EU要执行的指令。而断点则应该是要执行的指令内存地址，而不是IP内的下一条要取指的指令地址。
• PC是模型机中的概念，IP是实际使用的，调试时我们发现，IP实现的就是PC的功能。

为什么有了进程还需要线程？

• 优点
  • 进程可以使多个程序能并发执行，以提高资源的利用率和系统的吞吐量.
• 缺点
  • 进程在同一时间只能干一件事
  • 进程在执行的过程中如果阻塞，整个进程就会挂起，即使进程中有些工作不依赖于等待的资源，仍然不会执行。

因此，操作系统引入了比进程粒度更小的线程，作为并发执行的基本单位，从而减少程序在并发执行时所付出的时空开销，提高并发性

用户态和内核态

概念

• 用户态和内核态是操作系统的两种运行级别，两者最大的区别就是特权级不同。
• 用户态拥有最低的特权级，内核态拥有较高的特权级。
• 运行在用户态的程序不能直接访问操作系统内核数据结构和程序
• 操作系统的数据都是存放于系统空间的，用户进程的数据是存放于用户空间的。
  • 分开来存放，就让系统的数据和用户的数据互不干扰，保证系统的稳定性。
  • 分开存放，管理上很方便，而更重要的是，将用户的数据和系统的数据隔离开，就可以对两部分的数据的访问进行控制。这样就可以确保用户程序不能随便操作系统的数据，这样防止用户程序误操作或者是恶意破坏系统。

用户态和内核态可以通过指针传递数据吗？

• 用户态不能访问内核态的指针
  • 为了实现内存的保护，防止越界访问而造成受保护内存的被非法修改，甚至造成系统的崩溃，这种直接传递数据指针来传递数据的方式是被禁止的。
• 内核态可以访问用户态的指针(有前提)
  • 必须保证用户态虚拟空间的指针（虚拟空间的地址），已经分配物理地址，否则指针传入内核态中将不会引发缺页异常而报错
• 内核中访问用户进程的地址的时候用copy_from_user，而不是用memcpy直接拷贝(或者说使用用户态指针)
  • copy_from_user主要是这个函数提供了两个功能
    • 对用户进程传过来的地址范围进行合法性检查；
    • 当用户传来的地址没有分配物理地址时，定义了缺页处理后的异常发生地址，保证程序顺利执行；
    • 对于用户进程访问虚拟地址，如果还未分配物理地址，就会触发内核缺页异常，接着内核会负责分配物理地址，并修改映射页表。这个过程对于用户进程是完全透明的。但是在内核空间发生缺页时，必须显式处理，否则会导致内核出现错误
  • 直接使用memcpy时为什么没有出现异常
    • 只有用户传来的地址空间没有分配对应的物理地址时才会进行修复，如果用户进程之前已经使用过这段空间，代表已经分配了物理地址，自然不会发生缺页异常。

两种状态转换

• 系统调用
  • 用户进程主动要求切换到内核态的一种方式，用户进程通过系统调用申请操作系统提供的服务程序完成工作
• 异常
  • 当CPU在执行运行在用户态的程序时，发现了某些事件不可知的异常，这是会触发由当前运行进程切换到处理此异常的内核相关程序中，也就到了内核态，比如缺页异常。
• 外围设备中断
  • 当外围设备完成用户请求的操作之后，会向CPU发出相应的中断信号，这时CPU会暂停执行下一条将要执行的指令，转而去执行中断信号的处理程序
  • 比如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执行后续操作等

存储器层次结构

层次结构

本地磁盘 -> 主存(DRAM) -> L3高速缓存(SRAM) -> L2高速缓存(SRAM) -> L1高速缓存(SRAM) -> L0寄存器

缓存思想

• 位于K层的更快更小的存储设备作为位于K+1层更大更慢的存储设备的缓存
• K+1层的存储器被划分成连续的数据对象组块，称为块，数据总是以块大小为传送单元在K和K+1层之间来回复制

缓存命中

• 当程序需要K+1层的某个数据对象d时，首先在当前存储在K层的块中查找d，若d刚好缓存在k层中，则称为缓存命中
• 若缓存不命中，则需要将K+1层中包含对象d的块缓存到K层中，若K层中满了，则需要替换现存的一个块

什么是虚拟内存

为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存，防止不同进程同一时刻在物理内存中运行而对物理内存的争夺和践踏，采用了虚拟内存。

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

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

虚拟内存的好处

• 可以更加高效的使用物理内存
  • 虚拟地址空间一开始并没有真正的对应物理地址，而是在真正使用的时候才去对应。
  • 通过虚拟内存置换算法在访问后边的地址空间的时候就可以将前边当前没有在访问的物理页释放掉，或者交换到硬盘中。这样这个物理页又可以去对应新的虚拟地址。从而使物理内存可以充分的利用。
• 内存管理
  • 为每个进程提供了一致的地址空间，简化内存管理
• 内存保护
  • 在使用虚拟地址的时候，暴露给程序员永远都是虚拟地址，而具体的物理地址在哪里，这个只有系统才了解。这样就提高了系统的封装性。
  • 保护了每个进程的地址空间不被其他进程破坏

虚拟内存页表寻址

分页

虚拟内存分割成虚拟页，物理内存被分割成物理页，用来作为磁盘和主存的传输单元。 虚拟页分为三个不相交的子集

• 未分配的，不占磁盘空间
• 缓存的，当前已缓存在物理内存中的已分配页，在页表中标志位为1
• 未缓存的，未缓存在物理内存中的已分配页，在页表中标志位为0

页表

内存管理单元（MMU，属于硬件）管理着地址空间和物理内存的转换，操作系统为每一个进程维护了一个从虚拟地址到物理地址的映射关系的数据结构，叫页表，存储着程序地址空间到物理内存空间的映射表。

页表存放在物理内存中，物理页存放在物理内存中，虚拟页存放在磁盘上

页表寻址

• 一个虚拟地址分为两部分，一部分存储页面号，一部分存储偏移量
• 页表分为序号、页基地址、标志位
• 访问虚拟地址，先通过页表查询页面号，查看标志位确认虚拟地址是否在物理内存中有缓存，然后由逻辑地址的高位部分先找到逻辑地址对应的页基地址，再由页基地址偏移虚拟地址中的偏移量就得到最后的物理地址
• 一般情况下，这个过程都可以由硬件完成，所以效率还是比较高的。页式内存管理的优点就是比较灵活，内存管理以较小的页为单位，方便内存换入换出和扩充地址空间。

缺页中断

在请求分页系统中，可以通过查询页表中的状态位来确定所要访问的页面是否存在于内存中。每当所要访问的页面不在内存时(缓存不命中)，会产生一次缺页中断，此时操作系统会根据页表中的外存地址在外存中找到所缺的一页，将其调入内存。

缺页本身是一种中断，与一般的中断一样，需要经过4个处理步骤：

• 保护CPU现场
• 分析中断原因
• 转入缺页中断处理程序进行处理
• 恢复CPU现场，继续执行

但是缺页中断是由于所要访问的页面不存在于内存时，由硬件所产生的一种特殊的中断，因此，与一般的中断存在区别：

• 在指令执行期间产生和处理缺页中断信号
• 一条指令在执行期间，可能产生多次缺页中断
• 缺页中断返回是，执行产生中断的一条指令，而一般的中断返回是，执行下一条指令。

虚拟内存置换算法

当访问一个内存中不存在的页，并且内存已满，则需要从内存中调出一个页或将数据送至磁盘对换区，替换一个页，这种现象叫做缺页置换。

当前操作系统最常采用的缺页置换算法如下：

• 先进先出(FIFO)算法：置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。

• 最近最少使用（LRU）算法: 置换最近一段时间以来最长时间未访问过的页面。根据程序局部性原理，刚被访问的页面，可能马上又要被访问；而较长时间内没有被访问的页面，可能最近不会被访问。

当前最常采用的就是LRU算法。

说一下LINUX系统中的锁

互斥锁，读写锁，自旋锁

• 互斥锁：mutex，用于保证在任何时刻，都只能有一个线程访问该对象。当获取锁操作失败时，线程会进入睡眠，等待锁释放时被唤醒

• 读写锁：rwlock，分为读锁和写锁。处于读操作时，可以允许多个线程同时获得读操作。但是同一时刻只能有一个线程可以获得写锁。其它**获取写锁失败的线程都会进入睡眠状态**，直到写锁释放时被唤醒。 注意：写锁会阻塞其它读写锁。当有一个线程获得写锁在写时，读锁也不能被其它线程获取；写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）。适用于读取数据的频率远远大于写数据的频率的场合。

• 自旋锁：spinlock，在任何时刻同样只能有一个线程访问对象。但是**当获取锁操作失败时，不会进入睡眠，而是会在原地自旋**，循环检测锁的保持者是否释放，直到锁被释放。这样节省了线程从睡眠状态到被唤醒期间的消耗，在加锁时间短暂的环境下会极大的提高效率。但如果加锁时间过长，则会非常浪费CPU资源。

自旋锁发生死锁

死锁产生的条件

多个并发进程因争夺系统资源而产生相互等待的现象。

• 互斥条件：进程对所分配到的资源不允许其他进程访问，若其他进程访问该资源，只能等待，直至占有该资源的进程使用完成后释放该资源；

• 请求和保持条件：进程获得一定的资源后，又对其他资源发出请求，但是该资源可能被其他进程占有，此时请求阻塞，但该进程不会释放自己已经占有的资源

• 不可剥夺条件：进程已获得的资源，在未完成使用之前，不可被剥夺，只能在使用后自己释放

• 环路等待条件：进程发生死锁后，必然存在一个进程-资源之间的环形链 ，环路中每个进程都在等待下一个进程所占有的资源

如何避免死锁

• 破坏请求和等待条件。 所有的进程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源
• 破坏不可抢占条件。 当进程新的资源未得到满足时，释放已占有的资源
• 破坏环路等待条件。 系统给每类资源赋予一个序号，每个进程按编号递增的请求资源，释放则相反

死锁检测和死锁恢复

• 死锁检测
  • 每种类型一个资源的死锁检测
  • 每种类型多个资源的死锁检测
• 死锁恢复
  • 抢占恢复。 从一个或多个进程中抢占足够数量的资源分配给死锁进程，以解除死锁状态
  • 回滚恢复。 周期性地检查进程的状态（包括请求的资源），将其写入一个文件，当发生死锁，回滚到之前的某个时间点
  • 杀死进程恢复。 终止或撤销系统中的一个或多个死锁进程，直至打破死锁状态。

信号处理机制

哪两个信号不能忽略

SIGKILL和SIGSTOP，这两种信号不能被忽略

• 它们向超级用户提供一种使进程终止或停止的可靠方法。
• 如果忽略某些由硬件异常产生的信号（例如非法存储访问或除以0），则进程的行为是示定义的。

原子操作和锁机制

原子操作实现同步