并行程序模拟
《算法竞赛入门经典》刘汝佳 6-1 并行程序模拟 P139
题目：
在单处理器系统上同时执行的程序看起来是同时执行的，但实际上，单个CPU在程序之间交替，在切换到下一个程序之前从每个程序执行一些指令。您将在这样的系统上模拟最多十个程序的并发执行，并确定它们将产生的输出。
当前正在执行的程序被称为运行，而所有等待执行的程序都被称为已准备好。一个程序由一个不超过25个语句的序列组成，每行一个，后面一个结束语句。下面列出的语句如下所示。
Statement Type Syntax
Assignment variable = constant
Output print variable
Begin Mutual Exclusion lock
End Mutual Exclusion unlock
Stop Execution end
变量是任何一个小写字母字符，常数是一个小于100的无符号十进制数。在计算机系统中只有26个变量，并且它们在程序之间共享。因此，对一个程序中的变量赋值会影响由不同程序打印的值。最初将所有变量设置为零。
每个语句都需要一个整数的时间单位来执行。允许运行程序继续执行一段时间的指令，称之为量子。当程序的时间量子到期时，将选择另一个就绪程序来运行。当时间量子期满时，当前执行的任何指令都将被允许完成。
程序先排好队列，以便在就绪队列中执行。就绪队列的初始顺序对应于输入文件中程序的原始顺序。但是，由于执行锁定和解锁语句，该顺序可能会改变。
每当程序希望声明对其正在操作的变量的互斥访问时，就使用锁和解锁语句。这些语句总是成对出现，包围一个或多个其他语句。一个锁总是在解锁之前，这些语句永远不会嵌套。一个程序成功执行锁语句，除非锁程序运行并执行相应的解锁语句，否则没有其他程序可以成功执行锁语句。如果一个正在运行的程序试图在锁已经生效时执行锁，那么这个程序将被放置在阻塞队列的末尾。以这种方式被阻塞的程序失去它们当前的剩余量子余量。当执行解锁时，阻塞队列头上的任何程序都被移动到就绪队列的头部。该程序运行时的第一个语句将是以前失败的锁语句。请注意，通过正确使用锁和解锁语句来执行互斥协议取决于所涉及的程序。（一个没有锁/解锁对的叛变程序可以改变它希望的任何变量，尽管其他程序正确使用锁/解。
Input
输入以一行上的单个正整数开头，该行本身指示由空白行跟随的情况的数目，并且两个连续输入之间还有空白行。
输入文件的第一行由七个由空间分隔的整数组成。这些整数指定（按顺序）：随后的程序的数量、五个语句中的每个语句的单位执行时间（按上面给出的顺序）以及包含时间量的时间单位的数量。输入的其余部分由程序组成，这些程序是根据上述规则由语句正确形成的。
所有的程序语句都从一行的第一列开始。在语句中出现的空白应该被忽略。根据每个程序在输入数据中的位置（第一个程序具有ID=1，第二个程序具有ID=2等），关联每个程序是一个标识号。
Output
对于每个测试用例，输出必须遵循下面的描述。两个连续情况的输出将被空白线分隔。
输出将包含打印报表生成的输出，因为它们在模拟过程中发生。在执行打印语句时，程序应该显示程序ID、冒号、空格和所选变量的值。分开的打印语句的输出应该出现在不同的行上。
样本输入和正确输出如下所示。
Sample Input
1
3 1 1 1 1 1 1
a = 4 print a
lock
b = 9
print b
unlock
print b
end
a = 3
print a
lock
b = 8
print b
unlock
print b
end
b = 5
a = 17
print a
print b
lock
b = 21
print b
unlock
print b
end
Sample Output
1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21
注：
英文版的题目见https://blog.csdn.net/leo6033/article/details/80639945
如果没有了解一点进程的知识，这道题目还是别看了。我上了操作系统，这道题目看半天。
上面的链接也有程序答案，我改变了一点。我提取变量和对应大小的时候，采用了映射map。
至于其他地方，看懂题目应该没啥难度。
代码：
#include<iostream>
#include<queue>
#include<string>
#include<vector>
#include<cstring>//memset()函数
#include<map>//匹配变量和对应的值
using namespace std;
deque<int> qr;
queue<int> qw;
const int maxn=1005;
int t[5];//记录每条指令的时间
int T;//记录时间片
vector<string> prog[maxn];//记录程序内容
int p[maxn];//用来记录第i个程序执行位置
map<string,string> vars;
bool lock=false;
void run(int i)
{
int rt=T;
string s;
string var,cons;//表示变量和常量
while(rt>0)
{
s=prog[i][p[i]];
if(s[2]=='=')
{
rt=rt-t[0];
var=s[0];//默认变量名为char
cons=s.substr(4);
vars[var]=cons;
}
else if(s[2]=='i')
{
rt=rt-t[1];
var=s.substr(6);
cout<<i<<":"<<vars[var]<<endl;
}
else if(s[2]=='c')
{
rt=rt-t[2];
if(lock)
{
qw.push(i);
return ;
}
else
lock=true;
}
else if(s[2]=='l')
{
rt=rt-t[3];
lock=false;
if(!qw.empty())
{
qr.push_front(qw.front());
qw.pop();
}
}
else
return;
p[i]++;
}
}
int main()
{
int cas;
string s;
cin>>cas;
while(cas--)
{
int i,n;//n个程序并行
cin>>n;
for(i=0;i<5;i++)//输入每条指令执行的时间
{ //'=' 'print' 'lock' 'ulock' 'end'顺序
cin>>t[i];
}
cin>>T; //输入时间片
for(i=1;i<=n;i++)
{
prog[i].clear();//由于是在外部申请的，每次需要清空
while(getline(cin,s))
{
if(s=="")
continue;//防止输入空行
prog[i].push_back(s);
if(s=="end")
break;
}
qr.push_back(i);
}
memset(p,0,sizeof(p));
while(!qr.empty())
{
int cur=qr.front();
qr.pop_front();
run(cur);
qr.push_back(cur);
}
if(cas)
cout<<endl;
}
}
参考文章：
双端队列：http://www.cplusplus.com/reference/deque/deque/?kw=deque
上一篇： 机器学习的回归评价指标
下一篇： torch.nn、(二)