Yarrow Blog

常见调度算法FCFS-先来先服务 (First Come First Server)算法思想主要从“公平”角度考虑，类似我们生活中的排队购物现象，先到先服务 算法规则按照作业/进程到达的先后顺序进行服务 用于作业/进程调度 用于作业调度时：考虑的是哪个作业先到达后备队列 用于进程调度时：考虑的是哪个进程先到达就绪队列 是否可抢占？非抢占式算法 示例 优缺点 优点：公平，算法实现简单 缺点：排在长作业/长进程后面的短作业需要等待很长时间，其带权周转时间很大，对短作业用户体验不好。 综上即FCFS算法对长作业有利，对短作业不利（例如上面例题种P3作业的带权周转时间达到了很大的8） 是否会导致饥饿饥饿指某进/作业长时间得不到服务 FCFS算法不会导致饥饿，只要各个任务依序排队，总会轮到响应作业 SJF-短作业优先 (Shortest Job First)算法思想追求最少的平均等待时间，最少的平均周转时间，最少的平均带权周转时间 算法规则最短的作业/进程有限得到服务（这里的最短指的是要求服务时间最短） 用于作业/进程调度即可用于作业调度，也可用于进程调度，用于进程调度事被称为“短进程优先算 ...

调度算法的评价指标CPU利用率指CPU忙碌时间占总时间的比例 $$利用率=\frac{忙碌的时间}{总时间}$$ Eg:某计算机只支持单道程序，某个作业刚开始需要在CPU上运行5秒，再用打印机打印输出5秒，之后再执行5秒，才能结束。在此过程中CPU利用率、打印机利用率分别是多少? $$CPU利用率=\frac{5+5}{5+5+5}=66.67%$$ $$打印机利用率=\frac{5}{5+5+5}=33.33%$$ 系统吞吐量单位时间内完成作业的数量，对于计算机而言，肯定更希望用尽可能少的时间处理完尽可能多的作业，即系统吞吐量越大越好 $$系统吞吐量=\frac{总共完成的作业数目}{总共花费的时间总数}(单位：道/秒)$$ 周转时间指从作业被提交给系统开始，到作业完成为止的这段时间间隔。由四部分组成： 高级调度时间：作业在外存后被队列上等待的时间(在一个作业处理过程中，只会发生一次) 低级调度时间(就绪态)：进程在就绪队列上等待进程调度的时间。即进程处于就绪态的情况 运行态：进程在CPU上执行的时间 阻塞态：进程等待I/O设备操作完成的时间 (后三种时间在一个作业的整个处理过程 ...

进程调度进程调度(低级调度)，就是按照某种算法从就绪队列中选择一个进程为其分配处理机 需要进行进程调度与切换的情况（进程调度的时机）1. 当前运行的进程主动放弃处理机 进程正常终止 运行过程中发生异常而终止 进程主动请求阻塞（如等待I/O设备） 2. 当前运行的进程被动放弃处理机 分给进程的时间片用完 有更紧急的事情需要处理（如I/O中断） 有更高优先级的进程进入就绪队列 不能进行进程调度与切换的情况 在处理中断的过程中：中断处理过程复杂，与硬件密切相关，很难做到在中断处理过程中进行进程切换 进程在操作系统内核程序临界区中（具体解释见下文） 在原子操作过程中(原语)。原子操作不可中断，要一气呵成，所以运行过程中不可进行进程调度或切换 进程在操作系统内核程序临界区中不能进行进程调度和切换。临界资源：一个时间段内只允许一个进程使用的资源，各个进程需要互斥的访问临界资源 临界区：访问临界资源的代码 内核程序临界区一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪进程PCB组成） 假如某进程当前正处在内核程序临界区，并且正在/之前访问就绪队列，则该进程会对就绪队列进行上锁操作 ...

调度概念当有多项任务需要处理时，由于资源有限，所有任务无法同时处理，此时就需要确定某种规则来决定各项任务的执行顺序，这就是调度 在多道程序系统中，进程的数量往往多于处理机个数，这样不可能同时并行处理各个进程 处理机调度，就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给该进程使用，以实现进程的并发执行 调度的三个层次高级调度（作业调度） 由于内存空间有限，有时无法将用户提交的作业全部放入内存，因此就需要确定某种规则来决定作业调入内存的顺序，即高级调度 高级调度（作业调度）。按一定的原则从外存上处于后备队列（存储所有还没有进过内存的任务）的作业中挑选一个或多个作业，给他们分配内存等必要资源，并建立相应进程（建立PCB），以使他们获得竞争处理机的权利 高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次，调出一次。作业调入时会建立相应的PCB，作业调出时才撤销PCB。高级调度主要是指调入的问题，因为只有调入的时机需要操作系统来确定，但调出的时机必然是作业运行结束才调出。（即对于每项任务，高级调度只执行一次） 中级调度（内存调度） 引入了虚拟存储技术之后，可将暂时不能运行的进程 ...

线程概念线程是一个基本的CPU执行单元，也是程序执行流的最小单元 引入线程后，不仅是进程间可以并发执行，一个进程的不同线程之间也可以并发执行，提高了系统的并发度，使得一个进程内可以并发执行多项任务（例如QQ可以同时视频聊天，发送文件等等） 引入线程后，进程只作为除CPU以外的系统资源的分配单元（如打印机，内存地址空间等），即除CPU以外的系统资源还是直接分配给进程而不是某个线程 引入线程机制后，发生的变化 线程的属性 线程是处理机调度的单位 多CPU计算机中，各个线程可以占用不同的CPU 每个线程都有一个线程ID，和线程控制块（TCB）用来进行区分 线程同样有就绪，阻塞，运行三种基本状态 线程几乎不拥有系统资源 同一进程的不同线程间可以共享进程的资源 由于同一进程的不同线程间共享内存地址空间，所以各个线程间通信甚至无需系统干预 同一进程中的线程间进行切换，不会引起进程切换 不同进程中的线程进行切换，会引起进程切换 切换同进程中的线程，系统开销很小 切换进程，开销较大 线程的实现方式 用户级线程用户级线程由应用程序通过线程库实现，所有的线程管理工作都是由应用程序负责的（线程的创建，撤销 ...

进程的状态和转换进程是程序的一次执行。在这个执行过程中，有时进程正在被CPU处理，有时需要等待CPU服务，显然进程的状态是在不断变化的。为了方便对各个进程的管理，操作系统将进程合理的划分为几种状态 进程的三种基本状态运行态 Running占有CPU，并在CPU上运行。 单核处理器下，同一时刻最多只有一个进程处于运行态，双核环境下可以有两个进程处于运行态 就绪态 Ready已经具备运行条件，但由于没有空闲CPU，而暂时不能运行 注意这里所说的具备运行条件是指进程已经拥有了除CPU以外的所有需要的资源，包括所需要的设备的控制权限，缺少的只有CPU的控制权 阻塞态 Waiting/Blocked又称等待态，因等待某一事件而暂时不能运行 例如，等待操作系统分配打印机的控制权限，读取磁盘操作的请求等。CPU是计算机中最昂贵的不见，为了提高CPU利用率，需要先将其他进程所需资源分配到位，才能得到CPU服务 进程的另外两种状态创建态 New也称新建态，进程正在被创建，操作系统为进程分配资源，初始化PCB的阶段 终止态 Terminated进程正在从系统中撤销，操作系统回收进程拥有的资源，撤销PCB ...

进程程序的定义: 就是一个指令序列 早期的计算机，只支持单道程序。同一时间内只能有一道程序执行，此时计算机的CPU，内存以及I/O设备都由该程序单独使用，所以此时程序的代码放在程序段内，程序运行的数据放在数据段内，二者可分别置于内存的首尾两侧。 在引入多道程序技术后，同一时间可能有多道程序执行，此时内存中存放了各个程序的程序段和数据段，如果不引入其他数据结构便无法找到对应程序的存放位置。所以系统为每个运行的程序都配置一个数据结构，称为进程控制块PCB(Progress Control Block)，用来描述进程的各种信息（如程序代码的存放位置） 进程实体由PCB，程序段，数据段三部分构成，也称为进程映像 一般情况下，我们可以把进程实体简称为进程。我们平常所说的创建进程，指的就是创建进程实体中的PCB，而撤销进程，是指就是撤销进程实体中的PCB PCB是进程存在的唯一标志 进程定义 进程（Process）是计算机中的程序关于某数据集合上的一次运行活动，是系统进行资源分配和调度的基本单位，是操作系统结构的基础。在早期面向进程设计的计算机结构中，进程是程序的基本执行实体；在当代面向线程设 ...

系统调用系统调用是操作系统提供给应用程序（开发人员）使用的接口，可以理解为一种可供应用程序调用的特殊函数，应用程序可以发出系统调用请求来获得操作系统的服务 程序接口由一组系统调用组成 系统调用的概念和作用应用程序通过系统调用请求操作系统的服务。系统中各种共享资源都由操作系统统一掌管，因此用户程序想要执行与资源有关的操作（例如存储分配。I/O操作，文件管理等）都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代为完成。这样可以保证系统的稳定性和安全性，防止用户进行非法操作 如果没有系统调用存在，各个应用程序就可能会产生非法争夺共享资源的情况发生，例如多个应用同时对一个文件进行读写操作这显然是十分危险的 系统调用分类（依照功能分类） 设备管理：完成设备的请求/释放/启动等功能 文件管理：完成文件的读/写/创建/删除等功能 进程控制：完成进程的创建/撤销/阻塞/唤醒等功能 进程通信：完成进程之间的消息传递/信号传递等功能 内存管理：完成内存的分配/回收等功能 由于系统调用涉及到对系统资源的管理，对进程的控制，这些功能需要执行一些特权指令，所以系统调用的相关处理需要在核心态下进行 系 ...

中断和异常本质发生中断就意味着需要操作系统介入，开展管理工作。由于操作系统的管理工作（如进程切换，分配I/O设备等）需要使用特权指令，所以需要CPU由用户态切换到核心态。中断可以使CPU从用户态切换到核心态，是操作系统获得计算机的控制权。有了中断，才能实现多道程序并发执行 概念 中断发生时，CPU立即进入核心态 中断发生后，当前进程暂停运行，并由操作系统内核对中断进行处理 对于不同的中断信号，会进行不同的处理 用户态切换到核心态是通过中断实现的，并且中断是唯一的实现方式 核心态到用户态的切换只需要执行一个特权指令，将程序状态字(PSW)的标志位设置为“用户态”即可 中断的分类内中断也称为异常，例外，陷入 信号来源：CPU内部，与当前执行的指令有关 内中断还细分为 自愿中断：指令中断，如系统调用时的访管指令（陷入指令，trap指令） 强迫中断：硬件故障（如缺页中断），软件中断（如除0） 内中断另一种分类方式： 陷阱，陷入（trap）：有意而为之的异常，如系统调用 故障（fault）：由错误条件引起的，可能被故障处理程序修复，如缺页 终止（abort）：不可恢复的致命错误造成的结果 ...

运行机制指令的概念“指令”就是处理器（CPU）能够识别，执行的最基本命令 一般而言，指令可以由高级语言（C，Java，C++）翻译而来，一条高级语言的代码翻译过来可能对应多条指令 一些诸如基本运算的指令（加减乘除）不会影响到系统的安全性，但也有一些指令具有很高权限，例如内存清零指令，如果所有用户都可以执行任意指令，势必会影响到系统的安全性，因此就需要对指令进行分类 指令的分类 特权指令：不允许用户程序使用，如内存清零指令 非特权指令：如普通的运算指令（加减乘除） 经过分类后我们还需要考虑，CPU如何判断当前状态是否可以执行特权指令 处理器的两种状态 用户态（目态）：此时CPU只能执行非特权指令 核心态（管态）：此时CPU特权指令和非特权指令都可以执行 处理器的状态由程序状态字寄存器（PSW）中的某个标志位来标识，如0为用户态，1为核心态 两种程序 内核程序：操作系统的内核程序是系统的管理者，既可以执行特权指令，又可以执行非特权指令，运行在核心态 应用程序：为了保证系统安全运行，只能执行非特权指令，运行在用户态 操作系统的内核 上图中所提到的原语具有原子性，即其运行只能一次全部执行 ...