OS

进程的通信方式

  • 共享存储器系统：基于共享数据结构；基于共享内存读写
  • 管道通信系统：所谓管道是指用于连接一个读进程和一个写进程以实现它们之间通信的一个共享文件(pipe文件)。管道机制需要保证互斥、同步、确认对方是否存在的协调能力
  • 消息传递系统：直接通信方式，利用 os 提供的原语直接将消息发送给目标进程；间接通信方式，发送和接收进程都通过共享实体(邮箱)的方式进行消息的发送和接收
  • 客户端服务器系统：Socket套接字，类似于管道的基于文件型的系统或基于网络型；RPC

共享内存

共享内存（Shared Memory），指两个或多个进程共享一个给定的存储区。特点如下：

  • 共享内存是最快的一种 IPC，因为进程是直接对内存进行存取
  • 因为多个进程可以同时操作，所以需要进行同步
  • 信号量 + 共享内存通常结合在一起使用，信号量用来同步对共享内存的访问

管道

管道，通常指无名管道，是 UNIX 系统中 IPC 最古老的形式。特点如下：

  • 它是半双工的（即数据只能在一个方向上流动），具有固定的读端和写端
  • 它只能用于具有亲缘关系的进程之间的通信（也是父子进程或者兄弟进程之间）
  • 它可以看成是一种特殊的文件，对于它的读写也可以使用普通的 read、write 等函数。但是它不是普通的文件，并不属于其他任何文件系统，并且只存在于内存中

当一个管道建立时，它会创建两个文件描述符：fd[0]为读而打开，fd[1]为写而打开。单个进程中的管道几乎没有任何用处。所以，通常调用 pipe 的进程接着调用 fork，这样就创建了父进程与子进程之间的 IPC 通道。

信号量

信号量（semaphore）与已经介绍过的 IPC 结构不同，它是一个计数器。信号量用于实现进程间的互斥与同步，而不是用于存储进程间通信数据。特点如下：

  • 信号量用于进程间同步，若要在进程间传递数据需要结合共享内存
  • 信号量基于操作系统的 PV 操作，程序对信号量的操作都是原子操作
  • 每次对信号量的 PV 操作不仅限于对信号量值加 1 或减 1，而且可以加减任意正整数
  • 支持信号量组

虚拟内存的实现方式

虚拟内存的实现需要建立在离散分配的内存管理方式的基础上，虚拟内存的实现有以下三种方式：

  • 请求分页存储管理
  • 请求分段存储管理
  • 请求段页式存储管理

不管哪种方式，都需要有一定的硬件支持。一般需要的支持有以下几个方面：

  • 一定容量的内存和外存
  • 页表机制（或段表机制），作为主要的数据结构
  • 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断
  • 地址变换机构，逻辑地址到物理地址的变换

进程的调度方式

先来先服务(FCFS)

先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机，即具有不可剥夺性。FCFS算法简单，但是效率较低；对长作业比较有利，对短作业不利；有利于CPU密集型作业，不利于IO密集型作业。

短作业优先(SJF)

短作业(进程)优先调度算法，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先(SJF)的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程优先(SPF)调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度，即具有不可剥夺性。短作业算法对于长作业不利，会产生饥饿现象；未考虑作业的紧急程度；难以实现真正意义上的短作业优先。

优先权调度

为了照顾紧迫型作业，使之在进入系统后便获得优先处理，引入了最高优先权优先(FPF)调度算法。此算法常被用于批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度算法，还可用于实时系统中。当把该算法用于作业调度时，系统将从后备队列中选择若干个优先权最高的作业装入内存。当用于进程调度时，该算法是把处理机分配给就绪队列中优先权最高的进程，这时，又可进一步把该算法分成如下两种。

非抢占式优先权算法

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

抢占式优先权算法

在这种方式下，系统同样是把处理机分配给优先权最高的进程，使之执行。但在其执行期间，只要又出现了另一个其优先权更高的进程，进程调度程序就立即停止当前进程(原优先权最高的进程)的执行，重新将处理机分配给新到的优先权最高的进程。因此，在采用这种调度算法时，是每当系统中出现一个新的就绪进程i时，就将其优先权Pi与正在执行的进程j的优先权Pj进行比较。如果Pi≤Pj，原进程Pj便继续执行；但如果是Pi>Pj，则立即停止Pj的执行，做进程切换，使i进程投入执行。显然，这种抢占式的优先权调度算法能更好地满足紧迫。进程优先级可分为静态优先级和动态优先级。静态优先级在进程创建时就已经确定，且整个运行期间不发生改变。动态优先级在运行期间可变，主要依据为进程占用CPU时间的长短、就绪进程等待CPU时间的长短。

时间片轮转法

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

多级反馈队列调度

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

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

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

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