进程同步与互斥

什么是进程同步

答：进程同步指的是，由于进程并发执行具有异步性（即各自以独立地、不可预知的速度向前推进），但是某些情况下又需要进程之间进行配合和协调来完成一项工作（存在执行的顺序），因此操作系统需要提供一种机制来实现这一功能，即进程同步。

例：

双标志后检查法

• 算法思想：双标志先检查法的改进版。通过先上锁，后检查来避免先检查法的缺陷。

• 存在的主要问题：违背了有限等待和空闲让进原则。会因各进程都无法长期访问临界资源而产生饥饿现象。

Peterson算法

• 算法思想：主动让对方先使用临界区。

• Peterson算法存在的主要问题：违背了让权等待原则（当进程无法进入临界区时，应该立即释放处理机）。 Peterson算法用软件方法解决了进程互斥问题，遵循了空闲让进、忙则等待、有限等待三个原则。但是依然不够好。

进程互斥的硬件实现方法

中断屏蔽方法

利用开/关中断指令实现。关中断后，无法发生中断切换进程，则不存在两个进程同时访问某个临界区。

优点：简单、高效

缺点：

1. 不适合多处理机（关中断只对某个处理机管用）
2. 只适用于操作系统内核进程，不适用于用户进程（因为开/关中断指令只能运行在内核态，这组指令如果能让用户随意使用非常危险）
3. 自己想的一条缺点：关中断是无差别攻击，使得别的许多没有与当前进程竞争临界区的进程也无法获得处理机，降低了操作系统的灵活性。

TestAndSet（TS指令/TSL指令）

简称TS指令，也有些地方称为TestAndSetLock指令，或者TSL指令。TSL指令是用硬件实现的，执行的过程不允许被中断，只能一气呵成。以下是用C语言描述的逻辑。

优点：实现简单，把“上锁”和“检查“通过硬件的方式变成原子操作；适用于多处理机环境。

缺点：仍然不满足让权等待原则（无法进入临界区时释放处理机）。 原因：暂时无法进入临界区的进程会占用CPU并循环执行TSL指令，从而导致忙等。

Swap指令（XCHG指令）

Swap指令，又叫XCHG指令，是用硬件实现的，执行的过程中不允许被中断。以下是C语言描述的逻辑

逻辑上和TSL一样，优缺点和TSL也一样，不满足让权等待。

信号量机制

1965年，荷兰学者Dijkstra提出了一种卓有成效的实现进程互斥、同步的方法–信号量机制。

用户进程可以通过操作系统提供的一对原语（原语：无法中断、连续执行的一组操作）来对信号量进行操作，从而很方便地实现了进程互斥、进程同步。

信号量其实就是一个变量（可以是一个整数，也可以是更复杂的记录型变量），可以用一个信号量来表示系统中某种资源的数量，比如：系统中只有一台打印机，就可以设置一个初值为1的信号量。

一对原语：wait（S）和signal（S），信号量为S。 wait、signal原语简称为P、V操作（来自荷兰语proberen和verhogen）。

整型信号量

用一个整数型的变量作为信号量，用来标识系统中某种资源的数量。

与普通整型变量的区别：对信号量的操作只有三种，初始化、P操作、V操作

e.g. 某计算机系统中有一台打印机

检查和上锁一气呵成，避免了并发、异步导致的问题。

存在的问题：不满足“让权等待”，会发生“忙等”

记录型信号量

整形信号量的缺陷是存在“忙等”问题，因此人们又提出了“记录型信号量”，即用记录型数据结构标识的信号量。

//记录型信号量的定义typedef struct{    int value;	//剩余资源数    struct process *L;	//等待队列}semaphore;//某进程需要使用资源时，通过wait原语申请void wait(semaphore S){    S.value来源：余丰旭
                                                        
声明：本站部分文章及图片转载于互联网，内容版权归原作者所有，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！