洛谷-UVA210 并行程序模拟 Concurrency Simulator-蒲公英云

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

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;
}