【第十一天】进程调度算法，进程间通信方式，进程同步和互斥

进程调度算法有哪些

进程调度算法是操作系统中用来管理和调度进程（任务，作业）执行的方法。这些方法决定了在多任务环境下，如何为各个进程分配CPU时间，以实现公平性、高吞吐量、低延迟等目标。

先到先服务调度算法（FCFS，first come,first served）:

从就绪队列中选择一个最先进入该队列的进程，并为它分配资源，让它立即执行并一直执行到完成任务或被阻塞放弃占用CPU时再重新调度。

短作业优先的调度算法（SJF，short job first）：

从就绪队列中选一个估计执行时间最短的进程，给它分配资源，让它理科执行并一直执行到完成任务或被阻塞放弃占用CPU时再重新调度。

高响应比优先的调度算法：

综合考虑等待时间和服务时间的比率，选择具有高响应比的进程来执行。

优先级调度算法（Priority):

为每个进程分配优先级，首先执行具有最高优先级的进程，依次类推。具有相同优先级的进程以FCFS方式执行。可以根据内存要求，时间要求或任何其他资源要求来确定优先级。

时间片轮转调度算法（RR，round-robin）：

时间片轮转调度是一种最古老最简单最公平且使用最广的算法。每个进程被分配一个时间段，称为它的时间片，即该进程允许运行的时间。

多级反馈队列调度算法（MFQ，Multi-level Feedback Queue）：

将进程划分为多个队列，每个队列具有不同的优先级，进程会在队列之间移动。具有更高优先级的队列的进程会更早执行，而长时间等待的进程会被提升到更高优先级队列

最短时间剩余优先：

每次选择剩余执行时间最短的进程来执行。

最大吞吐量调度：

旨在最大化单位时间内完成的进程数量。

进程间有哪些通信方式

1.管道：

这是一种半双工的通信方式，数据只能单向流动而且只能在具有父子进程关系的进程间使用。

2.命名管道：

也是半双工的通信方式，但是它允许无亲缘关系进程间的访问。

3.信号量：

是一个计数器，可以用来控制多个进程对共享资源的访问，常作为一种锁机制，防止进程正在访问共享资源时，其他进程也访问该资源。主要作为进程间以及同一进程内不同线程之间的同步手段。

4. 消息队列：

消息队列是消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少，管道只能承载无格式字节流以及缓冲区大小受限等缺点。

5.信号：

用于通知接收进程某个时间已经发生，从而迫使进程执行信号处理程序。

6. 共享内存：

就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的进程通信方式，它是针对其他进程通信方式运行效率低而专门设计的。它往往与其他通信机制配合使用来实现进程间的同步和通信。可以配合信号量。

7. Socket套接字：

是支持TCP/IP网络通信的基本操作单元，主要用于在客户端和服务器之间通过网络进行通信。

进程的同步和互斥

进程同步是指协调和管理多个并发执行的进程的执行顺序，确保它们按照一定顺序或一定间隔执行。
互斥是指在某一时刻只允许一个进程访问某个共享资源。当一个进程正在使用共享资源时，其他进程不能同时访问该资源。

要解决进程同步和互斥的问题，可以采用信号量和PV操作。
信号量是一种特殊的变量，它表示系统中某种资源的数量或者状态。PV操作是一种对信号量进行增加或者减少的操作，它们可以用来控制进程之间的同步或者互斥。

举个例子，有一个信号量s表示一个卫生间是否可以使用，初始值为1。如果s值为1，表示卫生间空闲；如果s值为0，表示卫生间被占用；如果s值为-1，表示还有1个人在等着用卫生间。那么我们就可以用pv操作来实现对卫生间的互斥访问：

• 如果你想使用卫生间，那么你就得执行P(s)操作，将s的值-1。如果结果为0或者为正，那你就可以用卫生间；如果为负，那你就等着。注意这是想用，不是在用
• 如果你使用完了卫生间，就执行V(s)操作，将s的值+1。如果结果为正数或者0，表示没有人用卫生间；如果结果为负数，表示还有人等着用卫生间，你就得喊下其中一个人“我好了，你可以来上厕所了”。