OS复习笔记ch5-1

引言

讲解完进程和线程之后，我们就要来到进程的并发控制这里，这一章和下一章是考试喜欢考察的点，有可能会出大题，面试也有可能会被频繁问到，所以章节内容较多。请小伙伴们慢慢食用，看完之后多思考加强消化吸收。

并发原理

既然我们本章的主题是并发，那么我们就围绕它来展开。

1. 并发从何而来
2. 并发可能出现的问题
3. 如何解决可能出现的并发问题

并发从何而来

百度词条：并发，在操作系统中，是指一个时间段中有几个程序都处于已启动运行到运行完毕之间，且这几个程序都是在同一个处理机上运行，但任一时刻只有一个程序在处理机上运行。

并发，简单来说就是基于分时系统涉及的宏观上的并行（即程序一并执行）。
微观上，任一时刻只有一个程序上处理机，也就是依然是串行执行。

为啥要引入并发，其实也是设计分时OS的初衷，希望我们的OS可以快速响应。比如，当我们点击多个可执行文件，不应该出现一程序个等待另一个程序执行完才能上处理机，反之应该立刻响应，尽快满足用户需求。所以并发可以说是随着分时的产生而产生的。

对于现代OS来说，分时已经是最基本的特征了，但是早期的OS还没有实现的时候，这种设计思路是非常大的一个创新。比如，在1986年的一篇《No Silver Bullet —Essence and Accident in Software Engineering》论文中，Fred Brooks指出“Most observers credit time-sharing with a major improvement in the productivity of programmers and in the quality of their product, although not so large as that brought by high-level languages.”
翻译成中文：大多数观察家都认为，分时工作大大提高了程序员的工作效率和产品质量，尽管其提高幅度还不如高级语言。

并发可能出现的问题

这里从以下四个角度去分析问题所在。

（1）资源的共享和竞争
这个很好理解。试想，如果是一个公司的员工，大家坐在一个办公室，使用同一台打印机和饮水机，资源共享很正常，但是如果大家都想晋升，名额又有限，自然就会出现竞争。
CPU只有一个，处理器寄存器、内存等也有限，资源的共享和竞争在所难免。
（2）处理器的时间分配
这个就是典型的分时OS存在的问题，即如何来管理和调度进程，分给不同的进程多少时间片合适。时间片分配不合理，就会出现一个进程长时间霸占处理机，导致其他进程饿死。
（3）进程之间的通信
比如，工作中老板和员工的沟通，就有点像父进程和子进程之间的通信，他们之间的信息需要传递，如何传递才能确保信息不会出错，发送方和接收方可以正常通信。如果微信的消息转发机制有问题，你跟
（4）进程活动的同步
马上五一了，假设12306现在放票，如果说兰州到郑州只剩下一张票了，大家都想要，此时只有一位幸运儿能抢到票。当这个幸运儿抢到票的同时，所有没有抢到票的人需要同步更新这个信息，如果说更新延迟，会导致多个人进入购票系统，有可能都已经付了钱，但是信息同步不及时最后还是购票失败，想必有人就会痛骂12306😂。

并发执行的特征

并发执行通常在多任务处理和多线程程序设计中出现，它指的是多个进程或线程在同一时间段内运行，但不一定是同时执行。这种技术可以提高效率，同时又会有一些问题，总结下来会有以下几个特征。

1. 间断性（异步）：

   • 解释：在并发执行中，任务不需要按照严格的顺序完成，而是可以根据资源的可用性和调度策略异步进行。这允许系统在等待某些操作（如输入/输出操作）完成时继续执行其他任务。
   • 例子：在Web服务器中，服务器可以同时处理多个客户端请求。当一些请求需要等待数据库查询结果时，服务器不会空闲，而是继续处理其他客户端的请求。

2. 失去封闭性：

   • 解释：在并发环境中，因为多个进程或线程可能会共享某些资源（如变量、文件等），单个进程的行为可能受到其他进程的影响，从而失去封闭性。这意味着进程的输出不仅取决于其输入和程序代码，还可能取决于其他并发执行的进程的状态。
   • 例子：如果两个线程同时向同一个文件写入数据，没有适当的同步，最终文件中的内容可能是这两个线程输出的混合，这会破坏数据的一致性。

3. 结果不可再现性：

   • 解释：并发程序的结果可能每次运行都不同，即使在相同的输入下也是如此。这是因为多个线程或进程之间的交互和调度可能每次都不一样。
   • 例子：一个多线程的计数器程序，多个线程在没有适当锁机制的情况下同时更新同一个共享变量，可能导致计数结果在不同的运行中出现不一致。

4. 不确定性：

   • 解释：由于操作系统的调度策略和外部条件的影响，同一个并发程序在不同时间的表现可能不同，其行为和性能具有不确定性。
   • 例子：在实时多任务操作系统中，任务的执行优先级和时间限制可能根据系统的当前负载和资源状态动态变化，使得任务完成的具体时间难以预测。

这些特征使得并发程序设计成为一个复杂且具有挑战性的领域，需要精心设计和测试以确保程序的正确性和性能。

并发处理系统

先看一个小例子

比如对于char in = getchar()，有可能并发接受到别的字符，导致程序错误
如果不加控制，那么对于对同一个代码的相同变量/资源就会产生竞争关系。

那么，遇到这个问题，我们应该如何解决呢？
举一个可能不太恰当的例子🤣，假如张三和李四是同班同学，他们都喜欢班花翠翠，这个时候就会出现问题，翠翠该如何抉择？
第一种：翠翠直接拒绝其中一个，选择另一个。
第二种：张三和李四公平竞争，谁更讨翠翠喜欢，谁就能心想事成。

同理，并发的解决方案：

1. 强制单个访问（一次只允许一个进程访问）
2. 产生竞争条件
   1. 多个进程/线程共享数据
   2. 最终结果依赖于进程的执行顺序
   3. 结果往往由最后一次操作决定

进程交互

首先了解一下，进程交互的几种情况

• 原子操作(atomic operation)或原语(primitive)，一个或多个指令序列，对外（执行）不可分；
• 互斥(mutual exclusion) ，指多个进程不能同时访问同一个资源；
• 死锁(deadlock)，指多个进程互不相让，都得不到足够的资源而无法运行；
• 饥饿(starvation)，指一个进程一直得不到资源（其他进程可能轮流占用资源）

根据感知情况可以分为以下几类

• 相互不感知：互斥和死锁（可复用）、饥饿
• 间接感知（通过全局变量等共享资源）：互斥、死锁、饥饿、数据不一致
• 直接感知（通信交互）：死锁（可消耗资源）、饥饿

间接感知：
假设12306的抢票进程如下（票数作为全局变量）

看上述代码，我们很容易发现，如果i是全局变量，那么很有可能因为进程之间信息不同步导致数据不一致，出现我们上述并发的问题举例的情况。

直接感知：

以口罩的生产线为例：

当I生产线完成了成型、压合和切边，发送一个信号给P生产线，P生产线从流水线上拿到I送过来的产品进行耳带点焊，以此类推IPO三个生产线通过通信合作。

互斥

说到解决方案，咱们的第一种方案其实就是互斥问题——对某些资源设置排他性的访问。
这里我们引入两个相关的概念。

• 临界资源：系统中某些资源只允许一个进程使用（可以是硬件/软件）
• 临界区：进程中访问临界资源的一段代码

对多个并发进程中相关临界区的代码设置互斥访问，就可以解决我们之前提到的并发问题。

其中，对于临界区的访问有16字方针：“空闲让进，忙则等待，有限等待，让权等待”

• 空闲让进：如果临界区某一时刻没有进程访问，那么允许此刻任何试图访问的进程访问临界区。
• 忙则等待：当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环，陷入忙等状态。
• 有限等待：对要求访问临界资源的进程，应保证有限时间内能进入自己的临界区，以免陷入“死等”状态～（受惠的是进程自己）
• 让权等待：当进程不能进入自己想要访问的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。（受惠的是其他进程）
  上述提及了死等和忙等两个状态，这里着重说一下。
• 死等状态：
  进程在有限时间内根本不能进入临界区，而一直在尝试进入，陷入一种无结果的等待状态。
  （没有进入临界区的正在等待的某进程根本无法获得临界资源而进入进程，这种等待是无结果的，是死等状态～）-> 这个时候应该放弃这个无结果的事情，保证自己等待的时间是有限的
• 忙等状态：
  当一个进程正处在某临界区内，任何试图进入其临界区的进程都必须进入代码连续循环，陷入忙等状态。连续测试一个变量直到某个值出现为止，称为忙等。
  （没有进入临界区的正在等待的某进程不断的在测试循环代码段中的变量的值，占着处理机而不释放，这是一种忙等状态～）-> 这个时候应该释放处理机让给其他进程

简单来说，死等就是没有结果的等待，应该及时止损，停止内耗；忙等是进程无意义的盲目等待，此时应该放弃占用的资源，学会放下。

硬件支持

上述讲解了互斥问题的解决思路，那么我们接下来具体了解一下具体的实现。
先来看看硬件是如何做的

1. 关中断：
   借鉴我们之前讲解的原语，当我们在访问临界区的时候关中断，此时不受外界的干扰，只有一个进程可以访问，也就不存在多个进程反复访问临界区的资源最后数据不一致。

不过，这个思路只适用于单处理器，原因是单处理器只允许交替进行，关中即不响应中断，CPU拿不到控制权，进程得不到调度，其他进程无法上处理机，也就不可能访问临界区。

但是对多处理器无效，多个处理器可以多进程上处理机同时访问临界区，关中只能关闭某一个处理器的，没有从根本上解决问题，同时若只能用单处理器，效率也十分低下，

2. 硬件指令1
   
   这里有三个参数，有两个整数是word，testval，还有一个整形指针word。
   函数内部定义了一个oldval用来存放word指针中的内容，然后比对oldval和testval，，如果相等，就让word指针指向newval的地址，然后返回oldval。

进程不停检查bolt的值，然后交换
试想，假设有n个进程都要访问临界区
第一个进程传入了testval=0，newval=1，他访问的时候bolt指向testval的值，满足if条件，此时更新bolt指向newval，最后返回oldval=0，跳出循环执行临界区代码。
第二个进程传入了testval=0，newval=1，他访问的时候bolt已经指向了newval，满足不了if条件，返回1一直陷入循环。
同理第三个进程陷入循环
……
当第一个进程走出临界区，此时bolt赋值为0，这样其他的进程就可以像第一个进程一样访问临界区，以此类推直到所有的进程执行结束，每一次只有进程能访问临界区。
3. 硬件指令2

同理，这里的bolt是锁，keyi相当于钥匙，交换之后第一个进程就可以拿到钥匙退出循环，但是其他进程keyi一直是1陷入循环，直到第一个进程退出临界区重新初始化bolt。

最后，我们来聊一下采用硬件方式解决中断的优缺点：

优点

• 适用于单处理器或者共享内存的多处理器中的多进程互斥
• 简单，易于验证
• 可支持多个临界区

缺点

• 忙等，浪费处理器时间
• 可能饥饿
• 可能死锁

限于篇幅，我们就先介绍到这里，下一节我们将着重讲一下“信号量”机制，希望小伙伴们能持续关注博主啊，你们的支持是我前进的最大动力💕