《算法竞赛入门经典》(第二版) 第 6 章例题 6-1。
题目描述
英文描述
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.
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
题目全文·中文翻译
在单处理器系统上并发执行的程序看起来像是同时执行的，但实际上单个 CPU 在多个程序之间交替执行，在切换到下一个程序之前，每个程序执行一定数量的指令。你需要模拟最多十个程序在这种系统上的并发执行，并确定它们将产生的输出。
当前正在执行的程序称为“运行中”，而所有等待执行的程序称为“就绪”。一个程序由不超过 25 条语句的序列组成，每行一条语句，最后以一个结束语句结尾。可用的语句列在下面。
一个变量是任何单个的小写字母字符，常量是小于 100 的无符号十进制数。系统中只有 26 个变量(按：也就是 26 个英文字母)，并且这些变量在所有程序中共享。因此，一个程序中对变量的赋值会影响其他程序可能打印的值。所有变量初始值均为零。
每条语句的执行都需要一个整数量的时间单位。运行中的程序被允许在一个称为“时间片”的时间段内继续执行指令。当程序的时间片耗尽时，将选择另一个就绪程序来运行。当时间片到期时，正在执行的指令会被允许完成。
程序按照先进先出的顺序排队执行，就绪队列的初始顺序与输入文件中的程序顺序相对应。然而，由于锁（lock）和解锁（unlock）语句的执行，这一顺序可能发生变化。
当一个程序希望对其操作的变量进行互斥访问时，会使用锁和解锁语句。这些语句总是成对出现，包围一个或多个其他语句。锁语句总是先于解锁语句执行，并且这些语句不会嵌套。一旦程序成功执行锁语句，其他程序在锁定程序运行并执行相应的解锁语句之前，无法成功执行锁语句。如果一个正在运行的程序在已有锁生效时尝试执行锁语句，该程序将被放置到阻塞队列的末尾。以这种方式被阻塞的程序会失去当前剩余的时间片。当解锁语句执行时，阻塞队列头部的程序会被移到就绪队列的头部。该程序在运行时执行的第一条语句将是之前失败的锁语句。需要注意的是，互斥协议的实施依赖于程序通过正确使用锁和解锁语句来实现。（一个不遵循锁/解锁规则的流氓程序仍然可以随意修改任何变量，尽管其他程序正确使用了锁/解锁语句。）
输入
输入以一行包含单个正整数的行开始，表示接下来要处理的测试用例数量，每个测试用例如以下所述。该行后有一行空行，两个连续输入之间也有一行空行。
输入文件的第一行由七个用空格分隔的整数组成。这些整数按顺序指定：后续程序的数量、五条语句的单位执行时间（按上述顺序）、以及构成时间片的时间单位数。输入的其余部分由程序组成，这些程序根据上述规则正确由语句组成。
所有程序语句都从行的第一列开始。语句中的空格应被忽略。每个程序都有一个与其在输入数据中的位置相关的标识号（第一个程序的 ID = 1，第二个程序的 ID = 2，以此类推）。
输出
对于每个测试用例，输出必须遵循以下描述。两个连续测试用例的输出之间应有一个空行。
你的输出应包含在模拟过程中由 print 语句生成的输出。当 print 语句被执行时，程序应显示程序 ID、一个冒号、一个空格，以及被选变量的值。不同 print 语句的输出应分别显示在不同的行上。
输入样例
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: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21
注意：这里的输入样例是有问题的，修正后如下：
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 表示有接下来有一个 case 需要我们去处理，然后接下来的下一行是空行，这是固定的格式要求，然后，下一行是
13 1 1 1 1 1 1
其中，3 表示接下来有 3 个 program 要并行运行。然后，
- 第一个 1：赋值(Assignment)语句花费的时间。
- 第二个 1：输出(Output)语句花费的时间。
- 第三个 1：锁(lock)语句花费的时间。
- 第四个 1：解锁(unlock)语句花费的时间。
- 第五个 1：结束(end)语句花费的时间。
最后的 1 表示：cpu 会分配的时间片的长短。
关于对题目的理解，有个地方需要注意一下，
当时间片到期时，正在执行的指令会被允许完成。
比如某个语句(指令)执行主要 4 个单位的时间，但是当前被分配的时间片只剩 2 个单位了，没关系，这个语句依旧会被执行。
书中还提出了一个问题：本题不会出现越界错误，为什么？这是因为在执行插入到队首这个动作之前，队首的元素已经被 pop 出来进行处理了，所以队首总是空着一个位置的，这时如果想要插入一个元素到队首，自然不会发生越界的情况。
那么，本题的思路，说起来其实很简单：
- 先把所有的程序按照输入的顺序放入 ready 队列中；
- 然后，逐个从队列中 pop 出程序进行处理。
具体的处理过程如下，
- 如果当前这次时间片用完了，但是程序还没有执行完，那么，记录当前执行到的位置，再将程序放入 ready 队列中；
- 当前运行到了程序结尾，此程序生命周期结束，无需额外操作；
- 如果遇到了 lock 语句，那么，根据当前是否有其他程序上了锁来进行处理；
- 如果已经被上锁，那么，将当前程序放入 block 队列，时间片如果还没用完，那么，也作废了；
- 如果还没有被上锁，那么，进行上锁操作(这里其实就是设置以下 locked 这个全局变量)，然后还是正常执行；
- 如果遇到了 unlock，
- 如果阻塞队列不为空，出队一个元素，然后，入队到 ready 的队首；
- 接下来还是正常运行。
代码分析
代码分析就全部在注释里面了。如果觉得不够清晰，那就再听一听我视频里面的讲解。
主要就三个部分。
全局变量定义
1const int maxlinecnt = 1000; // 最多 1000 行，这是一个大致的数量
2const int linecharcnt = 10; // 每一行的字符串长度不会超过 10(按：这是推断出来的，我们假定程序中没有过多的空格，否则这里就还需要再调整)
3
4deque<int> readyQ; // ready 队列
5queue<int> blockQ; // 存放被阻塞的程序的队列
6int n; // 会参与并行运行的程序的数量
7int quantum; // 时间片长度
8int c[5]; // 每个语句所需的运行时间
9int var[26]; // 最多 26 个变量
10int ip[maxlinecnt]; // ip[pid]是程序pid的当前行号。所有程序都存在prog数组，更类似真实的情况，代码也更短
11bool locked; // 是否已经被锁住
12char prog[maxlinecnt][linecharcnt]; // 存储所有程序的指令，每个程序的每条指令都是一行字符串
主要的模拟函数
1void run(int pid) {
2 int q = quantum;
3 while (q > 0) {
4 char *p = prog[ip[pid]]; // 取出 pid 号程序中当前该运行的那一行
5 switch (p[2]) { // 根据第 3 个字符来判断
6 case '=': // 赋值
7 var[p[0] - 'a'] = isdigit(p[5]) ? (p[4] - '0') * 10 + p[5] - '0' : p[4] - '0';
8 q -= c[0];
9 break;
10 case 'i': // 打印
11 printf("%d: %d\n", pid + 1, var[p[6] - 'a']);
12 q -= c[1];
13 break;
14 case 'c': // lock
15 if (locked) {
16 blockQ.push(pid); // 放入阻塞队列
17 return;
18 }
19 locked = true;
20 q -= c[2];
21 break;
22 case 'l': // unlock
23 locked = false;
24 if (!blockQ.empty()) {
25 int pid2 = blockQ.front();
26 blockQ.pop();
27 readyQ.push_front(pid2);
28 }
29 q -= c[3];
30 break;
31 case 'd': // end
32 return;
33 }
34 ip[pid]++;
35 }
36 readyQ.push_back(pid);
37}
main 函数
主要是做一些数据的读入操作。
1int main() {
2 // 重定向输入数据，省去我们手动输入的繁琐
3 string relativePathToCurrentCFile = "./data/UVa210/input1.txt";
4 // relativePathToCurrentCFile = "./data/UVa210/input3.txt";
5 freopen(string("./ch06" + relativePathToCurrentCFile.substr(1, relativePathToCurrentCFile.size() - 1)).c_str(), "r", stdin);
6
7 int T; // input 数据中 case 的数量
8 scanf("%d", &T);
9 while (T--) { // 分别处理每一个 case
10 scanf("%d %d %d %d %d %d %d\n", &n, &c[0], &c[1], &c[2], &c[3], &c[4], &quantum);
11 memset(var, 0, sizeof(var));
12
13 int line = 0;
14 for (int i = 0; i < n; i++) {
15 fgets(prog[line++], maxlinecnt, stdin); // 按行读取数据
16 ip[i] = line - 1;
17 while (prog[line - 1][2] != 'd')
18 fgets(prog[line++], linecharcnt, stdin);
19 readyQ.push_back(i); // 把 id 为 i 的程序入队
20 }
21
22 locked = false; // 初始值为 false
23 while (!readyQ.empty()) {
24 int pid = readyQ.front();
25 readyQ.pop_front();
26 run(pid);
27 }
28 if (T)
29 printf("\n");
30 }
31 return 0;
32}