当前位置:网站首页>(the first set of course design) 1-4 message passing interface (100 points) (simulation: thread)
(the first set of course design) 1-4 message passing interface (100 points) (simulation: thread)
2022-07-06 12:33:00 【Vigorous waist Nuo dance】
subject
1-4 Messaging interface (100 branch )
The teacher gave it T Share MPI Sample code for , Each code implements n Process communication . These processes are labeled from 0 To n − 1, Each process will execute its own send and receive instructions in sequence , Such as :“S x”,“R x”.“S x” To express to x Send data to process No ,“R x” From x No. process receives data . Each pair of send / receive commands must be executed to take effect , Otherwise “ Deadlock ”. for instance ,x Process No. 1 executes the send command first “S y”,y No. process must . Must be . Execute the transfer command “R x”, This pair of commands were successfully executed . otherwise x No. process will be waiting y No. process executes the corresponding receive command . conversely , if y Process No. 1 executes the receive command first “R x”, Will wait x No. process executes the send command “S y”, if x No. process has not executed the send command “S y”, be y No. process will be waiting x No. process executes the corresponding send command . The mismatching of the above sending and receiving commands will cause the whole program to appear “ Deadlock ”. in addition ,x No. process will not execute “S x” or “R x”, That is, they will not send or receive messages from their own processes .. Now the teacher asks you to judge whether each sample code will appear “ Deadlock ” The situation of . Each process has at least 1 strip , At most 8 strip , These instructions are executed sequentially , That is, the execution of Article 1 is completed , To implement Article 2 , Go to the last one .
Input format :
Reading data from standard input . Enter two positive integers on the first line T, n, Express T Sample code , Realized n Process communication . Next there is T × n That's ok , There are several in each line (1 − 8 individual ) character string , There is a space between the adjacent , Indicates the receiving and sending instructions of the corresponding process . There are no illegal instructions . For the first 2 + i, 0 ≤ i ≤ (T × n − 1) That's ok , It means the first one i ÷ n( merchant ) Of the code i KQ/ n( remainder ) Send and receive instructions for process No . ( such as ,“S1” To express to 1 Send message to process No ,“R1” From 1 Message received by process No . Please refer to the example for details .)
Output format :
Output to standard output . The output, T That's ok , One number per line , Indicates whether the corresponding sample code appears “ Deadlock ” The situation of .1 Indicates deadlock ,0 It means no dead lock .
sample input :
3 2
R1 S1
S0 R0
R1 S1
R0 S0
R1 R1 R1 R1 S1 S1 S1 S1
S0 S0 S0 S0 R0 R0 R0 R0
sample output :
0
1
0
author
Jingrong
Company
Yanshan University
Code length limit
16 KB
The time limit
400 ms
Memory limit
64 MB
Ideas
Simulation question
Refer to others' ideas
Because it involves the deletion and addition of a thread
use list Delete is more efficient
Code
// There are no illegal instructions
//x No. process will not execute S x
// Sequential execution
// At least one instruction Up to eight
// Input format i KQ/ n( remainder ) Number
using namespace std;
#include<unordered_set>
#include<bits/stdc++.h>
int main() {
int t, n;
cin >> t >> n;
getchar();
for (int z = 0; z < t; z++) {
//t Copy code
unordered_set<int>waiting;// Waiting for the
list < pair<queue<int>, int>>pool;// Thread pool
for (int i = 0; i < n; i++) {
//n Threads
pool.push_back({
queue<int>(),INT_MAX });// Make room for new threads
string temp;// A whole line of instructions
getline(cin, temp);// Each thread corresponds to a string of instructions
// Split instruction
// When there is only one instruction , Finally, there are no spaces
for (int j = 0,c; j < temp.size(); j = c + 1) {
c = temp.find(" ", j);
if (c== string::npos) {
c = temp.size();
}
if (temp[j] == 'S') {
// send out
pool.back().first.push(i*10000+stoi(string(temp.begin() + j + 1, temp.begin() + c)));// The scope may
}
else {
// Accept
pool.back().first.push(-i - 10000*stoi(string(temp.begin() + j + 1, temp.begin() + c)));// The scope may be wrong
}
}
}
bool flag = true;
while (flag && !pool.empty()) {
// There are still
for (auto i = pool.begin(); i != pool.end(); i++) {
// There is at least one match in a trip , Otherwise, it will be locked
if (waiting.find(i->second) != waiting.end()) {
// The process is blocking , next
continue;
}// Pay attention to the first two if The order of
else if ((i->first).empty()) {
// The process has no instructions to continue
i->second = 0;
continue;
}
else {
while (!(i->first).empty()) {
// The instruction is not empty , Just out of the team , Until no match is found or the instruction is gone
int getout =( i->first).front();
(i->first).pop();
if (waiting.find(-getout) != waiting.end()) {
// Find a match
waiting.erase(-getout);
flag = false;
}
else {
i->second = getout;
waiting.insert(getout);
break;
}
}
}
}
if (flag == true)break;
else flag = true;
}
bool pass = true;
if (waiting.empty()) {
for (auto i = pool.begin(); i != pool.end(); i++) {
if (i->second != 0) {
pass = false;
break;
}
}
}
else pass = false;
if (pass)cout << "0" << endl;
else cout << "1" << endl;
}
return 0;
}
边栏推荐
- HCIP Day 12
- PT OSC deadlock analysis
- Arduino gets the length of the array
- Flink late data processing (3)
- (3) Introduction to bioinformatics of R language - function, data Frame, simple DNA reading and analysis
- [offer29] sorted circular linked list
- 基于Redis的分布式锁 以及 超详细的改进思路
- MySQL占用内存过大解决方案
- 单片机蓝牙无线烧录
- (5) Introduction to R language bioinformatics -- ORF and sequence analysis
猜你喜欢
Conditional probability
History object
Expected value (EV)
Redis cache update strategy, cache penetration, avalanche, breakdown problems
[Clickhouse kernel principle graphic explanation] about the collaborative work of partitioning, indexing, marking and compressed data
AMBA、AHB、APB、AXI的理解
idea中好用的快捷键
Custom view puzzle getcolor r.color The color obtained by colorprimary is incorrect
MySQL takes up too much memory solution
js 变量作用域和函数的学习笔记
随机推荐
. elf . map . list . Hex file
Important methods of array and string
Esp8266 connects to bafayun (TCP maker cloud) through Arduino IED
(课设第一套)1-4 消息传递接口 (100 分)(模拟:线程)
Amba, ahb, APB, Axi Understanding
Basic operations of databases and tables ----- classification of data
[offer29] sorted circular linked list
History object
Unity3D摄像机,键盘控制前后左右上下移动,鼠标控制旋转、放缩
Esp8266 connects to onenet cloud platform (mqtt) through Arduino IDE
Imgcat usage experience
.elf .map .list .hex文件
HCIP Day 12
gcc 编译选项
Latex learning
记一次云服务器被密码爆破的经历——关小黑屋、改密码、改端口
Intermediate use tutorial of postman [environment variables, test scripts, assertions, interface documents, etc.]
Common DOS commands
CUDA C programming authoritative guide Grossman Chapter 4 global memory
ES6 grammar summary -- Part 2 (advanced part es6~es11)