操作系统（一）

1. 进程和线程之间的区别

• 进程：程序运行资源分配的最小单位，进程内部有多个线程，会共享这个进程的资源
• 线程：CPU调度的最小单位，必须依赖于进程存在

2. 操作系统的调度算法

1. 先来向服务调度算法
   先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。（都是遵纪守法的好公民，懂得先来后到）

2. 短作业(进程)优先调度算法
   短作业(进程)优先调度算法SJ(P)F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。（我短我骄傲，就算你比我先来也得是我先执行）

3. 优先权调度算法的类型

1. 非抢占式优先权算法
   在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可用于某些对实时性要求不严的实时系统中。（我虽然坏，要插队，但是你已经在执行了就让你执行完）

2. 抢占式优先权调度算法
   在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。常用于要求比较严格的实时系统中，以及对性能要求较高的批处理和分时系统中。（我更坏，我不仅要插队，就算你已经在执行了我还是要把你踢走，自己先执行）

例题：有以下的进程需要调度执行(见表2-5)：
表2-5　进程调度
进程名 到达时间 运行时间
P1 0.0 9
P2 0.4 4
P3 1.0 1
P4 5.5 4
P5 7 2
1)如果用非抢占式短进程优先调度算法，请问这5个进程的平均周转时间是多少
2)如果采用抢占式短进程优先调度算法，请问这5个进程的平均周转时间是多少
A．8.62；6.34
B．8.62；6.8
C．10.62；6.34
D．10.62；6.8

非抢占式：
进程名 到达时间 运行时间 开始时间 结束时间 周转时间
P1 0.0 9 0.0 9.0 9
P2 0.4 4 12.0 16.0 15.6
P3 1.0 1 9.0 10.0 9
P4 5.5 4 16.0 20.0 14.5
P5 7 2 10.0 12.0 5
平均周转时间为(9+15.6+9+14.5+5)/5=10.62

抢占式：
进程名 到达时间 运行时间 开始时间 结束时间 周转时间
Pl 0.0 9 0.0 20.0 20
P2 0.4 4 0.4 5.4 5
P3 1.0 1 1.0 2.0 1
P4 5.5 4 5.5 11.5 6
P5 7 2 7.0 9.0 2
平均周转时间为(20+5+1+6+2)/5=6.8
因此答案选D

3. 高响应比优先调度算法
   高响应比算法，是一种动态调整优先级的算法，在PSA算法中（优先级调度算法，先来先服务和最短作业优先都可以看做特殊的PSA算法），给每个作业安排一个优先级后，始终这个优先级不再改变，这有些不合理。因为可能造成一个低优先级作业始终得不到执行。
   为了解决这个问题，HRRN算法每次都计算作业的优先级，随着作业等待时间的变长，优先级不断的提高，所以能够得到更快的执行。

这个优先级可以描述为: 优先级 = (作业已等待时间 + 作业的服务时间) / 作业的服务时间
从上式可以看到，作业的服务时间是固定的， 优先级随着已等待时间的提高而变大。（我这人很公平的，每执行一轮我都看看下一轮谁最应该被执行）

4. 基于时间片的轮转调度算法
   1）时间片轮转法
   在早期的时间片轮转法中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU 分配给队首进程，并令其执行一个时间片。时间片的大小从几ms 到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。（雨露均沾，每个人都执行那么点时间，谁都不得罪）

5. 多级反馈队列调度算法
   前面介绍的各种用作进程调度的算法都有一定的局限性。如短进程优先的调度算法，仅照顾了短进程而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。而多级反馈队列调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下所述。

(1) 应设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第i+1个队列的时间片要比第i个队列的时间片长一倍。

(2) 当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业(进程)从第一队列依次降到第n队列后，在第n 队列便采取按时间片轮转的方式运行。

(3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1～(i-1)队列均空时，才会调度第i队列中的进程运行。如果处理机正在第i队列中为某进程服务时，又有新进程进入优先权较高的队列(第1～(i-1)中的任何一个队列)，则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第i队列的末尾，把处理机分配给新到的高优先权进程。

多级反馈队列调度算法体现了计算思维的调度特点，应用了先来先服务原则、应用时间片等做法使得每个申请者都能及时使用资源，是一种很好的协调整体的解决方案。（我喜欢你，因此把你的事放在第一队列，但我也有其他的事，不能一直帮你做事。帮你做了一段时间就得把你放到第二队列队尾去。等我把所有第一队列的事都做完了，到了第二队列轮到你了再帮你做，这次要比第一队列做的更长一点。如果这段时间内还是做不完，那就得把你放到第三队列的队尾了，依次类推）
注：在队列中是按照先来先服务的原则

转载：https://blog.csdn.net/u010757019/article/details/83309465

3. 进程间通信的方式和区别

进程间通信主要包括管道, 系统IPC(包括消息队列,信号量,共享存储), SOCKET.
管道包括三种:
1)普通管道PIPE, 通常有种限制,一是半双工,只能单向传输;二是只能在父子进程间使用.
2)流管道s_pipe: 去除了第一种限制,可以双向传输.
3)命名管道:name_pipe, 去除了第二种限制,可以在许多并不相关的进程之间进行通讯.

系统IPC的三种方式类同,都是使用了内核里的标识符来识别.

• 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。
• 有名管道 (named pipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。
• 信号量( semophore ) ： 信号量是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 信号 ( sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。
• 共享内存( shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。
• 套接字( socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

4. 虚拟内存机制的作用

1. 作为缓存的工具（虚拟页）
2. 作为内存管理的工具
3. 作为内存保护的工具

5. 缓存替换算法（页面置换算法）

当没有足够的物理内存的时候，系统通过把进程的一部分转移到硬盘上以设法容纳进程，当再次需要进程中被转移到硬盘中的那一部分时，再返回到物理内存中，这个过程就被称为页面调度。它使得系统在有限的物理内存环境下也能具备多任务处理的能力。
1 .理想页面置换算法(OPT):
这是一种理想的算法，在实际中不可能实现。
该算法的思想是：发生缺页时，所调出的页应该是以后不再访问的页(永远不会再使用)或最长时间内不再被访问的内存页面(距当前最长时间后再访问的页)予以淘汰。

2.先进先出页面置换算法(FIFO)：
即字面意思很好理解，当发生缺页时，把先进来的先淘汰。
思路：选择最先进入内存的页面予以淘汰。

3. 最近最久未使用算法（LRU）：
   思想：当发生缺页时，在给定的一定数量的物理页中，选择在最近一段时间内最久没有使用过的页，把它淘汰。

4. 少使用算法（LFU）：
   思想：根据页面被访问的次数来判断，选择到当前时间为止被访问次数最少的页转换

6. 线程的实现方式

线程的实现可分为两大类，用户级线程（user-levelthread，ULT）和内核级线程（kernel-levelthread，KLT）。后者又称为内核支持的线程或轻量级进程。

https://blog.csdn.net/weixin_42229896/article/details/80667187?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.channel_param

7. 虚拟文件系统