解題區/解題區 - UVa

UVa 210 - Concurrency Simulator

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

模擬 CPU 排程，並且每種指令的所需時間都不同。一個程式可以使用 quantum 的時間，最多負一次執行某個指令 (quantum > 0 變成 quantum <= 0 的情況)。而當 unlock 只將一個程式從 block queue 吐出，而非所有程序。

保證每一個程序都會有一對 lock/unlock。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

Sample Output

1
2
3
4
5
6
7
8
9
10
1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21

Solution

作業系統排程 lock & unlock 模擬，去年某一天心血來潮寫，卻狂 WA。現在回過頭才發現對 quantum 的使用錯誤，在有限時間內，即使在有剩餘時間下，執行下一條單位操作，直到沒有剩餘時間，我卻用加法限制於 quantum 下，導致炸掉。

題目中 “When an unlock is executed, any program at the head of the blocked queue is moved to the head of the ready queue”，為什麼只有一個 blocked queue 元素彈出，雖然在效率考量上是這樣，誤看成全部彈出，怪不得會一直 WA。但這樣所有模擬都會完結？ 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <assert.h>
#include <string.h>
#include <list>
#include <sstream>
using namespace std;
#define MAXN 1024
#define MAXM 32
#define MAXVAR 26
struct Memory {
    char s[MAXM][MAXM];
    int counter;
    void read() {
        int n = 0;
        while (gets(s[n])) {
            if (s[n][0] == 'e' && s[n][1] == 'n' && s[n][2] == 'd')
                return;
            n++;
        }
    }
} mem[MAXN];
int N, unitTime[5], quantum, locked, var[MAXVAR];
deque<int> readyQ, blockQ;
vector<string> decode(string s) {
    vector<string> ret;
    stringstream sin(s);
    while (sin >> s)
        ret.push_back(s);
    return ret;
}
int toInt(string s) {
    int ret;
    stringstream sin(s);
    sin >> ret;
    return ret;
}
void execute(int pid) {
    int q = quantum;
    while (q > 0) {
        vector<string> args = decode(mem[pid].s[mem[pid].counter]);
        if (args[0].length() == 1) {
            var[args[0][0] - 'a'] = toInt(args[2]);
            q -= unitTime[0];
        } else if (args[0] == "print") {
            printf("%d: %d\n", pid+1, var[args[1][0] - 'a']);
            q -= unitTime[1];
        } else if (args[0] == "lock") {
            if (locked) {
                blockQ.push_back(pid);
                return;
            }
            locked = 1;
            q -= unitTime[2];
        } else if (args[0] == "unlock") {
            locked = 0;
            if (!blockQ.empty()) {
                readyQ.push_front(blockQ.front());
                blockQ.pop_front();
            }
            q -= unitTime[3];
        } else if (args[0] == "end") {
            return ;
        }
        mem[pid].counter++;
    }
    readyQ.push_back(pid);
}
void run(int N) {
    for (int i = 0; i < N; i++)
        readyQ.push_back(i), mem[i].counter = 0;
    for (int i = 0; i < MAXVAR; i++)
        var[i] = 0;
    locked = 0;
    int pid;
    while (!readyQ.empty()) {
        pid = readyQ.front(), readyQ.pop_front();
        execute(pid);
    }
}
int main() {
    int testcase;
    scanf("%d", &testcase);
    while (testcase--) {
        scanf("%d", &N);
        for (int i = 0; i < 5; i++)
            scanf("%d", &unitTime[i]);
        scanf("%d", &quantum);
        while (getchar() != '\n');
        for (int i = 0; i < N; i++)
            mem[i].read();
        
        run(N);
        
        if (testcase)
            puts("");
    }
    return 0;
}
/*
 */