物理层

物理层为设备之间的数据通信提供传输媒体及互连设备，为数据传输提供可靠的环境。

通信方式

根据信息在传输线上的传送方向，分为以下三种通信方式：

• 单工通信：单向传输
• 半双工通信：双向交替传输
• 全双工通信：双向同时传输

信号分类

• 模拟信号：连续量
• 数字信号：离散量，码元是代表不同离散数值的基本波形

基本带通调制方法

带通调制把数字信号转换为模拟信号。

• 调幅（AM）：调整振幅，垂直调整
• 调频（FM）：调整频率，水平调整
• 调相（PM）：初始相位的调整，移位调整。

物理层设备（集线器、中继器）

中继器

• 诞生原因：由于存在损耗，在线路上传输的信号功率会逐渐衰减，衰减到一定程度时将造成信号失真，因此会导致接收错误。

• 中继器的功能：对信号进行再生和还原，对衰减的信号进行放大，保持与原数据相同，以增加信号传输的距离，延长网络的长度。简单来说，中继器就是在再生数字信号。

中继器只将任何电缆段上的数据发送到另一端电缆上，它仅作用于信号的电气部分，并不管数据中是否有错误数据或不适于网段的数据。

集线器（多口中继器）

• 集线器的功能：对信号进行再生放大转发，对衰减的信号进行放大，接着转发到其他所有（除输入端口外）处于工作状态的端口上，以增加信号传输的距离，延长网络的长度。不具备定向传送信号的能力，属于共享式设备。（一般采用广播方式）

参考资料

CS-Notes
物理层设备

以太网

以太网是一种计算机局域网技术。IEEE组织的IEEE 802.3标准制定了以太网的技术标准，它规定了包括物理层的连线、电子信号和介质访问层协议的内容。以太网是目前应用最普遍的局域网技术。
以太网有两类：第一类是经典以太网，第二类是交换式以太网，使用了一种称为交换机的设备连接不同的计算机。经典以太网是以太网的原始形式，运行速度从3~10 Mbps不等；而交换式以太网正是广泛应用的以太网，可运行在100、1000和10000Mbps那样的高速率，分别以快速以太网、千兆以太网和万兆以太网的形式呈现。

互联网是网络的网络

网络把主机连接起来，而互连网（internet）是把多种不同的网络连接起来，因此互连网是网络的网络。互联网（Internet）是全球范围的互连网。

ISP(网络服务提供商)

互联网服务提供商 ISP 可以从互联网管理机构获得许多 IP 地址，同时拥有通信线路以及路由器等联网设备，个人或机构向 ISP 缴纳一定的费用就可以接入互联网。

目前的互联网是一种多层次 ISP 结构，ISP 根据覆盖面积的大小分为第一层 ISP、区域 ISP 和接入 ISP。互联网交换点 IXP(互联网交换中心，功能相当于计算机网络中所提及的交换机) 允许两个 ISP 直接相连而不用经过第三个 ISP。

主机之间的通信方式

• 客户-服务器（C(client)/S(server)）：客户是服务的请求方，服务器是服务的提供方。
• 对等（P2P）：不区分客户和服务器。

分组

分组是将一个数据包分成一个个更小的数据包的操作。

交换

简单地讲，就是服务器与服务器之间的数据交换。

电路交换、报文交换和分组交换

• 电路交换：电路交换用于电话通信系统，两个用户要通信之前需要建立一条专用的物理链路，并且在整个通信过程中始终占用该链路。由于通信的过程中不可能一直在使用传输线路，因此电路交换对线路的利用率很低，往往不到 10%。电路交换的三个阶段：1.建立连接，2.数据传输，3.释放连接

• 报文交换(不常用)：整个报文先传输到相邻的结点，全部存储下来后查找转发表，转发到下一个结点。

• 分组交换：单个分组(报文的一部分)传送到相邻结点，相邻结点存储下来后查找转发表，转发到下一个结点，即是一种采取把小数据包存储转发传输的机制。每个分组都有首部和尾部，包含了源地址和目的地址等控制信息，在同一个传输线路上同时传输多个分组互相不会影响，因此在同一条传输线路上允许同时传输多个分组，也就是说分组交换不需要占用传输线路。类比于邮局通信系统，邮局收到一份邮件之后，先存储下来，然后把相同目的地的邮件一起转发到下一个目的地，这个过程就是存储转发过程，分组交换也使用了存储转发过程。

速率

指的是单位时间传送的比特数，其单位是 b/s(比特每秒)。一个比特(bit)就是一个二进制数字中的一个 1 或 0。

带宽

在计算机网络中，带宽用来表示通信线路的数据传输能力，因此网络带宽指的是在单位时间内从网络中的某一点到另一点所能通过的最高速率。

时延

时延指的是数据从网络的一端传送到另一端所需的时间。
总时延 = 排队时延 + 处理时延 + 传输时延（发送时延）+ 传播时延

• 排队时延：分组在进入路由器后要先在输入队列中等待处理。在路由器确定了转发接口后还需要在输出队列中等待转发，所以就产生了排队时延。分组在路由器的输入队列和输出队列中排队等待的时间，取决于网络当前的通信量。

• 处理时延：主机或者路由器在接受到分组时候要花费一定的时间进行处理，例如分析分组的首部，从分组中提取数据部分，运行差错检验或是查找适当的路由等等。

• 传输时延（发送时延）：主机或者路由器发送数据帧所需要的时间。
  

• 传播时延：电磁波在信道中传播一定距离需要花费的时间
  

计算机网络体系结构

1. 五层协议：

• 应用层：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等协议。数据单位为报文。

• 传输层：为进程提供通用数据传输服务。由于应用层协议很多，定义通用的传输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服务，数据单位为用户数据报。TCP 主要提供完整性服务，UDP 主要提供及时性服务。

• 网络层：为主机提供数据传输服务。而传输层协议是为主机中的进程提供数据传输服务。网络层把传输层传递下来的报文段或者用户数据报封装成分组。

• 数据链路层：网络层针对的还是主机之间的数据传输服务，而主机之间可以有很多链路，链路层协议就是为同一链路的主机提供数据传输服务。数据链路层把网络层传下来的分组封装成帧。

• 物理层：考虑的是怎样在传输媒体上传输数据比特流，而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异，使数据链路层感觉不到这些差异。

2. OSI七层模型

• 表示层：数据压缩、加密以及数据描述，这使得应用程序不必关心在各台主机中数据内部格式不同的问题。

• 会话层：建立及管理会话。

五层协议没有表示层和会话层，而是将这些功能留给应用程序开发者处理。

3. TCP/IP

它只有四层，相当于五层协议中数据链路层和物理层合并为网络接口层。

TCP/IP 体系结构不严格遵循 OSI 分层概念，应用层可能会直接使用 IP 层或者网络接口层。

数据在各层之间的传递过程

在向下层传递的过程中，需要添加下层协议所需要的首部或者尾部，而在向上的过程中不断拆开首部和尾部。

路由器只有下面三层协议，因为路由器位于网络核心中，不需要为进程或者应用程序提供服务，因此也就不需要传输层和应用层。

参考资料

CS-Notes
电路交换，报文交换，分组交换

编译系统

一个hello.c程序：

1
2
3
4
5
6
7

#include <stdio.h>

int main()
{
    printf("hello, world\n");
    return 0;
}

1

gcc -o hello hello.c

对于上述gcc命令，不跟任何的选项的话，会默认执行预处理、编译、汇编、链接这整个过程；如果程序没有错，就会得到一个可执行文件，默认为a.out。

• -E选项：提示编译器执行完预处理就停下来，后边的编译、汇编、链接就先不执行了。
• -S选项：提示编译器执行完编译就停下来，不去执行汇编和链接了。
• -c选项：提示编译器执行完汇编就停下来。

以上三种选项限定了编译器执行操作的停止时间，而不是单独的将某一步拎出来执行。

• -o选项：输出名字的参数，指定输出的文件名；不用-o则一般会在当前文件夹下生成默认的a.out文件作为可执行程序

• -O选项：对程序进行优化编译、链接，采用这个选项，整个源代码会在编译、链接过程中进行优化处理，这样产生的可执行文件的执行效率可以提高，但是，编译、链接的速度就相应地要慢一些。比如氧气优化-O2。（吸口氧，呼呼）

编译的整个过程如下：

• 预处理阶段(hello.c -> hello.i)：预处理器（cpp）根据以字符#开头的命令，修改原始的C程序。处理包括：#include，#define，条件编译指令(#if，#ifdef…)，删除注释等内容；添加行号和文件标识名；保留所有的#pragma编译指令(留待编译器使用)
• 编译阶段(hello.i -> hello.s)：翻译成汇编文件；
• 汇编阶段(hello.s -> hello.o)：将汇编文件翻译成可重定位目标文件；汇编器将 hello.s 翻译成机器语言指令，把这些指令打包成一种叫做可重定位目标程序的格式，并将结果保存在目标文件 hello.o 中。 hello.o 文件是一个二进制文件，它的字节编码是机器语言指令而不是字符。
• 链接阶段(hello.o + 其他.o文件 -> hello)：在本例中调用了 printf() 函数，因此需要使用链接器将重定位目标文件 hello.o 和 printf.o 等单独预编译好的目标文件进行合并，得到最终的可执行目标文件（简称可执行文件，可以被加载到内存中，由系统执行）。

库

• 库是写好的，现有的，成熟的，可以复用的代码。现实中每个程序都要依赖很多基础的底层库。
• 本质上来讲，库是一种可执行代码的二进制形式，可以被操作系统载入内存执行。

静态链接

静态链接器以一组可重定位目标文件为输入，生成一个完全链接的可执行目标文件作为输出；在链接阶段，要把所有需要的函数的二进制代码都包含到可执行文件中去。

优点：

• 在可执行程序中具备了执行程序所需要的所有东西，执行时运行速度快。

缺点：

• 浪费空间：每个可执行程序对需要的目标文件都有一份副本，目标文件可能会在内存中有多个副本。
• 更新困难：每当库函数的代码被修改，就需要重新进行编译链接形成可执行程序。

链接器主要完成以下两个任务：

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

动态链接

为了解决静态链接中：空间浪费、更新困难两大问题。动态链接把程序按照模块拆分成各个相对独立部分，在程序运行时才将它们链接在一起形成一个完整的程序，而不是像静态链接一样把所有程序模块都链接成一个单独的可执行文件。

特点：

• 在给定的文件系统中一个动态库只有一个文件，所有引用该库的可执行目标文件都共享这个文件，它不会被复制到引用它的可执行文件中;
• 在内存中，一个共享库的已编译程序的机器代码的一个副本可以被不同的正在运行的进程共享。
• Linux 系统：.so 后缀;
• Windows 系统：.DLL 后缀;

优点：

• 节省空间：因为即使所有程序都依赖都一个库，但是该库在内存中只存在一个副本。
• 更新方便：因为更新时只需要替换原来的目标文件，而无需将所有的程序再重新链接一遍。当程序下一次运行时，新版本的目标文件会自动加载到内存中并且链接起来。

缺点：

• 由于是运行时加载，可能会影响程序的前期执行性能。

目标文件

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

参考资料

CS-Notes
编译和链接的过程
gcc -o hello hello.c 执行过程

磁盘结构

• 盘面（Platter）：一个磁盘有多个盘面；
• 磁道（Track）：盘面上的圆形带状区域，一个盘面可以有多个磁道；
• 扇区（Track Sector）：磁道上的一个弧段，一个磁道可以有多个扇区，它是最小的物理储存单位，目前主要有 512 bytes 与 4 K 两种大小；
• 磁头（Head）：与盘面非常接近，能够将盘面上的磁场转换为电信号（读），或者将电信号转换为盘面的磁场（写）；
• 制动手臂（Actuator arm）：用于在磁道之间移动磁头；
• 主轴（Spindle）：使整个盘面转动。

磁盘调度算法

读写一个磁盘块的时间的影响因素有：

• 旋转时间（主轴转动盘面，使得磁头移动到适当的扇区上）
• 寻道时间（制动手臂移动，使得磁头移动到适当的磁道上）
• 实际的数据传输时间

其中，寻道时间最长，因此磁盘调度的主要目标是使磁盘的平均寻道时间最短。

1. 先来先服务(FCFS, First Come First Served)

按照磁盘请求的顺序进行调度。
优点是公平和简单。缺点也很明显，因为未对寻道做任何优化，使平均寻道时间可能较长。

2. 最短寻道时间优先(SSTF, Shortest Seek Time First)

优先调度与当前磁头所在磁道距离最近的磁道。

虽然平均寻道时间比较低，但是不够公平。如果新到达的磁道请求总是比一个在等待的磁道请求近，那么在等待的磁道请求会一直等待下去，也就是出现饥饿现象。具体来说，两端的磁道请求更容易出现饥饿现象。

3.电梯算法(SCAN，也称扫描算法)

电梯总是保持一个方向运行，直到该方向没有请求为止，然后改变运行方向。

电梯算法和电梯的运行过程类似，总是按一个方向来进行磁盘调度，直到该方向上没有未完成的磁盘请求，然后改变方向。

因为考虑了移动方向，因此所有的磁盘请求都会被满足，解决了 SSTF 的饥饿问题。

参考资料

CS-Notes

虚拟内存

虚拟内存使得物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。虚拟内存允许执行中的进程只有部分在内存中，因此程序可以比物理内存大。而且虚拟内存将内存抽象成一个巨大的数组，将用户视界的逻辑内存与物理内存分离，使得程序员不受内存存储的限制。虚拟内存展现在程序员面前的是一个比物理内存要大得多的、地址连续的内存空间，而事实上是映射到支离破碎的物理内存，乃至磁盘上。

分页存储管理

逻辑空间分页，物理空间分块，页与块同样大，页连续块离散，用页号查页表，由硬件做转换，页面和内存块大小一般选为2的若干次幂。
页表作用：实现从页号到物理地址的映射
将用户程序的逻辑地址空间分为若干个固定大小的区域，称为“页”或“页面”，典型的页面大小为1KB；相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
一个虚拟地址分成两个部分，前一部分存储页面号，后一部分存储偏移量。
内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就会发生缺页中断，将缺页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。算法的主要目标是使页面置换频率最低（缺页率最低）。

• 最佳置换算法：所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。（理想化的，不可实现，因为无法知道一个页面多长时间不再被访问）
• 最近最久未使用（LRU，Least Recently Used）：将最近最久未使用的页面换出。
• 最近未使用（NRU，Not Recently Used）：有两个状态位R与M，页面被访问时置R = 1， 页面被修改时置M = 1。
  当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。
  NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。
• 先进先出（FIFO）：简单，但是会把经常被访问的页面换出，提高了缺页率。
• 第二次机会算法 （FIFO的改进）：为每个页面设置了一个访问标志位R，对该页面访问时将该位置1；需要页面置换时，检查最老页面的R值，0立即替换；1则清零后放入链表尾部，重新搜索。
• 时钟（第二次机会算法的改进）：采用环形链表。

分段式存储管理

使用分页系统的一维地址空间，其动态增长的特点会出现覆盖的问题。为了使程序和数据划分开来，不出现覆盖问题而使用分段，程序和数据就在逻辑上拥有独立的地址空间。
分段是一种二维结构，把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。
段的长度由相应的逻辑信息组的长度决定，因而各段长度不等，引入分段存储管理方式的目的主要是为了满足用户（程序员）在编程和使用上多方面的要求。完整的逻辑意义信息，就是说将程序分页时，页的大小是固定的，只根据页面大小大小死生生的将程序切割开；而分段时比较灵活，只有一段程序有了完整的意义才将这一段切割开。（例如将一个人每隔50厘米切割一段，即为分页；而将一个人分割为头部、身体、腿部（有完整逻辑意义）三段，即为分段）

段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。（地址空间分段，分段的基础上再分页）

分页与分段的比较

• 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
• 地址空间的维度：分页是一维地址空间，分段是二维的。
• 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

参考资料

CS-Notes

进程通信(IPC, Inter Process Communication)的六种方式

进程通信：进程间传输信息。
进程通信是一种手段，而进程同步是一种目的。也可以说，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息。

1. 管道

2. FIFO（命名管道）

3. 消息队列

4. 信号量

5. 共享储存

6. 套接字

参考资料

CS-Notes

进程同步的四种方式

进程同步：控制多个进程按一定顺序执行；

1. 临界区

对临界资源进行访问的那段代码称为临界区。为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。

2. 同步与互斥

同步：多个进程因为合作产生的直接制约关系，使得进程有一定的先后执行关系。
互斥：多个进程在同一时刻只有一个进程能进入临界区。互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权限。

3. 信号量

信号量（Semaphore）是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。
down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。
down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1，那么就成为了互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。
使用信号量实现生产者-消费者问题（代码看一下）

4. 管程

管程可以看做一个软件模块，它是将共享的变量和对于这些共享变量的操作封装起来，形成一个具有一定接口的功能模块，进程可以调用管程来实现进程级别的并发控制。
管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

经典同步问题（代码实现）

1. 哲学家进餐问题

2. 读者写者问题

参考资料

CS-Notes
管程的理解

进程和线程

进程：

1. 操作系统对正在运行的程序的一种抽象，程序是指令、数据及其组织形式的描述，进程是程序的实体。
2. 指在系统中正在运行的一个应用程序；程序一旦运行就是进程。
3. 进程是操作系统资源分配的最小单位。

线程：

1. 是操作系统能够进行运算调度的最小单位。
2. 包含在进程之中，是进程中的实际运作单位。
3. 一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。
4. 系统分配处理器时间资源的基本单元，或者说进程之内独立执行的一个单元执行流。

一个程序至少有一个进程,一个进程至少有一个线程。

进程与线程区别：

1. 资源拥有：进程是cpu资源分配的最小单位，线程不拥有资源，线程可以访问隶属于进程的资源，是CPU调度的最小单位。
2. 调度：线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。
3. 系统开销：进程在创建、切换和销毁时开销比较大，而线程比较小。进程创建的时候需要分配系统资源，而销毁的的时候需要释放系统资源。线程切换时只需保存和设置少量寄存器内容，开销很小。
4. 通信：线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。
5. 一个进程崩溃，不会对其他进程产生影响；而一个线程崩溃，会让同一进程内的其他线程也死掉。

参考资料

CS-Notes

进程调度算法：

根据系统的资源分配策略所规定的资源分配算法；不同的环境调度算法不同。

1.批处理系统

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量和周转时间（从提交到终止的时间）。

1.1 先来先服务 first-come first-serverd（FCFS）

非抢占式的调度算法，按照请求的顺序进行调度。
当每个进程就绪后，它加入就绪队列。当前正运行的进程停止执行，选择在就绪队列中存在时间最长的进程运行。
该算法既可以用于作业调度，也可以用于进程调度。有利于长作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能执行，而长作业又需要执行很长时间，造成了短作业等待时间过长。

1.2 短作业优先 shortest job first（SJF）

非抢占式的调度算法，按估计运行时间最短的顺序进行调度。从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。
长作业有可能会饿死（不是“死锁”），处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来，那么长作业永远得不到调度。

1.3 最短剩余时间优先 shortest remaining time next（SRTN）

抢占式的调度算法，最短作业优先的抢占式版本。当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程，否则新的进程等待。存在长进程饥饿的危险。

2.交互式系统

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行响应。

2.1 时间片轮转

按 FCFS 的原则将所有就绪进程排成队列。每次调度时，把 CPU 时间分配给队首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续把 CPU 时间分配给队首的进程。
算法的效率和时间片的大小有很大关系：
进程切换要保存进程的信息并且载入新进程的信息，如果时间片太小，会导致进程切换得太频繁，在进程切换上就会花过多时间；如果时间片过长，那么实时性就不能得到保证。

2.2 优先级调度

为每个进程分配一个优先级，按优先级进行调度。
为了防止低优先级的进程永远等不到调度，可以随着时间的推移增加等待进程的优先级。

2.3 多级反馈队列

公认的一种较好的进程调度算法。
若一个进程需要执行 100 个时间片，如果采用时间片轮转调度算法，那么需要交换 100 次。
多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..(随着优先降低时间片变长)。进程在第一个队列没执行完，就会被移到下一个队列。这种方式下，之前的进程只需要交换 7 次（1 + 2 + 4 + 8 + 16 + 32 + 64 > 100）。
每个队列优先权也不同，最上面的优先权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。

3.实时系统

实时系统要求一个请求在一个确定时间内得到响应。
分为硬实时和软实时，前者必须满足绝对的截止时间，后者可以容忍一定的超时。

参考资料

CS-Notes
进程常用调度算法

进程状态：

• 就绪状态（Ready）：等待被调度
• 运行状态（Running）
• 阻塞状态（Waiting）：等待资源

状态间切换要注意：

1. 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
2. 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

参考资料

CS-Notes