当前位置:网站首页>(课设第一套)1-4 消息传递接口 (100 分)(模拟:线程)
(课设第一套)1-4 消息传递接口 (100 分)(模拟:线程)
2022-07-06 09:18:00 【劲腰傩舞】
题目
1-4 消息传递接口 (100 分)
老师给了 T 份 MPI 的样例代码,每份代码都实现了 n 个进程通信。这些进程标号从 0 到 n − 1,每个进程会顺序执行自己的收发指令,如:“S x”,“R x”。“S x”表示向x 号进程发送数据,“R x”表示从 x 号进程接收数据。每一对收发命令必须匹配执行才能生效,否则会“死锁”。 举个例子,x 号进程先执行发送命令“S y”,y 号进程必. 须. 执行接送命令“R x”,这一对命令才执行成功。否则 x 号进程会一直等待 y 号进程执行对应的接收命令。反之,若 y 号进程先执行接收命令“R x”,则会一直等待 x 号进程执行发送命令“S y”,若 x号进程一直未执行发送命令“S y”,则 y 号进程会一直等待 x 号进程执行对应的发送命令。上述这样发送接收命令不匹配的情况都会造成整个程序出现“死锁”。另外,x 号进程不会执行“S x”或“R x”,即不会从自己的进程收发消息。.现在老师请你判断每份样例代码是否会出现“死锁”的情况。每个进程的指令最少有 1 条,最多有 8 条,这些指令按顺序执行,即第一条执行完毕,才能执行第二条,依次到最后一条。
输入格式:
从标准输入读入数据。 输入第一行两个正整数 T, n,表示有 T 份样例代码,实现了 n 个进程通信。 接下来有 T × n 行,每行有若干个(1 − 8 个)字符串,相邻之间有一个空格隔开,表示相应进程的收发指令。不存在非法指令。对于第 2 + i, 0 ≤ i ≤ (T × n − 1) 行,表示第 i ÷ n(商)份代码的 i KQ/ n(余数)号进程的收发指令。 (比如,“S1”表示向 1 号进程发送消息,“R1”表示从 1 号进程接收消息。细节请参考样例。)
输出格式:
输出到标准输出。 输出共 T 行,每行一个数字,表示对应样例代码是否出现“死锁”的情况。1 表示死锁,0 表示不死锁。
输入样例:
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
输出样例:
0
1
0
作者
景荣
单位
燕山大学
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
思路
模拟题
参考的别人的思路
因为涉及到某个线程的删除和添加
用list删除效率比较高
代码
//不存在非法指令
//x号进程不会执行S x
//顺序执行
//指令最少一条 最多八条
//输入格式 i KQ/ n(余数)号
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份代码
unordered_set<int>waiting;//等待中
list < pair<queue<int>, int>>pool;//线程池
for (int i = 0; i < n; i++) {
//n个线程
pool.push_back({
queue<int>(),INT_MAX });//为新线程腾地
string temp;//一整行指令
getline(cin, temp);//每个线程对应一串指令
//拆分指令
//只有一个指令的情况下,最终没有空格
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') {
//发送
pool.back().first.push(i*10000+stoi(string(temp.begin() + j + 1, temp.begin() + c)));//范围可能会
}
else {
//接受
pool.back().first.push(-i - 10000*stoi(string(temp.begin() + j + 1, temp.begin() + c)));//范围可能会错
}
}
}
bool flag = true;
while (flag && !pool.empty()) {
//池中还有
for (auto i = pool.begin(); i != pool.end(); i++) {
//一趟至少有一对匹配,否则锁死
if (waiting.find(i->second) != waiting.end()) {
//该进程阻塞,下一个
continue;
}//注意前两次if的顺序
else if ((i->first).empty()) {
//该进程没有可以继续执行的指令
i->second = 0;
continue;
}
else {
while (!(i->first).empty()) {
//指令非空,就出队,直到未找到匹配的或指令没了
int getout =( i->first).front();
(i->first).pop();
if (waiting.find(-getout) != waiting.end()) {
//找到匹配的
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;
}
边栏推荐
- AMBA、AHB、APB、AXI的理解
- Single chip Bluetooth wireless burning
- Whistle+switchyomega configure web proxy
- 1081 rational sum (20 points) points add up to total points
- 基于Redis的分布式锁 以及 超详细的改进思路
- 基於Redis的分布式ID生成器
- About using @controller in gateway
- Redis based distributed ID generator
- 【ESP32学习-2】esp32地址映射
- Time slice polling scheduling of RT thread threads
猜你喜欢
Single chip Bluetooth wireless burning
Pat 1097 duplication on a linked list (25 points)
Types de variables JS et transformations de type communes
CUDA C programming authoritative guide Grossman Chapter 4 global memory
Walk into WPF's drawing Bing Dwen Dwen
基於Redis的分布式ID生成器
JS variable types and common type conversions
VSCode基础配置
ORA-02030: can only select from fixed tables/views
Several declarations about pointers [C language]
随机推荐
Imgcat usage experience
Arduino uno R3 register writing method (1) -- pin level state change
Pytoch temperature prediction
About using @controller in gateway
. elf . map . list . Hex file
Vscode basic configuration
Flink late data processing (3)
关于Gateway中使用@Controller的问题
Arduino gets the length of the array
(四)R语言的数据可视化——矩阵图、柱状图、饼图、散点图与线性回归、带状图
Kconfig Kbuild
[offer18] delete the node of the linked list
CUDA C programming authoritative guide Grossman Chapter 4 global memory
2021.11.10汇编考试
E-commerce data analysis -- salary prediction (linear regression)
Types de variables JS et transformations de type communes
History object
Priority inversion and deadlock
@Autowired 和 @Resource 的区别
map文件粗略分析