操作系统【四】

PV操作解题思路

1.同步和互斥的关系

进程(线程)之间的两种关系:同步与互斥。

所谓互斥,是指三部在不同进程之间的若干程序片断,当某个进程运行其中一个程序片段时,其它进程就不能运行它们之中的任一程序片段,只能等到该进程运行完这个程序片段后才可以运行。

所谓同步,是指散步在不同进程之间的若干程序片断,它们的运行必须严格按照规定的 某种先后次序来运行,这种先后次序依赖于要完成的特定的任务。

显然,同步是一种更为复杂的互斥,而互斥是一种特殊的同步。也就是说互斥是两个线程之间不可以同时运行,他们会相互排斥,必须等待一个线程运行完毕,另一个才能运行,而同步也是不能同时运行,但他是必须要安照某种次序来运行相应的线程(也是一种互斥)!

总结:

互斥:是指某一资源同时只允许一个访问者对其进行访问,具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序,即访问是无序的。

同步:是指在互斥的基础上(大多数情况),通过其它机制实现访问者对资源的有序访问。在大多数情况下,同步已经实现了互斥,特别是所有写入资源的情况必定是互斥的。少数情况是指可以允许多个访问者同时访问资源。

个人理解:

==互斥问题:多个线程对某资源的一定程度上的独占性,重点体现空间性==

  • 进程互斥中用于实现互斥的P操作和V操作必须成对地出现

==同步问题:多个线程能够互相配合并发执行所需要的某种顺序上的限制条件,重点体现时间性==

  • 进程同步的P操作和V操作,同样需要成对地出现,但处于不同的程序中

==应先执行对同步信号量的P操作,再执行对互斥信号量的P操作,否则可能引起进程死锁==

  • 因为:若先对空间独占,再进行时间上的资源请求,若资源请求不到,而另一个释放资源的进程也被阻挡在空间独占,就会死锁
2.解题思路
  • 信号量机制

​ P:申请资源 V:访问资源,产生资源 S:大于0时代表当前可用资源,小于0时代表因请求该资源而被阻塞的资源)

​ 有i个生产者,j个消费者,信号量empty的初值为k,信号量full初值为0,信号量mutex为1,共用k个缓冲区。求各信号量的取值范围?

​ 此题帮助很好的理解了p v s的含义

  • 解题思路

拿到一个应用题,一般进行如下分析:

1.有无互斥

2.有无同步

3.有无前驱关系

4.有无类似读读共享、读写互斥情况

5.若有互斥,套用互斥模式;若有同步,套用同步模式;若有前驱关系,套用前驱模式;若有读读共享情况,套用读者-写者模式

解题注意:

1.定义信号量;赋初值;解释信号量含义(互斥信号量一般为1。同步信号量的初始值要看对应资源的初始值是多少)

2.信号量除初始化外只能由wait()、 signal()改变其值.即除初始化外,在算法中不能直接对信号量进行任何操作

3.用类C语言描述算法

(4)管程机制

【操作系统】 管程机制

信号量机制中,每个要访问临界资源的进程都必须自备同步的PV操作,大量分散的同步操作会给系统管理带来麻烦,且容易因为同步操作不当而导致系统死锁。于是便产生了一种新的进程同步工具——管程(Monitors)

管程(Monitors):是一个资源管理模块,其中包含了共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程(方法)所组成的资源管理程序。

管程中包含条件变量,用于管理进程的阻塞和唤醒。其形式为 condition x;对它的操作仅有wait和signal。

x.wait:正在调用管程的进程因 x 条件需要被阻塞或挂起,则调用 x.wait 将自己插入到 x 条件的等待队列上,并释放管程,直到 x 条件变化。此时其它进程可以使用该管程。

x.signal:正在调用管程的进程发现 x 条件发生了变化,则调用 x.signal,重新启动一个因 x 条件而阻塞或挂起的进程。(与信号量的signal不同,没有s:=s+1的操作)

个人理解:

  1. 管程相当于把对临界资源的操作封装了起来,当进程要对资源进行操作时,只要调用管程中的方法就可以了,而不用进程自己担心同步和互斥的问题,管程的内部有自己的一套机制进行同步与互斥。
  2. 管程中每次只允许一个进程进入管程。
  3. 当调用管程的进程因为某原因阻塞或者挂起时,把这个原因定义为一个条件变量x。
  4. x.wait操作就是把自己放到一个队列上,这个队列上的进程都是因为x原因而阻塞的。
  5. x.signal操作就是让在x阻塞队列上的一个进程重新启动。

相对形象的比喻:假如一个管程叫ATM(取款机),其包含两个方法:存款和取款,不同的人代表不同的进程,但是ATM只允许一个人在一个时间段中进行操作,当一个人在使用时,其他的人只能wait。此外,一个人如果使用的时间太长也不行,所以需要一个条件变量来约束他。

比如一个人在操作ATM时突然接电话了,没法继续操作,把这个原因记为x,执行x.wait,让他离开ATM机,去接电话的队列中等待。等到打完电话,即调用了x.signal后,他就可以继续操作ATM了(一般令正在操作ATM的人操作完后,他才能重新进去)。

生产者-消费者问题

建立producer-consumer管程,其中包括两个方法

1.put(x):生产者利用该过程将自己生产的产品投放到缓冲池中,并用整型变量 count 来表示在缓冲池中已有的产品数目,当 count≥n 时,表示缓冲池已满,生产者须等待。

2.get(x):消费者利用该过程从缓冲池中取出一个产品,当 count≤0 时,表示缓冲池中已无可取用的产品,消费者应等待。

两个条件变量:notfull和notempty,代表进程阻塞原因

producer-consumer管程的描述:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
type producer-consumer=monitor
Var in,out,count: integer;
buffer: array[0, …, n-1] of item;
notfull,notempty:condition; //条件变量
procedure entry put(item)
begin
if count>=n then notfull.wait; //缓冲池已经满了,生产者需要等待(我觉得命名为full可能更好,代表原因;不过也可以理解为:等到notfull才继续执行)
buffer(in):=nextp;
in:=(in+1) mod n;
count:=count+1
if notempty.queue then notempty.signal; //唤醒一个在notempty队列中等待的进程
end
procedure entry get(item)
begin
if count<=0 then notempty.wait;
nextc:=buffer(out);
out:=(out+1) mod n;
count:=count - 1
if notfull.quene then notfull.signal;
end
begin in:=out:=0
count:=0
end

不是很明白,怎么解决的资源打架问题

(5)小结

  • 实现进程互斥时用P操作测试是否可以使用共享资源,这相当于测试“资源是否可以使用” ; 用V操作归还共享资源,这相当于发送了“共享资源已空闲”的消息。

  • 把进程的互斥与进程的同步统称为进程同步,把用来解决进程互斥与进程同步的机制(如PV操作)统称为同步机制

  • 但是,进程的互斥与进程的同步是有差别的。进程的互斥是进程之间竞争共享资源的使用权。这种竞争没有固定的必然关系,哪个进程竞争到使用权则共享资源就归哪个进程使用,直到使用完再归还使用权。若无进程在使用共享资源,就允许某申请资源进程去使用它,即使是一个刚刚使用过某共享资源的进程,而此时无其他进程要使用这个共享资源,则该进程仍可再次使用它。

  • 而进程同步的情况就不同了,涉及共享资源的并发进程之间有一种必然的依赖关系。当进程必须同步时,即使无进程在使用共享资源,尚未得到同步进程的消息仍然不能去使用这个资源

  • 所以用PV操作管理共享资源时,一定要正确区分互斥与同步。最关键的是确切地定义信号量,以及合理地调用各信号量上的P操作和V操作。

6、进程通信

操作系统学习笔记-7:进程通信

进程通信指的是进程之间的信息的传播和交换。

低级通信:进程之间的互斥和同步。

  • 信号量机制作为通信工具的缺点:
    • (1)效率低 ;
    • (2)通信对用户不透明。

高级进程:通信是指用户可直接利用操作系所提供的一组通信命令,高效地传送大量数据的一种通信方式。

  • 特点:
  • (1)使用方便操作系统隐藏了进程通信的细节,对用户透明,减少了通信程序编制上的复杂性。
  • (2)高效的传送大量数据,利用通信原语实现。

1. 共享存储

进程 A 无法直接访问进程 B 的地址空间,反之亦然,所以提供一块可以供 AB 访问的共享空间。这块共享空间属于互斥的临界资源。

1.1 基于数据结构

各个进程共用某些数据结构,借以实现进程间的信息交换。比如共用一个长度为 10 的数组。这种共享速度慢、限制多,属于低级通信方式。

1.2 基于存储区

在内存中划出一块共享存储区,各个进程通过对这个共享区的读写交换信息、实现通信。数据的形式、存放位置都由进程控制,而不是操作系统。相比之下,这种共享方式速度更快,属于高级通信方式。

2. 消息传递

进程通过操作系统提供的“发送消息/接受消息”两个原语进行数据交换,而数据交换的基本单位是一个格式化的消息,该消息包括消息头和消息体。消息头包括:发送进程 ID,接受进程 ID,消息类型,消息长度等格式化的信息。

2.1 直接通信方式

发送进程发送消息之前,首先申请一个缓冲区,之后把消息复制到缓冲区,再通过发送原语把缓冲区发送给接受进程,缓冲区首先到达接受进程的消息缓冲队列队尾。接受进程通过接受原语读取队列消息,并复制到本地变量。

2.2 间接通信方式

也叫做信箱通信。发送进程发送的消息首先到达一个消息容器,接受进程再从消息容器中接受消息。

3. 管道通信

管道又名 pipe 文件,其实就是在内存中开辟一个大小固定的缓冲区。它采用的是半双工通信,一个时间段内只能实现单向的传输。另外,管道也是互斥的临界资源。管道写满的时候,写进程会被阻塞,直到读进程把数据读走;而管道空的时候,读进程会被阻塞,直到写进程把数据读入。这里要注意,管道与我们之前说过的生产者、消费者使用的缓冲区不同。写会一次性写完,读会一次性读完,不存在写一下、读一下的情况

7、线程基本概念

操作系统学习笔记-8:线程

(1)线程的引入

首先回忆一下为什么会有进程 —— 在以前,程序是串行执行的,为了让多道程序并发执行,引入了进程。进程虽然显著提高了资源利用率和系统吞吐量,满足了并发的需求,但是这种并发能不能做得更好呢?事实上,进程既是一个携带资源的独立单位,也是独立调度的基本单位,因此,在进程的创建、撤销和切换时,系统必须为之付出较大的时间空间开销(没办法“轻装上阵”)。鉴于此,系统不宜设置过多的进程,也不宜频繁地切换进程,这对于并发来说是一种限制。

如何解决这个问题呢?可以把进程看作是管理初创公司的老板,一开始人手不足,老板既要管理公司,也要四处奔跑沟通业务;但是一旦人手充足,那么老板仍然可以管理公司,只是沟通业务的工作就可以交给手下人去执行了。同理,我们可以考虑依然让进程作为拥有资源的独立单位,但是独立调度的基本单位则不再是进程,而是新引入的线程了。

它将进程的两个基本属性分开,==作为调度和分派的基本单位==,==不同时作为拥有资源的单位==,以“轻装上阵”;对于拥有资源的基本单位,又不对之进行频繁切换。

在多线程OS中,通常一个进程包括多个线程,每个线程是利用CPU的基本单位,是花费最小开销的实体。

(2)进程和线程的比较

  • 进程是指在系统中正在运行的一个应用程序

  • 每个进程之间是独立的,每个进程均运行在其专用且受保护的内存空间内

    • 比如同时打开QQ、Xcode,系统就会分别启动2个进程

  • 1个进程要想执行任务,必须得有线程(每1个进程至少要有1条线程)

  • 线程是进程的基本执行单元,一个进程(程序)的所有任务都在线程中执行

    • 比如使用酷狗播放音乐、使用迅雷下载电影,都需要在线程中执行

    • 1个进程中可以开启多个线程,每个线程可以并行(同时)执行不同的任务:进程 ->车间,线程->车间工人 多线程技术可以提高程序的执行效率 比如同时开启3条线程分别下载3个文件(分别是文件A、文件B、文件C)

  • 同一时间,CPU只能处理1个线程,只有1个线程在工作(执行)多线程并发(同时)执行,其实是CPU快速地在多个线程之间调度(切换)如果CPU调度线程的时间足够快,就造成了多线程并行执行的假象。

    • 如果线程非常非常多,CPU会在N多线程之间调度,CPU会累死,消耗大量的CPU资源每条线程被调度执行的频次会降低
  • 总结

    • 调度的基本单位

      引入线程后,调度的基本单位不再是进程,而是线程。线程能够独立运行,且切换的时候,代价远远小于进程切换的代价。同一进程不同线程的切换,不会引起进程的切换。

      执行的基本单位

      通常认为进程不再作为可执行的实体。也即,可以说进程处于“执行”状态,但其实指的是该进程的某个线程正在执行;可以说进程处于“挂起”状态,但其实指的是该进程的所有线程都被挂起。其他同理。

      并发性

      进程间仍然能够并发,不仅如此,一个进程中的多个线程间也能并发,不同进程中的线程也能够并发,大大提高了 OS 的并发性。

      资源

      资源依然掌握在进程手中。为了性能考虑,线程仅占有一点必不可少的资源(比如 TCB,程序计数器等)。那么如何访问其它资源呢?事实上,同一进程的线程共享该进程所拥有的资源。另外,这些线程还共享同一片内存地址空间,所以也可以方便地进行通信。

      独立性

      同一进程中的线程间独立性要比不同进程间独立性低很多。前者独立性高,因为要防止进程之间彼此干扰和破坏;后者独立性低,因为同一进程的多个线程通常需要协作完成任务,互相之间可访问程度相对来说会比较高。

      系统开销

      在创建和撤销进程时,系统需要分配或者回收 PCB,分配或者回收资源,所以需要付出一定的时空开销;但是线程的创建和撤销的时空开销则明显小很多,尤其是在同一进程内的线程创建和撤销,这种开销会更加地小。

      支持多处理机系统

      传统的单线程进程,即使处理机再多,一个进程也只能运行在一个处理机上;但是引入了线程后,一个进程的多个线程可以分配到多个处理机上、并行执行。

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~