处理机调度与死锁

死锁

1、什么是死锁？

死锁，是指多个进程循环等待它⽅占有的资源⽽⽆限期地僵持下去的局⾯。若无外力作用，他们都无法向前继续推进。

2、产生死锁的原因？

• 竞争资源(不可剥夺资源)

例如：系统中只有一台打印机，可供进程 A 使用，假定 A 已占用了打印机，若 B 继续要求打印机打印将被阻塞。
系统中的资源可以分为两类：

1. 可剥夺资源：是指某进程在获得这类资源后，该资源可以再被其他进程或系统剥夺，CPU 和主存均属于可剥夺性资源；
2. 不可剥夺资源，当系统把这类资源分配给某进程后，再不能强行收回，只能在进程用完后自行释放，如磁带机、打印机等。

• 进程推进顺序不当

例如：进程 A 和 进程 B 互相等待对方的数据。

3、产生死锁的必要条件是什么？

1. 互斥条件：进程要求对所分配的资源进行排它性控制，即在一段时间内某资源仅为一进程所占用。
2. 请求和保持条件：当进程因请求资源而阻塞时，对已获得的资源保持不放。
3. 不剥夺条件：进程已获得的资源在未使用完之前，不能剥夺，只能在使用完时由自己释放。
4. 环路等待条件：在发生死锁时，必然存在一个进程–资源的环形链。

（循环等待条件：存在一种进程资源循环等待链，链中每个进程已获得的资源同时被链中下一个进程所请求。）

4、解决死锁的基本方法？

1. 预防死锁
2. 避免死锁
3. 检测死锁
4. 解除死锁

   5、如何预防死锁？

在程序运行之前预防发生死锁。

1. 破坏互斥条件：例如假脱机打印机技术允许若干个进程同时输出，唯一真正请求物理打印机的进程是打印机守护进程。
2. 破坏请求和保持条件：一次性分配所有资源，这样就不会再有请求了；只要有一个资源得不到分配，也不给这个进程分配其他的资源：
3. 破坏不可剥夺条件：当某进程获得了部分资源，但得不到其它资源，则释放已占有的资源；
4. 破坏环路等待条件：系统给每类资源赋予一个编号，每一个进程按编号递增的顺序请求资源，释放则相反。

   6、如何避免死锁？

   在程序运行时避免发生死锁。
   安全状态
   所谓安全状态，是指系统能按某种进程推进顺序( P1, P2, …, Pn)，为每个进程Pi分配其所需资源，直至满足每个进程对资源的最大需求，使每个进程都可顺序地完成。此时称 P1, P2, …, Pn 为安全序列。如果系统无法找到一个安全序列，则称系统处于不安全状态。
   并非所有的不安全状态都是死锁状态，但当系统进入不安全状态后，便可能进入死锁状态；反之，只要系统处于安全状态，系统便可以避免进入死锁状态。
   银行家算法
   在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。
   银行家算法中的数据结构
   　　为了实现银行家算法，在系统中必须设置这样四个数据结构，分别用来描述系统中可利用的资源、所有进程对资源的最大需求、系统中的资源分配，以及所有进程还需要多少资源的情况。
   　　(1) 可利用资源向量 Available。这是一个含有 m 个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果 Available[j] = K，则表示系统中现Rj类资源K个。
   　　(2) 最大需求矩阵Max。这是一个n x m的矩阵，它定义了系统中n个进程中的每个进程对m类资源的最大需求。如果Max[i,j] = K，则表示进程i需要Rj 类资源的最大数目为K。
   　　(3) 分配矩阵 Allocation。这也是一个n x m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果 Allocation[i,jl = K，则表示进程i当前己分得Rj类资源的数目为K。
   　　(4) 需求矩阵Need.这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j] = K，则表示进程i还需要Rj类资源K个方能完成其任务。
   上述三个矩阵间存在下述关系:Need[i,j] = Max[i,j] - allocation[i, j]　
   银行家算法详述：
   　　设 Request；是进程Pi的请求向量，如果 Requesti[j] = K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检査:
   　　(1) 如果 Requesti[j] ≤ Need[i,j]便转向步骤(2)；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。
   　　(2) 如果 Requesti[j] ≤ Available[j]，便转向步骤(3)；否则，表示尚无足够资源，Pi须等待。
   　　(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值
   　　　　Available[j] = Available[j] - Requesti[j];
   　　　　Allocation[i,j] = Allocation[i,j] + Requesti[j];
   　　　　Need[i,j] = Need[i,j] - Requesti[j];
   　　(4) 系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。
   　　
   安全性算法:
   系统所执行的安全性算法可描述如下:
   　　(1) 设置两个向量:①工作向量Work，它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work = Available；② Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。开始时先做 Finish[i] = false；当有足够资源分配给进程时，再令Finish[i] = true。
   　　(2) 从进程集合中找到一个能满足下述条件的进程
   　　　　① Finish[i] = false;
   　　　　② Need[i,j] ≤ Work[j];
   若找到，执行步骤(3)，否则，执行步骤(4)。
   　　(3)当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行:
   　　　　Work[j] = Work[j] + Allocation[i,j];
   　　　　Finish[i] = true;
   　　　　go to step 2;(goto语句不推荐使用 _ )
   　　(4)如果所有进程的 Finish[i] =true都满足，则表示系统处于安全状态；否则，系统处于不安全状态。

   7、怎么检测与解除死锁？

   检测

   死锁定理：如果某时刻系统的资源分配图是不可完全简化的，那么此时系统死锁。
   如果进程 - 资源分配图中无环路，此时系统没有发生死锁。
   如果进程 - 资源分配图中有环路，则可分为以下两种情况：

• 每种资源类中仅有一个资源，则系统发生了死锁。此时，环路是系统发生死锁的充分必要条件，环路中的进程就是死锁进程。
• 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。

每种资源类中仅有一个资源的死锁检测算法：
每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。
每种资源类中有多个资源的死锁检测算法：

每个资源类用一个方框表示，方框中的原点表示此资源类中的各个资源；
每个进程用一个圆圈来表示，用有向边表示进程申请资源和资源分配情况。
约定方框→圆圈表示资源分配，圆圈→方框表示申请资源。

解除

1. 资源剥夺：挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他死锁进程（但应该防止被挂起的进程长时间得不到资源）；
2. 撤销进程：强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源（撤销的原则可以按进程优先级和撤销进程代价的高低进行）；
3. 进程回退：让一个或多个进程回退到足以避免死锁的地步。进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。

   8、鸵鸟策略是什么？

   当系统发⽣死锁时不会对⽤户造成多⼤影响，或系统很少发⽣死锁的场合采⽤允许死锁发⽣的鸵⻦算法。出现死锁的概率很⼩，并且出现之后处理死锁会花费很⼤的代价，还不如不做处理，OS中这种置之不理的策略称之为鸵⻦策略（也叫鸵⻦算法）

   处理机调度

   1、程序从代码到可执行程序经历了什么？

   
   （1）预编译
   主要处理源代码文件中的以“#”开头的预编译指令。处理规则见下：
   1. 删除所有的#define，展开所有的宏定义。
   2. 处理所有的条件预编译指令，如“#if”、“#endif”、“#ifdef”、“#elif”和“#else”。
   3. 处理“#include”预编译指令，将文件内容替换到它的位置，这个过程是递归进行的，文件中包含其他文件。
   4. 删除所有的注释，“//”和“//”。
   5. 保留所有的#pragma 编译器指令，编译器需要用到他们，如：#pragma once 是为了防止有文件被重复引用。
   6. 添加行号和文件标识，便于编译时编译器产生调试用的行号信息，和编译时产生编译错误或警告是能够显示行号。
   （2）编译
   把预编译之后生成的xxx.i或xxx.ii文件，进行一系列词法分析、语法分析、语义分析及优化后，生成相应的汇编代码文件。
   1. 词法分析：利用类似于“有限状态机”的算法，将源代码程序输入到扫描机中，将其中的字符序列分割成一系列的记号。
   2. 语法分析：语法分析器对由扫描器产生的记号，进行语法分析，产生语法树。由语法分析器输出的语法树是一种以表达式为节点的树。
   3. 语义分析：语法分析器只是完成了对表达式语法层面的分析，语义分析器则对表达式是否有意义进行判断，其分析的语义是静态语义——在编译期能分期的语义，相对应的动态语义是在运行期才能确
   定的语义。
   4. 优化：源代码级别的一个优化过程。
   5. 目标代码生成：由代码生成器将中间代码转换成目标机器代码，生成一系列的代码序列——汇编语言表示。
   6. 目标代码优化：目标代码优化器对上述的目标机器代码进行优化：寻找合适的寻址方式、使用位移来替代乘法运算、删除多余的指令等。
   （3）汇编
   将汇编代码转变成机器可以执行的指令(机器码文件)。 汇编器的汇编过程相对于编译器来说更简单，没有复杂的语法，也没有语义，更不需要做指令优化，只是根据汇编指令和机器指令的对照表一一翻译过来，汇编过程有汇编器as完成。
   经汇编之后，产生目标文件(与可执行文件格式几乎一样)xxx.o(Linux下)、xxx.obj(Windows下)。
   （4）链接**
   将不同的源文件产生的目标文件进行链接，从而形成一个可以执行的程序。链接分为静态链接和动态链接。

   2、谈谈你对动态链接库和静态链接库的理解？区别在哪里？

   1、静态链接：
   静态链接就是在编译链接时直接将需要的执行代码拷贝到调用处。 函数和数据被编译进一个二进制文件。在使用静态库的情况下，在编译链接可执行文件时，链接器从库中复制这些函数和数据并把它们和应用程序的其它模块组合起来创建最终的可执行文件。
   静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出。链接器主要完成以下两个任务：

• 符号解析：每个符号对应于一个函数、一个全局变量或一个静态变量，符号解析的目的是将每个符号引用与一个符号定义关联起来。
• 重定位：链接器通过把每个符号定义与一个内存位置关联起来，然后修改所有对这些符号的引用，使得它们指向这个内存位置。

目标文件

• 可执行目标文件：可以直接在内存中执行；
• 可重定位目标文件：可与其它可重定位目标文件在链接阶段合并，创建一个可执行目标文件；
• 共享目标文件：这是一种特殊的可重定位目标文件，可以在运行时被动态加载进内存并链接；

缺点：

• 空间浪费。因为每个可执行程序中对所有需要的目标文件都要有一份副本，所以如果多个程序对同一个目标文件都有依赖，会出现同一个目标文件都在内存存在多个副本；
• 更新困难：每当库函数的代码修改了，这个时候就需要重新进行编译链接形成可执行程序。

优点：

• 运行速度快。在可执行程序中已经具备了所有执行程序所需要的任何东西，在执行的时候运行速度快。
• 在程序发布的时候就不需要的依赖库，也就是不再需要带着库一块发布，程序可以独立执行，但是体积可能会相对大一些。

2、动态链接：
静态库有以下两个问题：

• 当静态库更新时那么整个程序都要重新进行链接；
• 对于 printf 这种标准函数库，如果每个程序都要有代码，这会极大浪费资源。

共享库是为了解决静态库的这两个问题而设计的，在 Linux 系统中通常用 .so 后缀来表示，Windows 系统上它们被称为 DLL。它具有以下特点：

• 在给定的文件系统中一个库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中；
• 在内存中，一个共享库的 .text 节（已编译程序的机器代码）的一个副本可以被不同的正在运行的进程共享。

共享库：就是即使需要每个程序都依赖同一个库，但是该库不会像静态链接那样在内存中存在多份副本，而是这多个程序在执行时共享同一份副本；
动态链接就是在编译的时候不直接拷贝可执行代码，而是通过记录一系列符号和参数，在程序运行或加载时将这些信息传递给操作系统，操作系统负责将需要的动态库加载到内存中，然后程序在运行到指定的代码时，去共享执行内存中已经加载的动态库可执行代码，最终达到运行时连接的目的。
基本思想是把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。
优点是多个程序可以共享同一段代码，而不需要在磁盘上存储多个拷贝。同时更新方便，更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会被自动加载到内存并且链接起来，程序就完成了升级的目标。
缺点是性能损耗，由于是运行时加载，每次执行程序都需要进行链接，可能会影响程序的前期执行性能。
区别
静态连接库就是把 (lib) ⽂件中⽤到的函数代码直接链接进⽬标程序，程序运⾏的时候不再需要其它的库⽂件；动态链接就是把调⽤的函数所在⽂件模块（DLL）和调⽤函数在⽂件中的位置等信息链接进⽬标程序，程序运⾏的时候再从 DLL 中寻找相应函数代码，因此需要相应 DLL ⽂件的⽀持。静态链接库与动态链接库都是共享代码的⽅式，如果采⽤静态链接库，则⽆论你愿不愿意，lib 中的指令都全部被直接包含在最终⽣成的 EXE ⽂件中了。但是若使⽤ DLL，该 DLL 不必被包含在最终 EXE ⽂件中，EXE ⽂件执⾏时可以“动态”地引⽤和卸载这个与 EXE 独⽴的 DLL ⽂件。
静态链接库和动态链接库的另外⼀个区别在于静态链接库中不能再包含其他的动态链接库或者静态库，⽽在动态链接库中还可以再包含其他的动态或静态链接库。
动态库就是在需要调⽤其中的函数时，根据函数映射表找到该函数然后调⼊堆栈执⾏。如果在当前⼯程中有多处对dll⽂件中同⼀个函数的调⽤，那么执⾏时，这个函数只会留下⼀份拷⻉。但静态库如果有多处对 lib ⽂件中同⼀个函数的调⽤，那么执⾏时该函数将在当前程序的执⾏空间⾥留下多份拷⻉，⽽且是⼀处调⽤就产⽣⼀份拷⻉。

3、中断是什么？过程讲一下？外中断和异常有什么区别吗？

概念

中断是指在程序执行过程中，出现某种紧急事件，CPU暂停执行现行程序，转去执行处理该事件的程序——中断服务程序，执行完后再返回到被暂停的程序继续执行，这一过程称为中断。
中断源
引起中断的设备或事件称为中断源。分为两类，CPU内产生的，称为内部中断；其他的称为外部中断。

• 内部中断包括：由CPU本身产生的中断、由控制器产生的中断、由程序源安排的中断指令引起的中断。
• 外部中断由根据中断事件的紧迫程序将中断源划分为可屏蔽中断和不可屏蔽中断。
  • 可屏蔽中断：指可以延时处理的事件。例如打印机的输入输出中断请求，如果CPU正在处理更加紧急的事件，打印机的中断请求就会被暂时屏蔽。被屏蔽的中断请求保存再中断寄存器中，当屏蔽接触后，仍然能够得到响应和处理。
  • 不可屏蔽中断：指事件异常紧急，必须马上处理。例如掉电、RAM奇偶校验错误等引起的中断。

外部硬件中断有：

• I/O设备:如显示器、键盘、打印机等。
• 数据通道:软盘、硬盘、光盘等。
• 实时时钟:如外部的定时电路等。
• 硬件故障:如电源掉电、RAM奇偶校验错误等

产生于CPU内部的软件中断源有几种:

• 由CPU得运行结果产生:如除数为0、结果溢出、单步执行等。
• 执行中断指令INT:INT3
• 非法操作或指令引起异常处理、地址越界。

中断作用

• 可以使CPU和外设同时⼯作，使系统可以及时地响应外部事件；
• 可以允许多个外设同时⼯作，⼤⼤提⾼了CPU的利⽤率；
• 可以使CPU及时处理各种软硬件故障。

  中断处理的基本过程

  包括中断请求、中断判优、中断响应、中断服务 和中断返回等五个阶段。

1. 中断请求

（1）发生在CPU内部的中断，不需要中断请求，CPU内部的中断控制逻 辑直接接收处理。
（2）外部中断请求由中断源提出。外部中断源利用CPU的中断输入引脚 输入中断请求信号。一般CPU设有两个中断请求输入引脚：可屏蔽中断请求输入引脚（INTR）和不可屏蔽中断请求输入引脚（NMI）。
中断请求触发器
每个中断源发中断请求信号的时间是不确定的，而CPU在何时响应中断也 是不确定的。所以，每个中断源都有一个中断请求触发器，锁存自己的中 断请求信号，并保持到CPU响应这个中断请求之后才将其清除。
中断允许触发器
在CPU内部有一个中断允许触发器，当其为“1”时，允许CPU响应中断， 称为开中断。若其为“0”，不允许CPU响应中断，中断被屏蔽，称为关 中断。
通常，当CPU复位时，中断允许触发器也复位为“0”，即不允许CPU响应中断。当 CPU中断响应时，CPU自动关闭中断，禁止接受另一个新的中断。

1. 中断判优

CPU一次只能接受一个中断源的请求，当多个中断源同时向CPU提出 中断请求时，CPU必须找出中断优先级最高的中断源，这一过程称为 中断判优。中断判优可以采用硬件方法，也可采用软件方法
（1）软件判优
CPU检测到中断请求后，首先读取中断请求寄存器的内容，逐位检测它 们的状态，检测到某一位为1，就确定对应的中断源有中断请求，转去 执行它的中断服务程序。只要某一位为1，INTR就会显示高电平，否则低电平。先检测哪一个，哪一个的优先级就高，后检测 哪一个，哪一个优先级就低，检测的顺序就是各中断源的优先级顺序。
软件判优耗时较长。如果中断源很多，中断的实时性就很差，但是软 件判优优先权安排灵活。
（2）硬件判优
利用专门的硬件电路确定中断源的优先级，有两种常见的方式：菊花 链判优电路和中断控制器判优。
菊花链判优电路
基本设计思想：每个中断源都有一个中断逻辑电路，所有的中断逻辑电路 连成一条链，形如菊花链。排在链前端的中断源优先级最高，越靠后的设 备优先级越低。
菊花链判优电路
基本设计思想：每个中断源都有一个中断逻辑电路，所有的中断逻辑电路 连成一条链，形如菊花链。排在链前端的中断源优先级最高，越靠后的设 备优先级越低。

1. 中断响应

中断响应时，CPU向中断 源发出中断响应信号，同时：
① 保护硬件现场；
② 关中断，不允许CPU响应中断了；
③ 保护断点；
④ 获得中断服务程序的入口地址。

1. 中断服务

中断服务程序的一般结构为：
（1）保护现场。在中断服务程序的起始部分安排若干条入栈指令，将各 寄存器的内容压入堆栈保存。
（2）开中断。在中断服务程序执行期间允许级别更高的中断请求中断现 行的中断服务程序，实现中断嵌套。
（3）中断服务。完成中断源的具体要求。
（4）恢复现场。中断服务程序结束前，必须恢复主程序的中断现场。通 常是将保存在堆栈中的现场信息弹出到原来的寄存器中。
（5）中断返回。返回到原程序的断点处，继续执行原程序。
总结
① 关中断，进⼊不可再次响应中断的状态，由硬件实现。
② 保存断点，为了在[中断处理]结束后能正确返回到中断点。由硬件实现。
③ 将[中断服务程序]⼊⼝地址送PC，转向[中断服务程序]。可由硬件实现，也可由软件实现。
④ 保护现场、置屏蔽字、开中断，即保护CPU中某些寄存器的内容、设置[中断处理]次序、允许更⾼级的中断请求得到响应，实现中断嵌套由软件实现。
⑤ 设备服务，实际上有效的中断处理⼯作是在此程序段中实现的。由软件程序实现 。
⑥ 退出中断。在退出时，⼜应进⼊不可中断状态，即关中断、恢复屏蔽字、恢复现场、开中断、中断返回。由软件实现。

中断向量和中断向量表

CPU的中断系统可以处理256种中断。每种中断都有对应的中断服务程序。中断服务程序的入口地址称为中断向量。256种中断向量存储在内存中构成一张表，称为中断向量表。
CPU的中断系统可以处理256种中断。每种中断都有对应的中断服务程序。中断服务程序的入口地址称为中断向量。256种中断向量存储在内存中构成一张表，称为中断向量表。
中断向量在中断向量表中的存放首地址称为向量地址.

1. 中断返回

返回到原程序的断点处，恢复硬件现场，继续执行原程序。中断返回 操作是中断响应操作的逆过程。

区别

外中断是指由 CPU 执行指令以外的事件引起，如 I/O 完成中断，表示设备输入/输出处理已经完成，处
理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
而异常时由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
异常是由CPU产生的，同时，它会发送给内核，要求内核处理这些异常
相同点

• 最后都是由CPU发送给内核，由内核去处理
• 处理程序的流程设计上是相似的

不同点

• 产生源不相同，异常是由CPU产生的，而中断是由硬件设备产生的
• 内核需要根据是异常还是中断调用不同的处理程序
• 中断不是时钟同步的，这意味着中断可能随时到来；异常由于是CPU产生的，所以它是时钟同步的

• 当处理中断时，处于中断上下文中；处理异常时，处于进程上下文中

  4、什么是用户态和内核态，他们之间如何切换？

  用户态和内核态是操作系统的两种运行状态。

• 内核态：处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。

• 用户态：处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

那么为什么要有用户态和内核态呢？
这个主要是访问能力的限制的考量，计算机中有一些比较危险的操作，比如设置时钟、内存清理，这些都需要在内核态下完成，如果随意进行这些操作，那你的系统得崩溃多少次。
当我们在系统中执⾏⼀个程序时，⼤部分时间是运⾏在⽤户态下的，在其需要操作系统帮助完成某些它没有
权⼒和能⼒完成的⼯作时就会切换到内核态。
区别
这两种状态的主要差别是： 处于⽤户态执⾏时，进程所能访问的内存空间和对象受到限制，其所处于占有的处理机是可被抢占的 ； ⽽处于核⼼态执⾏中的进程，则能访问所有的内存空间和对象，且所占有的处理机是不允许被抢占的。
转换
1) 系统调⽤
这是⽤户态进程主动要求切换到内核态的⼀种⽅式，⽤户态进程通过系统调⽤申请使⽤操作系统提供的服务程序完成⼯作，⽐如前例中fork()实际上就是执⾏了⼀个创建新进程的系统调⽤。⽽系统调⽤的机制其核⼼还是使⽤了操作系统为⽤户特别开放的⼀个中断来实现。
2) 异常当 CPU 在执⾏运⾏在⽤户态下的程序时，发⽣了某些事先不可知的异常，这时会触发由当前运⾏进程切换到处理此异常的内核相关程序中，也就转到了内核态，⽐如缺⻚异常。
3) 外围设备的中断
当外围设备完成⽤户请求的操作后，会向 CPU 发出相应的中断信号，这时 CPU 会暂停执⾏下⼀条即将要执⾏的指令转⽽去执⾏与中断信号对应的处理程序，如果先前执⾏的指令是⽤户态下的程序，那么这个转换的过程⾃然也就发⽣了由⽤户态到内核态的切换。⽐如硬盘读写操作完成，系统会切换到硬盘读写的中断处理程序中执⾏后续操作等。
具体切换过程
用户态 -> 内核态 -> 用户态，而唯一能够做这些操作的只有 系统调用，而能够执行系统调用的就只有 操作系统。
一般用户态 -> 内核态的转换我们都称之为 trap 进内核，也被称之为 陷阱指令(trap instruction)。
工作流程如下：

• 首先用户程序会调用 glibc 库，glibc 是一个标准库，同时也是一套核心库，库中定义了很多关键 API。
• glibc 库知道针对不同体系结构调用系统调用的正确方法，它会根据体系结构应用程序的二进制接口设置用户进程传递的参数，来准备系统调用。
• 然后，glibc 库调用软件中断指令(SWI) ，这个指令通过更新 CPSR 寄存器将模式改为超级用户模式，然后跳转到地址 0x08 处。
• 到目前为止，整个过程仍处于用户态下，在执行 SWI 指令后，允许进程执行内核代码，MMU 现在允许内核虚拟内存访问
• 从地址 0x08 开始，进程执行加载并跳转到中断处理程序，这个程序就是 ARM 中的 vector_swi()。
• 在 vector_swi() 处，从 SWI 指令中提取系统调用号 SCNO，然后使用 SCNO 作为系统调用表 sys_call_table 的索引，调转到系统调用函数。
• 执行系统调用完成后，将还原用户模式寄存器，然后再以用户模式执行。

  5、处理机调度算法有哪些？

  调度算法是指：根据系统的资源分配策略所规定的资源分配算法。
  常见的进程调度算法有：
  1.先来先去服务
  2.时间片轮转法
  3.多级反馈队列算法
  4.最短进程优先
  5.最短剩余时间优先
  6.最高响应比优先
  7.多级反馈队列调度算法

  先来先服务 （FCFS，first come first served）

  在所有调度算法中，最简单的是非抢占式的FCFS算法。
  算法原理：进程按照它们请求CPU的顺序使用CPU。当每个进程就绪后，它加入就绪队列。当前正运行的进程停止执行，选择在就绪队列中存在时间最长的进程运行。
  优点：易于理解且实现简单，只需要一个队列(FIFO)，且相当公平。
  缺点：比较有利于长进程，而不利于短进程，有利于CPU 繁忙的进程，而不利于I/O 繁忙的进程。（平均等待时间很长）
  该算法既可以用于作业调度，也可以用于进程调度。

  最短作业优先（SJF, Shortest Job First）

  短作业优先（SJF, Shortest Job First）又称为“短进程优先”SPN(Shortest Process Next)；这是对FCFS算法的改进，其目标是减少平均周转时间。
  算法原理：从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。非抢占
  算法优点：相比FCFS 算法，该算法可改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。
  算法缺点：对长进程非常不利，可能长时间得不到执行，且未能依据进程的紧迫程度来划分执行的优先级，以及难以准确估计进程的执行时间，从而影响调度性能。

  时间片轮转法（RR）

  轮转法是基于适中的抢占策略的，以一个周期性间隔产生时钟中断，当中断发生后，当前正在运行的进程被置于就绪队列中，然后基于先来先去服务策略选择下一个就绪作业的运行。这种技术也称为时间片，因为每个进程再被抢占之前都给定一片时间。
  算法优点：时间片轮转调度算法的特点是简单易行、平均响应时间短。
  算法缺点：不利于处理紧急作业。在时间片轮转算法中，时间片的大小对系统性能的影响很大，因此时间片的大小应选择恰当
  时间片大小的确定
  1.系统对响应时间的要求
  2.就绪队列中进程的数目
  3.系统的处理能力

  多级反馈队列(Multilevel Feedback Queue)

  多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
  多级反馈队列调度算法描述：
  　　多级反馈队列算法，不必事先知道各种进程所需要执行的时间，他是当前被公认的一种较好的进程调度算法。其实施过程如下：
  1)设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中，为每个进程所规定的执行时间片就越小。
  2)当一个新进程进入内存后，首先放入第一队列的末尾，按照先来先去原则排队等候调度。如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，同样等待调度…..如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
  3)仅当第一队列空闲的时候，调度程序才调度第二队列中的进程运行；仅当第1到（i-1）队列空时，才会调度第i队列中的进程运行，并执行相应的时间片轮转。
  4)如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列，则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。

  最高响应比优先法(HRRN，Highest Response Ratio Next)

  最高响应比优先法(HRRN，Highest Response Ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。
  算法原理：响应比R定义如下： R =(W+T)/T = 1+W/T
  其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。
  算法优点：由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRRN方式时其吞吐量将小于采用SJF 法时的吞吐量。
  算法缺点：由于每次调度前要计算响应比，系统开销也要相应增加。

  优先级调度算法

  优先级调度算法每次从后备作业队列中选择优先级最髙的一个或几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。在进程调度中，优先级调度算法每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

  最短剩余时间优先调度算法shortest remaining time next（SRTN）

  最短剩余时间是针对最短进程优先增加了抢占机制的版本。在这种情况下，进程调度总是选择预期剩余时间最短的进程。当一个进程加入到就绪队列时，他可能比当前运行的进程具有更短的剩余时间，因此只要新进程就绪，调度程序就能可能抢占当前正在运行的进程。像最短进程优先一样，调度程序正在执行选择函数是必须有关于处理时间的估计，并且存在长进程饥饿的危险。