UVA 210 Concurrency Simulator(deque,queue,模拟)

曾经终败给现在 2022-06-07 07:53 183阅读 0赞

Programs executed concurrently on a uniprocessor system appear to be executed at the same time, but  
in reality the single CPU alternates between the programs, executing some number of instructions from  
each program before switching to the next. You are to simulate the concurrent execution of up to ten  
programs on such a system and determine the output that they will produce.  
The program that is currently being executed is said to be running, while all programs awaiting  
execution are said to be ready. A program consists of a sequence of no more than 25 statements, one  
per line, followed by an end statement. The statements available are listed below.  
Statement Type Syntax  
Assignment variable = constant  
Output print variable  
Begin Mutual Exclusion lock  
End Mutual Exclusion unlock  
Stop Execution end  
A variable is any single lowercase alphabetic character  
and a constant is an unsigned decimal number  
less than 100. There are only 26 variables in  
the computer system, and they are shared among  
the programs. Thus assignments to a variable  
in one program affect the value that might be  
printed by a different program. All variables are  
initially set to zero.  
Each statement requires an integral number of time units to execute. The running program is  
permitted to continue executing instructions for a period of time called its quantum. When a program’s  
time quantum expires, another ready program will be selected to run. Any instruction currently being  
executed when the time quantum expires will be allowed to complete.  
Programs are queued first-in-first-out for execution in a ready queue. The initial order of the ready  
queue corresponds to the original order of the programs in the input file. This order can change,  
however, as a result of the execution of lock and unlock statements.  
The lock and unlock statements are used whenever a program wishes to claim mutually exclusive  
access to the variables it is manipulating. These statements always occur in pairs, bracketing one or  
more other statements. A lock will always precede an unlock, and these statements will never be  
nested. Once a program successfully executes a lock statement, no other program may successfully  
execute a lock statement until the locking program runs and executes the corresponding unlock  
statement. Should a running program attempt to execute a lock while one is already in effect, this  
program will be placed at the end of the blocked queue. Programs blocked in this fashion lose any of their  
current time quantum remaining. When an unlock is executed, any program at the head of the blocked  
queue is moved to the head of the ready queue. The first statement this program will execute when  
it runs will be the lock statement that previously failed. Note that it is up to the programs involved  
to enforce the mutual exclusion protocol through correct usage of lock and unlock statements. (A  
renegade program with no lock/unlock pair could alter any variables it wished, despite the proper use  
of lock/unlock by the other programs.)

### Input ###

The input begins with a single positive integer on a line by itself indicating the number of the cases  
following, each of them as described below. This line is followed by a blank line, and there is also a  
blank line between two consecutive inputs.  
The first line of the input file consists of seven integers separated by spaces. These integers specify  
(in order): the number of programs which follow, the unit execution times for each of the five statements  
(in the order given above), and the number of time units comprising the time quantum. The remainder  
of the input consists of the programs, which are correctly formed from statements according to the  
rules described above.  
All program statements begin in the first column of a line. Blanks appearing in a statement should  
be ignored. Associated with each program is an identification number based upon its location in the  
input data (the first program has ID = 1, the second has ID = 2, etc.).

### Output ###

For each test case, the output must follow the description below. The outputs of two consecutive cases  
will be separated by a blank line.  
Your output will contain of the output generated by the print statements as they occur during the  
simulation. When a print statement is executed, your program should display the program ID, a colon,  
a space, and the value of the selected variable. Output from separate print statements should appear  
on separate lines.

### Sample Input ###

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

### Sample Output ###

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

3: 21

### 思路： ###

理解题意，输入 n,t1,t2,t3,t4,t5,lim，下面有n个程序，每个程序有若干条操作，以end结束。

t1~t5分别表示赋值、print、lock、unlock、end5种操作所消耗的时间，lim表示任何一个程序每次最多运行lim个时间。

首先处理器处理 执行队列队首（双端队列qr） 程序，当一个程序用完lim时间后，把当前未运行完的程序插入到 等待队列 队尾（队列 qb），继续处理 执行队列qr 队首程序。

执行队列的初始顺序按输入顺序排列，但是由于lock/unlock 操作，顺序可能会改变。

lock操作阻止了处理器继续处理当前程序，并将其插入到 等待队列qb后面（即使浪费掉了剩余的im时间）。

unlock操作把 等待队列的队首程序插入到 执行队列qr 的首部。 lock总在unlock前面，它们成对出现。

所以，这里用到 deque 实现优先处理，模拟题意，逐一求解。

### code： ###

#include <iostream>
    #include <cstdio>
    #include <queue>
    #include <vector>
    #include <cstring>
    
    using namespace std;
    
    const int N = 1005;
    bool lock;
    deque<int> qr;//执行队列
    queue<int> qb;//等待队列
    vector<string> prg[N];
    string s;
    //数组p: 标记每个i程序当前应该执行的操作
    //数组var：储存以26个小写字母作为变量的值，可实现跨程序改变变量的值
    int t[N], p[N], var[26], lim;
    
    void run(int i){
        int rt = lim, v;
        string cur;
        while(rt > 0){//limite时间
            cur = prg[i][p[i]];//执行i程序的第p[i]个操作
            if(cur[2] == '='){// 赋值
                rt -= t[0];//赋值消耗时间
                v = cur[4] - '0';//字符转整型值
                if(cur.size() == 6) v = v * 10 + cur[5] - '0';
                var[cur[0] - 'a'] = v;//对 cur[0] 这个变量赋值
            }
            else if(cur[2] == 'i'){//print
                rt -= t[1];
                printf("%d: %d\n", i, var[cur[6] - 'a']);
            }
            else if(cur[2] == 'c'){//lock
                rt -= t[2];
                if(lock){
                    qb.push(i);//插入等待队列
                    return;
                }
                else lock = true;
            }
            else if(cur[2] == 'l'){//unlock
                lock = false;
                rt -= t[3];
                if(!qb.empty()){
                    v = qb.front();
                    qb.pop();
                    qr.push_front(v);//插入执行队列队头
                }
            }
            else return;  //end
            ++p[i];//执行i程序的下一步操作
        }
        qr.push_back(i);//lim时间用完，把当前i程序插入等待队列末尾
    }
    
    int main()  {
        int cas, n;
        scanf("%d", &cas);
        while(cas--)  {
            scanf("%d", &n);
            for(int i = 0; i < 5; ++i)
                scanf("%d", &t[i]);
            scanf("%d", &lim);
    
            for(int i = 1; i <= n; ++i){
                prg[i].clear();
                while(getline(cin, s)){
                    if(s == "") continue;
                    prg[i].push_back(s);
                    if(prg[i].back() == "end") break;
                }
                qr.push_back(i);
            }
    
            memset(p, 0, sizeof(p));
            memset(var, 0, sizeof(var));
            while(!qr.empty()){//根据等待队列顺序，执行i程序
                int cur = qr.front();
                qr.pop_front();
                run(cur);
            }
            if(cas) puts("");
        }
        return 0;
    }