操作系统学习笔记:进程同步

网友投稿 1241 2022-09-29

操作系统学习笔记:进程同步

操作系统学习笔记:进程同步

互相协作的进程之间有共享的数据,于是这里就有一个并发情况下,如何确保有序操作这些数据、维护一致性的问题,即进程同步。

从底层到高级应用,同步机制依次有临界区、信号量、管程、原子事务。

1、临界区

每个进程有一个代码段称为临界区,共享数据在此进行操作。没有两个进程同时在临界区执行。

临界区方案是一种协议,即每个进程进入临界区操作都需要请求。实现这一请求的代码称为进入区,从临界区退出的善后工作由退出区,之后是剩余区。

临界区方案必须满足三项要求:

1)互斥

两个进程不能同时在临界区操作

2)前进

临界区空闲,如果有进程需要,且不在剩余区,则可参加选择

3)有限等待

进程只要有意愿,总有一天会进入临界区,因为进程进入临界区的次数有上限。

操作系统内部的临界区问题中,非抢占式比较容易,因为进程没有竞争条件;而抢占式则困难得多,因为进程可能会运行在不同处理器上。但抢占式内核更适合实时编程。

Peterson算法是一种临界区问题算法。

对于临界区问题,除了软件上进行设计,也可以在硬件层面来解决。现代计算机系统提供了一些特殊硬件指令,可以原子地执行。

2、信号量

临界区方案比较复杂,可以使用信号量这个同步工具。

信号量是一个整数变量,除了初始化,只能通过两个标准原子操作:wait()和signal()来访问。

wait(s){ while(s <= 0) ;//当s<=0时,循环等待,直到S变为正数。如果将这个S看做可用资源,就很好理解了。S<=0,代表没有资源 s--;//可用资源减一}signal(s){ s++;//可用资源加一}

//使用信号量实现临界区问题方案do{ wait(mutex); //临界区 signal(mutex); //剩余区}while(true);

上述例子中,有循环等待,又叫忙等待。忙等待浪费了CPU时钟,这在多道程序系统中,显然是个问题,因为本可以让给其他进程执行。

不过,这种依靠忙等待实现的信号量又称为自旋锁(spinlock)。自旋锁有一定的优越性,因为无须进行上下文切换,有时上下文切换相比之下更浪费时间)。通常,等待时间如果比较短,就适合用自旋锁。自旋锁常用在多处理器系统中,因为多线程可以用于多处理器,一个线程自旋,另一个线程可以在另一个处理器上运行。

不过,为了克服忙等的缺点,可以修改wait()和signal()的定义,采用进程堵塞来替代忙等:

typedef struct { int value;//记录了这个信号量的值 struct process *list;//储存正在等待这个信号量的进程 } semaphore;wait(semaphore *S) { S->value--; if(S->value < 0) {//没有资源了 add this process to S->list;//进入等待队列 block();//堵塞 }}signal(semaphore *S) { S->value++; if(S->value <= 0) {//上面++后,S仍然还<=0,说明资源供不应求,等待者众,于是唤醒等待队列中的一个,意思是说,我做完了,你好自为之。至于是否可以获得资源,看造化。。。就此别过,青山绿水,后会有期,good bye! remove a process P from S->list; wakeup(P);//切换到就绪状态 }}

3、管程

信号量比临界区方便,但如果使用不正确,比如顺序不当,仍然会导致一些错误。

管程用高级语言封装了信号量,方便程序员调用。

管程结构确保一次只有一个进程能在管程内活动。但是,进程在管程内 应该怎么理解?难道是进程在管程里面运行?但看上去,是进程调用了管程,依管程的返回信号而行事?

管程通常是用于管理资源的,因此管程中有进程等待队列和相应的等待和唤醒操作。在管程入口有一个等待队列,称为入口等待队列。当一个已进入管程的进程等待时,就释放管程的互斥使用权;当已进入管程的一个进程唤醒另一个进程时,两者必须有一个退出或停止使用管程。在管程内部,由于执行唤醒操作,可能存在多个等待进程(等待使用管程),称为紧急等待队列,它的优先级高于入口等待队列。

因此,一个进程进入管程之前要先申请,一般由管程提供一个enter过程;离开时释放使用权,如果紧急等待队列不空,则唤醒第一个等待者,一般也由管程提供外部过程leave。

管程内部有自己的等待机制。管程可以说明一种特殊的条件型变量:var c:condition;实际上是一个指针,指向一个等待该条件的PCB(进程控制块)队列。对条件型变量可执行wait和signal操作

wait(c):若紧急等待队列不空,唤醒第一个等待者,否则释放管程使用权。执行本操作的进程进入C队列尾部;

signal(c):若C队列为空,继续原进程,否则唤醒队列第一个等待者,自己进入紧急等待队列尾部。

(额,从上述描述看,管程可以控制进程等待、唤醒等,从这点来说,进程在管程内是说得过去的)

生产者-消费者问题(有buffer)问题描述:(一个仓库可以存放K件物品。生产者每生产一件产品,将产品放入仓库,仓库满了就停止生产。消费者每次从仓库中去一件物品,然后进行消费,仓库空时就停止消费。 解答: 管程:buffer=MODULE; (假设已实现一基本管程monitor,提供enter,leave,signal,wait等操作)notfull,notempty:condition; // notfull控制缓冲区不满,notempty控制缓冲区不空; count,in,out: integer;    // count记录共有几件物品,in记录第一个空缓冲区,out记录第一个不空的缓冲区 buf:array [0..k-1] of item_type; define deposit,fetch; use monitor.enter,monitor.leave,monitor.wait,monitor.signal; procedure deposit(item); {   if(count=k) monitor.wait(notfull);   buf[in]=item;   in:=(in+1) mod k;   count++;   monitor.signal(notempty); } procedure fetch:Item_type; {   if(count=0) monitor.wait(notempty);   item=buf[out];   in:=(in+1) mod k;   count--;   monitor.signal(notfull);   return(item); } { count=0; in=0; out=0; } 进程:producer,consumer; producer(生产者进程): Item_Type item; {   while (true)   {     produce(&item);     buffer.enter();     buffer.deposit(item);     buffer.leave();   } } consumer(消费者进程): Item_Type item; {   while (true)   {     buffer.enter();     item=buffer.fetch();     buffer.leave();     consume(&item);   } }

4、原子事务

有一些操作里面的步骤必须一口气全部执行完,不可分割,结果是要么全部成功,要么就失败。

这点在数据库技术上体现得淋漓尽致:事务。近来(什么时候的事了?)有将数据库技术应用于操作系统的热潮。

1)日志

数据库的数据为什么能保存得那么好?很大程度上是归功于日志。

最常用的方法是操作数据的时候,先记录日志,再操作数据。

每条日志记录:

(1)事务名称

(2)数据项名称

(3)旧值

(4)新值

事务开始前,记录记入日志;

当事务提交时,记录记入日志;

如果事务失败,或者系统故障,系统就会检查日志(这一步也许在系统重启之时),凡有记录而无的,系统做回滚操作;两条记录都有的,系统则将数据重新写一遍。(有些重写可能是不必要的,但也不会引起错误)

但这种做法很浪费,因为绝大多数的事务都是成功的。于是引入检查点(checkpoint):

当系统将数据从内存写入硬盘或稳定存储设备时,记录一个。以后系统重启时只处理这个checkpoint之后的日志记录。

2)锁及时间戳

在并发的情况下,多个事务同时执行,由于事务是原子性的,所以事务并发,其实相当于让一个个事务串行化执行。这里就牵扯到串行调度和非串行调度。

非串行调度不一定会引起错误,因为事务之间,里面的步骤不一定会相关。将这些步骤打散、组合,可能效率会更高。

串行处理可以依靠:

(1)锁

(2)时间戳

方案是数据读写时记录时间值:

W-timestamp(Q)

R-timestamp(Q)

Q是数据项,只要操作Q,即记录时间。

在一个事务中,如果发出read(Q)

(1)事务开始时间 < W-timestamp(Q),表明值正在被改写,read被拒绝,事务回滚;

(2)事务开始时间 >= W-timestamp(Q),read,R-timestamp(Q) = MAX(R-timestamp(Q),事务时间);

如果事务发出write(Q)

(1)事务开始时间 < R-timestamp(Q),表明值正在被读取,write被拒绝,事务回滚;

(2)事务开始时间 < W-timestamp(Q),表明值正在被修改,write被拒绝,事务回滚;;

(3)否则,write

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:如何成为一名快枪手
下一篇:操作系统学习笔记:死锁
相关文章

 发表评论

暂时没有评论,来抢沙发吧~