对操作系统概念的复习与总结。
进程和线程
进程
概念
程序本身是一个静态的概念，而进程的本质是程序的一次执行过程，是一个动态的概念，进程是资源分配的基本单位。进程控制块描述进程的基本信息和运行状态，用于对进程的管理和控制，包括进程标识符，进程当前状态，进程相应程序与数据地址，进程资源清单，进程优先级，CPU现场保护区，进程同步与通信机制，进程所在队列PCB的链接字（下一个PCB的首地址），与进程有关的其他信息（记账信息，占用的CPU时间）
状态
- 创建状态：进程正在创建，不能运行。操作系统在创建状态要进行分配和建立进程控制块，建立资源表格分配资源、加载程序并建立地址空间表。
- 运行态：该进程实际占用CPU
- 就绪态：可运行，但其它进程正在占用CPU而暂时停止
- 阻塞态：进程由于某种事件而暂时无法继续执行，放弃CPU处于暂停状态。如请求I/O，申请缓冲空间等。
- 退出状态：进程已结束运行，回收除进程控制块之外的其他资源
线程
概念
线程是进程的一个实体，是被系统独立调度和分派的基本单位，线程不拥有系统资源，但它可与同属一个进程的其他线程共享进程的资源。
区别
- 拥有资源：进程是资源分配的基本单位，线程不拥有系统资源，线程可以访问隶属进程的资源
- 调度：线程是调度的基本单位，同一进程中线程的切换不会引起进程切换，从一个进程内的线程切换到另一个进程中的线程时，会引起进程切换。
- 系统开销：创建进程或撤销时，系统要为之分配或回收资源，付出的开销远大于线程；类似的，进程的切换涉及进程CPU环境的保存和新进程CPU环境的设置，而线程切换只需保存和设置少量寄存器，开销很小。
- 通信：进程间通讯有管道、信号量、信号消息队列、socket等，线程间通讯通过通道、共享内存等来通信
调度算法
- 先来先服务：调度最先进入就绪队列的作业。有利于长作业，但不利于短作业。
- 短作业优先：调度估计运行时间最短的作业。长作业可能会饿死，永远得不到调度。
- 优先权调度：把CPU分配给就绪队列中优先权最高的进程，除了手动赋予优先权之外，还可以通过计算响应比作为优先权，响应比=(等待时间+要求服务时间)/要求服务时间。同时考虑了短作业优先和先来先服务，是一个比较好的折中方法，但是会增加系统开销。
- 时间片轮转法：类似于先来先服务，每次调度时，CPU分配给首进程，但是只执行一个时间片，当时间片用完时，由计时器发出中断请求，调度程序停止该进程，并将它送往就绪队列的末尾，之后执行相同的过程。
- 多级反馈队列调度：当一个作业需要100个时间片的时候，使用时间片轮转法会交换100次，多级反馈队列为了解决这个问题，设置了多个队列，每个队列有不同的时间片大小，并且有不同的优先级。第一个队列优先级最高，时间片大小最小。新进程首先先在第一个队列末尾，当执行完第一个队列的一个时间片后，进程还没有结束，则转入到第二队列末尾，以此类推。当高优先级的队列空闲时才执行下一个队列的作业。
IPC通信方式
- 管道（pipe）：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据，读进程在管道的首端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道有三种：
- 普通管道：有两个限制：一是只支持半双工通信方式，即只能单向传输；二是只能在父子进程之间使用；
- 流管道：去除第一个限制，支持双向传输；
- 命名管道：去除第二个限制，可以在不相关进程之间进行通信。
- 命名管道 (named pipe)： 命名管道也是半双工的通信方式，它克服了管道没有名字的限制，并且它允许无亲缘关系进程间的通信。命令管道在文件系统中有对应的文件名，命名管道通过命令mkfifo或系统调用mkfifo来创建。
- 信号量( semophore )： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
- 消息队列( message queue )： 消息队列是由消息的链表结构实现，存放在内核中并由消息队列标识符标识。有足够权限的进程可以向队列中添加消息，被赋予读权限的进程则可以读走队列中的消息。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
- 信号 ( sinal )：信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。除了用于进程通信外，进程还可以发送信号给进程本身。
- 共享内存( shared memory )：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的IPC方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号量配合使用，来实现进程间的同步和通信。
- 套接字( socket )： 也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同机器间的进程通信。
中断分类
- 外中断：由 CPU 执行指令以外的事件引起，如 I/O 完成中断
- 异常：由 CPU 执行指令的内部事件引起，如非法操作码、地址越界
- 陷入：在用户程序中使用系统调用
死锁
临界区
对临界资源进行访问的那段代码称为临界区。 为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
死锁概念
是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。
活锁
活锁指的是任务或者执行者没有被阻塞，由于某些条件没有满足，导致一直重复尝试，失败，尝试，失败。
死锁条件
- 互斥条件:一个资源每次只能被一个进程使用
- 不可剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺
- 请求与保持条件:一个进程因请求资源而阻塞时，对已获得的资源保持不放
- 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系
死锁预防
- 破坏互斥条件。允许某些进程(线程)同时访问某些资源，但有的资源不允许同时被访问如打印机等。例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
- 破坏不可抢占条件:即允许进程强行从占有者那里夺取某些资源。这种预防方法实现起来困难，会降低系统性能。
- 破坏占有且申请条件。可以实行预先分配策略，即进程在运行前一次性地向系统申请它所需要的全部资源。如果当前进程所需的全部资源得不到满足，则不分配任何资源。只有当系统能够满足当前的全部资源得到满足时，才一次性将所有申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源，所以不会发生占有资源又重新申请资源的现象，因此不会发生死锁。但是有以下缺点：
- 在许多情况下，一个进程在执行之前不可能知道它所需的全部资源。这是由于进程在执行时是动态的，不可预测的。
- 资源利用率低。无论所分配资源何时用到，一个进程只有在占有所需的全部资源后才能执行。即使有些资源最后才被该进程用到一次，但该进程在生存期间一直占有它们，造成长期占有。
- 降低了进程的并发性。因为资源有限，又加上存在浪费，能分配到所需全部资源的进程个数必然少了。
- 破坏循环等待条件。实行资源有序分配策略。采用这种策略即把资源事先分类编号，按号分配。所有进程对资源的请求必须严格按资源需要递增的顺序提出。进程占用小好资源，才能申请大号资源，就不会产生环路。这种策略与前面的策略相比，资源的利用率和系统吞吐量都有很大提高，但是也存在以下缺点：
- 限制了进程对资源的请求，同时系统给所有资源合理编号也是件困难事，并增加了系统开销。
死锁的避免
银行家算法可以找到当前资源申请的安全序列，基本思想是在分配资源之前，判断系统是否是安全的，若是才分配。
银行家算法的数据结构：
- 可利用资源向量Available：表示每个资源的可利用数
- 最大需求矩阵Max：表示每个进程对各个资源的最大需求数
- 分配矩阵Allocation：表示进程已经分配的资源数
- 需求矩阵Need：表示进程还需要的资源数，可以通过2，3相减计算得来
银行家算法过程： Request_i是进程P_i的请求向量，发出资源请求后，进行下述步骤检查：
- 如果Request < Need，转向2，否则认为出错，因为所需的资源已经超过所宣布的资源最大值
- 如果Request < Available，转向3，否则表示尚无足够资源，P_i需等待
- 系统试探着把资源分配给进程P_i，并修改数据结构的值：Available = Available - Request;Allocation = Allocation + Request;Need = Need - Request
- 检查系统是否处于安全状态，若安全才正式把资源分配给P_i，否则恢复到资源分配之前的状态，让P_i等待。
安全性算法：
- 设置两个向量，1）工作向量Work：表示系统可提供给进程运行的资源，初始值为Available。2）Finish：表示系统是否有足够的资源分配给进程，使之运行完成，初始值为false。
- 从进程集合中找到一个能满足下述条件的进程：Finish = false和Need <= Work。若找到，执行3，否则执行4.
- 当进程P_i获得资源后，可顺利执行，直至完成，并释放分给它的所有资源，故修改数据结构：Work = Work + Allocation;Finish = true。之后回到第2步
- 如果所有进程Finish均为true则是安全状态，否则是不安全状态
执行完安全性算法就可以找到一条安全序列，安全序列不唯一。
死锁的解除
一旦检测出死锁，就应立即釆取相应的措施，以解除死锁。 死锁解除的主要方法有：
- 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于资源匮乏的状态。
- 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
- 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。
内存管理
虚拟内存
物理内存:在应用中，自然是顾名思义，物理上，真实的插在板子上的内存是多大就是多大了。而在CPU中的概念，物理内存就是CPU的地址线可以直接进行寻址的内存空间大小。
虚拟内存:它使得应用程序认为它拥有连续的可用的内存(一个连续完整的地址空间),而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。
分页存储
将程序的逻辑地址空间划分为固定大小的页（page），而物理内存划分为同样大小的页框（page frame）或物理块,每个物理块的大小一般取2的整数幂。程序加载时，可将任意一页放人内存中任意一个页框，这些页框不必连续，从而实现了离散分配。该方法需要CPU的硬件支持，来实现逻辑地址和物理地址之间的映射。在页式存储管理方式中地址结构由两部构成，前一部分是页号，后一部分为页内地址w（位移量）。
逻辑地址到物理地址变化原理：CPU中的内存管理单元(MMU)按逻辑页号通过查进程页表得到物理页框号，将物理页框号与页内地址相加形成物理地址。
优点：
- 没有外碎片，每个内碎片不超过页大小，提高内存的利用率。
- 一个程序不必连续存放。
- 便于改变程序占用空间的大小(主要指随着程序运行，动态生成的数据增多，所要求的地址空间相应增长)。
缺点：
- 无论数据有多少，都只能按照页面大小分配，容易产生内部碎片（一个页可能填充不满，造成浪费。
- 不能体现程序逻辑
- 分页方式的缺点是页长与程序的逻辑大小不相关
- 不利于编程时的独立性，并给换入换出处理、存储保护和存储共享等操作造成麻烦。
页面置换算法
程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。
页面置换算法和缓存淘汰策略类似。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。
页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。
- 最佳（Optimal）
所选择的被换出页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率，但是这是一种理论上的算法，因为无法预测一个页面多长时间不被访问。
以70120304230321201701页面引用序列为例，系统为进程分配了3个物理块，开始运行是，先将7，0，1三个页面装入内存，之后访问页面2时，产生页面中断，会将页面7换出，因为7再次被访问的时间最长。
- 最近最久未使用（LRU,Least Recently Used）
虽然无法知道将来要使用的页面情况，但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面时最近最久未访问的。因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。
以47071012116为页面引用序列为例：
- 最近未使用（NRU,Not Recently Used）
首先，系统为毎一页面设置了两个状态位。当页面被访问 (读或写) 时设置 R 位; 当页面 (即修改页面) 被写入时设置 M 位。当启动一个进程时，它的所有页面的两个位都由操作系统设置成 0，R 位被定期地 (比如在每次时钟中断时) 清零，以区别最近没有被访问的页面和被访问的页面。 当发生缺页中断时，操作系统检査所有的页面并根据它们当前的 R 位和 M 位的值，把它们分为 4 类: 第 0 类: 没有被访问，没有被修改 第 1 类: 没有被访问，已被修改 第 2 类: 已被访问，没有被修改 第 3 类: 已被访问，已被修改 NRU 算法随机地从类编号最小的非空类中挑选一个页面淘汰之。
- 先进先出（FIFO,First In First Out）
选择换出的页面是最先进入的页面，最早调入内存的页，其不再被使用的可能性比刚调入内存的可能性大。
- 第二次机会算法
FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改。
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
第二次机会算法就是寻找一个最近的时钟间隔以来没有被访问过的页面。如果所有的页面都被访问过了，该算法就简化为纯粹的 FIFO 算法。
- 时钟（Clock）
第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面链接起来，再使用一个指针指向最老的页面。
分段存储
将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。通常，程序员把子程序、操作数和常数等不同类型的数据划分到不同的段中（写c程序时会用到），并且每个程序可以有多个相同类型的段。段表本身也是一个段，可以存在辅存中，但一般是驻留在主存中。在段式虚拟存储系统中，虚拟地址由段号和段内地址组成，虚拟地址到实存地址的变换通过段表来实现。在段式管理系统中，整个进程的地址空间是二维的，即其逻辑地址由段号和段内地址两部分组成。
优点：
- 段的逻辑独立性使其易于编译、管理、修改和保护，也便于多道程序共享。
- 段长可以根据需要动态改变，允许自由调度，以便有效利用主存空间。
- 方便编程，分段共享，分段保护，动态链接，动态增长
缺点：
- 主存空间分配比较麻烦。
- 容易在段间留下许多碎片（外部碎片），造成存储空间利用率降低。
- 由于段长不一定是2的整数次幂，因而不能简单地像分页方式那样用虚拟地址和实存地址的最低若干二进制位作为段内地址，并与段号进行直接拼接，必须用加法操作通过段起址与段内地址的求和运算得到物理地址。因此，段式存储管理比页式存储管理方式需要更多的硬件支持。
分页与分段的区别
- 页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；段则是信息的逻辑单位，它含有一组其意义相对完整的信息，分段的目的是为了能更好地满足用户的需要。
- 页的大小固定且由系统决定，由系统把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而在系统中只能有一种大小的页面；而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
- 分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址是，即需给出段名，又需给出段内地址。
- 分页信息很难保护和共享、分段存储按逻辑存储所以容易实现对段的保存和共享。
段页存储
程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。 为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块。 它首先将程序按其逻辑结构划分为若干个大小不等的逻辑段，然后再将每个逻辑段划分为若干个大小相等的逻辑页。主存空间也划分为若干个同样大小的物理页。辅存和主存之间的信息调度以页为基本传送单位，每个程序段对应一个段表，每页对应一个页表。
段页式系统中，作业的地址结构包含三部分的内容：段号，页号，页内位移量 CPU访问时，段表指示每段对应的页表地址，每一段的页表确定页所在的主存空间的位置，最后与页表内地址拼接，确定CPU要访问单元的物理地址。 段页存储管理方式综合了段式管理和页式管理的优点，但需要经过两级查表才能完成地址转换，消耗时间多。
优点：
- 它提供了大量的虚拟存储空间。
- 能有效地利用主存，为组织多道程序运行提供了方便。
缺点：
- 增加了硬件成本、系统的复杂性和管理上的开消。
- 存在着系统发生抖动的危险。
- 存在着内碎片。
- 还有各种表格要占用主存空间。
虚拟地址、逻辑地址。线性地址、物理地址的区别
- 虚拟地址：指的是由程序产生的由段选择符和段内偏移地址两个部分组成的地址。为什么叫它是虚拟的地址呢？因为这两部分组成的地址并没有直接访问物理内存，而是要通过分段地址的变换机构处理或映射后才会对应到相应的物理内存地址。
- 逻辑地址：指由程序产生的与段相关的偏移地址部分。不过有些资料是直接把逻辑地址当成虚拟地址，两者并没有明确的界限。
- 线性地址：指的是虚拟地址到物理地址变换之间的中间层，是处理器可寻指的内存空间（称为线性地址空间）中的地址。程序代码会产生逻辑地址，或者说是段中的偏移地址，加上相应段的基地址就生成了一个线性地址。如果启用了分页机制，那么线性地址可以再经过变换产生物理地址。若是没有采用分页机制，那么线性地址就是物理地址。
- 物理地址：指的是现在CPU外部地址总线上的寻址物理内存的地址信号，是地址变换的最终结果
堆和栈的区别
栈区：由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。
堆区：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收 。
静态链接库和动态链接库的区别
目的都是共享代码。 静态链接库在编译连接的时候就被复制到程序中，包含在最后的可执行文件中。 而动态链接库没有包含在可执行文件中，多个进程共享一个文件。
磁盘调度
读写一个磁盘块的时间的影响因素有：
- 旋转时间（主轴旋转磁盘，使得磁头移动到适当的扇区上）
- 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
- 实际的数据传输时间
其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。
- 先来先服务（FCFS,First Come First Served）
按照磁盘请求的顺序进行调度。 优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。
- 最短寻道时间优先（SSTF,Shortest Seek Time First）
优先调度与当前磁头所在磁道距离最近的磁道。 虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两边的磁道请求更容易出现饥饿现象。
- 电梯算法/扫描算法（SCAN）
电梯算法（扫描算法）和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。 因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。
- 循环扫描算法（CSCAN）
电梯算法反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长 循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单向移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。