【UVA No. 210】 并发模拟器 Concurrency Simulator

【UVA No. 210】 并发模拟器 Concurrency Simulator

洛谷题目地址

【题意】

模拟n个程序（按输入顺序编号1～n ）的并行执行。每个程序都包含不超过25条语句。语句格式共有5种：赋
值（var=constant）、打印（print var）、锁（lock）、解锁（unlock）、结束（end），耗时分别为t1 、t2 、t3 、t4 、t5 。

将变量用一个小写字母表示，初始时值为0，为所有并行程序共有，且它的值始终保持在[0,100)，所以一个程序对某一个变量的赋值会影响另一个程序。

在每个时刻只能有一个程序处于运行状态，其他程序处于等待状态。处于运行状态的程序每次最多分配Q 个单位时间，一旦在未执行完程序时超过分配时间，则这个程序会被放入就绪队列，然后从其队首取出一个程序继续执行。而初始的就绪队列按照程序输入顺序。

但是由于lock和unlock命令的出现，这个顺序会被改变。

lock的作用是申请对所有变量的独占访问，unlock则是解除对所有变量的独占访问，且它们一定成对出现。当一个程序已经对所有的变量独占访问后，其他程序若试图执行lock，则无论其是否耗尽分配时间，都会被放在一个阻止队列的尾部，且当解锁的时候，会将阻止队列头部的程序放入就绪队列的头部。

【输入输出】

输入：

第1行为测试用例数T ，第2行为空行，第3行包含7个数，分别为n 、t 1 、t 2 、t 3 、t 4 、t 5 和Q ，接下来有n 个程序。

输出：

对于每个测试用例，两个测试用例的输出都将用一个空行隔开，输出包含print语句在模拟过程中生成的输出。执行print语句时，程序应该显示程序ID、冒号、空格和所选变量的值。

不同print语句的输出应该在单独的行上。

【样例】

【思路分析】

使用两个队列进行实现：就绪队列和阻止队列。

解锁时，会将阻止队列头部的程序放入就绪队列的头部，因此就绪队列需要使用双端队列（支持两端进出操作）。每个程序都被存储在一个vector中，因此使用vector数组。

【算法设计】

1. 读入T ，表示T 个测试用例。
2. 读入7个整数，包括程序数、5条指令执行时间及时间周期。
3. 将程序分别读入数组prg[]。
4. 将程序序号加入就绪队列，初始化阻止队列。
5. 变量均为小写字母a～z，转换为数字下标0～25，因此变量数组val[26]初始化为0，当前运行程序的位置数组p[maxNum]也初始化为0，锁初始化为locked=false。
6. 如果就绪队列非空，则队头元素pid出队，执行pid程序。
7. 获取当前指令，即第pid个程序的第p[pid]单元，cur=prg[pid][p[pid]]，执行该指令，然后p[pid]++，指向第1个程序的下一条指令。如果时间周期未用完，则继续执行该程序的下一条指令，直到时间周期耗尽。时间周期已用完时，将pid号程序加入就绪队列的队尾。
8. 如果cur=“lock”，且locked为true，则将pid号程序加入阻止队列，p[pid]不加1。
9. 如果cur=“unlock”，则locked=false，解锁，当阻止队列不为空时，将阻止队列的队头加入就绪队列的队头。
10. 如果是赋值、打印、结束，则执行相应的指令。

【完美图解】

① 以输入样例为例

有一个测试用例，包含3个程序，5条指令的执行时间都为1，时间周期为1。

② 将3个程序分别读入prg[]

③ 将程序的序号加入就绪队列

④ 将变量数组val[26]和当前运行程序的位置数组p[maxNum]初始化为0，锁初始化为locked=false。

⑤ 如果就绪队列非空，则队头元素pid = 1 出队，执行第1个程序。

⑥ 获取当前指令，第1个程序的第p[1]（p[1]=0）单元，当前运行指令为cur=“a = 4”，注意“a = 4”中的“=”号前后都有空格。val[0]=4，p[1]++，此时p[1]=1，指向第1个程序的下一条指令。如果时间周期未用完，则继续执行该程序的下一条指令，直到时间周期耗尽。时间周期已用完，将1号程序加入就绪队列的队尾。

⑦ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

⑧ 获取当前指令，第2个程序的第p[2]（p[2]=0）单元，当前运行指令为cur=“a=3”。val[0]=3，p[2]++，此时p[2]=1，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

⑨ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

⑩ 获取当前指令，第3个程序的第p[3]（p[3]=0）单元，当前运行指令为cur=“b = 5”。val[1]=5，p[3]++，此时p[3]=1，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

⑪ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

⑫ 获取当前指令，第1个程序的第p[1]（p[1]=1）单元，当前运行指令为cur=“print a”，该指令是第1个程序中的输出，val[0]=3，因此输出1:3，p[1]++，此时p[1]=2，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾。

⑬ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

⑭ 获取当前指令，第2个程序的第p[2]（p[2]=1）单元，当前运行指令为cur=“print a”，该指令是第2个程序中的输出，val[0]=3，因此输出2: 3，p[2]++，此时p[2]=2，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

⑮ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

⑯ 获取当前指令，第3个程序的第p[3]（p[3]=1）单元，当前运行指令为cur=“a=17”。val[0]=17，p[3]++，此时p[3]=2，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

⑰ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

⑱ 获取当前指令，第1个程序的第p[1]（p[1]=2）单元，当前运行指令为cur=“lock”，locked=true，p[1]++，此时p[1]=3，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾。

⑲ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

⑳ 获取当前指令，第2个程序的第p[2]（p[2]=2）单元，当前运行指令为cur=“lock”，因为locked为true，所以将2号程序加入阻止队列，p[2]不加1。

㉑ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

㉒ 获取当前指令，第3个程序的第p[3]（p[3]=2）单元，当前运行指令为cur=“print a”，该指令是第3个程序中的输出，val[0]=17，因此输出3:17。p[3]++，此时p[3]=3，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

㉓ 如果就绪队列非空，则队头元素pid=1，出队，执行第1个程序。

㉔ 获取当前指令，第1个程序的第p[1]（p[1]=3）单元，当前运行指令为cur=“b=9”，令val[1]=9，p[1]++，此时p[1]=4，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾

㉕ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

㉖ 获取当前指令，第3个程序的第p[3]（p[3]=3）单元，当前运行指令为cur=“print b”，该指令是第3个程序中的输出，val[1]=9，因此输出3:9。p[3]++，此时p[3]=4，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

㉗ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

㉘ 获取当前指令，第1个程序的第p[1]（p[1]=4）单元，当前运行指令为cur=“print b”，该指令是第1个程序中的输出，val[1]=9，因此输出1:9。p[1]++，此时p[1]=5，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾。

㉙ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

㉚ 获取当前指令，第3个程序的第p[3]（p[3]=4）单元，当前运行指令为cur=“lock”，因为locked为true，所以将3号程序加入阻止队列，p[3]不加1。

㉛ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

㉜ 获取当前指令，第1个程序的第p[1]（p[1]=5）单元，当前运行指令为cur=“unlock”。令locked=false；当阻止队列不为空时，将阻止队列的队头加入就绪队列的队头。p[1]++，此时p[1]=6，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾。

㉝ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序

㉞ 获取当前指令，第2个程序的第p[2]（p[2]=2）单元，当前运行指令为cur=“lock”，locked=true，p[2]++，此时p[2]=3，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

㉟ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

㊱ 获取当前指令，第1个程序的第p[1]（p[1]=6）单元，当前运行指令为cur=“print b”，该指令是第1个程序中的输出，val[1]=9，因此输出1: 9。p[1]++，此时p[1]=7，指向第1个程序的下一条指令。时间周期已用完，将1号程序加入就绪队列的队尾。

㊲ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

㊳ 获取当前指令，第2个程序的第p[2]（p[2]=3）单元，当前运行指令为cur=“b=8”，令val[1]=8。p[2]++，此时p[2]=4，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

㊴ 如果就绪队列非空，则队头元素pid=1出队，执行第1个程序。

㊵ 获取当前指令，第1个程序的第p[1]（p[1]=7）单元，当前运行指令为cur=“end”，第1个程序处理完毕。

㊶ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

㊷ 获取当前指令，第2个程序的第p[2]（p[2]=4）单元，当前运行指令为cur=“print b”，该指令是第2个程序中的输出，val[1]=8，因此输出2: 8。p[2]++，此时p[2]=5，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

㊸ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

㊹ 获取当前指令，第2个程序的第p[2]（p[2]=5）单元，当前运行指令为cur=“unlock”，令locked=false；当阻止队列不为空时，将阻止队列的第1个加入就绪队列队首。p[2]++，此时p[2]=6，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

㊺ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

㊻ 获取当前指令，第3个程序的第p[3]（p[3]=4）单元，当前运行指令为cur=“lock”，locked=true，p[3]++，此时p[3]=5，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

㊼ 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

㊽ 获取当前指令，第2个程序的第p[2]（p[2]=6）单元，当前运行指令为cur=“print b”，该指令是第2个程序中的输出，val[1]=8，因此输出2:8。p[2]++，此时p[2]=7，指向第1个程序的下一条指令。时间周期已用完，将2号程序加入就绪队列的队尾。

㊾ 如果就绪队列非空，则队头元素pid=3出队，执行第3个程序。

㊿ 获取当前指令，第3个程序的第p[3]（p[3]=5）单元，当前运行指令为cur=“b=21”，令val[1]=21，p[3]++，此时p[3]=6，指向第1个程序的下一条指令。时间周期已用完，将3号程序加入就绪队列的队尾。

51 如果就绪队列非空，则队头元素pid=2出队，执行第2个程序。

52 获取当前指令，第2个程序的第p[2]（p[2]=7）单元，当前运行指令为cur=“end”，第2个程序处理完毕。

53 队列中只剩下第3个程序，一直执行完毕即可。又执行两个“print b”，val[1]=21，因此输出两个3:21。

【算法实现】

#include
#include
#include
#include
#include
#include
#include

using namespace std;
const int maxNum=1005;

int n;//n个进程
int times[5];//表示5个指令所花的时间
int quantum;//周期时间
int val[26];//26个变量
int p[maxNum];//进程运行在指令的位置
vector<string>prg[maxNum];//指令
deque<int>readyQ;//就绪队列
queue<int>blockQ;//阻塞队列
bool locked;//锁
string s;

void run(int i){//执行指令
    int t=quantum,v;//周期时间
    while(t>0){
        
		string cur;
       
	    cur=prg[i][p[i]];//获取指令
        switch(cur[2]){
            case '=':{//举例 a=58,常量为正整数，且小于100
                t-=times[0];
				v=cur[4]-'0';
				if(cur.size()==6)
					v=v*10+cur[5]-'0';//两位数 
				val[cur[0]-'a']=v;
                break;
            }
            case 'i':{//举例 print a
                t-=times[1];
                cout<<i<<": "<<val[cur[6]-'a']<<endl;
                break;
            }
            case 'c':{
                t-=times[2];
                if(locked){//lock，则将进程加入阻塞队列
                    blockQ.push(i);
                    return;
                }
                else//上锁
                	locked=true;
                break;
            }
            case 'l':{ //举例 unlock
        		t-=times[3];
                locked=false; // 解锁
                //当阻塞队列不为空，则将阻塞队列的第一个加入到就绪队列的第一个
                if(!blockQ.empty()){
                    int u=blockQ.front();
                    blockQ.pop();
                    readyQ.push_front(u);//加入队头 
                }
                break;
            }
            case 'd':{//end
                
				return;
            }
        }
        
		p[i]++;//时间没用完，进入该进程的下一条指令
    }
    
	readyQ.push_back(i);//时间用完了，将该进程加入到执行队列最后
}

int main(){
    
	int T;//T组用例
    cin>>T;
    
	while(T--){
        cin>>n;
		for(int i=0;i<5;i++)
			cin>>times[i];
		cin>>quantum;//时间周期 
        memset(val,0,sizeof(val));
        for(int i=1;i<=n;i++){
            prg[i].clear();
            while(getline(cin,s)){
                prg[i].push_back(s);
                if(prg[i].back()=="end")
					break;
            }
            readyQ.push_back(i);//加入就绪队列 
        }
        
		memset(p,0,sizeof(p));
        memset(val,0,sizeof(val));
       
	    locked=false;
        while(!readyQ.empty()){
            int pid=readyQ.front();//获取就绪队列最前面的进程编号
            readyQ.pop_front();
            run(pid);//执行指令
        }
        if(T)
        	cout<<endl;
    }
    
	return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113

判不了，跑一下测试用例