操作系统的同步互斥

同步互斥

同步互斥是操作系统, 协调进程之间动作和相互关系的一种机制

• 背景:

在这里头呢, 我们先通过生活中的例子, 先来说明同步互斥到底是个什么样的问题,我们有一些什么样的方法来解决它

• 临界区

然后是在计算机系统当中, 我们给出三类不同的做法,我们下边会一一来介绍它

同步互斥的背景

也就是说, 我们为什么要做这件事情

并发进程的正确性

• 独立进程

① 不和其他进程共享资源或状态

之前我们在写程序的时候, 我写一个独立的程序,这个程序它不需要和其他的进程共享状态和资源,

② 确定性->输入状态决定结果

在这种情况下,他的确定性和可重现是可以保证的, 也就是说, 只要输入的状态是一致的, 那么它输出的结果一定就是相同的.

③ 可重现->能够重现起始条件

也就是说, 我第一遍执行和第二遍执行它的结果是一样的

④ 调度顺序不重要

对于独立进程，由于它们不与其他进程共享资源或状态，它们的执行结果只取决于自身的输入。因此，即使操作系统改变了它们的调度顺序，只要每个进程的输入保持不变，它们的输出也会保持不变。这意味着进程的执行顺序对于最终结果没有影响，从而保证了程序的正确性和可预测性。

这种特性在某些类型的程序中是非常有用的，因为它允许操作系统灵活地调度进程，以优化系统性能，例如通过减少等待时间或平衡处理器负载，而不必担心这会影响程序的输出。然而，这种假设并不总是成立的，特别是在涉及到需要同步操作或共享资源的程序中，调度顺序可能会变得非常重要。

• 并发进程

① 在多个进程间有资源共享

在操作系统中, 在有了多进程后, 会有多个并发的进程交替执行,这种交替执行会导致进程之间有资源共享。

比如说， 大家都要占用CPU, 我是时分的, 大家都要占用内存, 那我是把一块儿区域分配给你,把另一块区域分配给另外一个进程

② 不确定性 ③ 不可重现

正是由于这种资源的共享, 这种不确定性, 和不可重现就会产生.

那如果说, 在这里头你的程序的结果, 对这种不确定性, 或者说, 这种不一致性是没有依赖的 , 那在我这里变化的一部分, 是不影响你的结果,那这时候我们的程序应该也算正确的.

但是一些时候呢, 这些状态的不一致, 会导致你运行结果的不一致, 甚至于这种不一致呢, 就是我们希望它出现的,比如说我两个进程之间在通讯, 那根据通讯对方回过来的信息的不同, 我这边处理是不一样的, 而这种在通讯的过程当中, 两者之间保证它可重现这事儿不行的.

并发进程的正确性

• 执行过程是不确定性和不可重现的

• 程序错误可能是间歇性发生的

那在这种情况下, 我们要想保证一个进程执行的正确性, 难度就增加了,

这时就会出现一些什么样的错误呢? 就是我们有一些错误它是间歇性的,

也就是说你第一遍执行, 那外界的环境跟现在不一样了, 那也许没错,到另一次执行的时候呢? 它可能就出错了.实际上这就是我们在实际写程序当中呢? 经常碰到这种情况, 你自己在那儿测试的时候,你的程序都一切正常 , 交给用户用的时候, 情况就变了, 那你说我严格测试之后, 为啥会不一样呢, 实际上说, 你所说的严格, 总会有一些依赖的环境, 跟你在测试的时候, 和真实系统运行的时候, 是不一样的

进程并发执行的好处

那这样说, 进程并发这么麻烦, 我们不这样做不就行了吗? 但是进程的并发执行呢? 又给我们带来了很多好处, 这些好处呢? 导致于我们非常希望这样做

• 进程需要与计算机中的其他进程和设备进行协作

•好处1: 共享资源

①多个用户使用同一台计算机

这样我们可以节约成本

② 银行账户存款余额在多台ATM机操作

你的钱存在银行里面, 但你并不一定在什么时间什么地方,那这个银行账号的余额呢? 可以在多台取款机上操作, 那么我就可以就近存取我的现金.这会给你带来好处的.

③机器人上的嵌入式系统协调手臂和手的动作

机器人上面有多种设备, 比如手臂和手之间的控制机构,它们之间要协调,因为只有在这种情况下, 你们协调到一切, 你才能够完成一个复杂的动作, 比如说机器人的直立行走或者说跑步, 那这些都需要多个机构来协调的,这些共享是我们这里必须要做的,

•好处2:加速

可以提高速度

① I/O操作和CPU计算可以重叠(并行)

我们之前在讲进程的时候说, CPU是管计算, 设备是跟外界做交互的,这两个实际上它们可以在时间重叠上可以一起工作的,那它是并行, 如果说, 你在算的时候,IO设备你不能让他工作, 那这时候I/O设备就只能闲着,而你在做IO的时候, CPU没有相关的数据 ,他也没办法做, 这样话, 这两个效率就降低了.

我们希望呢, 这两个能很合理的进行安排, 以便于它们俩可以同时工作,那这样的话, 程序运行的速度就提高了.

② 程序可划分成多个模块放在多个处理器上并行执行

再有一个就是说, 我们程序有若干个处理机, 我把程序切成若干个模块,这些模块可以作为独立的程序, 跑到不同的处理机上, 那这时候它可以并行执行,也可以提高它的速度,

•好处3:模块化

我用多个进程来完成一个综合的功能, 比如说我们在这里头说到编译

•将大程序分解成小程序

以汇编为例, gcc会调成cpp, cc1,cc2,as,ld

以编译的过程为例, 编译呢, 我们可以把它分成源代码模块的编译,库的编译,和最后的链接, 我们把他分成这几个部分,

•使系统易于复用和拓展

这几个部分, 我们把它写成独立的程序, 那这样的话, 它们组合到一起,进行复用和拓展会比原来方便

综上所述, 基于这几个好处,我们需要多个进程并发执行.

并发创建新进程时的标识分配

我们刚才说, 并发执行有状态的变化, 这些状态的变化可能影响到,我程序执行的结果, 在这儿我们就举一个例子, 看看到底会有什么样的影响,这些影响我们怎么来控制它,

•程序可以调用函数fork()来创建一个新的进程

我们在操作系统里有一个进程创建的系统调用fork()

①操作系统需要分配一个新的并且唯一的进程ID

这个创建进程的系统调用呢? 他要给每一个新创建的进程呢, 分配一个进程ID 一个标识,那这个标识的分配呢

② 在内核中, 这个系统调用会运行

new_pid = next_pid++

在我们系统里头呢,就会对应过来这样一行代码, 在操作系统内核里头,fork()的实现代码里头,也能找到这样一行, 说我一个进程的id, 系统里有一个全局变量next_pid, 我把它赋值并且加一, 也就是说把当前的值赋给你新分配的这个进程, 然后把它的值加一,这样的话, 下一次再来分配的时候, 我就是接下来这个值了,

③ 翻译成机器指令

LOAD next_pid Reg1
STORE Reg1 new_pid
INC Reg1
STORE Reg1 next_pid    

那这个代码呢, 机器在翻译的时候, 就会把它转换成几条汇编指令,在源代码里就一行, 那这翻译成的四条指令,你拿过来执行呢, 应该也是没问题的, 它是把全局变量里的id读到寄存器里头, 然后呢, 再把这个寄存器, 赋值到这个进程自己的进程控制块里的变量new_pid, , 然后把寄存器值加一, 然后把寄存器加一后的结果, 存回到你原来的next_pid.

这个过程就结束了

•两个进程并发执行时的预期结果(假定next_pid = 100)

正常情况下, 执行是没问题的, 我们期望它预期的结果是这样的,

① 一个进程得到的ID应该是100

② 另一个进程的ID应该是101

③ next_pid应该增加到102

假定我开始的时候对pid是100, 一个进程调用fork, 它由100变成101, 然后第二个进程再调用fork, 那它分配到101, 然后把当前值变成102,那这是我们期望的结果.

新进程分配标识中的可能错误

好,你在这个过程当中, 我们看一下, 如果说, 我的执行顺序在一种特定顺序下,这个预期的结果能出现吗?

假定我有两个进程A和 B , 那它们在调用fork之前呢, 它们各自都有自己的一个局部变量new_pid, 它俩的名字是一样的, 整个系统里呢, 有一个next_pid, 当前值是100, 我们这个时候调用fork(), 我们重点关注的是那条分配进程标识的代码, 它所对应的汇编代码的执行顺序

首先呢, 这四条汇编语句, 他可能出现切换, 先上来之后,读next_pid ,然后这时候呢, 发生了一次切换

到进程B再去读这个next_pid, 那这两条执行完了之后呢, 我们的new_pid就已经变成100了, 而进程B呢, 也变成了100,

那这个时候, 我们就已经发现它有问题了, 这两个进程new_pid是相同的值, 你给两个不同的新创建的进程, 分配了一个相同的标识, 那这时候会有麻烦的

左边和右边 , 加一都是101, 这个赋值就被赋值了两遍, 并且是相同的值

在这个过程当中,出现了什么一情况,两个进程分配的ID是一样的,并且新创建的变化完了之后,ID它不是创建了两个进程,我应该加2 这地方它只加了1

好 那这时候出现,这种情况的原因是什么,原因就是在于 我们正常假设这四条是一块执行的 ,读出来 赋值 然后加1写回去,

B进程这边呢读出来赋值做了,加1写回去这件事情中间被切断了,切断之后,这两头的加1就变成是相同的了,写回去也就变成相同的了,我们这个状态就出结果了

原子操作(Atomic Operation)

造成上面的原因就是, 就是读出加1这个操作 ,它并没有是一个整体在进行操作 这就是我们这里说的原子操作

•原子操作是指一次不存在任何中断或失败的操作

原子操作是指一次不存在任何中断或失败的操作, 如果出现了中间的失败 ,中断那这时候是不行的,在生活当中的原子操作是什么呢,你比如说我到银行里去 存款或者取款, 那你是有一个假设, 说我把钱给到窗口里头 那么这时候呢我的存折上的钱 金额是要发生变化的, 这两个一起发生 那储户没有任何意见,如果这两个分开 你存进去钱了 但是你的存折上的 金额没有发生变化, 要么你不同意 ,要么银行不同意

• 要么操作成功完成

• 或者操作没有执行

•不会出现部分执行的状态

这里说的原子操作 那要求要么成功执行 要么没有操作 不会出现部分执行的状态 , 如果说我们刚才pid加1的这个操作,它是个原子,那我们这儿就没问题了,现在的问题是我们把它分成两段,中间做了个切换,这是我们要面临的挑战

•操作系统需要利用同步机制在并发执行的同时, 保证一切操作是原子操作

所以我们今天讨论 同步互斥问题的时候 就是要在操作系统里头 提供一种同步机制,既允许并发执行 以便于我能做到资源共享 和提高速度,同时我要让一些操作是原子操作,因为你不是原子操作之后,所带来的麻烦就会很大,那这是我们在这里的需求,接下来我们会来说, 我们有一些什么样的办法来解决这个问题