早期的学习笔记📗

主要参考来源

操作系统_清华大学(向勇、陈渝)

Operating systems: internals and design principles

Operating System Concepts

还有其余的一些网络博文

博客记录

操作系统-Operating-System第一章：概述

操作系统-Operating-System第二章：启动、中断、异常和系统调用

操作系统-Operating-System第三章01：计算机体系结构及内存分层体系

操作系统-Operating-System第三章02：地址空间和地址生成

操作系统-Operating-System第三章03：内存管理方式（连续内存分配）

作为非科班，前两个月学习操作系统的时候由于很多知识点不是很了解，所以学习起来有点吃力。为打好基础，本人补习了一下《计算机组成原理》的相关知识，并在博客专栏中做了记录。事实证明，先学一点计组知识有助于理解《操作系统》这门课。

《计算机组成原理》笔记可参考：计算机组成原理，博客内容如下：

计算机组成原理-计算机硬件的基本组成

计算机组成原理-计算机的功能部件及层次结构

计算机组成原理-计算机性能指标

计算机组成原理-数制与编码（进制转换）

计算机组成原理-定点数的表示和运算

计算机组成原理-浮点数的表示与运算

计算机组成原理-算术逻辑单元ALU

计算机组成原理-存储系统

计算机组成原理-高速缓冲存储器

计算机组成原理-指令系统 (指令、操作码、地址码、指令寻址、数据寻址)

计算机组成原理-总线（系统总线、总线仲裁、总线操作和定时）

Tips: 个人感觉学习完《计算机组成》和《操作系统》再去看《Java虚拟机》，也许会有更清晰的思路，而不是像大多数非科班一样直接背面筋，效果并不是很好。

资源💾

王道考研：链接: https://pan.baidu.com/s/1Dsk6KjJEwBBgNGLFWrIQDQ 密码: nmo1

英文书籍：Operating System Concepts | Operating systems: internals and design principles

在多道系统中，进程的数量往往是多于处理机的个数的，有限的硬件资源下无法做到并行的处理每一个进程。而「处理机调度」就是就是从进程的就绪队列中按照一定的算法选择一个进程，并将处理机分配给它，实现进程的并发执行。

又称「作业调度」

按照一定的原则从外存中处于后备队列的作业中挑选一个（或多个）作业，给它们分配内存等必要资源，并创建相应的进程（建立PCB），使他们获得可以竞争处理机的权力。

高级调度是外存与内存之间的调度。每个作业只调入一次，调出一次。作业调入的时候会创建对应的PCB，作业调出的时候才会撤销PCB。

多道批处理系统中大多配有「作业调度」，而其他的操作系统中通常不需要配置「作业调度」。「作业调度」的执行效率执行效率较低。高级调度主要是指调入的问题，因为只有调入的时机需要由操作系统来决定，但是调出的时机必然是作业运行结束才会结束。

又称「内存调度」

作用是提高内存利用率和系统吞吐量。将暂时不能够执行的进程调至外存中，并将此时的进程状态称为挂起态。当它们具备运行条件且内存有空闲时，再通过中级调度将外存中具备运行条件的就绪进程调入内存，修改状态为就绪态，在就绪队列中等待。

又称「进程调度」

主要作用就是按照某种方法的策略从就绪队列中选取一个进程，将处理机分配给它。「进程调度」是操作系统中最基本的一种调度，在一般的操作系统中都必须配置「进程调度」。「进程调度」的使用频率是最高的，一般几十毫秒一次。

用户向操作系统提交了多个作业，系统则将这些作业放在外存的作业等待队列中等待执行。「作业调度」为外存的后备队列中合适的作业分配内存、I/O资源等，在内存中创建相应的进程。而「内存调度」就将作业执行过程中暂时不能够运行的进程挂起移至外存中，将其状态切换为挂起态。待内存空间空闲且具备其他的该进程所需的条件时，「内存调度」将其唤醒。

「作业调度」为进程活动作准备，「进程调度」使得进程正常活动起来，中级调度起到挂起和唤醒的作用，中级调度处于「作业调度」和「进程调度」之间。

「作业调度」的次数最少，中级调度次数略多，「进程调度」频率最高。

「进程调度」是最基本的，不可或缺的。

参考：进程、程序、作业 的区别

一个「进程」是一个程序对某个数据集的执行过程，是分配资源的基本单位。

「作业」是用户需要向计算机提交的某项任务，是要求计算机所做工作的集合。一个作业的完成需要经历作业提交、作业收容、作业执行和作业完成4个阶段。而「进程」是对已提交完毕的程序所执行过程的描述。

参考：多道批处理系统、分时系统和实时系统

在「多道批处理系统」中，用户所提交的作业都先存放在外存上并排成一个队列。由「作业调度」按照一定的算法从后备队列中选择若干个作业调入内存中，使得他们去共享CPU和系统中的各种资源。在程序的运行期间用户不能干预。

在「分时系统」中，一台计算机的资源可以同时给多个用户一起使用，提高了计算机的利用率。不同的用户可以利用各自的终端去连接同一台计算机，以交互式的方式去使用计算机。典型的就是UNIX系统，可以满足多用户登录进行独立同时操作。

在「实时系统」中，所谓“实时”，就代表“及时”，「实时系统」要求系统能够及时的响应外部事件的请求。在规定的时间内完成对该事件的处理，并控制全部实时任务协调一致的执行，一般用于工业控制。

当前运行的进程主动放弃处理机

进程正常终止

运行过程中发生异常

进程主动请求阻塞（等待I/O）

当前运行的进程被动放弃处理机

分配给进程的时间片用完

发生了中断操作，需要处理更紧急的事情

更高优先级的进程进入就绪队列

中断处理过程中。中断过程复杂，和硬件密切相关，很难做到在中断过程中进行进程切换。

进程在操作系统内核程序临界区中，此时进程无法被调度与切换。

临界资源：一个时间段内只允许有一个进程使用的资源

临界区：访问临界资源的那段代码

「内核程序临界区」一般是用来访问某种内核数据结构的，比如进程的就绪队列（由各就绪队列的PCB组成）

进入临界区后，需要独占式的访问共享数据，通常必须加锁，防止其他并行程序进入，在解锁前不应该切换到其他进程运行，以加快该共享数据的释放。因为「内核程序临界区」访问的临界资源如果不尽快释放，则会影响到操作系统内核的其他管理工作。因此在访问「内核程序临界区」期间不能够进行调度与切换。

又称「非抢占式」

「非抢占式调度」是指当一个进程在处理机上执行的时候，即使有另外一个优先级更高的进程进入到就绪队列，也不会影响正在执行的进程继续执行，只有当当前的进程执行完毕或者主动进入阻塞状态的时候，才会将处理机分配给就绪队列中的进程。

又称「抢占式」

「抢占式调度」是指当一个进程在处理机上执行的时候，如果有另外一个优先级更高的进程需要使用处理机，则就会立即暂停当前执行的进程，将处理机分配给优先级更高的进程使用。

不同的CPU调度算法有着不同的特性，在选择调度算法的时候，需要考虑算法的特性，为比较CPU调度算法的性能，可以参考如下的准则：

因为在计算机中，CPU是最昂贵且最重要的硬件资源之一，所以需要尽可能的让CPU保持忙碌状态。在实际的系统中，通常在40%（轻载系统）~90%（重载系统）之间，在LINUX, MAC, UNIX系统中可以通过top命令查看相关信息，WINDOWS直接任务管理器查看即可。

表示单位时间内CPU完成的作业或者进程的数量。对于长进程，可能是几秒一个进程。对于短进程，可能是每秒几十个进程。

周转时间是指从作业提交到作业完成所经历的时间，是作业等待、在就绪队列中排队、在处理机上运行及运行I/O操作所花费的时间总和。

作业的周转时间

周转时间 = 作业完成时间 - 作业提交时间

对于用户来说，更关心自己的单个作业的周转时间

平均周转时间是指多个作业周转时间的平均值

平均周转时间 = (作业1周转时间 + … + 作业n周转时间)/n

对于操作系统而言，更关心系统的整体表现，所以更关心所有作业周转时间的平均值

平均带权周转时间是指周转时间与作业实际运行时间的比值

带 权 周 转 时 间 = 作 业 周 转 时 间 作 业 实 际 运 行 时 间 带权周转时间 = \frac{作业周转时间}{作业实际运行时间} 带权周转时间=作业实际运行时间作业周转时间​

平均带权周转时间是指多个作业带权周转时间的平均值

平均带权周转时间 = (作业1的带权周转时间 + … + 作业n的带权周转时间)/n

等待时间是指进程处于等待处理机状态的时间之和，等待时间越长，用户满意度越低。处理机调度算法实际上并不会影响作业执行或者I/O操作的时间，只会影响作业就绪队列中等待所花的时间。

响应时间指从用户提交请求到系统首次产生响应所用的时间。

First-Come, First-Served Scheduling(FCFS)

FCFS调度算法可以由一个FIFO队列轻松实现。当一个进程进入到就绪队列，该进程的PCB就会链接到队尾。当CPU空闲的时候，就会优先执行队列头部的进程。正在执行的进程就会被移除队列。

参考：Convoy Effect in FCFS Scheduling

摘自：《Operating System Concepts》

Assume we have one CPU-bound process and many I/O-bound processes.

假设现有一个绑定CPU和进程和许多绑定I/O设备的进程。

As the processes flow around the system, the following scenario may result.

当进程开始执行的执行，就会出现如下的情况：

The CPU-bound process will get and hold the CPU.

绑定CPU的进程会持续占有CPU

During this time, all the other processes will finish their I/O and will move into the ready queue, waiting for the CPU.

与此同时，其他的进程完成I/O操作之后会进入到就绪队里，等待CPU

While the processes wait in the ready queue, the I/O devices are idle.

当就绪队列中的进程在等待期间，I/O设备一直处于空闲状态。

Eventually, the CPU-bound process finishes its CPU burst and moves to an I/O device.

最终，绑定CPU的进程完成了执行，然后进入到I/O设备

All the I/O-bound processes, which have short CPU bursts, execute quickly and move back to the I/O queues.

所有绑定I/O设备的进程很快的被CPU执行完之后，又回到等待I/O设备的队列中

At this point, the CPU sits idle.

此时，CPU一直处于空闲状态

The CPU-bound process will then move back to the ready queue and be allocated the CPU.

绑定CPU的进程回到就绪队列，然后再次被CPU加载

Again, all the I/O processes end up waiting in the ready queue until the CPU-bound process is done.

等到绑定CPU的进程被执行完毕，绑定I/O设备的进程停止等待

There is a convoy effect as all the other processes wait for the one big process to get off the CPU.

此时存在一个护航效应，所有其他的进程需要等待一个长进程解除CPU的占用

This effect results in lower CPU and device utilization than might be possible if the shorter processes were allowed to go first.

这种效应导致了CPU和设备的利用率低于短进程优先的情况。

如何避免护航效应

像时间片轮转抢占式调度可以用来避免护航效应，每个进程有平等的机会去访问CPU。通过执行这些较短的进程，不必花费太多的时间去等待CPU，使其整体执行速度更快，减少了资源空闲的状态。

短作业优先：Shortested-Job-First(SJF)

短进程优先：Shortested-Process-First(SPF)

短作业（进程）优先调度算法是指对短作业（进程）优先调度的算法。执行过程中，始终优先从就绪队列中选择一个估计运行时间最短的进程，并将处理机分配给它，使其立即执行，直到完成或发生某事件而阻塞的时候，才会释放处理机。

从CPU调度的基本指标来看，SJF是优于FCFS的，SJF调度算法的平均等待时间、平均周转时间最少。但是该算法也存在着不容忽视的缺点：

在实际情况下，操作系统并不知道下一个进程所需要花费的时间是多长，所以其可参考的值是一个预测值，是一个估计值。详情可以参考预测SJF进程的CPU突发时间或者书籍《Operating System Concepts》

We may not know the length of the next CPU burst, but we may be able to predict its value. We expect that the next CPU burst will be similar in length to the previous ones. By computing an approximation of the length of the next CPU burst, we can pick the process with the shortest predicted CPU burst.

我们并不知道下一个进程的具体运行时间，但是我们可以进行估计下一个CPU突发长度的近似值。

The next CPU burst is generally predicted as an exponential average of the measured lengths of previous CPU bursts.

下一个CPU突发通常被预测为前一个CPU突发的测量长度的指数平均值。

t n t_n tn​代表第n个CPU突发的长度，$0 \leq \alpha \leq 1 ， ， ，t_{n+1}$被预测为：

τ n + 1 = α t n + ( 1 − α ) τ n \tau_{n+1} = \alpha t_n + (1 - \alpha)\tau_n τn+1​=αtn​+(1−α)τn​

t n t_n tn​包含了近期的大部分信息，然而 τ n \tau_n τn​存储了过去了历史， α \alpha α控制了最近和过去历史数据的权重比。

]

Highest Response Ratio Next(HRRN)

高响应比优先调度算法主要用于作业调度，是对FCFS算法和SJF算法的一种总和平衡，同时考虑了每个作业的等待时间和估计的运行时间。每次进行作业调度的时候，都需要计算后备作业队列中的响应比，从而选出响应比最高的那个作业加载到内存中。

响应比的变化规律可以描述为：

响 应 比 R p = 等 待 时 间 + 要 求 服 务 时 间 要 求 服 务 时 间 响应比R_p=\frac{等待时间+要求服务时间}{要求服务时间} 响应比Rp​=要求服务时间等待时间+要求服务时间​

注：这几种是算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，但是不关心“响应时间”，也不区分任务的紧急程度，因此对于用户来说，交互性很糟糕。因此这三种算法适合早期的批处理系统。

Round-Robin(RR)

时间片轮转调度算法（抢占式）主要适用于分时系统。系统将所有的就绪进程按照到大时间的先后次序排成一个队列，进程调度程序总是选择就绪队列中的第一个进程执行，即先来先服务原则，但是仅能执行一个时间片。时间片使用完后，即使该进程没有完成执行，也会被剥夺处理机的使用权，处理机需要调出下队列中队首PCB，而被剥夺的进程则回到队尾重新排队。

如果时间片过大，则时间片轮转算法将会退化为先来先服务算法。

如果时间片过小，则处理机就会过于频繁的切换进程，使得处理机的开销增大，而真正用于处理用户进程的时间将减少。

时间片长短主要由以下的因素确定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。

Priority Scheduling

优先级调度算法又称为优先权调度算法，既可以用于作业调度，也可以用于进程调度。优先级代表了该作业运行的紧迫程度。

作业调度：每次从后诶作业队列中选择优先级最高的一个或者几个作业，将它们调入内存，分配必要的资源，创建进程并放入就绪队列。

进程调度：每次从就绪队列中选择优先级最高的进程，将处理机分配给它，使之投入运行。

另外，根据进程创建后优先级是否可以改变，也可以将进程的优先级分为：静态优先级和动态优先级。

优先级在创建进程的时候就已经确定了，在整个进程运行期间是不变的。确定优先级的主要依据有进程类型、进程对资源的要求、用户要求。

在进程的运行期间，根据进程情况的变化动态的调整优先级。动态调整优先级的主要依据有进程占有CPU时间的长短、就绪进程等待CPU时间的长短。

一般而言，进程的优先级设置可以参考如下的原则：

Multilevel Feedback Queue Scheduling

多级反馈队列调度算法是时间片轮转调度算法和优先级调度算法的综合与发展。通过动态的调整时间片和优先级的大小，该算法可以兼顾多方面的系统目标。例如，为提高系统吞吐量和缩短平均周转时间而照顾短进程；为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程，同时也不用事先估计进程的执行时间。

主要实现原理：

注：比起早期的批处理操作系统来说，由于计算机造价大幅降低，因此之后出现的交互式操作系统（包括分时操作系统、实时操作系统等）更注重系统的响应时间、公平性、平衡性等指标。而这几种算法恰好也能较好地满足交互式系统的需求。因此这三种算法适合用于交互式系统。（比如UNIX使用的就是多级反馈队列调度算法）