首页 > 代码库 > 210 - Concurrency Simulator(WF1991, deque, 模拟）
210 - Concurrency Simulator(WF1991, deque, 模拟）
题目有点长，理解题花了不少时间
粘下别人的翻译~
你的任务是模拟n个程序（按输入顺序编号为1~n）的并行执行。每个程序包含不超过25条语句，格式一共有5种：
var=constant（赋值）；
print var（打印）；
lock；
unlock；
end。
变量用单个小写字母表示，初始值为0，为所有程序公有（因此在一个程序里对某个变量赋值可能会影响到另一个程序）。常数是小于100的非负整数。
每个时刻只能有一个程序处于运行态，其他程序均处于等待。上述五种语句分别需要t1、t2、t3、t4、t5单位时间。运行态的程序每次最多运行Q个单位时间（成为配额）。当一个程序的配额用完之后，把当前语句（如果存在）执行完之后该程序会被插入一个等待队列中，然后处理器从队首取出一个程序继续执行。初 始等待队列包含按输入顺序排列的各个程序，但由于lock和unlock语句的出现，这个序列可能会改变。
lock的作用是申请对所有变量的独占访问。lock和unlock总是成对出现，并且不会嵌套。lock总是在unlock的前面。当一个程序成功执行完lock指令后，其他程序一旦试图执行lock指令，就会马上被放到一个所谓的阻止队列的尾部（没有用完的配额就浪费了），当unlock指令执行完毕后，阻止队列的第一个程序进入等待队列的首部。
输入n、t1、t2、t3、t4、t5Q以及n个程序，按照时间顺序输出所有print语句的程序编号和结果。
附代码如下：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstdlib> 4 #include<queue> 5 #include<cstring> 6 #include<deque> 7 using namespace std; 8 const int maxn = 1000; 9 int n, t1, t2, t3, t4, t5, Q; 10 char pro[maxn][10]; 11 int ID[maxn]; 12 int var[30]; 13 bool locked; 14 deque<int> ReadyQ; 15 deque<int> BlockQ; 16 17 void Run(int id) 18 { 19 int q = Q; 20 while(q > 0) 21 { 22 char *ins = pro[ID[id]]; 23 switch(ins[2]) 24 { 25 case ‘=‘://var = constant; 26 { 27 /*通过数组var进行各变量值的记录*/ 28 int buf = 0; 29 for(int i = 4; i < strlen(ins)-1; i++) 30 buf = buf*10+(ins[i]-‘0‘); 31 var[ins[0]-‘a‘] = buf; 32 q -= t1; 33 break; 34 } 35 case ‘i‘://print var; 36 { 37 printf("%d: %d\n", id+1, var[ins[6]-‘a‘]); 38 q -= t2; 39 break; 40 } 41 case ‘c‘://lock 42 { 43 /*Once a program successfully executes a lock statement, no other program may successfully execute a lock statement 44 until the locking program runs and executes the corresponding unlock statement. 45 Should a running program attempt to execute a lock while one is already in effect, 46 this program will be placed at the end of the blocked queue.*/ 47 if(locked) 48 { 49 BlockQ.push_back(id); 50 return; 51 } 52 locked = true; 53 q -= t3; 54 break; 55 } 56 case ‘l‘://unlock; 57 { 58 locked = false; 59 /*When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue. */ 60 if(!BlockQ.empty()) 61 { 62 ReadyQ.push_front(BlockQ.front()); 63 BlockQ.pop_front(); 64 } 65 q -= t4; 66 break; 67 } 68 case ‘d‘://end; 69 { 70 q -= t5; 71 return; 72 break; 73 } 74 }//switch; 75 ID[id]++; 76 }//while; 77 /*When a program time quantum expires, another ready program will be selected to run. 78 Any instruction currently being executed when the time quantum expires will be allowed to complete. */ 79 ReadyQ.push_back(id); 80 }//Run; 81 82 83 int main() 84 { 85 int T; 86 scanf("%d", &T); 87 for(int cases = 0; cases < T; cases++) 88 { 89 memset(var, 0, sizeof(var)); 90 if(cases) printf("\n"); 91 scanf("%d%d%d%d%d%d%d", &n, &t1, &t2, &t3, &t4, &t5, &Q); 92 int line = 0; 93 for(int i = 0; i < n; i++) 94 { 95 ///注意记录多行字符串方法 96 ///================================================ 97 fgets(pro[line++], maxn, stdin); 98 ID[i] = line-1; ///line可记录某ID开始到最后的操作； 99 /*identification number based upon its location in the input data.100 (the first program has ID = 1, the second has ID = 2, etc.)*/101 while(pro[line-1][2] != ‘d‘)102 fgets(pro[line++], maxn, stdin);103 /*Programs are queued first-in-first-out for execution in a ready queue.104 The initial order of the ready queue corresponds to the original order of the programs in the input file.*/105 ///================================================106 ReadyQ.push_back(i);107 }108 locked = false;109 while(!ReadyQ.empty())110 {111 int Pro_id = ReadyQ.front();112 ReadyQ.pop_front();113 Run(Pro_id);114 }115 }116 return 0;117 }
210 - Concurrency Simulator(WF1991, deque, 模拟）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。