进程同步

同步互斥的几个概念

（1）进程同步。进程间的同步是指某些进程之间在逻辑上的相互制约关系。

（2）进程互斥。进程互斥是指某一资源同一时间只允许一个进程对其进行访问，这种访问具有唯一性和排他性。进程互斥通常是进程之间争夺互斥资源而引起的，在这种情况下，任何时刻都不允许两个及两个以上的并发进程同时执行那段访问该互斥资源的程序代码。

互斥的实现还会产生两个额外的控制问题：饥饿（Starvation）和死锁（Deadlock）。

（1）饥饿。一个进程所申请的资源总是被优先于自己的其他进程所占有，而长时间处于不能被调度执行的状态（长时间处于就绪或阻塞状态），将这种现象称为「饥饿」。

（2）死锁。一个进程集合中已经占有部分资源的两个或两个以上进程，还需要获得已被其他进程占有的资源才能够继续执行，有可能出现某些进程相互之间都在等待对方占有的资源而无法运行的局面，即在进程集合中的这些进程处于永远的阻塞状态，这就是「死锁」。

进程同步与进程互斥的相似之处是进程互斥实际上是进程同步的一种特殊情况，即逐次使用互斥资源，这也是对进程使用资源次序的一种协调（同步）。因此可以将进程互斥和进程同步统称为进程同步。

进程同步与进程互斥的区别是进程互斥是由互斥资源引起的，这种互斥无法限制进程对资源的访问顺序，即访问是无序的。进程同步则是指相互协作的并发进程之间存在着必然的联系，若当前运行进程执行过程中需要进行同步时，在没有得到协同工作的其他合作进程发来的同步消息之前，当前运行进程则不能继续向前推进（运行）。在进程同步中，虽然互斥资源仍然制约着进程的执行，但协调各进程向前推进的只能是进程同步，即通过进程同步来协调和制约各合作进程的执行，去完成一个共同的任务，即进程同步是在互斥的基础上（大多数情况），通过其他机制实现进程对资源的有序访问。

临界

一定时间内只允许一个进程访问的资源成为临界资源。

硬件互斥

采用硬件方法实现进程互斥就是通过计算机提供的一些机器指令来实现进程的互斥实现进程互斥本质上是实现临界区互斥,而实现临界区互斥的关键又是正确的设置进入区和退出区机器指令是指在一个指令周期内执行完成的指令,而专用机器指令的执行则不会被中断使用专用机器指令可以在没有其他指令干扰的情况下,获得临界区是否使用的状态信息专用机器指令通过设置控制临界区访问的布尔型变量,来控制多个进程对临界区的互斥访问常用的专用机器指令有 3 个:开关中断指令测试与设置指令以及交换指令。

开关中断指令

最简单粗暴的方法，具体方法是进程在进入临界区之前,先执行关中断指令来屏蔽掉所有中断,进程完成临界区的任务后,再执行开中断指令将中断打开。
测试与设置指令 TS

采用 TS 方法则要为每个临界资源设置一个整型变量 s,可以将它看成一把锁若 s 的值为 0(开锁状态),则表示没有进程访问该锁对应的临界资源;若 s 的值为 1(关锁状态),则表示该锁对应的临界资源已被某个进程占用。
交换指令（Swap）

交换指令(Swap)的功能是交换两个字的内容,可以用以下函数描述。

若要使用交换指令来实现进程互斥,则需要为每个临界资源设置一个整型的全局变量 s 若 s 的值为 0 则表示没有进程在临界区;若 s 的值为 1 则表示有进程在临界区(即正在访问临界资源) 此外,还要为每个进程设置一个整型局部变量 key,只有当 s 的值为 0 并且 key 的值为 1 时,本进程才能进入临界区进入临界区后,s 的值为 1 且 key 的值为 0,退出临界区时,应将 s 的值置为 0。

虽然使用 TS 和 Swap 指令可以方便地实现进程互斥,但它们都存在以下缺点:当一个进程还在访问临界区时,其他欲进入临界区的进程,只能不断地循环测试 s 的值,显然,不断循环测试 s 造成了 CPU 浪费,这就是忙等也就是说,上述两种方法都没有遵循让权等待的原则。

存储管理

逻辑地址和物理地址

逻辑地址。用户源程序经编译、链接后得到可装入程序。由于无法预先知道程序装入内存的具体位置，因此不可能在程序中直接使用内存地址，只能暂定程序的起始地址为 0。这样，程序中指令和数据的地址都是相对 0 这个起始地址进行计算的，按照这种方法确定的地址称为逻辑地址或相对地址。一般情况下，目标模块（程序）和装入模块（程序）中的地址都是逻辑地址。
逻辑地址空间。一个目标模块（程序）或装入模块（程序）的所有逻辑地址的集合，称为逻辑地址空间或相对地址空间。
物理地址。内存中实际存储单元的地址称为物理地址，物理地址也称为绝对地址或内存地址。为了使程序装入内存后能够正常运行，就必须将程序代码中的逻辑地址转换为物理地址，这个转换操作称为地址转换。
物理地址空间。内存中全部存储单元的物理地址集合称为物理地址空间、绝对地址空间或内存地址空间。由于每个内存单元都有唯一的内存地址编号，因此物理地址空间是一个一维的线性空间。要使装入内存的程序后能够正常运行、互不干扰，就必须将不同程序装入到内存空间的不同区域。
虚拟地址空间。CPU 支持的地址范围一般远大于机器实际内存的大小，对于多出来的那部分地址（没有对应的实际内存）程序仍然可能使用，我们将程序能够使用的整个地址范围称为虚拟地址空间。如 Windows XP 采用 32 位地址结构，每个用户进程的虚拟地址空间为 4GB（232），但可能实际内存只有 2GB。虚拟地址空间中的某个地址称为虚拟地址，而用户进程的虚拟地址就是前面所说的逻辑地址。

分页存储管理的基本原理

1．实现原理

在分页存储管理中，一个程序的逻辑地址空间被划分成若干个大小相等的区域，每个区域称为页或页面，并且程序地址空间中所有的页从 0 开始顺序编号。相应地，内存物理地址空间也按同样方式划分成与页大小相同的区域，每个区域称为物理块或页框，与页一样内存空间中的所有物理块也从 0 开始顺序编号。在为程序分配内存时，允许以页为单位将程序的各个页，分别装入内存中相邻或不相邻的物理块中。由于程序的最后一页往往不能装满分配给它的物理块，于是会有一定程度的内存空间浪费，这部分被浪费的内存空间称为页内碎片。

分页系统中页的选择对系统性能有重要影响。若页划分得过小，虽然可以有效减少页内碎片，并提高内存利用率，但会导致每个进程需要更多的页，这样会使分页系统中用于页管理的页表增大，而占用更多的内存空间。若页划分得过大，虽然可以减少页表大小，并提高页的置换速度，但会导致页内碎片增大，而且当一个页大到能装下一个程序时就退化为分区存储管理了。因此页的大小应适中，分页系统中页的大小取决于机器的地址结构，一般设置为 2 的整数幂，通常为 512B～8KB。

2．逻辑地址结构

在分页存储管理中，程序中的逻辑地址被转换为页号和页内地址。这个转换工作在程序执行时由系统硬件自动完成，整个过程对用户透明。因此用户编程时不需要知道逻辑地址与页号和页内地址的对应关系，只需要使用一维的逻辑地址。

程序的一维逻辑地址空间经过系统硬件自动分页后，形成「页号 + 页内地址」的地址结构。在图所示的地址结构中，逻辑地址通过页号和页内地址来共同表示。其中，0～11 位是页内地址，即每个页的大小是 4KB；12～31 位是页号，即地址空间最多允许有 1M 个页。一维逻辑地址与页号和页内地址的关系是（注：页长即一页的大小）

一维逻辑地址 = 页号 × 页长 + 页内地址

3．数据结构

为了实现分页存储管理，系统主要设置了以下两种表格。

（1）页表

在分页系统中，允许程序所有的页以离散方式分别存储在内存不同的物理块里，为了使程序能够正确运行，必须在内存空间中找到存放每个页的物理块。因此操作系统为每个程序（进程）建立了一张页映射表，简称页表（Page Table），用来存储页号及其映射（装入）的内存物理块号。最简单的页表由页号及其映射的物理块号组成。由于页表的长度由程序所拥有页的个数决定，故每个程序的页表长度通常不同。

（2）内存分配表

为了正确地将一个页装入到内存的某一物理块中，就必须知道内存中所有物理块的使用情况，因此系统建立一张内存分配表来记录内存中物理块的分配情况。由于每个物理块的大小相同且不会改变大小，因此最简单的办法是用一张位示图（Bitmap）来构成内存分配表。位示图是指在内存中开辟若干个字，它的每一位与内存中的一个物理块相对应。每一位的值可以是 0 或 1，当取值为 0 时，表示对应的物理块空闲；当取值为 1 时，表示对应的物理块已分配。此外，在位示图中增加一个字节，来记录内存当前空闲物理块的总数。

4. 地址保护

基本地址转换

在分页存储管理中,系统为每个程序建立了一张页表并存放于内存中当程序被装入内存但尚未运行时,页表始址(页表在内存中的起始地址)和页表长度(程序逻辑地址空间从页号 0 开始划分出的最大页号)等信息被保存到为该程序(进程)创建的 PCB 中,或保存到请求表中一旦进程调度程序调度该进程运行时,其 PCB 中保存的页表始址和页表长度信息(或请求表中这两个的信息)便被装入到页表控制寄存器中,基本地址转换过程如图所示

从基本地址转换过程可知 物理地址 = 物理块号页长 + 页内地址,由于页表驻留在内存,因此当 CPU 依据指令中的逻辑地址进行操作时,至少要两次访问内存

为了提高地址转换的速度,一种行之有效的方法是在地址转换机构中,增加一个具备并行查找能力的高速缓冲寄存器,又称联想存储器(Associative Memory)来构成一张快表,快表中保存着当前运行进程最常用的页号及其映射的物理块号