[UVA]UVA – 210 Concurrency Simulator – 并发模拟器

题目地址:

https://cn.vjudge.net/problem/UVA-210

紫书 P139

题目描述:

(谷歌翻译)

Background
背景

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.
在单处理器系统上并发执行的程序似乎同时执行,但是实际上,单个CPU在程序之间交替执行一些数量的指令每个程序切换到下一个。 您将模拟最多十个并发执行在这种系统上的程序,并确定它们将产生的输出。

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.
当前正在执行的程序正在运行,而所有正在执行的程序据说已经准备就绪。 程序由不超过25个语句的序列组成,每行一个,后跟一个结束语句。 以下列出的可用语句如下。

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 characterand 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.
变量是任何单个小写字母字符,常数是小于100的无符号十进制数。计算机系统中只有26个变量,它们在程序之间共享。 因此,一个程序中变量的赋值会影响不同程序可能打印的值。 所有变量最初设置为零。

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.
只要程序希望声明对其正在操作的变量的互斥访问权限,就会使用lock和unlock语句。 这些语句总是成对出现,包含一个或多个其他语句。 一个锁将永远在一个解锁之前,这些语句永远不会嵌套。

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.
一旦程序成功执行锁定语句,在锁定程序运行并执行相应的unlock语句之前,没有其他程序可能会成功执行锁定语句。 如果正在运行的程序尝试在一个已经生效的时候执行锁定,则该程序将被放置在阻塞队列的末尾。 以这种方式阻止的程序会损失他们目前的剩余时间。

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.)
当执行解锁时,阻塞队列的头部的任何程序被移动到就绪队列的头部。 该程序运行时执行的第一个语句将是先前失败的lock语句。 请注意,所涉及的程序取决于通过正确使用锁定和解锁语句来执行互斥协议。 (没有锁/解锁对的叛逃程序可能会改变任何想要的变量,尽管正确使用其他程序的锁定/解锁。)

The 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.).
所有程序语句从一行的第一列开始。 一个语句中出现的空格应该被忽略。 与每个程序相关联的是基于其在输入数据中的位置的识别号(第一程序具有ID = 1,第二个ID为2等)。

The 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.
您的输出将包含print语句在模拟期间发生的输出。 执行打印语句时,程序应显示程序ID,冒号,空格和所选变量的值。 单独的打印语句的输出应该出现在单独的行上。

Sample Input
输入示例

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: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21


我的分析

对我来说,本题的难点主要是在题目的理解、lock和unlock的操作、题目中“程序语句”的读取和配额使用的条件。首先本题不能只做一组用例,本题中The Input部分,第一句话有说要先写用例数,然后再进行操作。然而,后面的Sample Input并没有开头表示用例数的1。我已补全。而由于英文水平不够或是对长篇英文阅读能力不足,从用例中读取的信息可能会漏掉这个点。

关于lock和unlock,在我模拟出上锁和解锁后的操作后,我想当然地认为解锁一定要从阻塞队列中取程序,然而有时候阻塞队列为空,会出现读取失败。所以在解锁时务必确认阻塞队列是否有程序。

程序语句的读取,我的做法是先看是不是赋值语句,也就是命令字符串中的下标2所指的值是否为’=’,然后如果不是的话,再根据首字母为‘p’,’l’,’u’,’e’进行区分。

配额使用的条件,我的理解是,如果当前语句所需要的时间大于配额所剩时间,则不执行。然而题目中加粗的那句话的意思是,只要有,你就尽管做。这也是后面焦头烂额的时候查看别人博客才知道的。(来源于http://www.cnblogs.com/lighter-blog/p/6091019.html

最后还有一点,就是本题中的变量是公用的,然而,不同case切换的过程中,所有的东西都要进行初始化,所以变量数组也要全部赋值为0。这是我在本题中踩的最后一个坑。

题外话,uDebug真是个好东西。

代码