操作系统的典型算法的概念以及例子解释

　　计算机的运行简单来说可以理解为三层：应用程序、操作系统、硬件。而操作系统夹在两者中间，负责硬件调度、资源管理和分配等一系列的功能。所以了解操作系统中的各种算法是很有必要的。在本文中，我们将会对操作系统中的FCFS(先来先服务)和SJF(短作业优先)两种调度算法以及银行家算法进行概念的讲解。

　　FCFS算法(先来先服务)

　　FCFS是一种很简单的算法，简单来说就是最先进入队列的进程可以最先分配资源。在作业调度中，算法会从就绪队列中选择最先进入队列的作业，并分配处理机。而在进程调度中也是一样的。FCFS的算法特点是，算法简单、先进先出对长作业比较有利，但是效率低下，对短作业不利。

　　FCFS算法就像是平常超市的排队，服务员总是为第一个人先服务，不管后面的人所买东西的多少。例子：有4个进程ABCD，到达时间以及要求系统服务时间如图。

      我们可以看到，ABCD4个进程的到达时间分别是0,1,2,3.所以服务的顺序是A->B->C->D。下面是计算过程：(周转时间=完成时间-到达时间  带权周转时间=周转时间/服务时间)

      执行过程：

　　SJF(短作业优先)

　　短作业优先调度算法顾名思义就是短作业可以优先分配资源。当前面的作业运行完毕，会在后续队列中选择一个运行时间最短的作业，将它调入内存运行。

　　SJF的优点是平均等待时间少、平均周转时间最少。

　　但是它也有很多的缺点，该算法对于长作业不利，如果在长作业的的后备队列中，不断的有短作业。那么系统总会优先调度短作业，从而导致长作业长期不被调度。SJF算法并未完全考虑作业的紧急程度，因而不能保证紧急的作业会被及时处理。

　　例子：有4个进程ABCD

　　可以看出，当B完成的时候时间为4，这时CD都已经进入队列，但是由于D的所要求的系统服务时间比C的短，所以先执行D再执行C。计算过程如下图：

　　在优先级调度算法中有分为以下两种：

　　非剥夺式优先级调度算法：如果有一个更为重要的进程进入就绪队列中，但是此时处理机中有程序正在运行。这时会让正在运行的程序继续进行，直到任务完成或者等待事件。才会把处理机分配给更为重要的进程。

　　剥夺式优先级调度算法：和非剥夺式优先级调度算法相反，当有一个更为重要或者紧急的进程进入就绪队列，会立即暂停处理机中运行的进程，让给更为重要的进程运行。

　　银行家算法

　　在银行家算法中我们把操作系统看做是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源就是相当于向银行家贷款。而银行为了防止资金无法周转会对每一笔的贷款进行考察，看是否能在规定的期限内归还。

　　银行家为了保证资金的安全，做出了以下的规定：

　　1）如果一个顾客对资金的最大需求量不超过银行家现有的资金时就可以接纳该顾客。

　　2）顾客可以选择分期贷款，但是贷款总数不能超过最大需求。

　　3）如果银行家现有的资金不能满足顾客所需的贷款数额，可以推迟支付贷款。但是总能在一定的时间内使顾客得到贷款。

　　4）当顾客得带所需资金后，一定能在有限的时间内归还所有的资金。

　　下面看一个例子：

　　在图中系统有四种类型的资源(A、B、C、D)和五个进程(P0、P1、P2、P3、P4)，Allocation代表进程已经拥有的资源，Need代表进程还需要的资源，Available代表系统中可以分配的资源。现在我们进行分析：

　　系统中可以分配的资源为1 6 2 2，但是满足的进程只有P0，所以首先分配P0。等待P0结束后，把P0的资源回收，可分配的资源变为1 6 5 4，只能满足P3，所以分配资源给P3，等待P3结束回收资源后继续上面的步骤，直到所有进程结束或者所有的资源不能满足任何一个进程。(要注意的是：回收的是Allocation，Need知识一个需求)。下面是解决的顺序：

      讲到银行家，就简单讲一下死锁问题(银行家算法是解决死锁的重要方法)假设有两个进程A、B同时运行，A占用了资源a，B占用了资源b。但是此时A需要资源b，B需要资源a，但是a需要进程A释放，b需要资源B释放。所以就造成了一直在等待，无法解决问题造成死锁。

     先来先服务调度算法、短作业优先调度算法以及银行家算法都是操作系统中典型的算法。操作系统中各个算法的运用使计算机系统的各个部件协调工作，使资源利用，程序执行更加合理高效。文中只是对操作系统算法的概念进行讲述，尽量做到简单易懂，帮助不懂这几种算法的朋友快速理解。