洛谷-UVA210 并行程序模拟 Concurrency Simulator

ゞ浴缸里的玫瑰 2023-06-12 11:30 46阅读 0赞

[PDF][]

![format_png][]

## 输入格式 ##

![format_png 1][]

## 输出格式 ##

![format_png 2][]

## 题意翻译 ##

你的任务是模拟nn个程序（按输入顺序编号11~nn）的并行执行。每个程序包含不超过25条语句。

格式一共是5种：赋值（var=constantvar=constant），打印（print varvar），locklock，unlockunlock，endend，耗时分别为t\_1,t\_2,t\_3,t\_4,t\_5t1,t2,t3,t4,t5。

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

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

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

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

现在给出n,t\_1,t\_2,t\_3,t\_4,t\_5,Qn,t1,t2,t3,t4,t5,Q以及nn个程序，你需要输出所有printprint命令执行输出的值。

## 输入输出样例 ##

**输入 \#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

**输出 \#1**复制

1: 3
    2: 3
    3: 17
    3: 9
    1: 9
    1: 9
    2: 8
    2: 8
    3: 21
    3: 21

#include<bits/stdc++.h>
    using namespace std;
    const int maxNum=1005;
    
    int n; //进程个数 
    int times[5];//表示5个指令所花的时间
    int quantum;//时间片大小 
    vector<string> prg[maxNum]; //并行程序个数,指令 
    deque<int> readyQ;//就绪队列 
    queue<int> blockQ;// 阻塞队列 
    bool locked=false;//锁
    int val[26];//26个变量
    int p[maxNum];//进程运行在指令的位置 
    
    
    void run(int i){
    	int t=quantum;	
    	while(t>0){
    		string cur; //指令
    		cur=prg[i][p[i]];
    			
    		//赋值语句 
    		switch(cur[2]){
    			case '=' : {
    				t=t-times[0];
    				int num;
    				if(cur.size()==6){
    					num=cur[4]*10-'0'+cur[5]-'0';
    				}else{
    					num=cur[4]-'0';
    				}
    				val[cur[0]-'a']=num-'0'; //赋值 
    				break;
    			}
    			case 'i':{//打印
    				t=t-times[1];
    				cout<<i+1<<": "<<val[cur[6]-'a']; 
    				break;
    			}
    			case 'c':{
    				t=t-times[2];
    				if(locked==false){//未锁 
    					blockQ.push(i);
    					return; //结束此指令 
    				}else{
    					locked=true;//上锁 
    				}
    				break;
    			}
    			case 'l':{
    				t=t-times[3];
    				locked=false;//解锁
    				if(!blockQ.empty()){
    					int u=blockQ.front();
    					blockQ.pop();
    					readyQ.push_front(u);
    				} 
    				break;
    			}
    			case 'd':{
    				//不用写：t=t-times[4];
    				break;
    			}	
    		} 
    		p[i]++;//获取下一条指令 
    	}
    }
    int main(){
    	int n; 
    	cin>>n;//T组用例
    	
    	for(int i=0;i<5;i++){
    		cin>>times[i]; //每个指令所花时间 
    	}
    	
    	cin>>quantum;//时间片 
    	
    	
    	//读入n组指令集合 
    	for(int i=0;i<n;i++){
    		string s;
    		while(s!="end"){
    			cin>>s;
    			prg[i].push_back(s);
    		}
    		readyQ.push_back(i);//加入就绪队列			
    	}
    	
    	
    	//执行 程序 
    	while(!readyQ.empty()){
    		int pid=readyQ.front();// 获取就绪队列最前面的进程编号
    		readyQ.pop_front();
    		run(pid); 
    	} 
    	 
    	 return 0;
    }

[PDF]: https://uva.onlinejudge.org/external/2/p210.pdf
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTIxMC80N2E4ZWJiY2VlMmUyNTBjMDBiYzZhMzA3ZmRkNWJjOTM2ODQwOTI4LnBuZw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTIxMC8yM2U4YWE5YjE4NDIzZjU2ZTQzYmMwZGIzOGVmZWVhZmUyNWQyZTA1LnBuZw?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubHVvZ3UuY29tLmNuL3VwbG9hZC92anVkZ2VfcGljL1VWQTIxMC9kMThlYjI5NDk2M2UxY2FmM2VmNTViMTQyYzQyYzMyN2E2ZDFjNDNlLnBuZw?x-oss-process=image/format,png