UVa 210 Concurrency Simulator

题目分析本题要求模拟单处理器系统中多个程序的并发执行。系统中有最多101010个程序每个程序由不超过252525条语句组成语句类型包括赋值assignment\texttt{assignment}assignment、输出output\texttt{output}output、加锁lock\texttt{lock}lock、解锁unlock\texttt{unlock}unlock和结束end\texttt{end}end。共有262626个共享变量小写字母a到z初始值为000。每个语句执行需要固定的时间单位每个程序被分配一个时间片time quantum\texttt{time quantum}time quantum。程序在时间片内连续执行若时间片用完但当前语句未执行完则该语句会执行完毕后才切换。程序按先进先出FIFO\texttt{FIFO}FIFO顺序在就绪队列中等待执行。关键机制是互斥锁lock\texttt{lock}lock和unlock\texttt{unlock}unlock成对出现不会嵌套。当某个程序成功执行lock\texttt{lock}lock后其他程序尝试执行lock\texttt{lock}lock时会被放入阻塞队列末尾并失去当前剩余的时间片。当执行unlock\texttt{unlock}unlock时阻塞队列头部的程序被移入就绪队列头部之后它将重新执行之前失败的lock\texttt{lock}lock语句。解题思路数据结构设计使用结构体statement表示一条语句包含programId所属程序编号statementType语句类型用常量000到444表示variableName变量名用于赋值和输出variableValue赋值的常量值每个程序是一个dequestatement双端队列便于从头部取出语句执行。就绪队列ready和阻塞队列blocked也都使用deque类型。模拟流程初始化读入测试用例数对每个用例读入程序数、各语句执行时间、时间片大小然后读入每个程序的语句序列。变量存储用数组valueSetted[26]存储262626个变量的值初始全为000。执行模拟从就绪队列头部取出一个程序执行。每个程序在时间片内循环执行语句每次执行扣减相应的时间。遇到lock时检查isLocked标志若已锁定则将当前程序包含剩余语句放入阻塞队列尾部并退出执行否则设置isLocked true并继续。遇到unlock时检查阻塞队列若非空则将阻塞队列头部的程序移入就绪队列头部然后清除isLocked标志。遇到end时程序结束不再放回就绪队列。若时间片用完且程序未结束、未进入阻塞队列则放回就绪队列尾部。输出每次执行输出语句时按格式程序编号: 变量值输出。注意事项程序执行lock\texttt{lock}lock失败时原语句需要保留并放回程序头部使用push_front。unlock\texttt{unlock}unlock时移入就绪队列的应是阻塞队列头部的程序且该程序被移入就绪队列头部而非尾部。两个测试用例之间需输出一个空行。代码实现// Concurrent Simulator// UVa ID: 210// Verdict: Accepted// Submission Date: 2016-01-18// UVa Run Time: 0.395s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 语句类型常量constintASSIGNMENT0;constintOUTPUT1;constintLOCK2;constintUNLOCK3;constintEND4;// 语句结构体structstatement{intprogramId;// 程序 IDintstatementType;// 语句类型charvariableName;// 变量名称intvariableValue;// 变量值仅用于赋值语句};// 每个程序是一个双端队列存储语句序列typedefdequestatementprogram;inttimeNeeded[END1];// 每种语句执行所需时间inttimeQuantum;// 时间片包含的单位时间数boolisLockedfalse;// 当前是否有程序成功执行了 lockintvalueSetted[26];// 存储 26 个变量的值a~z// 模拟程序执行过程voidexecute(dequeprogramready){dequeprogramblocked;// 阻塞队列while(!ready.empty()){program pRunningready.front();// 取出队首程序ready.pop_front();inttimeRemaintimeQuantum;// 当前程序剩余时间片boolintoBlockedQueuefalse;// 是否进入阻塞队列while(timeRemain0){statement sCurrentpRunning.front();// 取出当前要执行的语句pRunning.pop_front();switch(sCurrent.statementType){caseASSIGNMENT:// 赋值语句valueSetted[sCurrent.variableName-a]sCurrent.variableValue;break;caseOUTPUT:// 输出语句coutsCurrent.programId: ;coutvalueSetted[sCurrent.variableName-a]endl;break;caseLOCK:// 加锁语句if(isLocked)// 已有程序锁定当前程序需阻塞{pRunning.push_front(sCurrent);// 保留当前语句blocked.push_back(pRunning);// 加入阻塞队列timeRemain0;// 立即结束时间片intoBlockedQueuetrue;}elseisLockedtrue;// 无锁成功加锁break;caseUNLOCK:// 解锁语句if(!blocked.empty())// 阻塞队列非空{program pNextblocked.front();blocked.pop_front();ready.push_front(pNext);// 移入就绪队列头部}isLockedfalse;// 释放锁break;caseEND:// 程序结束timeRemain0;// 结束时间片不再放回队列break;}// 扣除当前语句执行所需的时间timeRemain-timeNeeded[sCurrent.statementType];}// 若程序未结束且未进入阻塞队列则放回就绪队列尾部if(!pRunning.empty()!intoBlockedQueue)ready.push_back(pRunning);}}// 解析一行语句转换为 statement 结构体statementparseToStatement(string line,intprogramId){statement s;s.programIdprogramId;if(line.find()!line.npos)// 赋值语句{istringstreamiss(line);string blank;s.statementTypeASSIGNMENT;isss.variableNameblanks.variableValue;}elseif(lineend)// 结束语句{s.statementTypeEND;}elseif(linelock)// 加锁语句{s.statementTypeLOCK;}elseif(lineunlock)// 解锁语句{s.statementTypeUNLOCK;}else// 输出语句格式为 print x{s.statementTypeOUTPUT;s.variableNameline[line.length()-1];}returns;}intmain(){cin.tie(0);cin.sync_with_stdio(false);string line;intcases,numbers;boolstartPrintBlankLinefalse;// 读入测试用例数cincases;while(cases--0){// 在两个测试用例输出之间输出空行if(startPrintBlankLine)coutendl;elsestartPrintBlankLinetrue;// 读入空行用例间的空行getline(cin,line);// 读入程序数、各语句执行时间及时间片大小cinnumbers;for(intiASSIGNMENT;iEND;i)cintimeNeeded[i];cintimeQuantum;cin.ignore();// 忽略换行符// 读入每个程序的语句序列intprogramIdnumbers;dequeprogramready;while(numbers--0){dequestatementprogram;while(getline(cin,line),line!end)program.push_back(parseToStatement(line,programId-numbers));program.push_back(parseToStatement(line,programId-numbers));ready.push_back(program);}// 初始化所有变量为 0memset(valueSetted,0,sizeof(valueSetted));// 开始模拟执行execute(ready);}return0;}