?? prob_c.html
字號:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1991 ACM Finals, Problem C - Concurrency Simulator</TITLE>
<!SGML "ISO 8879:1986">
<LINK HREF="mailto:karree46@sol.acs.uwosh.edu" REV=made>
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H2>
<I>1991 ACM Scholastic Programming Contest Finals</I></H2></CENTER>
<CENTER>
<H4>
<I>sponsored by AT&T Computer Systems</I></H4></CENTER>
<CENTER>
<H2>
Problem C<BR>
Concurrency Simulator</H2></CENTER>
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.
<P>The program that is currently being executed is said to be <I>running</I>,
while all programs awaiting execution are said to be <I>ready</I>. 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.
<PRE><B>Statement Type</B> <B>Syntax
</B>-------------- ------
Assignment <I>variable</I> = <I>constant</I>
Output <B>print</B> <I>variable
</I>Begin Mutual Exclusion <B>lock
</B>End Mutual Exclusion <B>unlock
</B>Stop Execution <B>end</B></PRE>
A <I>variable</I> is any single lowercase alphabetic character and a <I>constant</I>
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.
<P>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 <I>quantum</I>. 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.
<P>Programs are queued first-in-first-out for execution in a <I>ready queue</I>.
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 <B>lock</B> and <B>unlock</B> statements.
<P>The <B>lock</B> and <B>unlock</B> 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 <B>lock</B> will always precede an <B>unlock</B>, and these statements
will never be nested. Once a program successfully executes a <B>lock</B>
statement, no other program may successfully execute a <B>lock</B> statement
until the locking program runs and executes the corresponding <B>unlock</B>
statement. Should a running program attempt to execute a <B>lock</B> while
one is already in effect, this program will be placed at the end of the
<I>blocked queue</I>. Programs blocked in this fashion lose any of their
current time quantum remaining. When an <B>unlock</B> 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 <B>lock</B> statement that previously failed. Note that it is up
to the programs involved to enforce the mutual exclusion protocol through
correct usage of <B>lock</B> and <B>unlock</B> statements. (A renegade
program with no <B>lock</B>/<B>unlock</B> pair could alter any variables
it wished, despite the proper use of <B>lock</B>/<B>unlock</B> by the other
programs.)
<H3>
Input and Output</H3>
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.
<P>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.).
<P>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. A sample input and correct output are shown below.
<H3>
Sample Input</H3>
<PRE>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</PRE>
<H3>
Sample Output</H3>
<PRE>1: 3
2: 3
3: 17
3: 9
1: 9
1: 9
2: 8
2: 8
3: 21
3: 21</PRE>
<HR NOSHADE>
</BODY>
</HTML>
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -