浅析计算机操作系统原理
1.操作系统概述
我们从功能、组成、特征、结构4个方面对操作系统进行介绍。
1）功能：
从用户角度讲，操作系统是一个管理应用程序的控制程序，管理应用程序；
从资源管理角度讲，操作系统是管理外设、分配资源，对底层硬件管理服务的资源管理器。
操作系统把CPU、内存、硬盘抽象成进程、地址空间、文件来供应用程序使用。层次上在硬件和应用程序之间。开机启动的进程称为守护进程，开机不启动的进程需要用户跟操作系统交互，交互工具为shell，linux、Windows、安卓的界面都属于shell，而不是内核，我们主要研究在shell之下的kernel。
2）组成：
kernel-操作系统内部组件，包括：CPU调度器；物理内存管理；虚拟内存管理；文件系统管理；中断处理与设备驱动。
3）特征：
OS kernel：并发；共享（同时访问、互斥共享）；虚拟（利用多道程序设计技术，让每个用户都认为计算机专门为它服务）；异步（程序的执行是断断续续的，只要运行环境相同，不同次执行输出的结果相同）。
并发：在一段时间内有多个程序运行
并行：在同一个时间点有多个程序执行（有多个CPU才能并行）
时钟信号中断帮助操作系统完成时间片的分时调度
4）结构：
单体：由各模块组成一个整体，模块之间通过函数调用来实现访问
微内核：尽量把内核功能移动到用户空间，内核只放中断处理、消息传递，文件系统、内存管理、网络协议栈都是放在外围以进程的形式存在，服务之间不是通过函数调用而是通过内核的消息传递机制实现，是一种松耦合架构。通过地址隔离，不同应用程序无法恶意破坏对方的地址空间，架构有很强的灵活性，但是内核消息传递牺牲了一部分性能。
外核：内核分成两块，一块跟硬件打交道，完成硬件的复制，另一个libos跟应用打交道，每一个libos更一个专门的应用打交道，都可以访问sokernel。
虚拟化：榨取硬件性能的一种方式，使得多操作系统共享硬件资源。图一传统架构，图二有VMM的虚拟架构，VMM将单独的机器接口转换成很多的幻象，每个接口（虚拟机）是一个原始计算机系统的有效副本，并完成所有的处理器指令。
2.操作系统启动、中断、异常、系统调用
操作系统启动：
DISK：存放OS
BIOS：基本I/O处理系统，POST（加电自检），寻找显卡和执行BIOS，检查完毕后，把BootLoader从硬盘放到内存中，BootLoader一般放到硬盘第一个区间。
Bootloader：从硬盘加载OS到内存，CPU的控制权由BootLoader掌控，找到操作系统的起始扇区和操作系统长度，把操作系统读到内存中，CPU控制权交给OS。
中断、异常、系统调用：
1）特征：
面向外设使用中断和I/O来处理，面向应用程序使用系统调用和异常来提供相应功能。
系统调用：应用程序主动向OS提出服务请求。system call
异常：应用程序在执行过程中产生意想不到的问题，使得操作系统不得不完成相应的操作。
中断：来源于外设，不同硬件设备的计时器和网络中断
在计算机运行中，内核时被信任的第三方，只有内核可以执行特权指令。
2）三者区别：
产生源头：中断：外设；异常：应用程序意想不到的行为；系统调用：应用程序请求操作系统提供服务。
处理时间：中断：异步（不知道什么时候产生）；异常：同步；系统调用：发出请求式同步，返回结果是异步或同步。
响应：中断：持续，对用户应用程序是透明的；异常：杀死或重新执行意想不到的程序指令；系统调用：等待和持续
处理动作：中断：（1）硬件：设置中断标记，将内部、外部事件设置中断标记，中断号；（2）软件：保存被打断执行现场，便于恢复；根据中断号处理相应的中断，处理完之后清楚中断标记，会不被打断程序现场。
异常：异常ID号，杀死程序或服务弥补工作重新执行应用程序指令。
系统调用：程序访问主要通过高层次的API而不是直接进行系统调用，如Win32 API、POSIX API等，通常情况下，与每个系统调用相关的序号，系统调用接口根据这些序号来维护表的索引；系统调用接口调用内核态中预期的系统调用，并返回系统调用的状态和任何其他的返回值；用户不需要知道系统调用是如何实现的，只需要获取API和了解操作系统将返回什么结果，操作系统接口的细节大部分隐藏在API中，通过运行程序支持的库来管理（包括编译器的库来创建函数集合），应用程序发生系统调用的时候会切换到内核态，会有新的堆栈，增加系统开销，但是安全。
跨越操作系统边界的开销：在执行时间上的开销超过程序调用。
开销：建立中断/异常/系统调用号与对应服务例程映射关系的初始化开销；建立内核堆栈；验证参数；内核态映射到用户态地址空间更新页面映射权限；内核独立地址空间，TLB。
3.计算机体系结构和内存分层体系
在操作系统中管理内存的不同办法：程序重定位、分段、分页、虚拟内存、按需分页虚拟内存等，内存管理实现高度依赖于硬件，即操作系统必须知道内存架构，通过MMU处理CPU的内存访问请求。
地址空间：分为物理地址空间、逻辑地址空间（运行的程序看到的空间），CPU通过MMU实现逻辑地址到物理地址的映射。
地址转换大致过程：程序的变量是一种符号表示的内存地址，通过编译器变成逻辑内存地址，再通过CPU的MMU单元映射到物理内存地址。操作系统设置逻辑地址空间的基址和界限，对程序进行地址安全检查，保证程序内存访问安全。
内存分配：1）连续地址分配；2）非连续地址分配
1）连续地址分配：首次适配，最优适配，最差适配
该方法会产生外部碎片，针对于外部碎片主要有压缩式内存碎片管理和交换式碎片管理两种优化方法。
2）非连续地址分配：解决连续内存分配外碎片问题，主要有分段式、分页式、段页式内存分配方法
分段：把主程序、子程序、共享程序、栈、堆等根据应用程序运行特点不同，从堆、运行栈、程序数据、库、用户代码等不同层面把程序划分成不同的段，操作系统建设和维护包含起始地址和长度的段表，通过在逻辑地址中设置段号和段内位移，之后通过MMU映射到物理内存空间。
分页：分页需要操作系统初始化时建立和维护页表，页表中存储页号和页内偏移，把逻辑地址和物理地址都划分成大小固定且相等的页，页帧是物理页，页帧由页帧号和页帧偏移组成，page是逻辑页，由页号和页内偏移组成，把程序分成页，CPU通过查找pagetable页号获取帧号，逻辑页内偏移和物理页内偏移相同，帧号加页内偏移获得物理地址。
页表page-table：每个程序有一个页表来实现逻辑地址到物理地址的映射，如果页表很大，那么其不适合放到CPU中，放到内存中也会开销很大。目前使用两种方法，来缓解页表很大造成的开销：1）TLB：内存管理单元MMU中有TLB缓存，TLB使用关联内存实现，具备快速访问性能，如果TLB命中，物理页号快速获取，如果没有，对应表项更新到TLB中。2）多级页表：把page-num分成两块，先查找一级页表获取二级页表起始地址，找到二级页表项获取对应帧号frame-num，映射到最终物理地址。通过这种方式，使不存在物理逻辑映射关系的pagetable不需要放到内存中。多级页表也是类似实现原理。
段页式：结合分段和分页，先把程序以分段的形式来进行划分，再在分段基础上就不同段进行分页划分，完成逻辑地址到物理地址的映射。
4.虚拟内存技术
1）覆盖技术：把程序按照自身的逻辑结构，划分为若干个功能相对独立的程序模块，不会同时执行的模块共享同一块内存区域，按照时间先后顺序来运行。用分时的方式来共享某一块内存空间，需要常驻内存的功能模块进行管理和调度。覆盖在如何划分覆盖关系、换入换出的时间开销都比较大。
2）交换技术：将暂时不能 运行的程序放到外存，从而获得空闲内存空间。操作系统把一个进程的整个地址空间的内容保存到外存中（换出swap out），而将外存中的某个进程的地址空间读到内存中（换入swap in）。换入换出内容的大小为整个程序的地址空间。换入换出的开销比较大，在确实内存不够的情况下才使用这种方式，并减少换入换出的次数。
3）虚存技术：（虚拟内存管理技术）根据程序的局部性原理，在程序的执行过程中的一个较短时间内，所执行的指令地址和指令操作地址局限在一定区域内，把执行的程序段存入到物理内存中，没执行到的程序段放到外存中，以分段或分页等形式。以分页为例，在其基础上需要增加请求调页和页面置换功能。即在用户程序调入内存中的时候，不是将所有页面都装入内存，而只是装入部分页面就可以启动程序，在运行过程中，如果发现要运行的程序或要访问的数据不在内存中，则向系统发出缺页中断，系统在处理这个中断时，将外存中响应的页面调入内存，使得该程序能够继续运行。
虚拟内存管理的页面置换算法：
功能：当缺页中断发生，需要调入新的页面而内存已满是，选择内存当中哪个物理页面被置换。
目标：尽可能地减少页面的换入换出次数（即缺页中断次数）。具体来说，把未来不再使用的或短时期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。
页面锁定：在页表中添加锁定标志位，把用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程锁定不进行换入换出。
（1）局部页置换算法：局部页面置换算法只置换本进程内的物理页面，进程中一个页面进内存，就代表一个页面已经被替换出内存，所以一个进程所占用的物理页面的总数是确定的。
1）最优页面置换算法：当一个缺页中断发生时，对于保存在内存中的每一个逻辑页面，计算在它下一次访问之前需要等待的时间，从中选择等待时间最长的页面置换。一种理想情况，实际系统中无法实现。根据未来推测未来。
2）先见先出算法：选择在内存中驻留时间最长的页面并置换。性能较差，换出的页可能是经常访问的页，且有Belady现象。
3）最近最久未使用算法：当缺页中断时，选择最久未使用的页面并置换。最优置换算法的一个近似，根据过去推测未来。
4）时钟页面置换算法：跟LRU类似，对FIFO的一种改进，用页表项中的访问位，当一个页面被装入内存时，把该位初始化为0，如果该页面被访问，则设为1，把各个页面组织成环形链表（类似时钟表面），把指针执行最老的页面（最先进来），当发生缺页中断时，考察指针所指向的最老页面，如果它的访问位为0，立即换出，如果访问位为1则置为0，指针往下移动一格，直到找到被置换页面，然后指针移动到它的下一格。
二次机会法：修改clock算法，使它允许脏页总是在一次时钟头扫描中保留下来，同时使用脏位和使用位指导置换，减少对硬盘的访问。
5）最不常用算法：当一个缺页中断发生时，选择访问次数最少的那个页面，并置换。
Belady现象：
Belady现象：在采用FIFO算法时，有时会出现分配的物理页面增加，缺页率反而提高的异常现象。FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，与置换算法的目标是不一致的（即替换较少使用的页面），因此被置换出去的页面并不一定是进程不会访问的。
LRU、FIFO、Clock的比较：
LRU算法和FIFO本质上都是先进先出的思路，只不过LRU是针对页面的最近访问时间来进行排序，所以需要在每一次页面访问的时候动态地调整各个页面之间的先后顺序；而FIFO是针对页面内存的时间来进行排序，这个时间是固定不变的，所以各页面之间的先后顺序是固定的。如果一个页面在进入内存后没有被访问，那么它的最近访问时间就是它进入内存的时间。换句话说，如果内存中的所有页面都未访问过，那么LRU算法就退化为FIFO算法。Clock算法是LRU的一种近似，用了一些硬件的bit来模拟访问时间和先后顺序，开销较小。
（2）全局页置换算法：全局页面置换算法置换内存中所有可换出的物理页面，即换进内存的是进程A的页面，换出内存的可能是进程B的页面，所以进程在内存中占用的页面总数是可变的。
1）工作集置换算法：工作集表示为二元函数W（t,△），t为当前时刻，△为页面访问时间窗口，工作集就是在t-△到t的这段时间内所有访问页面的集合。常驻集是在当前时刻，进程实际驻留在内存当中的页面集合。工作集置换算法就是说每次访问内存时，就把不存在于工作集中的页面从内存中换出，不管这次访问缺页与否。
2）缺页率页面置换算法：访问内存不缺页时，就把相应的页面的引用为设置为1。缺页时，就把当前时间和上次缺页的时间相减计算时间间隔，如果时间间隔大于给定窗口的话，就说明缺页率过低了，进程在内存中的物理页面数太多了，进程并发度下降，CPU效率会降低，需要置换出去一些页面。如果时间间隔小于给定窗口的话，就说明缺页率过高，把缺页的添加进内存。缺页率置换算法只在缺页时才进行页面的增加或减少。在缺页中断的时候可以把置换的过程部分提交给硬件进行处理，提高了性能。
抖动问题：随着驻留内存的进程数目增加，分配给每个进程的物理页面数不断减小，缺页率不断上升，造成进程物理页面太少，不能包含工作集，造成大量缺页，频繁置换，进程运行速度变慢等问题。操作系统需要选择适当的进程数目和进程需要的物理页面数。
5.进程和线程
进程
进程：一个具有独立功能的程序在一个数据集合上的一次动态的执行过程。
进程包括：程序的代码；程序处理的数据；程序计数器中的值，指示下一条将运行的指令；一组通用的寄存器的值，堆栈；一组系统资源等一个运行的程序的所有状态信息。
程序是产生进程的基础，程序的每次运行构成不同的进程，进程是程序功能的体现。多次执行一个程序可以产生多个进程，通过调用关系，一个进程可以包括多个程序。
进程是动态的，程序是静态的；程序是有序的代码集合，进程是程序的执行，进程拥有核心态/用户态。进程是一个状态变化过程，进程是暂时的，程序是永久的。CPU可以根据具体情况切换不同的进程，完成不同的功能。
进程的特点：
1）动态性：可动态地创建、结束进程；
2）并发性：进程可以被独立调度并占用处理机运行；
3）独立性：不同进程的工作不相影响；
4）制约性：因访问共享数据/资源或进程间同步产生制约。
操作系统为每一个进程维护了一个PCB（Process Control Block），用来保存与该进程有关的各种状态信息。
进程控制结构
进程控制块PCB有以下三大类信息：
1）进程标识信息。2）处理机状态信息保存区。3）进程控制信息。
进程的生命周期：
进程创建：系统初始化；用户请求创建一个新进程；正在运行的进程执行了创建进程的系统调用。
进程运行：内核选择一个就绪的进程，让它占用处理机并执行。
进程等待（阻塞）：1、请求并等待系统服务，无法马上完成。2、启动某种操作，无法马上完成。3、需要数据没有到达。进程只能自己阻塞自己，因为只有进程自身才能知道何时需要等待某种事件的发生。
进程唤醒：1、被阻塞进程需要的资源可以满足。2、被阻塞进程等待的事件到达。3、将该进程的PCB插入到就绪队列。进程只能被别的进程或操作系统唤醒。
进程结束：1、正常退出。2、错误退出。3、致命错误。4、被其他进程杀死。
进程的基本状态：
1）运行状态：一个进程正在处理机上运行时。
2）就绪状态：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行。
3）等待状态：一个进程正在等待某一事件而暂停运行时。
4）创建状态：一个进程正在创建，还没被转到就绪状态之前。
5）结束状态：一个进程正在从操作系统中消失的状态。
进程挂起：进程在挂起时，意味着进程没有占用内存空间，挂起状态的进程映射到磁盘空间上。
阻塞挂起状态：进程在外存等待某事件的出现。
就绪挂起状态：进程在外存，但只要进入内存即可运行。
线程
线程是进程当中的一条执行流程。
进程管理资源，把进程的执行过程拆出来由线程执行，进程由资源管理和线程执行。进程可以有多个线程，线程可以共享进程的系统资源。线程控制结构TCB。
优点：一个进程可以同时存在多个线程；各线程之间可以并发执行；各线程之间可以共享地址空间和文件等资源。
缺点：一个线程崩溃会导致其所属进程所有线程的崩溃。
进程线程比较：
进程是资源分配的单位，线程是CPU调度的单位。进程拥有完成的资源平台，线程只独享不可少的资源，如寄存器和栈；线程同样具有就绪、阻塞、执行三种基本状态；线程能减少并发执行的时间和空间开销，线程创建时间比进程短，线程终止时间比进程短，同一进程内的线程切换时间比进程短，由于同一个进程的各线程共享内存和文件资源，可直接进行不通过内核的通信。
上下文：context，寄存器中的信息。
6.CPU调度
多个进程同时处于内存，当一个进程必须等待时，OS从该进程拿走CPU使用权交给其他进程，进程执行从一个IO区间(I/O burst)开始，随后进入一个CPU区间(CPU burst)并反复，进程循环地在CPU执行和I/O等待两个状态间切换，直到通过系统请求终止最后一个CPU burst。
抢占&非抢占
CPU调度决策发生在4种情况下：
1) 进程从运行(running)状态切换到等待(waiting)状态；
2) 进程从运行(running)状态切换到就绪(ready)状态；
3) 进程从等待(waiting)状态切换到就绪(ready)状态；
4) 进程终止
非抢占(nonpreemptive)调度方案：a.k.a. 协作(cooperative)调度方案，一旦CPU分配给一个进程，该进程会一直使用CPU直到进程终止或切换到等待状态，该方案中调度只发生在1、4两种情况下。
否则称为抢占(preemptive)调度方案。
调度准则
用于分析比较CPU调度算法的准则可包括
1）CPU使用率(CPU utilization)：理论上为0%~100%，真实系统一般为40%~90%。
2）吞吐量(Throughput)：一个时间单位内所完成进程的数量。
3）周转时间(Turnaround time)：一个进程从提交到完成的所用时间。
4）等待时间(Waiting time)：进程在就绪队列中等待所用时间之和。
5）响应时间(response time)：从提交请求到产生第一响应的所用时间。
需要使CPU utilization和throughput最大化，turnaround time、waiting time和response time最小化。绝大多数情况下需要优化平均值，有些情况下需要优化最大值、最小值或response time方差等。
调度算法
1）FCFS，先到先服务调度算法(first-come, first-served (FCFS) scheduling algorithm)：先请求CPU的进程先分配到CPU，通常用FIFO队列实现。 FCFS策略平均等待时间通常较长，不适用于time-sharing系统。
2）SJF （提供最短平均等待时间）最短作业有限调度算法(shortest-job-first (SJF) scheduling algorithm)：每个进程与其下一个CPU burst关联。当CPU空闲时，将它分配给具有最短CPU burst的进程。
3）优先级调度算法(priority scheduling algorithm)：每个进程都与一个优先级(priority)关联，CPU被分配给具有最高priority的进程，相同priority的进程按FCFS顺序调度。
4）RR （适合分时/交互系统）
时间片(time quantum, a.k.a. time slice)：一个较小的时间单元，通常为10~100ms。
轮转法调度算法(round-robin (RR) scheduling algorithm)：专门为time-sharing系统设计，CPU调度程序循环就绪队列，为每个进程分配不超过一个time quantum的CPU。
5）多级队列调度算法(multilevel queue scheduling algorithm)：将就绪队列划分成多个独立队列，每个队列有自己的调度算法。进程根据自身属性被永久分配到对应的一个队列。常用模型：前台交互队列使用RR，和后台批处理队列使用FCFS。
6）多级反馈队列调度算法(multilevel feedback queue scheduling algorithm)：根据CPU burst的特点区分进程。如果进程使用过多CPU时间则转移到更低队列，在低priority队列中等待时间过长的进程可被转移到高priority队列。
7.临界区和信号量
临界区
多个线程在同时调用函数时可能会产生问题，可能会产生问题的这部分代码称之为临界区（Critical Section）。
根据临界区是否会产生问题，函数可分为：
- 线程安全函数（Threa-safe function）
- 非线程安全函数（Thread-unsafe function）
线程安全函数被多个线程同时调用也没有问题，但是非线程安全函数就可能会引发问题。
大多数标准函数都是线程安全函数，我们不需要自己区分线程安全函数与非线程安全函数。
线程存在的问题和临界区
任何内存空间只要是被线程同时访问，就有可能发生问题。为了解决这个临界区的问题其实很简单，就是不让不同线程同时访问一个变量。而实现这个就是线程同步。
线程同步可以解决两方面的情况：
- 不能同时访问同一内存空间
- 需要指定访问同一内存空间的线程执行顺序
互斥量 Mutual Exclusion
表示不允许多个线程同时访问，互斥量主要用于解决线程同步的问题。
我们通过互斥量实现互斥锁，在一个线程在访问变量时就将他锁住，而等到访问完毕再释放这把锁。当其他线程预备进入临界区时，如果发现有其他线程已经进入临界区。将使这个函数阻塞，一直到那个线程结束使用临界区。如果线程退出临界区时，没有调用unlock函数，那么其他线程将一直处于阻塞状态，这种情况就是死锁。
互斥量lock，unlock函数的频繁调用使程序的执行效率降低，所以应该对于不同的程序适当的考虑是应该扩大还是缩小临界区。
信号量 Semaphore
与互斥量的开锁与解锁相比。信号量就是给一个信号，看是否复合条件能通过，当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。信号量本质上是一个计数器（不设置全局变量是因为进程间是相互独立的，而这不一定能看到，看到也不能保证++引用计数为原子操作）,用于多进程对共享数据对象的读取，它和管道有所不同，它不以传送数据为主要目的，它主要是用来保护共享资源（信号量也属于临界资源），使得资源在一个时刻只有一个进程独享。一般来说，信号量S>=0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S<0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。
PV操作是典型的同步机制之一， PV操作与信号量的处理相关，P表示通过的意思，V表示释放的意思。PV操作即可实现同步，也可以实现互斥。
由于信号量只能进行两种操作等待和发送信号，即P(sv)和V(sv),他们的行为是这样的：
（1）P(sv)：如果sv的值大于零，就给它减1；如果它的值为零，就挂起该进程的执行
（2）V(sv)：如果有其他进程因等待sv而被挂起，就让它恢复运行，如果没有进程因等待sv而挂起，就给它加1.
在信号量进行PV操作时都为原子操作（因为它需要保护临界资源），单指令的操作称为原子的，单条指令的执行不会被打断。
举例：
信号量就是在一个叫做互斥区的门口放一个盒子，盒子里面装着固定数量的小球，每个线程过来的时候，都从盒子里面摸走一个小球，然后进入互斥区，出来的时候，再把小球放回盒子里。如果一个线程走过来一摸盒子，一个球都没有，就只能站在门口等一个线程出来放回来一个球，再进去。由于小球的数量是固定的，那么互斥区里面的最大线程数量就是固定的，不会出现进入太多线程把互斥区给挤爆了的情况。这是用信号量做并发量限制。
另外一些情况下，小球是一次性的，线程拿走一个进了门，就把小球扔掉了，这样用着用着小球就没了，不过有另外一些线程（一般叫做生产者）会时不时过来往盒子里再放几个球，这样就可以有新的线程（一般叫做消费者）进去了，放一个球进一个线程，这是信号量做同步功能。
死锁
多个进程在运行过程中因争夺资源而造成的一种僵局，当进程处于这种僵持状态时，若无外力作用，它们都将无法再向前推进。
产生死锁的四个必要条件：
1）互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
2）请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
3）不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
4）环路等待条件：在发生死锁时，必然存在一个进程--资源的环形链。
预防死锁：
- 资源一次性分配：一次性分配所有资源，这样就不会再有请求了：（破坏请求条件）
- 只要有一个资源得不到分配，也不给这个进程分配其他的资源：（破坏请保持条件）
- 可剥夺资源：即当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源（破坏不可剥夺条件）
- 资源有序分配法：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反（破坏环路等待条件）
避免死锁：
- 预防死锁的几种策略，会严重地损害系统性能。因此在避免死锁时，要施加较弱的限制，从而获得 较满意的系统性能。由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统进入不安全的状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。
- 银行家算法：首先需要定义状态和安全状态的概念。系统的状态是当前给进程分配的资源情况。因此，状态包含两个向量Resource（系统中每种资源的总量）和Available（未分配给进程的每种资源的总量）及两个矩阵Claim（表示进程对资源的需求）和Allocation（表示当前分配给进程的资源）。安全状态是指至少有一个资源分配序列不会导致死锁。当进程请求一组资源时，假设同意该请求，从而改变了系统的状态，然后确定其结果是否还处于安全状态。如果是，同意这个请求；如果不是，阻塞该进程知道同意该请求后系统状态仍然是安全的。
8.文件系统
基本概念
- 盘面号（磁头号）：0 ～ M-1；（由于一个盘面上只有一个磁头，所以盘面号也叫作磁头号）
- 柱面号（磁道号）：0 ～ L-1；（磁道编号通常是从外沿向内进行编号）
- 扇区号： 1 ～ N；（对于同一条磁道可以分为若干扇区，对于扇区分成三个字段）
- 标识符字段：存放扇区的标识信息
- 校验字段：检验磁盘读写操作的正确性
- 数据字段：存放数据信息
存储容量 = 磁头数×磁道（柱面）数×每道扇区数 ×每扇区字节数
磁盘的类型
按照磁头是否需要移动进行分类：
- 固定头磁盘
- 移动头磁盘
固定头磁盘
对于同一盘面上的不同磁道我们都有相应位置固定的磁头进行读写，如上图中的黑色磁头和蓝色磁头分别读取一个磁道，对多条磁道进行读写的时候，磁头不需要移动位置。所以对于一个盘面上的多条磁道可以并行进行读取，访问速度较快。同样价格也较高。
移动头磁盘
对于移动头磁盘，它的磁头是可以沿着径向臂进行径向移动，所以只需要使用一个磁头就可以访问所有的磁道。但是同一时间只能访问一个磁道，只能实现顺序读写，读写速度较慢，但是造价较低。计算机中使用的磁盘大多数都是移动头磁盘。
磁盘调度
当有大量磁盘I/O请求时，恰当选择调度顺序，以降低完成这些I/O服务的总时间。
磁盘调度方式主要有以下两种：
- 移臂调度：当同时有多条磁道访问请求时，确定磁道访问顺序，以减少平均寻道时间
- 旋转调度：当一条磁道上有多个扇区访问请求时，确定扇区访问顺序，以减少旋转延迟时间。按照扇区距离磁头的位置的偏差来进行调度。
由于旋转调度算法较为简单，只是按照扇区距离磁头的位置的偏差来进行调度。所以下面将以移臂调度为讲解。
移臂调度算法
1）先来先服务FCFS(First-Come, First Served)
假设当前磁道在100号磁道，磁头正向磁道号增加的方向（由外向里）移动。现依次有如下磁盘请求队列：23，376， 205，132， 61， 190， 29， 4， 40。
则磁盘调度顺序和寻道距离为：
23，376， 205，132， 61， 190， 29， 4， 40
Ts = (100-23) + (376-23) + (376-205) + (205-132) + ... + (40-4)
平均寻道距离 = Ts / 9 。
由于先来新服务算法并没有对磁盘访问进行优化，所以它可能会得到比较长的寻道距离。
2）最短寻道时间优先算法SSTF
在选择下一条磁道的时候总是访问与当前磁盘距离最近的磁盘进行访问。
对于上例，其磁盘调度顺序和寻道距离为：
132 , 190, 205, 61, 40, 29, 23, 4, 376
Ts = (132-100) + (190-132) + (205-190) + ... + (23-4) + (376-4)
最短寻道距离优先可以保障每一次的寻道距离最短，但是不能够保障最后系统得到的平均寻道距离最短。如最后 4 到 376 的磁盘寻道跨度就非常大。
它也存在着一下几个问题：
- 不能保证平均寻道距离最短；
- 会产生饥饿现象； 如果系统不断的出现在100号磁道附近的磁道访问请求，则原先较远的磁道请求如205， 376 就会处于很长时间的等待中。
- 影响磁盘的机械寿命。 不考虑磁头的移动方向，可能会造成磁盘频繁的改变其磁头运动方向。从而影响磁盘的机械寿命。
3）扫描(SCAN)算法（又称为电梯算法）
它是目前操作系统中用的比较广泛的一种磁盘移臂调度算法。
其在对下一条磁道进行选择时，需要判断：
- 欲访问磁道与当前磁道的距离；
- 磁头当前的移动方向。（处于磁道号增加或者减少状态）
同样，对于上例，其磁盘调度顺序和寻道距离为：
132，190， 205，376， 61, 40, 29, 23, 4
Ts = (132-100) + (190-132) + (205-190) + (376-205) + (376-61) + (61-40) +... + (23-4)
4）N-Step-SCAN算法 (N步扫描算法)
它是为了克服扫描算法和最短寻道时间有限算法的“磁臂粘着”现象而引入的。
“磁臂粘着”现象就是指当系统不断的提出对当前磁道的访问，那么磁头会一直处于该磁道上进行磁道访问请求，导致其它磁道的访问被推迟的现象。
N步扫描算法的算法思想：将磁盘请求队列分成若干个长度为N的子队列，磁盘调度将按FCFS算法依次处理这些子队列； 而每处理一个子队列时又采用SCAN算法。
如对于上例，若其子队列的长度为4，则可以分为3个队列：
它就会首先处理第一个队列中的四个磁道请求，再处理第二个队列和最后的第三个队列。其对于每一个队列的处理都是按照扫描算法来进行处理。
5）FSCAN算法
该算法实质上是N步SCAN算法的简化， 它只将磁盘请求队列分成两个子队列：
① 由当前所有请求磁盘形成的队列，由磁盘调度按SCAN算法进行处理。
② 在扫描期间，将新出现的所有磁盘I/O请求， 放入另一个等待处理的请求队列。
如上例，先把所有的磁盘请求放在第一个队列中，对其应用扫描算法进行磁盘调度。若访问过程中出现的新的磁盘请求就放在下面的新队列中，当第一个队列全部访问完，再处理第二个队列。
6）旋转调度算法
当同一磁道（柱面）上有多个扇区请求时，总是选取与当前读写头最近的那个I/O请求，使旋转圈数最少。
例：对磁盘访问的5个请求，若磁头在1号柱面，先按SCAN算法做移臂调度（柱面号排序），再进行旋转调度（块号排序），则调度顺序如下：