知识点梳理

知识点梳理

计算机网络

TCP

TCP之流量控制和拥塞控制

流量控制

拥塞控制

拥塞控制算法

慢开始与拥塞避免

快重传与快恢复

IP

IP地址

IP地址分类

A类，B类，C类

子网掩码

网络地址与广播地址计算

操作系统

进程与线程

进程的五种状态

调度算法

特殊名词解释

常见调度算法

先来先服务调度算法（FCFS）

短作业优先调度算法（SJF）

高响应比优先调度算法（HRRN）

时间片轮转调度算法（RR）

优先级调度算法

多级反馈队列调度算法

总结

附注：

死锁

四个必要条件

处理死锁的方法

 

计算机网络

TCP

TCP之流量控制和拥塞控制

流量控制：如果发送方把数据发送得过快，接收方可能会来不及接收，这就会造成数据的丢失。

拥塞控制：拥塞控制就是防止过多的数据注入到网络中，这样可以使网络中的路由器或链路不致过载。

两者的区别：流量控制是为了预防拥塞。如：在马路上行车，交警跟红绿灯是流量控制，当发生拥塞时，如何进行疏散，是拥塞控制。流量控制指点对点通信量的控制。而拥塞控制是全局性的，涉及到所有的主机和降低网络性能的因素。

流量控制

滑动窗口实现流量控制

应答策略缺点：对每一个发送的数据段，都要给一个ACK确认应答，收到ACK后再发送下一个数据段，这样做有一个比较大的缺点，就是性能比较差，尤其是数据往返的时间长的时候。

滑动窗口优点：可以高效可靠的一次发送大量的数据、量控制

滑动窗口：类似于一个窗口一样的东西，是用来告诉发送端可以发送数据的大小即：窗口标记了接收端缓冲区的大小

滑动窗口机制：TCP的滑动窗口的可靠性也是建立在“确认重传”基础上的。

发送窗口只有收到对端对于本段发送窗口内字节的ACK确认，才会移动发送窗口的左边界。

接收端可以根据自己状况通告窗口大小，从而控制发送端的接收，进行流量控制。

拥塞控制

拥塞控制机制：慢开始( slow-start )、拥塞避免( congestion avoidance )、快重传( fast retransmit )和快恢复( fast recovery )

名词介绍

慢开始：不要一开始就发送大量的数据，先探测一下网络的拥塞程度，也就是说由小到大逐渐增加拥塞窗口的大小。

拥塞避免：让拥塞窗口缓慢增长，即每经过一个往返时间RTT就把发送发的拥塞窗口cwnd加1，而不是加倍。

快重传：要求接收方在收到一个失序的报文段后就立即发出重复确认，发送方收到3个重复确认立即重传对方尚未收到的报文段。

快恢复：当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。但接下来不慢开始，而是执行拥塞避免。

拥塞窗口（cwnd，congestion window）：大小取决于网络的拥塞程度，并且动态地在变化。

拥塞控制算法

拥塞控制的具体过程如下：

1. TCP连接初始化，将拥塞窗口设置为1
2. 执行慢开始算法，cwnd按指数规律增长
3. 直到cwnd=ssthresh时，开始执行拥塞避免算法，cwnd线性增长，加法增大
4. 当网络发生拥塞，把ssthresh = cwnd/2乘法减小，cwnd重新设置为1，按照步骤（2）执行。重新慢开始
5. 当报文段丢失，收到三个确认，把ssthresh = cwnd/2乘法减小，快重传丢失的报文段。
6. 报文段丢失为非拥塞情况，启动快恢复，cwnd=ssthresh新，按照步骤（3）执行。重新拥塞控制

慢开始与拥塞避免

慢开始：拥塞窗口cwnd指数增长。最开始设cwnd为1，慢启动算法每经过一个传输轮次（认为发送方都成功接收接收方的确认），拥塞窗口cwnd就加倍。

为了防止cwnd增长过大引起网络拥塞，还需设置一个慢开始门限ssthresh状态变量。ssthresh的用法如下：

当cwnd < ssthresh时，使用慢开始算法。

当cwnd > ssthresh时，改用拥塞避免算法。

当cwnd = ssthresh时，慢开始与拥塞避免算法任意。

拥塞避免（AIMD：加法增大乘法减小）：拥塞窗口cwnd线性增长。

1. 乘法减小：只要网络出现超时，就是将cwnd置为1，ssthresh   置为cwnd的一半，然后开始执行慢启动算法（cwnd<ssthresh）。
2. 加法增大：当网络频发出现超时情况时，ssthresh就下降的很快，为了减少注入到网络中的分组数，而加法增大是指执行拥塞避免算法后，拥塞窗口cwnd缓慢的增大，以防止网络过早出现拥塞。

快重传与快恢复

快重传：

1. 要求接收方在收到一个失序的报文段后就立即发出重复确认（为的是使发送方及早知道有报文段没有到达对方），而不要等到自己发送数据时捎带确认。
2. 快重传算法规定，发送方只要一连收到3个重复确认就应当立即重传对方尚未收到的报文段，而不必继续等待设置的重传计数器时间到期。

快恢复：

1. 当发送方连续收到三个重复确认，就执行“乘法减小”算法，把慢开始门限ssthresh减半。这是为了预防网络发生拥塞。请注意：接下去不执行慢开始算法。
2. 由于发送方现在认为网络很可能没有发生拥塞，因此与慢开始不同之处是现在不执行慢开始算法（即拥塞窗口cwnd现在不设置为1），而是把cwnd值设置为慢开始门限ssthresh减半后的数值，然后开始执行拥塞避免算法（“加法增大”），使拥塞窗口缓慢地线性增大。

IP

IP地址

IP地址是一个32位的二进制数，通常被分割为4个“8位二进制数”（也就是4个字节）。IP地址通常用“点分十进制”表示成（a.b.c.d）的形式，其中，a,b,c,d都是0~255之间的十进制整数。例：点分十进IP地址（100.4.5.6），实际上是32位二进制数（01100100.00000100.00000101.00000110）。

IP地址=网络地址+主机地址

IP地址分类

A类，B类，C类

概念	特征	网络范围	默认掩码
A类地址	第1个8位中的第1位始终为0	0-127.x.x.x	255.0.0.0/8
B类地址	第1个8位中的第1、2位始终为10	128-191.x.x.x	255.255.0.0/16
C类地址	第1个8位中的第1、2、3位始终为110	192-y.x.x.x	255.255.255.0/24

特殊

D类 以1110开始 用于组播

E类 以11110开始 用于科研保留

 

范围上划分有些要注意的：

A类 从1.0.0.0 到126.255.255.255

B类 从128.0.0.0到191.255.255.255

C类 从192.0.0.0到223.255.255.255

其中127.x.x.x段地址空间是被保留的回环地址

IP地址包含 网络地址+主机地址，即IP地址=网络地址+主机地址

子网掩码

子网掩码(subnet mask)又叫网络掩码、地址掩码、子网络遮罩，它是一种用来指明一个IP地址的哪些位标识的是主机所在的子网，以及哪些位标识的是主机的位掩码。

子网掩码不能单独存在，它必须结合IP地址一起使用。子网掩码只有一个作用，就是将某个IP地址划分成网络地址和主机地址两部分。
子网掩码是一个32位地址，用于屏蔽IP地址的一部分以区别网络标识和主机标识，并说明该IP地址是在局域网上，还是在远程网上。

子网掩码——屏蔽一个IP地址的网络部分的“全1”比特模式。对于A类地址来说，默认的子网掩码是255.0.0.0；对于B类地址来说默认的子网掩码是255.255.0.0；对于C类地址来说默认的子网掩码是255.255.255.0。

1. 通过子网掩码，就可以判断两个IP在不在一个局域网内部。
2. 子网掩码可以看出有多少位是网络号，有多少位是主机号

 

 

网络地址与广播地址计算

IP地址 = y1,y2,y3,y4/ n;  前x位为子网号，后32-x位为主机号

子网掩码 = 11111111(n位个1) 000(32- n位个0) 

网络地址 = 子网掩码 与 IP地址 （IP地址主机号全0）

广播地址 = 网络地址不变，主机地址变为1（IP地址主机号全1）

 

网络号位数向主机号借的位数：x = n%8

主网号：z = n – x  前z位

子网号：前n位

主机号：m = 32 – n

 

主机数：2^m – 2 (m为主机位数)

子网数：2 ^ x = y  (n表示以8为一个单元向主机位借了多少个位，y为划分多少个子网)

      如255.255.255.224 == 11111111.11111111.11111111.11100000

操作系统

进程与线程

1. 进程：即程序，一个具有一定独立功能的程序在一个数据集上的一次动态执行的过程，是操作系统进行资源分配和调度的一个独立单位，是应用程序运行的载体。
2. 线程：程序执行中一个单一的顺序控制流程，是程序执行流的最小单元，是处理器调度(CPU)和分派的基本单位。
3. 进程与线程对比如下：

	进程	线程
基本单位	操作系统资源分配和调度的基本单位	CPU任务调度和执行的基本单位
包含关系	一个进程中可以包括多个线程，>=1个线程	线程是进程的一部分
开销	每个进程都有独立的代码和数据空间（程序上下文），程序之间的切换会有较大的开销	同一类线程共享代码和数据空间，每个线程都有独立的运行栈空间，线程之间切换的开销小。
所处环境	操作系统中能同时运行多个进程（程序）	在同一个进程（程序）中有多个线程同时执行（通过CPU调度，在每个时间片中只有一个线程执行）
内存空间	系统在运行的时候会为每个进程分配不同的内存空间	除了CPU外，系统不会为线程分配内存（线程所使用的资源来自其所属进程的资源），线程组之间只能共享资源，但有独立栈(不共享)

1. 并发与并行：

并发，从宏观方面来说，并发就是同时进行多种事件，实际上，这几种事件，并不是同时进行的，而是交替进行的，而由于CPU的运算速度非常的快，会造成我们的一种错觉，就是在同一时间内进行了多种事情。

并行，则是真正意义上的同时进行多种事情。这种只可以在多核CPU的基础下完成。

进程的五种状态

调度算法

特殊名词解释

1. 调度：操作系统管理的系统资源有限，当有多个进程（或多个进程发出的请求）要使用这些资源时，必须按照一定的原则选择进程（请求）来占用资源。也就是说调度的实质是一种资源分配。
2. 调度算法：根据系统的资源分配策略所规定的资源分配算法。
3. 作业调度：根据作业控制块(JCB)中的信息，检查系统中的资源是否能满足作业对资源的需求，以及按照一定的调度算法，从外存的后备队列中选取某些作业调入内存，并为他们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上等待调度。因此，也把作业调度称为接纳调度。
4. 进程调度：当计算机系统处于就绪状态的用户进程数多于CPU数时，就会产生多个进程或线程同时竞争CPU的结果。假设现在只有一个CPU可用，那么操作系统就必须选择一个进程运行，并把处理机分配给该进程。
5. 非抢占式算法：在采用这种调度方式时，一旦把处理机分配给某进程时，就让它一直运行下去，绝不会因为时钟中断或者任何其他原因去抢占当前正在运行进程的处理机，直至该进程完成，或者因为发生某件事被阻塞时，才主动把处理机分配给别的进程。
6. 抢占式算法：这种调度方式允许调度程序根据某种规则，去暂停某个正在执行的进程，将已经分配给该进程的处理机重新分配给另一进程。（当然，抢占是有一定原则的：1）优先权原则；2）短进程优先原则；3）时间片原则）
7. 死锁：是指两个或两个以上的进程（或线程）在执行过程中，因争夺资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。
8. 活锁：是指线程1可以使用资源，但它很礼貌，让其他线程先使用资源，线程2也可以使用资源，但它很绅士，也让其他线程先使用资源。这样你让我，我让你，最后两个线程都无法使用资源。
9. 饥饿：类似于非公平锁机制，多个线程在等待资源的时候，有一个很早就在等待的线程一直获取不到锁，反而让后面来的线程获得了锁

常见调度算法

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
公平 等待时间长的先执行	按照作业/进程到达的先后顺序进行调度 ，即:优先考虑在系统中等待时间最长的作业	进程调度 作业调度	非抢占算法	易于理解且实现简单，只需要一个队列(FIFO)，且相当公平。	排在长进程后的短进程的等待时间大，带权周转时间大，不利于短作业/进程	不会

短作业优先调度算法（SJF）

又称为“短进程优先”SPN(Shortest Process Next)

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
减少平均周转时间 执行时间短	执行时间最短的进程/作业优先得到服务	进程调度 作业调度	非抢占算法	改善平均周转时间和平均带权周转时间，缩短进程的等待时间，提高系统的吞吐量。	不公平，对长作业不友好，对短作业友好	会 长作业饥饿

优先权=响应比=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
综合考虑等待时间和运行时间	在每次调度时，先计算各个作业/进程的优先权，选择优先权高的进行服务	进程调度 作业调度	非抢占算法	等待时同:服务时间定优先权，SJF优点。服务时同，等待时间定优先权，FCFS优点	需要计算优先权，增加系统开销	不会

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
公平的、轮流的为各个进程服务	系统根据FCFS策略，将所有的就绪进程排成一个就绪队列。轮流让各个进程执行一个时间片的CPU，若进程未在一个时间片内执行完，则被剥夺处理机，将进程放到就绪队列队尾重新排队。	进程调度	抢占算法	公平、响应快，适用于分时操作系统	由于高频率的进程切换，增加了开销，并且它不区分任务的紧急程度	不会

时间片大小的确定

• 时间片过小：有利于短作业，因为它能在该时间片内完成，但是，意味着频繁的执行进程调度和进程上下文的切换，增加系统的开销。即：退化为短作业优先算法 。
• 时间片过大：每个进程都能在一个时间片内完成，即退化为FCFS算法。

优先级调度算法

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
根据任务的紧急程度进行调度	调度时选择优先级最高的作业/进程，为其分配处理机	进程调度 作业调度 I/O调度	抢占式算法和非抢占式算法	用优先级区分任务的紧急程度，适用于实时操作系统	如果有源源不断的高优先级进程到来，那么低优先级的进程可能会饥饿	会

优先级确定

优先级是利用某一范围内的整数来表示的，又把该整数称为优先数（优先数的大小并不一定和优先级成正比）。确定优先级大小的依据如下;

• 进程类型
• 进程对资源的需求
• 用户要求

优先级的类型

• 静态优先级：在创建进程时确定的，在进程的整个运行期间保持不变。虽然静态优先级简单易行，系统开销小，但是不够精确，可能会出现优先级低的进程长期没有被调度的情况。
• 动态优先级：在创建程序之初，先赋予其一个优先级，然后其值随进程的推进或者等待时间的增加而改变，以获得更好的调度性能。

多级反馈队列调度算法

算法思想	算法规则	适用调度类型	是否可抢占	优点	缺点	是否饥饿
对以上调度算法的权衡和弥补	1.设置多个就绪队列，各级队列优先级由高到低，时间片从小到大；2.进程到达时先进入Q1队列队尾，按照FCFS的原则排队等待被分配时间片；若时间片已经用完进程还没结束，则进程进入Q2队尾，依次往推移。如果此时进程已经在最低一级的队列，则将其重新放回该队列的队尾； 3.有第k级队列为空时，才会为第k+1级队列分配时间片	进程调度	抢占式算法，新进程进入优先权更高的队列（1～(i-1)），此时新进程将抢占正在运行进程的队列i的处理机，正在运行的进程放回到第i队列的末尾。	对各类进程都比较公平，每个新到达的进程都会很快得到响应，短进程只用较少的时间就可以完成，不用估计进程的运行时间	/	导致饥饿概率不大

• 先来先服务调度算法FCFS, 最短作业优先SJF, 最高响应比优先法HRRN三种算法主要关心对用户的公平性、平均周转时间、平均等待时间等评价系统整体性能的指标，并不关心相应时间，也不区分任务的紧急程度，交互性糟糕。因此，这三种方式适用于早期的批处理系统。
• 时间片轮转调度算法（RR），优先级调度算法，多级反馈队列调度算法注重响应时间，公平性等，因此，这三种算法适用于交互式系统。

附注：

死锁

Def：多线程以及多进程改善了系统资源的利用率并提高了系统 的处理能力。然而，并发执行也带来了新的问题——死锁。

死锁是指两个或两个以上的进程（线程）在运行过程中互相持有对方需要的资源而争夺资源，导致这些进程（线程）处于等待状态，无法执行

四个必要条件

1. 互斥性：进程要求对所分配的资源（如打印机）进行排他性控制，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
2. 请求和保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
3. 非剥夺：进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。
4. 循环等待：发生死锁时，线程进入死循环，永久阻塞。

处理死锁的方法

预防、避免为主，检测、解除为辅

预防死锁：通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止死锁的发生。

避免死锁：在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。

检测死锁：允许系统在运行过程中发生死锁，但可设置检测机构及时检测死锁的发生，并采取适当措施加以清除。

解除死锁：当检测出死锁后，破坏条件解除死锁将进程从死锁状态中解脱出来。

进程调度