操作系统 并发与同步

进程（线程）间相互作用 相关进程与无关进程 相关进程：在逻辑上具有某种联系的进程。 无关进程：在逻辑上没有任何联系的进程。 如果一个进程的执行不影响其他进程的执行，且与其他进程的进展情况无关，即它们是各自独立的，则说这些并发进程的相互之间是无关的。无关的并发进程一定没有共享的变量。 如果一个进程的执行依赖其他进程的进展情况，或者说，一个进程的执行可能影响其他进程的执行结果，则说这些并发进程是相关的。 与时间有关的错误 京城执行的速度是不能由进程自身控制的。对于相关进程来说，可能有若干并发进程同时使用共享资源，即一个进程一次使用未结束，另一个进程也开始使用，形成交替使用共享资源。 进程同步：值多个进程中发生的事件存在某种时序关系，必须协同动作，相互配合，以共同完成一个任务。 进程互斥：指由于共享资源所要求的排他性，进程间要相互竞争以使用这些互斥资源。 进程互斥 解决进程互斥的两种方法： 由竞争各方平等协商。 引入进程管理者，有管理者来协调竞争各方对互斥资源的使用。 临界资源：计算机系统中的需要互斥使用的硬件或软件资源，如外设、共享代码块、共享数据结构等。对各进程在对临界资源进程进行访问时，特别是进行写入或修改操作时，必须互斥的运行。 计算机系统中资源共享的程度分为三个层次：互斥、死锁和饥饿。 互斥：保证资源的互斥使用是指多个进程不能同时使用同一个资源，这是正确使用资源的最基本要求。 死锁：避免死锁是指多个进程互不相让，避免出现都得不到足够资源的情况，从而保证系统功能的正常运行。 饥饿：避免饥饿是指避免某些进程一直得不到资源或者得到资源的概率很小，从而保障系统内资源使用的公平性。 为了保证临界资源的正确使用，可把临界资源的访问过程分为四个部分： 进入区：为了进入临界区使用临界值资源，在进入区要检查可否进入临界区；如果可以进入临界区，通常设置相应的”正在访问临界区“标志，以阻止其他进程同时进入临界区。 临界区：进程中访问临界资源的一段代码。 退出区：将”正在访问临界区“标识清除。 剩余区：代码中的其他部分。 为了合理使用计算机系系统中的资源，在操作系统中采用的进程同步机制应遵循以下几条： 空闲则入：任何同步机制都必须保证任何时间嗯最多只有一个进程位于临界区。当有程序位于临界区时，任何其他进程均不能进入临界区。 忙着等待：当以有进程处于其他临界区时，后到达的进程只能在进入区等待。 有限等待：为了避免死锁等现象的出现，等待进入临界区的进程不能无期限的”死等“。 让权等待：因在进入区等待而不能进入临界区的进程，应释放处理机，转换到阻塞状态以使得其他进程有机会得到处理机的使用权。 进程互斥的软件方法 算法1：单标志算法 假设有两个进程Pi和Pj，设立一个公用整理变量turn，描述允许进入临界区的进程标识。每个进程都在进入区循环检查变量turn是否允许本进程进入。即turn为i时，进程Pi可进入，否则循环检查该变量，直到turn为本进程标识，在退出区修改允许进入进程标识，即进程Pi退出时，Pj的标识为j。 可以保证任何时刻最多只有一个进程在临界区。 缺点：强制轮流进入临界区，没有考虑进程的实际需要，容易造成资源利用不充分。 算法2：双标志、先检查算法 修改临界区标志的设置，设立一个标志数组flag[]，描述各进程是否在临界区，初始值均为FALSE. 在进入区的操作为：先检查，后修改。即在进入区像检查另一个进程是否在临界区，不在时修改本进程在临界区的标志，表示本进程在临界区，在退出区修改本进程在临界区的标志，表示本进程不在临界区。 算法2的优点是克服了算法1的缺点，两个进程不用交替进入，可连续使用。但由于使用多个标志，算法有产生新的问题，即进程Pi和Pj可能同时进入临界区，从而违反了最左只有多个进程在临界区的要求。 算法3：双标志、后检查算法 一是保证检查和修改操作间不会出现间隔。 一是修改标志含义。 算法3可防止两个进程同时进入临界区，但它的缺点是Pi和Pj可能都进入不了临界区。在修改本进程标志flag之后和检查对方flag之间有一段时间间隔，这个间隔导致两个进程都想进入临界区，从而在检查对方标志时不通过。 算法4：先修改、后检查、后修改者等待算法 结合了算法3和1，标志flag[i]表示进程i想进入临界区，标志turn表示同时修改标志时要在进入区等待的进程标识。 在进入区先修改后检查，通过修改统一标志turn来描述标志修改的先后；检查对方标志flag，如果对方不想进入临界区则自己进入；否则在检查标志turn，由于标志turn中保存的是较晚的一次赋值，则交往修改标志的进程等待，较早的修改标志的进程进入临界区。 实现了同步机制要求的四条准则中的前两条：空闲则入、忙着等待。 进程互斥的硬件方法 主要思路：使用一种指令完成读和写的两个操作，因而保证读操作与写操作不被打断，依据采用的指令的不同，硬件方法分成TS指令和Swap指令。 TS（Test-and-Set）指令 TS指令的功能是读出指定标识后把该标志设置为TRUE。 每个临界资源设置一个公共布尔变量lock，表示资源两种状态：TURE表示正被占用，FALSE表示空闲，初始值为FALSE。 有进程在临界区时，重复检查，直到其他进程退出时检查通过，所有要访问临界资源的进程的进入区和退出区代码是相同的。 Swap指令 利用Swap指令实现的进程互斥算法是，每个临界资源设置一个公共布尔变量lock，初值为FALSE，每个进程设置一个私有布尔变量key，用于与lock间的信息交换。在进入区利用Swap指令交换lock和key的内容，然后检查key的状态，有进程在临界区时，重复交换和检查过程到其他进程推出啊是检查通过。 优点： 适用范围广：适用于任意数目的进程，在单处理器和多处理器黄健中完全相同。 简单：硬件方法的标志设置简单，含义明确，容易验证其正确性。 支持多个临界区：在一个进程内有多个临界区是，只需为每个临界区设立一个变量。 缺点： 进程在等待进入临界区时，要耗费处理机时间，不能实现”让权等待“。 由于进入临界区的进程是从等待进程中随机选择的，有的进程可能一直选不上，从而导致”饥饿“。 信号量 信号量机制所使用的P、V原语就来自荷兰语test和increment。每个信号量s除一个整数值s.count（计数）外，还有一个进程等待队列s.queue，其中存放的是阻塞在该信号量的各个进程的标识。 信号量只能通过初始化和标准的原语来访问。 P、V原语的执行，不受进程调度和执行的打断，从而很好地解决了原语操作的整体性。信号量的初始化可指定一个非负整数数值，表示空闲资源总数；若为负值，其绝对值表示当前等待临界区的进程数。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 P原语所执行的操作可用下面函数wait（s）来描述。 wait(s){ --s.count; //表示申请一个资源 if(s.count<0){ //表示没有空闲资源 调用进程进入等待队列s.queue; 阻塞调用进程; } } V原语所执行的操作可用下面函数signal(s)描述。 signal(s){ ++s.count; //表示释放一个资源 if(s.count <= 0){ //表示有进程处于阻塞状态 从等待队列s.queue中取出头一个进程P； 进程P进入就绪队列; } } 在使用信号量进行共享资源访问控制时，必须成对使用P和V原语。遗漏P原语则不能保证互斥访问，遗漏V原语则不能在使用临界资源之后将其释放给其他等待的进程。P、V原语的使用不能次序错误、重复或遗漏。 利用操作系统提供的信号量机制可实现进程间的同步，即所谓的前驱关系。 前趋关系是指并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成执行。可为每个前趋关系设置一个互斥信号量S12，其初值为0.这样，只有在P1执行到V（S12）后，P2才会结束P（S12）的执行。 经典的进程同步问题 Dijkstra将同步问题抽象成一种“生产者-消费者关系”。 简单生产者-消费者问题 设有一个生产者进程P，一个消费者进程Q，他们通过一个缓冲区联系起来。缓冲区只能容纳一个产品，生产者不断的生产产品；而消费者则不断从缓冲区中取出产品，并消费掉。 生产者-消费者同步问题的解决方案如下： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 生产者进程P: while(true){ P(empty); 生产一个产品; 送产品到缓冲区; V(full); }; 消费者进程Q： while(true){ P(full); 从缓冲区去产品; V(empty); 消费产品; }; 产品生产出来之后立即往缓冲区中存放产品，因为刚开始时缓冲区是空的，一定可以存放一个产品。 多个生产者-消费者问题 设有多个生产者进程P1，P2，……, Pn，若干个消费者进程Q1，Q2，Q3，……，Qm，他们通过一个唤醒缓冲池联系起来，该环形缓冲池由K个大小相等的缓冲区组成，每个缓冲区能容纳一个产品，生产者每次往空缓冲区送一个产品；消费者每次从缓冲区取出一个产品。生产者进程不断地生产产品并把他们放给缓冲池内，消费者进程不断的从缓冲池内取出产品并消费之。 当整个缓冲池全满时，出现供大于求的现象。当整个缓冲池全空时，出现供不应求的现象。 环形缓冲池是临界资源，因为生产者和消费者都需要使用它。 同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量empty，初值为k，用于指示缓冲池中空缓冲区数目。Q进程不能从“空”的缓冲区中取产品，设置信号量full，初值为0，用于指示缓冲池中满缓冲区数目。 互斥问题：设置信号量mutex，初值为1，用于实现临界区（环形缓冲区）的互斥。 算法： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 P1，P2，......,Pn; i:=0; while(true){ 生产产品; P(empty); P(mutex); 往Buffer[i]中放产品; i:=(i+1) mod k; V(mutex); V(full); }; Q1,Q2,......,Qm; j:=0; while(true){ P(full); P(mutex); 从Buffer[i]中存放产品; j:=(j+1) mod k; V(mutex); V(empty); 消费产品; } 读者-写者问题 假定有某个共享文件F，系统允许若干个进程对文件F进行读或写，这里要把读文件的进程称为读者，要把写文件的进程称为写者. 多个进程可以同时读文件F； 任一个进程在对文件F进行写时，按规定每次只允许一个进程执行写操作； 当有进程正在读文件时不允许任何进程去写文件。 当有多个读者与写者都需要读写文件时，按规定每次只允许一个进程执行写操作，且在有进程执行写的时候不允许进程读文件。 同步与互斥的综合应用 例1 路口单双号交通管制 Check：指示可否在车辆号码识别区中进入一辆汽车，由于只能进入一辆，其初值为1. Ddd：指示汽车号码是否为奇数，其初值为0，表是不是奇数。 Lven：指示汽车号码是否为偶数，其初值为0，表示不是偶数。 例2 物流系统中的物品分拣问题 问题 从沿长江一线进入枢纽的集装箱，要从这里直接吊装到上海至旧金山的定期集装箱班轮上。 而从沪杭高速公路上进入枢纽的集装箱，要从这里还转到专门在京沪高速公路上行驶的集装箱运输箱上。 该中转枢纽的场地每次只能接受一个方向来的同一批次的集装箱。 分析 长江一线进入的集装箱卸货是一个生产者，从沪杭高速公路上进入的集装箱卸货是第二个生产者。 这两个生产者都要使用中转枢纽的场地，由于该场地每次只能接受一个方向来的同一批次的集装箱，所以长江一线生产者和沪杭高速公路生产者必须互斥。 Site：指示能否在中转的枢纽的场地上卸下集装箱。 Arrive_Y:指示场地上的集装箱是否来自长江。 Arrive_H:指示场地上的集装箱是否来自沪杭。 说明 由于Site初值为