三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> (Google面试题)有四个线程1、2、3、4同步写入数据……C++11实现 -> 正文阅读
 

[C++](Google面试题)有四个线程1、2、3、4同步写入数据……C++11实现

(Google面试题)有四个线程1、2、3、4同步写入数据……C++11实现 最近在学习多线程,题目源自 MoreWindows先生的 《秒杀多线程第一篇》(http://blog.csdn.net/morewindows/article/details/7392749)
题目摘录:
第五题(Google面试题)
有四个线程1、2、3、4。线程1的功能就是输出1,线程2的功能就是输出2,以此类推.........现在有四个文件ABCD。初始都为空。现要让四个文件呈如下格式:
A:1 2 3 4 1 2....
B:2 3 4 1 2 3....
C:3 4 1 2 3 4....
D:4 1 2 3 4 1....
请设计程序。
代码实现如下:

 1 #include <iostream>
 2 #include <string>
 3 #include <thread>
 4 #include "Semaphore.h"
 5 
 6 constexpr unsigned MAX_COUNT = 10;
 7 constexpr unsigned MAX_THREAD = 4;
 8 
 9 unsigned getNext(unsigned current, bool order) {
10     if (order) {
11         unsigned next = current + 1;
12         return  next % MAX_THREAD; // //正序
13     } else {
14         unsigned next = current - 1;
15         return next % MAX_THREAD; //反序
16     }
17 }
18 
19 class File
20 {
21 public:
22     File(const std::string& name = "0") 
23     :m_name(name)
24     ,m_buffer(MAX_COUNT, '0')
25     ,m_pos(0){
26         
27     }
28 
29     void write(char c) {
30         m_buffer.at(m_pos++) = c;
31     }
32 
33     std::string getName() const {
34         return m_name;
35     }
36     std::string getData() const {
37         return m_buffer;
38     }
39 private:
40     std::string m_name;
41     std::string m_buffer;
42     size_t m_pos;
43 };
44 
45 Semaphore t1(1), t2(1), t3(1), t4(1);
46 Semaphore* semaphoreArray[MAX_THREAD] = { &t1, &t2, &t3, &t4 };
47 File files[MAX_THREAD] = { File("A"), File("B"), File("C"), File("D") };
48 unsigned currentFile[MAX_THREAD] = { 0, 1, 2, 3 }; //每个线程当前应该写入的文件id
49 
50 void write(unsigned threadId) {
51     const char c = '1' + threadId;
52     auto& fid = currentFile[threadId];
53     //auto fid = threadId;
54     auto nextThreadId = getNext(threadId, true); //正序
55     unsigned count = 0;
56     while (MAX_COUNT != count) {
57         semaphoreArray[threadId]->wait();
58         //写文件        
59         files[fid].write(c);
60         //将文件传递给下一个线程。
61         semaphoreArray[nextThreadId]->signal();
62         //更新要写入的文件id
63         fid = getNext(fid, false); //逆序
64         ++count;
65     }
66 }
67 
68 
69 int main() {
70     std::cout << "hello" << std::endl;
71 
72     //create thread
73     std::thread threads[MAX_THREAD];
74     for (unsigned i = 0; i != MAX_THREAD; ++i) {
75         threads[i] = std::thread(write, i);
76     }
77 
78     //join
79     for (auto& thread : threads) {
80         thread.join();
81     }
82 
83     //output
84     for (const auto& file: files) {
85         std::cout << file.getName() << ": " << file.getData() << std::endl;
86     }
87 
88     std::cout << "bye" << std::endl;
89     return 0;
90 }

其中Semaphore.h的代码见:http://www.cnblogs.com/waterfall/p/7966116.html
运行结果截图:

代码解析: 简单分析:
本问题也可以认为是生产者与消费者。只不过线程既生产又消费。按文件的角度,比如A文件的内容为1 2 3 4 1…… 相当于每个线程生产完之后交个下一个线程。
所以对于每一个线程,设置好其初始文件,调用自身信号量的wait()进行生产,生产完毕则调用下一个线程的signal()。将完成的文件交给下一个线程,形成流水作业。
啰里八嗦:
首先,本代码用File类模拟文件写入,方便打印调试。void File::write(char c) 方法即在文件结尾追加字符c。
根据题目要求可以看出,当文件(比如文件A)被线程1写入结束后,需要被下一个线程即线程2写入。因此会有A: 1 2 3 4 1...  B,C,D文件同理,只不过初始写入线程不同。
在代码中利用 :

unsigned currentFile[MAX_THREAD] = { 0, 1, 2, 3 }; //每个线程当前应该写入的文件id

指定每个线程初始写入哪个文件。如果不想配置也可以用threadId作为线程初始写入的文件id(write函数中被注释掉的那一句),他们刚好相等。
代码中用信号量表示线程可执行写入的次数。write函数会在写入完一个文件后,自动计算下一个要写入的文件。顺序为A,D,C,B,A....,逆序。

Semaphore t1(1), t2(1), t3(1), t4(1); //用于设置信号量
Semaphore* semaphoreArray[MAX_THREAD] = { &t1, &t2, &t3, &t4 }; //放入数组只是为了方便调用

如果只是给线程1的信号量设为1,其他都设为0。线程的运行状况可以看作:
step1: 线程1 信号量1 A->D     线程2 信号量0 B 阻塞    线程3 信号量0 C 阻塞  线程4 信号量0 D 阻塞
step2: 线程1 信号量0 D  阻塞  线程2 信号量1 B->A      线程3 信号量0 C 阻塞  线程4 信号量0 D 阻塞
step3: 线程1 信号量0 D  阻塞  线程2 信号量0 A 阻塞    线程3 信号量1 C->B    线程4 信号量0 D 阻塞
step4: 线程1 信号量0 D  阻塞  线程2 信号量0 A 阻塞    线程3 信号量0 B 阻塞  线程4 信号量1 D->C
第一轮运行结束:线程1在文件A中写入了1,线程2在文件B中写入了2,线程3在文件C中写入了3,线程4在文件D中写入了4。
之后第二轮开始:线程1在文件D中写入了1,线程2在文件A中写入了2……
以此类推,相当于同一时间只有1个线程在工作。每当线程工作时,将字符写入自己当前要写入的文件中,并计算出下一个要写入的文件。
这种情况显然是不会出现冲突的。
如果将线程1的初始信号量置为2:
step1: 线程1 信号量2 A->D  线程2 信号量0 B 阻塞  线程3 信号量0 C 阻塞  线程4 信号量0 D 阻塞
step2: 线程1 信号量1 D->C  线程1 信号量1 B->A    线程3 信号量0 C 阻塞  线程4 信号量0 D 阻塞
可以看出文件D中被写入了字符1,出现错误。原因在于文件D当前期待被线程4写入,在4写入之前处于未就绪状态。此时被任何其他线程写入都是错误的。
如果假设线程1和线程4的初始信号量各为1,其他为0。且假设线程4先运行
step1.1: 线程1 信号量1 A 就绪     线程2 信号量0 B 阻塞  线程3 信号量0 C 阻塞  线程4 信号量1 D->C
step1.2: 线程1 信号量2 A->D  线程2 信号量0 B 阻塞  线程3 信号量0 C 阻塞  线程4 信号量0 C 阻塞
step2.1: 线程1 信号量1 D->C  线程1 信号量1 B->A    线程3 信号量0 C 阻塞  线程4 信号量0 D 阻塞
文件D先被线程4写入字符4,之后再被线程1写入字符1便符合题目要求了。(D的序列应该为:4 1 2 3 4……)
也就是说,线程1的信号量的增加,是基于前一个线程已经完成文件写入了。此时文件处于就绪状态,可以被下一个线程使用,也即把文件传递给下一个线程。
所以最终的代码中,将每一个线程的初始信号量设置为1。可满足题目要求。哪怕任何线程在执行中出现阻塞(可用sleep模拟),也不影响其他线程运行。
假设在线程1中执行一个长时间的sleep。可能的运行情况如下
step0: 线程1 信号量1 A 就绪     线程2 信号量1 B 就绪  线程3 信号量1 C 就绪  线程4 信号量1 D 就绪
一段时间后……
step1:线程1 信号量4 A 就绪      线程2 信号量0 A 阻塞  线程3 信号量0 A 阻塞  线程4 信号量0 A 阻塞
所有的线程都在等待将数据写入文件A中。但只有线程1先在文件A中写入字符1,之后释放信号,B才能继续写入。之后是C,D。依然没有冲突。文件A也满足1,2,3,4的字符顺序。
其他:
目前网上搜到的很多代码,同一时间只允许一个线程进行文件的写入,或者是通过计数,一轮结束后才进行下一轮写入。本代码真正实现了线程间的并行。只有无文件可写时才会进行等待。
谢谢。
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
二叉搜索树与双向链表
C++的内存泄漏检测【转载】
C++重载流插入运算符和流提取运算符【转】
统计页码数字0~9分别出现了多少次
上一篇文章      下一篇文章      查看所有文章
加:2017-12-06 23:25:23  更:2017-12-06 23:25:25 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年12日历
2017-12-17 17:57:48
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库