操作系统-线程的调度方法---进程间通信--线程间的通信方式

文章目录

• ​​线程的调度方法有哪些:​​

• ​​先来先服务（First Come First Service，FCFS）​​
• ​​短作业优先（Shortest Job First，SJF）​​
• ​​优先级队列（PriorityQueue）​​
• ​​抢占​​
• ​​**Round-Robin(RR)轮转调度算法**​​
• ​​多级队列模型​​

• ​​进程间通信​​

• ​​管道:​​
• ​​共享内存​​
• ​​本地消息/队列​​
• ​​进程间通信，常见的方式主要有：​​

• ​​二、线程间的通信方式​​
• ​​LRU 用什么数据结构实现更合理？​​

进程就是正在执行的应用程序,是软件的执行副本,而线程时轻量级的进程

进程是分配资源的基础单位。而线程很长一段时间被称作轻量级进程（Light Weighted Process），是程序执行的基本单位。

线程的调度方法有哪些:

先来先服务（First Come First Service，FCFS）

先来先服务:（First Come First Service，FCFS）

先进去队列的作业,先处理,因此从公平性来说,公平,另外，一个作业完全完成才会进入下一个作业，作业之间不会发生切换，从吞吐量上说，是最优的——因为没有额外开销

但是这样对于等待作业的用户来说，是有问题的。比如一笔需要用时 1 天的作业 ，如果等待了 10 分钟，用户是可以接受的；一个用时 10 分钟的作业，用户等待一天就要投诉了。 因此如果用时 1 天的作业先到，用时 10 分钟的任务后到，应该优先处理用时少的，也就是短作业优先（Shortest Job First，SJF）。

短作业优先（Shortest Job First，SJF）

平均等待时间 = 总等待时间/任务数 在大多数情况下，应该优先处理用时少的，从而降低平均等待时长。

采用 FCFS 和 SJF 后，还有一些问题没有解决。

• 紧急任务
• 等得太久的任务如何插队

• 先执行的大任务导致后面来的小任务没有执行如何处理？比如先处理了一个 1 天才能完成的任务，工作半天后才发现预估时间 1 分钟的任务也到来了。

  有两种方案,: 一:优先级队列 另一种是: 抢占式

优先级队列（PriorityQueue）

优先级队列的一种实现方法用到了堆,更简单的实现方法,就是每次扫描一边整个队列找到优先级最高的任务,可以帮助你在 O(1) 的时间复杂度内查找到最大优先级的元素。

比如老板的任务，就给一个更高的优先级。 而对于普通任务，可以在等待时间（W） 和预估执行时间（P） 中，找一个数学关系来描述。比如：优先级 = W/P。W 越大，或者 P 越小，就越排在前面。 当然还可以有很多其他的数学方法，利用对数计算，或者某种特别的分段函数。

关于紧急任务如何让插队?等太久的任务如何插队,？这两个问题我们都解决了 接下来我们来先看执行的最大任务导致后面来的小任务没有执行的情况如何处理?

抢占

为了解决这个问题，我们需要用到抢占（Preemption）。

抢占就是把执行能力分时,分成时间片段,让每个任务都执行一个时间片段。如果在时间片段内，任务完成，那么就调度下一个任务。如果任务没有执行完成，则中断任务，让任务重新排队，调度下一个任务。

拥有了抢占的能力,再结合之优先级队列的能力,这就构成了一个基本的线程调度模型,线程相对于操作系统是排队到来的，操作系统为每个到来的线程分配一个优先级，然后把它们放入一个优先级队列中，优先级最高的线程下一个执行。

上面这个模型已经是一个非常优秀的方案了，但是还有一些问题可以进一步处理得更好。

如果一个线程优先级非常高，其实没必要再抢占，因为无论如何调度，下一个时间片段还是给它。那么这种情况如何实现？

如果希望实现最短作业优先的抢占，就必须知道每个线程的执行时间，而这个时间是不可预估的，那么这种情况又应该如何处理

Round-Robin(RR)轮转调度算法

• 设置一个时间片，按时间片来轮转调度（“轮叫”算法）
• 优点: 定时有响应，等待时间较短；缺点: 上下文切换次数较多；
• 时间片太大，响应时间太长；吞吐量变小，周转时间变长；当时间片过长时，退化为FCFS。

多级队列模型

紧急任务仍然走高优队列，非抢占执行。普通任务先放到优先级仅次于高优任务的队列中，并且只分配很小的时间片；如果没有执行完成，说明任务不是很短，就将任务下调一层。下面一层，最低优先级的队列中时间片很大，长任务就有更大的时间片可以用。通过这种方式，短任务会在更高优先级的队列中执行完成，长任务优先级会下调，也就类似实现了最短作业优先的问题。

实际操作中，可以有 n 层，一层层把大任务筛选出来。 最长的任务，放到最闲的时间去执行。要知道，大部分时间 CPU 不是满负荷的。

进程间通信

进程通信:是指进程之间的信息交互, 因此,对于用信号量进行的进程间的互斥与同步,对于用信号量进行的进程间的互斥和同步，由于其所交换的信息量少而被归结为低级通信。

所谓高级进程通信指：用户可以利用操作系统所提供的一组通信命令传送大量数据的一种通信方式。操作系统隐藏了进程通信的实现细节。或者说，通信过程对用户是透明的。

管道:

管道提供了一种非常重要的能力.就是组织计算,进程不用知道有管道存在,因此管道设计式非侵入的,

管道的核心是不侵入,灵活,不会增加程序设计负担,又能组织复杂的计算过程

管道：**管道是单向的、先进先出的、无结构的、固定大小的字节流，它把一个进程的标准输出和另一个进程的标准输入连接在一起。**写进程在管道的尾端写入数据，读进程在管道的道端读出数据。数据读出后将从管道中移走，其它读进程都不能再读到这些数据。管道提供了简单的流控制机制。进程试图读空管道时，在有数据写入管道前，进程将一直阻塞。同样地，管道已经满时，进程再试图写管道，在其它进程从管道中移走数据之前，写进程将一直阻塞。

注1：无名管道只能实现父子或者兄弟进程之间的通信，有名管道（FIFO）可以实现互不相关的两个进程之间的通信。

注2：用FIFO让一个服务器和多个客户端进行交流时候，每个客户在向服务器发送信息前建立自己的读管道，或者让服务器在得到数据后再建立管道。使用客户的进程号（pid）作为管道名是一种常用的方法。客户可以先把自己的进程号告诉服务器，然后再到那个以自己进程号命名的管道中读取回复。

共享内存

同一个进程的多个线程本身就是共享进程内存的,这种情况下不需要特别考虑共享内存,如果跨进程的线程(不同的进程),可以考虑使用共享内存,内存共享是现代操作系统提供的能力，

• 共享内存的方式，速度很快
• 虑并发控制，还要处理同步问题等

如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。

共享内存：共享内存允许两个或多个进程访问同一个逻辑内存。这一段内存可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取读出，从而实现了进程间的通信**。如果某个进程向共享内存写入数据，所做的改动将立即影响到可以访问同一段共享内存的任何其他进程。共享内存是最快的IPC方式，它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制（如信号量**）配合使用，来实现进程间的同步和通信。

因此，只要不是高性能场景，进程间通信通常不考虑共享内存的方式。

本地消息/队列

内存共享不太好用，因此本地消息有两种常见的方法。

• 一种是用消息队列——现代操作系统都会提供类似的能力。Unix 系可以使用 POSIX 标准的 mqueue。
• 另一种方式，就是直接用网络请求，比如 TCP/IP 协议，也包括建立在这之上的更多的通信协议
• 信号量：**信号量是一个计数器，可以用来控制多个进程对共享资源的访问。**它常作为一种锁机制，防止某进程正在访问共享资源时，其它进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。
• 消息队列：是一个在系统内核中用来保存消 息的队列，它在系统内核中是以消息链表的形式出现的。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
• 套接字：套接字也是一种进程间通信机制，与其它通信机制不同的是，它可用于不同机器间的进程通信。

进程间通信，常见的方式主要有：

• 基于内存的方式：1）匿名管道；2）信号量；3）消息队列；4）共享内存；
• 基于磁盘的方式：1）文件；2）命名管道；
• 基于网络的方式：1）socket；2）消息队列；3）RPC；4）HTTP等各种网络协议；

二、线程间的通信方式

1. 锁机制：包括互斥锁、条件变量、读写锁

   互斥锁提供了以排他方式防止数据结构被并发修改的方法。

   读写锁允许多个线程同时读共享数据，而对写操作是互斥的。

   条件变量可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。

2. 信号量机制(Semaphore)：包括无名线程信号量和命名线程信号量

3. 信号机制(Signal)：类似进程间的信号处理

   线程间的通信目的主要是用于线程同步，所以线程没有像进程通信中的用于数据交换的通信机制。

LRU 用什么数据结构实现更合理？

最原始的方式是用数组，数组的每一项中有数据最近的使用频次。数据的使用频次可以用计时器计算。每次置换的时候查询整个数组实现。