IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> C++知识库 -> 临界区互斥的软件实现方法 -> 正文阅读

[C++知识库]临界区互斥的软件实现方法

文章目录

C++11 thread

使用前需要首先

#include <thread>

创建一个新的线程

std::thread <thread_name>(<function_name>,<parameters>...);

比如

#include <iostream>
#include <thread>
using namespace std;
void func(){
	while(true){
		cout<<"actived"<<endl;
	}
}
int main(){
	thread t(func);//创建
	t.join();
	return 0;
}

join和detach

join是等待,detach是分离

join

在主函数中对创建的线程对象调用join,作用是使主函数在此等待线程函数执行完毕,然后主函数再继续执行

#include <iostream>
#include <thread>
using namespace std;
void func() {
	int cnt = 50;
	while (--cnt) {
		cout << cnt << " ";
	}
	cout << endl;
}
int main() {
	cout << "before t1" << endl;
	thread t1(func);
	t1.join();
	cout << "after t1" << endl;
	return 0;
}

before t1
49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1
after t1

如果不适用join等待线程函数,主函数自己呼呼跑完了,程序结束,进程释放资源,线程函数直接抛出异常

#include <iostream>
#include <thread>
using namespace std;

void func() {
	int cnt = 50;
	while (--cnt) {
		cout << cnt << " ";
	}
	cout << endl;
}

int main() {
	cout << "before t1" << endl;
	thread t1(func);
//	t1.join();//主函数不在此处等待线程函数
	cout << "after t1" << endl;
	return 0;
}


before t1
after t1
49t erminate called without an active exception
48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

线程函数在打印49之后主函数已经结束,抛出异常

join之后线程对象不再与任何线程相关联

detach

线程在detach之后会独立于创建它的线程,在后台运行,并且没有任何可以管理他的句柄

pslist命令

需要下载pstools然后解压,将pslist.exe放在C:\Windows\System32才能使用该命令

类似于tasklist

image-20220327192855986

只不过tasklist只能查看到进程层面,如果想知道一个进程有几个线程,tasklist是做不到的

使用pslist可以列出当前活动的进程以及进程包含的线程数

引入多线程概念之后,进程只剩下了组织和管理资源的作用,实际执行是线程的工作

一个进程可以有多个线程

栏目英文名NamePidPriThdHndPrivCPU TimeElapsed Time
翻译进程名称进程编号进程优先级线程数量句柄数特权总占用CPU的时间经过时间

使用pslist查看单线程进程

编译运行如下singleThread.cpp

#include <iostream>
using namespace std;
void func(){
	while(true);
}
int main(){
		func();
	return 0;
}

image-20220327194507620

注意不要使用devcpp等ide的编译运行,编译好了之后使用start命令执行,如果用devcpp编译运行可以找到singleThread有两个线程,其中一个是devcpp打开的singleThread.cpp

使用pslist命令之后发现该2572号进程只有一个线程

使用pslist命令观察多线程进程

编译运行如下multiThread.cpp

#include <iostream>
#include <thread>
using namespace std;
void func(){
	while(true);
}
int main(){
	thread t1(func);
	thread t2(func);
	t1.join();
	t2.join();
	return 0;
}

image-20220327202417581

此时发现该2852进程有三个线程,为什么是三个?主线程+t1托管线程+t2托管线程正好三个

单处理机下多线程程序的行为

使用vmware设置单处理机单内核模拟老式的单处理机机器

模拟单处理机机器的好处是某一时刻可以非常确定只有一个线程在运行

而有两个以上处理机则有可能两个线程同时运行

image-20220327202615470

编译运行下面程序

#include <iostream>
#include <thread>
using namespace std;
void func(const int &maxn) {
	for (int i = 0; i < maxn; i++) {
		cout << i << " ";
	}
	cout << endl;
}

int main() {
	thread t1(func, 1000);
	thread t2(func, 500);
	cout << "before t1.join" << endl;
	t1.join();
	cout << "after t1.join" << endl;
	cout << "before t2.join" << endl;
	t2.join();
	cout << "after t2.join" << endl;
	return 0;
}

image-20220327192627650

观察到t1首先执行,打印到11的时候挂起,t2执行打印了一个0挂起

主函数并没有等待t1,t2执行完毕再继续执行,而是在他俩执行同时执行

主线程,t1线程,t2线程三个线程轮流占用处理机

由于处理机只有一个,可以肯定任意时刻只有一个线程在进行,这一点可以通过以下程序体现:

#include <iostream>
#include <thread>
using namespace std;
void func(const char &name){
	int cnt=50;
	while(--cnt){
		cout<<name<<" ";
	}
}
int main() {
	cout<<"actived"<<endl;
	thread t1(func,'A');
	thread t2(func,'B');
	t1.join();
	t2.join();
	return 0;
}

编译运行

actived
A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A B B B B B B B B B B B B B B B BA A A A A A A A A A A A A A A  B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B B

可以发现,输出打印A或者B都是连成长串的,打印A时意味着处理机被线程t1占用.打印B时意味着处理机被线程t2占用.

这种行为和多核计算机上的运行该程序大不相同

在我的物理机上该程序的运行结果是这样的

actived
AB B B B B B B B B  BA  BA  BA  BA  BA  BA  BA  BA  BA  A AB A  A A A A A B B B A BA A  A BA  A BA  A BA  A BA  A BA  A BA A B B  B B B B B B B B B B B B B B B B B B A A A A A A A A A A A A A A A

存在好多BA一起打印,总不能处理机的处理时间就只允许打印一个字符吧,应该是两个线程同时进行了

临界区互斥的软件实现方法

标志法

单标志法

每个线程都有一个独立的标识,用于区分其他线程,在这里使用传入的参数id作为标识,只有当turn=id时线程才会进入临界区,其他时候线程在进入区等待turn被修改成自己的id值

这样保证了临界区互斥,但是坏处是每个进程在没有进入临界区时都是忙等待状态.

#include <iostream>
#include <thread>
using namespace std;

int turn=0;
int critical=0;
int maxn=3;
void func(const int &id) {
	while(true){
		while(turn!=id);
		cout<<id<<"    "<<critical<<endl;
		++critical;
		turn=(turn+1)%maxn;//处理机使用权让给id=turn+1的线程
	}
}


int main() {
	thread t0(func,0);
	thread t1(func,1);
	thread t2(func,2);
	t0.join();
	t1.join();
	t2.join();
	return 0;
}

效率非常慢,在单处理机的机器上甚至只有一秒五行的打印

image-20220328141016957

双标志法先检查

#include <iostream>
#include <thread>
using namespace std;
int turn=0;
int critical=0;
int flag[2]={0,0};
int i=0,j=1;
void funci(){
	while(true){
		while(flag[j]);//检查是j线程是否在临界区
		flag[i]=true;
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;
	}
}
void funcj(){
	while(true){
		while(flag[i]);//检查i进程是否在临界区
        //i线程没有在临界区,j趁机进入临界区
		flag[j]=true;//修改j的状态为"在临界区",作用是防止i同时进入临界区
		cout<<"j  "<<critical<<endl;
		++critical;
		flag[j]=false;
	}
}



int main() {
	thread ti(funci);
	thread tj(funcj);
	ti.join();
	tj.join();
	return 0;
}
在单处理机系统上的行为

image-20220328142314762

发现j线程貌似"从来就没有被执行过",一直都是i线程自娱自乐

注意这里"从来没有执行过"是加了引号的,没有打印打印输出并不能说明线程没有执行过,只能说明没有进入临界区

如果把主函数中创建线程对象时的顺序改成先j后i则一直都是j能进入临界区,i不能

考虑为什么会这样?

在主函数中加入打印语句观察:

int main() {
	cout<<"before ti"<<endl;
	thread ti(funci);
	cout<<"between ti and tj"<<endl;
	thread tj(funcj);
	cout<<"after tj"<<endl;
	ti.join();
	tj.join();
	return 0;
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oNModa1R-1648464946615)(https://raw.githubusercontent.com/DeutschBall/test/master/image-20220328142721225.png)]

主函数首先创建ti对象,意味着i线程比j线程开始地早

开始时flag[i]=flag[j]=false意味着临界区没有被占用

i线程理所应当进入临界区,此时j线程可能刚开始执行,但是可以肯定的时必然比i线程慢

i线程在临界区的行为是打印critical然后++critical,然后关闭自己的标记,意味着i线程退出了临界区,此时临界区空闲,也就是说j是有机会进入临界区的

	while(true){
		while(flag[j]);//检查是j进程是否在关键区
		flag[i]=true;
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;
	}

但是为什么j线程就是进不来呢?

注意我们有意设置只有一个处理机的虚拟机,作用是保证某时刻肯定只有一个线程在进行

那么当i线程设置flag[i]=false;之后i线程仍然在进行,意味着j线程还处于挂起状态,如果足够巧合,i线程的时间片在其设置flag[i]=false;之后正好用完,那么就换到j执行了,那么j此时肯定可以进入临界区了

但是哪有这么巧合呢,

		cout<<"i  "<<critical<<endl;
		++critical;

如果这两句很占用时间的话,那么i线程挂起的时候大概率是挂起在这个位置的,

此时flag[i]=true状态没有被改变,

i挂起后j一看flag[i]=true就知道i在临界区不干正事睡大觉,

(这里"知道"是不可能的,是因为单处理机系统上,当j进行时必然i挂起,但是flag[i]=true意味着i正在访问临界区,于是可以说i在临界区躺了)

但是j也没办法,因为flag[i]=true就把临界区的大门关死了,

然后j只能在进入区忙等,等自己时间片用尽后再次挂起,

换到i了,i下一次挂起时又躺在临界区睡觉…

但是如果说j永远不可能进入临界区,这样说也不对,

因为理论上i不可能总这么会挑时候睡觉,万一i就在刚出临界区的门的时候躺下了,

那么j就反客为主了,轮到i在进入区苦苦等待了

并且更严重的,如果i挑他在while(flag[j]);这句刚判断完,但是flag[i]=true;还没有执行的时候,也就是说他已经站在临界区门口了,骑在门框上了,这时候他躺了,由于他睡前懒到甚至不改flag,导致临界区的门没有关,j也可以进入临界区,两个线程都进入了临界区,所谓互斥算法名存实亡

关于这一点,在多核系统上体现的更明显

在多处理机系统上的行为

1.由于存在多个处理机,i和j能够同时进行(在单处理机系统上可以肯定某一时刻有且只有一个线程在进行)

这意味着,i进入临界区时,j不一定在睡觉,有可能在另一个处理机上进行,在j的进入去忙等,然后i出了临界区将自己的访问标志失效,此时j已经站在临界区门口了,但是i重新转一圈回到临界区门口需要时间,于是j就进入了临界区

image-20220328145319382

2.破坏互斥性的行为

image-20220328145632465

发现critical=2377被两个线程同时读取了

看似是"当i打印了critical,还没有没有打印换行符时,j进入临界区进行打印."(注意高亮文字的说法)

但是这样讲不通,因为只要i进入了临界区,flag一改,j是不可能"进入"临界区的

应该怎么解释呢?

看critical=2362时是j的最后一次打印,然后到i了,然后critical=2377时j突然进行了一次打印,接着就消失在了i的一大群打印中

合理的解释应该是,

j线程在critical=2363时,刚进入临界区就挂起了,没有来得及修改flag,自然后来的打印critical和自增也没有执行

i检查flag发现j没有修改flag,按照编程人员的逻辑,认为j没有在临界区(实际上时j在临界区门框上躺了),i进入临界区

i趁着j挂起时死劲儿进行,对应critical从2363到2377

此时j终于醒了,j断片之前还骑在临界区门框上,于是继续执行临界区,j首先修改访问标志,表示自己在临界区,然后打印critical

i完成了自增(可能),此时j还在打印换行符

i快j一步,率先离开临界区,去掉自己访问临界区的标志,i转了一圈又来到了进入区,但是由于j刚才睡醒之后第一件事就是修改了访问标志,i必须忙等

j和i前脚后脚出了临界区,j出临界区时修改访问标志

i一直在检查访问标志,就等j修改访问标志,i立刻冲进了临界区.

并且i没有j那么傻,起码i不会骑在临界区门框上睡觉,i进入临界区立刻修改访问标记,

j随后就进不了临界区了,然后j等时间片耗尽了又挂起了

i疯狂内卷…

双标志法后检查

#include <iostream>
#include <thread>
using namespace std;
int i=0;
int j=1;
int flag[2]={false,false};
int critical=0;
void funci(){
	while(true){
		flag[i]=true;
		while(flag[j]);
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;
	}
}
void funcj(){
	while(true){
		flag[j]=true;
		while(flag[i]);
		cout<<"j  "<<critical<<endl;
		++critical;
		flag[j]=false;
	}
}


int main(){
	thread t1(funci);
	thread t2(funcj);
	t1.join();
	t2.join();
	return 0;
}


		flag[i]=true;
		while(flag[j]);
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;

首先设定i的访问标记,作用是提醒线程j,如果j再次想要进入临界区时必须有个先来后到

然后判断while(flag[j])的作用是,j当前有可能在临界区中,i需要等待j出了临界区才能进入

程序员的想法是,只要flag[i]=true设置好了,就不存在i骑在临界区门槛上睡觉的情况了,即使i在判断while的时候睡觉了,j也进不来.

然后什么时候i睡醒了要出临界区就把自己的访问标记改一下,j就进来了

注意与双标志法前检查的区别

	while(true){
		while(flag[j]);//前检查
		flag[i]=true;
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;
	}

	while(true){
		flag[i]=true;
		while(flag[j]);//后检查
		cout<<"i  "<<critical<<endl;
		++critical;
		flag[i]=false;
	}

检查是指检查另一个线程是否在占用处理机,前后是相对于当前进程什么时候设定访问标记而言的

如果先设定当前线程的访问标记,然后检查另一个线程是否占用处理机则为后检查

想法是好的,破坏互斥的问题也解决了,但是又引入了新问题

过度谦让导致饥饿

上述程序在单处理机系统上的运行结果

image-20220328183305652

在i 6之后程序就不再有打印输出了,两个线程都在进入区忙等了,为什么呢?

两个线程存在同时修改自己访问标记的可能,即两个线程同时将flag[i]和flag[j]置1,

当两个标记都是1的时候两个线程都会认为对方正在临界区,我不能进去

这一点可以从主线程增加打印语句观察到:

int main(){
	thread t1(funci);
	thread t2(funcj);
	while(true){
		cout<<flag[i]<<" "<<flag[j]<<endl;//增加打印语句,观察flag[i]和flag[j]的值
	}
	t1.join();
	t2.join();
	return 0;
}

运行结果

image-20220328183829573

中间打印了一个6是因为i线程最后一次执行时没有执行完毕就挂起了,后来继续执行打印了一个6然后就傻眼了,i线程发现flag[j]一直为true,同时j线程也发现flag[i]一直为true

主函数打印的一堆1 1也证明了这一点

peterson算法

在双标志后检验法的基础上,考虑如何消除过度谦让的问题

注意到检查的方式是while(flag[j]);,while(flag[i]);

如果在两个flag都是1时,怎么打破这种僵局?

可以引入第三个标志

image-20220328184758764

如图,i在进入区首先修改自己的访问标识,然后修改turn=j意思是等我这次执行完后才可能轮到j,

然后判断j是否在临界区并且是不是j排在我后面执行

如果turn==j不成立即turn=i,说明在我修改turn之后进入while判断之前,j线程修改turn了,导致我竟然要排在j之后执行

i生气也没有用,因为最后修改的turn才算有效

于是过度谦让就成了后来吃香

如此程序就可以正常运行了

image-20220328185401705
  C++知识库 最新文章
【C++】友元、嵌套类、异常、RTTI、类型转换
通讯录的思路与实现（C语言)
C++PrimerPlus 第七章 函数-C++的编程模块（
Problem C: 算法9-9~9-12：平衡二叉树的基本
MSVC C++ UTF-8编程
C++进阶 多态原理
简单string类c++实现
我的年度总结
【C语言】以深厚地基筑伟岸高楼-基础篇（六
c语言常见错误合集
上一篇文章      下一篇文章      查看所有文章
加:2022-03-30 18:05:26  更:2022-03-30 18:08:10 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/24 2:53:16-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码