博客

🎉作者简介:👓



博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢

c

+

+

,

g

o

,

p

y

t

h

o

n

,

目前熟悉

c

+

+

，

g

o

语言，数据库，网络编程，了解分布式等相关内容

\textcolor{orange}{博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢c++,go,python,目前熟悉c++，go语言，数据库，网络编程，了解分布式等相关内容}






博主在读机器人研究生，目前研一。对计算机后端感兴趣，喜欢


c




+








+


,




g


o


,




p


y


t


h


o


n


,




目前熟悉


c




+








+


，


g


o


语言，数据库，网络编程，了解分布式等相关内容






📃



个人主页：

\textcolor{gray}{个人主页：}






个人主页：






小呆鸟_coding


🔎



支持

:

\textcolor{gray}{支持:}






支持




:








如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦

\textcolor{green}{如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦}






如果觉得博主的文章还不错或者您用得到的话，可以免费的关注一下博主，如果三连收藏支持就更好啦





👍



就是给予我最大的支持！

\textcolor{green}{就是给予我最大的支持！}






就是给予我最大的支持！





🎁

💛本文摘要💛

本专栏主要是讲解操作系统的相关知识 本文主要讲解 同步与互斥

文章目录

• 
  🎍同步与互斥
  
• • 
    🎉1. 背景
    
  • 
    🎉2. 一些概念（Part 1）
    
  • 
    🎉3. 一些概念（Part 2）
    
  • 
    🎉4. 一些概念（Part 3）
    
  • 
    🎉5. 临界区
    
  • • 
      💝5.1 方法1：禁用硬件中断
      
    • 
      💝5.2 方法2：基于软件的解决方法
      
    • 
      💝5.3 方法3：更高级的抽象
      
    • • 
        🎃5.3.1 现代操作系统提供的方法
        
  • 
    🎉6. 总结
    


清华操作系统系列文章：可面试可复习




1. 操作系统—概述



2. 操作系统—中断、异常、系统调用



3. 操作系统—物理内存管理



4. 操作系统—非连续内存分配



5. 虚拟内存管理



6. 操作系统—虚拟内存管理技术页面置换算法



7. 进程管理



8. 调度算法



9. 同步与互斥



10. 信号量和管程



11. 死锁和进程通信



12. 文件系统管理

🎍同步与互斥

🎉1. 背景

• 一些概念
• 临界区
• 方法1：禁用硬件中断
• 方法2：基于软件的解决方法
• 方法3：更高级的抽象

到目前为止

• 
多道程序设计

  : 现代操作系统的重要特性
• 
并行很有用(为什么?) 提示:

  • 
多个并发实体: CPU IO 用户 等

• 
进程,线程

  : 操作系统抽象出来用于支持多道程序设计
• 
CPU调度

  : 实现多道程序设计的机制
• 
调度算法: 不同的策略


如果资源处理不当，会发生饥饿和死锁等，出现一系列问题，跟调度有关

独立的线程:

• 不和其他线程共享资源或状态
• 确定性: 输入状态决定结果
• 可重现: 能够重现起始条件, IO
• 调度顺序不重要

合作线程:

• 在多个线程中共享状态
• 不确定性（对于单个进程而言，执行时间不确定，可能会被其他进程抢占）
• 不可重现
  
  
  不确定性和不可重现意味着bug可能是间歇性发生的
  


进程,线程;计算机,设备需要合作


合作优点:：

• 
  优点1：共享资源
  

  • 一台电脑,多个用户
  • 一个银行存款余额,多台ATM机
  • 嵌入式系统

• 
  优点2：加速
  

  • IO操作和计算可以重叠
  • 多处理器

• 
  优点3：模块化
  

  • 将大程序分解成小程序
    • 以编译器为例， gcc会调用cpp,cc1,cc2,as,ld
  • 使系统易于扩展

• 将
  
next_pid

  赋给
  
寄存器1

  （将内存中的内容加载到寄存器中）
• 
store

  将寄存器中的内容存到内存中，将
  
寄存器1

  中的内容存到
  
new_pid

  这个里面(此时
  
new_pid

  具有了
  
next_pid

  的值)

• 进程执行的时候会保存寄存器的值在自己的堆栈里
• 进程切换会把进程的资源保存起来，切回来时，再把资源恢复回去
• 恢复进程1的上下文

无论多个线程的指令序列怎样交替执行,程序都必须正常工作

• 多线程程序具有不确定性和不可重现的特点
• 不经过专门设计,调试难度很高

不确定性要求并行程序的正确性

• 先思考清楚问题,把程序的行为设计清楚
• 切忌给予着手编写代码,碰到问题再调试


同步互斥就是解决上述不确定，不重现问题


🎉2. 一些概念（Part 1）

前面的现象称为

Race Condition

(竞态条件)

系统缺陷: 结果依赖于并发执行或者时间的顺序,时间

• 不确定性
• 不可重现

怎么样避免竞态?

• 让指令不被打断
• Atomic Operator(原子操作)

解决办法（原子操作）

• 
原子操作是指一次不存在任何终端或者失败的执行


  • 该执行成功结束
  • 或者根本没有执行
  • 并且不应发生任何部分执行的状态

• 
实际上操作往往不是原子的


  • 有些看上去是原子操作,实际上不是
  • 连x++这样的简单语句,实际上是由三条指令构成的
  • 有时候甚至连单条假期指令都不是原子的
    • 
Pipeline,super-scalar,out-of-order,pape fault


实例

• load和store是原子操作，但是++不是原子操作
  
  
  
  
• 死锁：当俩个进程都拥有一定的资源，同时还需要其他共享资源时，俩个进程相互等待，进程A等待进程B的资源,进程B等待进程A的资源

🎉3. 一些概念（Part 2）

举例

• 交换一下顺序
  
  

🎉4. 一些概念（Part 3）

• 为note贴上标签，指定是谁留下的纸条，仍然会出现问题，当进程A留下标签后，切换到进程B，也会留下标签，此时结果就是都没有买面包

设置不同的控制逻辑

可以解决，但是太复杂

• 
临界区：

  只允许一个进程去访问临界区的代码，这个代码主要对一起共享的资源进行读操作或写操作，如果有一个程序在临界区执行了，其他程序就需要等地
• 
互斥：

  确保只有一个程序在临界区叫互斥

解决办法

🎉5. 临界区

• 
互斥

  : 同一时间临界区中最多存在一个线程
• 
Progress

  : 如果一个线程想要进入临界区,那么它最终会成功
• 
有限等待

  : 如果一个线程i处于入口区,那么在i的请求被接受之前,其他线程进入临界区的时间是有限制的
• 
无忙等待(可选)

  : 如果一个进程在等待进入临界区,那么在它可以进入之前会被挂起

💝5.1 方法1：禁用硬件中断


中断除了响应硬件事件之外，中断还会使得进程切换，这也就会导致死锁和饥饿等问题



时钟中断即使当前程序在执行，也会打断该程序，OS完成调度，切换到其他进程


• 
  没有中断,没有上下文切换,因此没有并发
  

  • 硬件将中断处理延迟到中断被启用之后
  • 大多数现代计算机体系结构都提供指令来完成

• 
  进入临界区
  

  • 禁用中断

• 
  离开临界区
  

  • 开启中断

缺点

• 对于多CPU是有限制的，因为一个CPU执行屏蔽中断时，他只会中断它自己的，并不会中断其他CPU的中断，其他CPU还是会继续执行
• 
受制于临界区的执行时间，，对整个系统效率会产生影响，不适合多CPU

  
  

💝5.2 方法2：基于软件的解决方法

• 进程1和进程2只能交替进行，一旦有一个程序退出，那么另一个程序下次还想进入临界区，那么它一直等待，一直进不去
  
  

缺点

• 满足互斥但是不满足前进

改进

• 无法满足互斥

• 将flag[i]=1,放在前面，此时满足互斥但是存在死锁

• 
正确方法

  :把前面的方法综合一下

• 
  满足进程Pi和Pj之间互斥的经典的基于软件的解决方法(1981年)
  

• 
  使用两个共享数据项
  

  • 
int turn; //指示该谁进入临界区

  • 
bool flag[]; //指示进程是否准备好进入临界区


• 
  进入临界区:
  

flag[i] = true;
turn = j;
while(flag[j] && turn == j);

• 
  退出临界区
  

flag[i] = false;

实例

do{
	flag[i] = true;
	turn = j;
	while(flag[j] && turn == j);
	CRITICAL SECTION
	flag[i] = false;
	REMAINDER SECTION
}while(true);


Bakery 算法(N个进程的临界区)


• 进入临界区之前,进程接收一个数字
• 得到的数字最小的进入临界区
• 如果进程Pi和Pj收到相同的数字,那么如果i<j,Pi先进入临界区,否则Pj先进入临界区
• 编号方案总是按照枚举的增加顺序生成数字

俩个窗口，很多人去窗口取钱，首先取票号，当俩个人取的票号一样时，此时比较身份证，看谁的身份证小则优先取钱。

总结



Dekker算法(1965):

第一个针对双线程例子的正确解决方案


Bakery算法(1979):

针对n线程的临界区问题解决方案

复杂:

• 
需要两个进程的共享数据项


需要忙等待:

• 
浪费CPU时间


没有硬件保证的情况下无真正的软件解决方案:

• 
Perterson算法需要原子的LOAD和STORE指令


💝5.3 方法3：更高级的抽象

硬件提供了一些原语

• 像中断禁用, 原子操作指令等
• 大多数现代体系结构都这样

操作系统提供更高级的编程抽象来简化并行编程

• 例如,锁,信号量
• 从硬件原语中构建

锁是一个抽象的数据结构

• 一个二进制状态(锁定,解锁),两种方法
• Lock::Acquire() 锁被释放前一直等待,然后得到锁
• Lock::Release() 锁释放,唤醒任何等待的进程

使用锁来编写临界区

• 前面的例子变得简单起来:

lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

🎃5.3.1 现代操作系统提供的方法

大多数现代体系结构都提供特殊的原子操作指令

• 通过特殊的内存访问电路
• 针对单处理器和多处理器

Test-and-Set 测试和置位

• 从内存中读取值
• 测试该值是否为1(然后返回真或假)
• 内存值设置为1

交换

• 交换内存中的两个值


这俩个程序，虽然由多条指令完成，但是被封装成了机器指令， 意味着在执行这三条指令的时候，不允许打断


bool TestandSet(bool *target){
		bool rv = *target;
		*target = true;
		return rv;
}

void Exchange(bool *a, bool *b){
		bool tmp = *a;
		*a = *b;
		*b = tmp;
}

• 不止适用于俩个进程，也适用于多个进程，而且多个进程，进入临界区与退出临界区的操作步骤是一样的

问题

解决办法1：使用

test-and-set


• 
当一个进程发现自己进不了临界区，需要等待时，可以让该进程阻塞睡眠，将该进程挂在队列中去,把CPU让出来，给其他进程使用，当之前的进程，退出临界区后，他会唤醒睡眠的进程


• 如果临界区很短，则使用忙等待，不需要进行上下文切换，上下文切换开销相对大

• 如果临界区很长，开销远远大于上下文切换，选择无忙等待
  
  

解决办法2：使用

exchange


共享数据（初始化为0）
int lock = 0;

线程Ti
	int key:
	do {
		key = 1;
		while (key == 1) exchange(lock, key);
			critical section
		lock = 0;
			remainder section
		}

优点

• 适用于单处理器或者共享主存的多处理器中任意数量的进程
• 简单并且容易证明
• 可以用于支持多临界区

缺点

• 忙等待消耗处理器时间
• 当进程离开临界区并且多个进程在等待的时候可能导致饥饿
• 
死锁

  • 如果一个低优先级的进程拥有临界区并且一个高优先级进程也需求，那么高优先级进程会获得处理器并等待临界区（使得高优先级进程忙等待，使得低优先级进程无法释放锁）

🎉6. 总结

• 
  锁是更高等级的编程抽象
  

  • 
互斥可以使用锁来实现

  • 
通常需要一定等级的硬件支持


• 
  常用的三种实现方法
  

  • 
禁用中断(仅限于单处理器)

  • 
软件方法(复杂)

  • 
原子操作指令(单处理器或多处理器均可)——最常用


• 
  可选的实现内容:
  

  • 
有忙等待

  • 
无忙等待