进程、处理机调度、存储器管理、虚拟存储器相关知识的系统整理
操作系统
进程
进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，每个进程之间是独立的，每个进程均运行在其专用的且受保护的内存，是操作系统结构的基础。
进程相对来说是更动态化一些的概念，进程是操作系统分配资源的最小单位，程序是一段写好的静态二进制代码。一个程序在操作系统中运行时，可能会拥有一个或多个进程，当一个程序只有一个进程时，这个进程就是程序本身。
进程是程序运行时的一个状态。在系统允许的情况下（非技术原因），程序可以在计算机系统中单独运行多次，分别是多个不同的进程，他们之间的状态各不相同。
进程拥有自己的地址空间，并且不同于线程，进程可以向系统申请资源。在系统中，存在PCB（进程控制块）来管理进程，在PCB中记录了进程的相关信息以及运行数据，如程序计数器、进程状态、CPU暂存器、IO状态等。
- 程序计数器：接着要执行的指令地址
- 进程状态：可以是new、ready、running、waiting或blocked等
- CPU寄存器：如累加器、变址寄存器、堆栈指针以及一般用途寄存器、状况代码等，主要用途在于中断时暂时存储资料，以便稍后继续利用；其数量及类别因计算机体系结构有所差异。进程调度中CPU切换进程时，就要将进程的状态例如在寄存器中的值存储起来。在进程未占用处理器时，进程的上下文是存储在进程的私有堆栈中的。
- CPU排班法：标示进程优先级
- 存储器管理：如标签页表等
- 输入输出状态：配置进程使用I/O设备，如磁带机
进程的PCB在系统中可以有几种组织方式（存放方式）
- 线性表方式：不论进程的状态如何，将所有的 PCB 连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。
- 索引表方式：该方式是线性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。
- 链接表方式：系统按照进程的状态将进程的 PCB 组成队列，从而形成就绪队列、阻塞队列、运行队列等。
进程之间可以进行通信，通常一个程序根据规模的大小可以拥有1个或多个进程，进程间的通信就显得尤为重要（IPC Inter-Process Communication）。IPC为资源互相隔离的进程提供了通信手段，常见的IPC实现方式有以下几种
- 无名管道：只允许父子进程通信，缓存区开辟在内核区上，自带互斥机制，同一时间只能单向传输
- 有名管道：可以允许没有亲缘关系的进程通信，缓存区在文件系统上，在创建时有一个路径与它绑定，只要能访问这个的进程就能进行IPC通信。即，需要交换的信息被写在一个文件系统中的特定位置，需要交换则向该块内存读出或写入
- 信号：信号是IPC通信中一种有限制的方式，它是一种异步的通知机制，相当于一个中断，由内核调解并分发给对应进程。此时如果信号被发送给了一个进程，操作系统将会中断进程中的所有非原子操作，如果进程有定义该信号处理的函数则执行对应函数，没有则执行默认操作。常见的有终端中的
control + c操作会发送一个终止信号，kill()信号也会发送一个终止信号给进程。 - 消息队列：信息列表是由信息组成的链表，存储在内核中，由信息标示符标示。它也是一种异步的通信方式，进程可以将需要交流的信息写入到消息队列中而不用一直等待别的进程将消息取出。和信号相比，消息队列可以传达更多的信息。和管道相比，消息队列可以提供有格式的信息。由于其异步的特点，接收者必须轮询消息队列才能获得最新的信息，这也是其中的一个缺点
- 共享内存：映射一段能被其他进程访问的内存，实现共享该块内存的目的。具体过程是首先在物理内存中申请分配一块共享内存 ，分配成功后需要共享内存的进程将该块内存的物理地址映射到自己的地址空间中 ，即将共享内存的物理地址与地址空间的虚拟地址进行绑定（页表，MMU），在这之后进程就能访问到共享内存。在访问结束后，进程需要与该块共享内存解绑 。另外，使用共享内存时需要注意的是内存的写入需要自己实现同步机制 ，一般在使用共享内存通信时会与信号量配合使用，实现同步的访问。
- 信号量
- 套接字
线程
线程可以说是一种轻量级的进程，但他不像进程一样拥有资源，线程只拥有所属进程的一点运行所必要的资源，它可以与所属进程的其他线程共享进程所持有的资源。在一个进程中可以同时拥有多个线程，但一个线程只对应一个进程。
通常在一个进程中可以包含多个线程，它们可以利用进程所拥有的资源，在引入线程的操作系统中，通常都是把进程作为分配资源的基本单位，而把线程作为独立运行和独立调度的基本单位，由于线程比进程更小，基本上不拥有系统资源，故对它的调度所付出的开销就会小的多，能更高效的提高系统内多个程序间并发执行的程度。也就是说线程间的切换开销比进程间的切换开销要小得多
操作系统不会向线程分配资源，线程也不可以申请资源。同一进程中的多条线程将共享该进程中的全部系统资源，如虚拟地址空间，文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈（call stack），自己的寄存器环境（register context），自己的线程本地存储（thread-local storage）。这是线程与进程的一大差别，核心区别是线程与进程的控制和隔离粒度不同。我们把多个进程考虑成一个个的沙盒，而线程就是沙盒中的一个个处理事务的工具，显然线程的控制粒度更细一些。
在某些情况下，线程也需要线程间的通信，因为线程自身的调用栈和寄存器环境也是私有的，其他线程无法获取到。多个线程只是共享着进程的资源和地址空间。
相对于进程的PCB，线程的状态由线程控制块Thread Control Block TCB描述。TCB包括以下信息:
- 线程状态。
- 当线程不运行时，被保存的现场资源。
- 一组执行堆栈。
- 存放每个线程的局部变量主存区。
- 访问同一个进程中的主存和其它资源。
- 进程和线程的关系
- 进程是操作系统分配和管理资源的最小单位，线程是进程中执行运算的最小单位，也是CPU进行计算的最小单位。线程可以说是一种轻量级的进程，但他不像进程一样拥有资源，线程只拥有所属进程的一点运行所必要的资源，它可以与所属进程的其他线程共享进程所持有的资源。在一个进程中可以同时拥有多个线程，但一个线程只对应一个进程。
- 区别：1.进程拥有资源，线程只访问资源 2.线程的销毁切换代价低，进程的销毁切换代价高 3.线程作为调度和分配的基本单位，进程作为资源分配的基本单位
多线程
多线程（multithreading），是指从软件或者硬件上实现多个线程并发执行的技术。具有多线程能力的计算机因有硬件支持而能够在同一时间执行多于一个线程，进而提升整体处理性能。具有这种能力的系统包括对称多处理机、多核心处理器以及芯片级多处理或同时多线程处理器。在一个程序中，这些独立运行的程序片段叫作 “线程”（Thread），利用它编程的概念就叫作“多线程处理”。
实现多线程是采用一种并发执行机制。简单地说就是把一个处理器划分为若干个短的时间片，每个时间片依次轮流地执行处理各个应用程序，由于一个时间片很短，相对于一个应用程序来说，就好像是处理器在为自己单独服务一样，从而达到多个应用程序在同时进行的效果。多线程就是把操作系统中的这种并发执行机制原理运用在一个程序中，把一个程序划分为若干个子任务，多个子任务并发执行，每一个任务就是一个线程。这就是多线程程序。
然而在多线程开发中，也存在着一些缺点。
- 过多的线程：如果程序中存在过多的线程，那么线程之间切换的开销就变得可观了起来，CPU为了在线程间进行切换可能会消耗非常多的时间和资源
- 数据竞赛：在多线程开发中最常见的问题就是数据竞赛。当多个线程同时访问或者修改同一个资源或变量，显然会产生某个进程读取到的资源出错的情况，在执行过程中产生了脏数据导致了错误。多个线程的操作中通常需要一些同步机制来保证程序的正确执行。
死锁原理
在多线程编程中，死锁问题是一个十分需要注意的点。（当然不止是多线程编程，单线程也可能会造成死锁）
死锁是指两个或两个以上的进程或线程由于不当的推进顺序或者资源分配引起的阻塞现象，在无外力作用下他们会一直互相等待下去，造成死锁。
死锁的四个原理
- 互斥：两个或两个以上的进程或线程对所需的共享资源进行互斥访问
- 循环等待：线程或进程之间形成了一个环链，每个线程或进程都在等待环中上一个线程或进程释放资源，每个线程或进程所持有的资源都是下一个线程或进程所需要的
- 不剥夺（非抢占）：线程或进程持有的资源不能被剥夺或者抢占
- 持有等待：线程或进程在持有资源的同时还在申请其他的资源
进程调度
调度算法
非抢占式调度算法
- 先来先服务（FCFS）
最简单的非抢占式调度算法，先到来的进程排在队列的头部，先得到处理机，后到来的进程排在后面。
优点是实现简单，相对公平。
缺点是不利于IO复杂型任务；对长进程有利，不利于短进程。
- 短作业优先（SJF）
对预计执行时间短的任务优先分配处理机（非抢占）。
优点是该算法相对于FCFS可改善平均周转时间。
缺点是该算法不利于长作业，执行长作业的进程可能长时间都得不到处理机的使用权。
- 最高响应比优先
该算法使用预计执行时间和等待时间定义了一个响应比，当等待时间相同时，预计执行时间越短响应比越高，则先被调度，照顾了短进程。
而长进程随着等待时间的增加，其响应比也会越来越高，所以长进程也有执行的机会，而不是像短作页优先那样存在长进程一直得不到执行机会的问题。
可以看到响应比与等待时间成正比，与预计执行时间成反比。 响应比 有关于 等待时间/预计执行时间
优点是在照顾短进程的同时也兼顾了长进程。
缺点是需要计算响应比，增加了开销。
- 多级反馈队列
该算法综合了几种算法的优点，算法定义了多级的队列，每个队列具有该队列对应的时间片大小。一开始将进程全部放到第一级队列中，并按照FCFS执行，当时间片结束后若进程已执行完毕则退出内存，若还没执行完毕，则将进程移入到下一级的队列中，等待在下一级队列中继续执行。
进程的调度顺序是从第一级到第N级，当前队列已无需要调度的进程时才进入到下一级队列进程的调度。
队列的时间片大小一般是慢慢变大，可以知道队列的优先级从第一级队列到第n级队列慢慢减小，同时时间片大小慢慢变大。
该算法是使用比较多的算法，因为他兼顾了短进程和长进程，并不必先知道进程的预计执行时间。
抢占式调度算法
- 时间片轮转法
每个进程被放置在一个队列里，并给予一定的时间片。从队头开始执行任务，当时间片用完时CPU发起时钟中断，调度程序暂停该进程的执行，并将该进程送至队列的末尾，同时将CPU交给当前的队头进程。
优点是平均响应时间短，且公平
缺点是不利于紧急进程，且由于进程的上下文切换，时间片需要选择一个较为合理的大小，否则会给系统带来很大的性能开销。
- 抢占式优先权调度算法
调度程序根据优先级的高低从就绪进程中挑选优先级较高的进程进入内存执行任务，同时如果此时有优先级更高的进程到来可以抢占处理机。
抢占式进程调度与进程优先级
在非抢占式的进程调度算法中，进程只有出错或者执行完任务才会释放CPU，将CPU交给其他进程使用。而在抢占式的进程调度算法中，CPU的使用权可以被抢占，当一个低优先级的进程在使用CPU执行任务时，此时一个高优先级进程的到来可以抢占运行中的低优先级进程的CPU使用权。
此时，操作系统向该低优先级的进程发起一个中断，将处理机分配该高优先级进程使用，当高优先级进程执行完任务后再恢复中断，将处理机交回给低优先级进程。
线程同步与线程安全
线程安全
在多线程编程中，各个线程访问同一个共享变量可能会带来线程安全问题和数据竞赛问题，原因是这些访问或修改操作都不是原子操作，在访问或修改过程中可能会获取到脏数据。
- 原子操作：no or all，要么不执行，要么一次执行完成的操作。由于开始执行后就不能被其他线程中断的特性，原子操作保证了线程安全。常见的实现机制是在执行前关闭中断，在执行结束后再开启中断。
线程同步机制
常见的线程同步解决方案有
临界区：临界区指的是一段并发执行的代码，将该断代码称为临界区。在进入临界区前关闭中断，在执行完毕后再开启中断。
锁
- 互斥锁（不可以重复加锁解锁）：互斥锁一般是用操作系统的mutex变量实现。互斥的定义是两者不能同时发生，常见的情景就是读-写问题，读跟写不能同时进行。
- 自旋锁（在获取锁时会进入忙等状态）
- 递归锁（可重复加锁解锁）
信号量
- 信号量是一类特殊的变量，是资源的抽象，他有两个原子操作，分别是signal()和wait()，这两个操作是原子性的，也就是原语。当wait操作申请不到信号量时，线程将会阻塞或忙等待，申请到时信号量-1
读写锁怎么实现
- 1.通过一个mutex（互斥锁）来实现读写锁，达到读写互斥。
- 2.通过信号量实现
- 3.通过一个同步串行队列实现
- 4.通过一把读锁和一把写锁以及一个互斥锁实现。
设计实现线程池
- 两个队列，一个队列存放初始的空闲线程，另一个队列存放正在执行程序的线程，两个线程的操作通过锁和信号量进行同步。
存储器管理与虚拟内存
内存分配
- 单一连续分配
- 固定分区分配
- 分区大小相等：缺乏灵活性，因为分区的大小都相等，可能会造成浪费以及分区大小不够的情况
- 分区大小不等
- 动态分区分配
- 以双向链表构成一个空闲分区表，动态给装入的程序分配内存
- 基于顺序搜索的动态分区分配算法
- 首次适应：从链表头开始查找，直至找到一块足够的内存大小，分配给程序后将剩下的内存块留在空闲分区表中。但这样会偏向于低地址，造成很多碎片
- 循环首次适应：每次查找从上次找到的下一个空闲分区开始查找，并可以循环查找，直至找到一个足够的空闲空间。
- 最佳适应：将空闲分区以从小到大的顺序排序，但这样会产生非常多的碎片
- 最坏适应：总是优先选择最大的一个空闲区，这样的算法产生碎片的可能性最小，同时效率也很高，然而容易导致内存中没有大的空闲分区。
- 基于索引的动态分区分配算法
- 快速适应算法：将空闲分区根据容量进行分类，每一类有自己的空闲分区链表，并且内存中设置一张索引表
- 伙伴系统算法
- 哈希表算法
内存回收
进程释放内存空间，回收机制将该块内存的首地址通过查找空闲分区链表的方式与其中的某块分区合并。
段页式存储管理
段页式存储管理将进程的内存地址分为各个段，段内使用分页的管理方式，结合了两种管理策略的优点。
装入时，需要进行逻辑地址->物理地址的映射。这个时候就是要将页表通过地址转换机制转换到物理地址，实现映射。由于我们知道页表的页内地址与物理地址是一一对应的，所以我们只需要做逻辑地址中的页号到物理内存中的块号的转换。
基本的地址变换机构
- 进程要访问某个逻辑地址的数据时，转换器（MMU）将逻辑地址分为页号和页内地址两个部分，并用页号去查询页表，此时如果页号超过页表长度会产生越界中断。查询到实际的物理块号后再使用页内地址，就获得到了实际的物理地址。
- 由于要查询页表->物理块号，所以该机制在访问数据时要访问两次内存，一次查询页表，一次实际访问。
具有快表的地址变换机构
- 为了加快页表号->物理块号的转换，降低访问数据的成本开销，增设一个具有查询能力的高速缓存寄存器，称为TLB（Translation Lookaside Buffer),转译后缓冲。
- 拥有TLB的机构在查询时会先将页表号送入TLB，如果查询到了对应的记录就直接返回，未命中的话再到页表查询，并将查询到的结果写入TLB中。
堆&栈 （分段管理的典型例子）
- 在计算机系统中，程序在运行时要进行进程的建立，系统会给进程分配内存，其中包括代码段、数据段、堆段、栈段、其他段。堆是我们在编写代码时主动申请的内存，栈由系统自动分配和销毁，存放临时变量、函数参数、函数返回值等数据。他们主要有以下几种不同
- 1.分配（管理）方式不同。堆由开发人员主动申请分配，栈有操作系统自动分配和释放。堆如果开发人员没有合理地释放会产生内存泄漏。
- 2.空间大小不同。堆理论上来说大小上限为虚拟地址空间的大小，远大于栈。
- 3.生长方向不同。由于在内存块中堆在栈的上面，所以堆向下生长，栈向上增长。
- 4.效率不同。栈的效率要远高于堆，因为栈的操作有硬件的支持。
- 5.内容不同。栈主要是函数返回地址、相关参数、局部变量和寄存器内容等数据，堆的内容由开发人员决定。
程序的装载/装入
程序是一段静态的二进制代码，在程序内部的地址空间是逻辑地址，所以在装入内存运行的时候必然要涉及到地址重定位，系统会给进程分配一段内存以及地址空间，程序需要将代码中的逻辑地址映射到该地址空间上。
装入时需要涉及到静态链接和动态链接两种情况。
静态链接
编译主要分为静态链接和动态链接。在编译器阶段进行的是静态链接，也就是在上文中提到的过程。这一阶段是将在前面生成的各种目标文件和各种库(or module in swift)链接起来，生成一个可执行文件mach-o。动态链接
静态链接是链接静态库，需要链接进Mach-o文件中，如果需要更新就需要重新编译一次，所以无法动态更新和加载。而动态链接是使用dyld动态加载动态库，可以实现动态地加载和更新。并且其他的进程、框架链接的都是同一个动态库，节省了内存。动态链接将动态链接库的符号等到装载时才进行重定位，而静态链接则在生成可执行文件前就完成了符号的重定位。
装载
一个程序从可执行文件到运行，基本都要经过装载和动态库链接两个阶段。由于在可执行文件生成前已经完成了静态库链接，所以在装载时所有的源代码和静态库已经完成了装载，而动态库链接则需要下文提到的动态链接来完成。
可执行文件，或者说程序，是一个静态的概念，而进程是一个动态的概念。每个程序在运行起来后，他对应的进程都会拥有独立的地址空间，而这个地址空间是由计算机硬件（CPU的位数）决定的，当然，进程只是以为自己拥有计算机整个的地址空间，实际上他是与其他的进程共享计算机的内存（虚拟化）
装载，就是把硬盘上的可执行文件映射到虚拟内存上的过程。
装载的过程，也可以当作是进程建立的过程，一般来说有以下几个步骤。
- 创建一个独立的虚拟地址空间
- 读取可执行文件头，建立虚拟地址空间与可执行文件之间的映射关系。（将可执行文件中的相对地址与虚拟地址空间的地址进行绑定）
- 将CPU的指令寄存器设为可执行文件的入口地址，交与CPU启动运行
iOS中我们常用的一些如UIKit、Foundation等框架都是使用动态链接的，而为了节省内存，系统将这些库放在动态库共享缓存区（Dyld shared cache)。
在mach-o文件中，属于动态库的符号会被标记为未定义，但他们的名字与路径会被记录下来。在运行时dyld会通过dlopen与dlsym导入动态库，并通过记录的路径找到对应的动态库，通过记录的名字找到对应的地址，进行符号与地址的绑定。
dlopen会将动态库映射到进程的虚拟地址空间中，由于载入的动态库中可能也会存在未定义的符号，也就是说该动态库还依赖了其他的动态库，这时会触发更多的动态库被载入，但dlopen可以决定是立刻载入这些依赖库还是延后载入。
dlopen打开动态库后返回的是引用的指针，dlsym的作用就是通过dlopen返回的动态库指针和函数符号，得到函数的地址然后使用。
动态链接解决了静态链接内存占用过多，只要有库修改就要重新编译打包的缺点，但同时也引入了新的问题。
- 结构复杂，动态链接将重定位推迟到运行时进行。
- 引入了安全问题，这也是我们能够进行PLT HOOK的基础
- 性能问题
而提到动态库链接，在iOS领域就必须提到我们的dyld。
虚拟存储器
虚拟存储器（虚拟内存）实现了内存扩充功能，但并不是从物理上实际地扩大了内存的容量，而是从逻辑上实现对内存的扩充。实际的实现是通过swap等技术实现的。
虚拟内存利用了时间局部性和空间局部性，在运行时仅将部分即将用到的页装入内存，在之后如果访问到还没装入的页，就发起缺页中断，将页调入内存。同时，利用swap技术，将一些暂时不用的页调出内存，等到需要时再调入。
当需要将页面调入内存而内存已无足够的空闲空间时，就面临需要在内存中的页面选择一个页面调出内存的情况。这个过程将其称为页面置换，对应的算法则是页面置换算法。一个良好的页面置换算法需要减少缺页率以及抖动。即减少同一页面很快地被换入又换出
页面置换算法
- 最佳置换算法
- 该算法预设已知未来所有页面置换的序列，所以他有着最好的性能，但这并不现实。所以他一般不作实际使用，而是作为一种参照标准，用来衡量其他置换算法的好坏。
- 先进先出算法
- 顾名思义，将先进入的页面先置换出去，一般不采用该算法。
- 最近最久未使用置换算法（LRU Least Recently Used）
- 该算法使用最近的过去来预测最近的未来，即挑选一个最近且最久没被使用过的页面，认为他在最近的未来里被使用的概率最小，将他调出内存。
- LRU算法的实现可以利用寄存器或者栈。当使用栈来实现时，当栈未满时将页面压入栈中，当访问到了栈中已有的页面（也就是内存中已有的页面）时，将该页面移至栈顶，当访问到栈中没有的页面且栈已满时，将栈底元素作为被置换的页面调出内存。所以其实际上是一个队列，元素从队头入队，从队尾出队，在书中将该结构形容为特殊的栈
- 最少使用置换算法（LFU Least Frequently Used）
- Clock置换算法
- 简单的Clock置换算法（NRU Not Recently Used)
- 设置一个访问位，将所有页面通过指针连成一个循环队列，当被访问时访问位置为1，在寻找页面淘汰时检查页的访问位，如果是0就将页面换出，如果是1则将他置0.
- 改进型的Clock置换算法
- 增加一个修改位，在淘汰时以
00->01的优先级来选择被淘汰的页面
- 增加一个修改位，在淘汰时以
- 简单的Clock置换算法（NRU Not Recently Used)
内存分类
虚拟内存(Virt) & 常驻内存(Resident) & 共享内存 (Shared)
- 虚拟内存：进程“需要的”虚拟内存大小，包括进程使用的库、代码、数据，以及malloc、new分配的堆空间和分配的栈空间等。假如申请了10MB Virt，但只使用了1MB，实际的Virt占用增长为10MB。
Virt = Res + Swap - 常驻内存：进程当前实际占用内存的大小，包括使用中的malloc、new分配的堆空间和分配的栈空间，但不包括swap out量。假如申请10MB内存，实际使用1MB，那么Res增长为1MB。Res = Code + Data
- 共享内存：共享库占用的大小。进程实际占用内存 = 常驻内存 - 共享内存
- 虚拟内存：进程“需要的”虚拟内存大小，包括进程使用的库、代码、数据，以及malloc、new分配的堆空间和分配的栈空间等。假如申请了10MB Virt，但只使用了1MB，实际的Virt占用增长为10MB。
Buffer & Cached
- Buffer：在需要向硬盘写入数据时，先将数据存入到Buffer，达到一定数据量后再统一写入，减少了硬盘的内存碎片和避免反复寻道。
- Cached：在从硬盘中读取数据时，在内存中开辟一片Cache区，将读取的数据存放在Cache中，如果在临近的时期再次读取该数据时就会直接在Cache中命中，提高数据读取的速度。（利用了时间局部性和空间局部性）
内存碎片 & 内存整理
- 内存碎片：在分配内存时，由于是按块分配，当申请的内存用不完一个块的大小时难免会产生一些剩余的小块内存，这些内存就是内存碎片。如果不经整理他们已经很难在之后再次被分配了。
- 内存整理：内存整理就是将这些内存碎片整理出来，使他们重新可用。常见的方式有将已分配的内存整块前移,将未分配的内存碎片整合成大块内存并重新分配出去。而在内存分配时也有常见的几种方法：首次适应，最佳适应，最坏适应等，他们产生碎片的情况也各不相同。