CIS 307: Guidelines for the solution of Homework 4
We have four processes - HMW_MAIN, RAND_PROC1, RAND_PROC2, and
STORE_MANAGER. HMW_MAIN first creates the pipes C_BOX, RAND_BOX1,
and RAND_BOX2 and then spawns the three child processes RAND_PROC1,
RAND_PROC2 and STORE_MANAGER.
STORE_MANAGER maintains a table of
ordered pairs in STORE, and processes serially requests for read and
update operations on STORE from RAND_PROC1 and RAND_PROC2 received
through C_BOX, placing the responses in RAND_BOX1 and RAND_BOX2
respectively. HMW_MAIN interacts with the child processes to make
available statistical information about RAND_PROC1 or RAND_PROC2, and
to terminate all processes according to the user's choice.
The child processes inherit the descriptors for the pipes from
HMW_MAIN. RAND_PROC1 and RAND_PROC2 execute identical algorithms
but use different seeds for the random number generator. Given this
set up, the program may be organized into three files - hmw_main.c,
rand_proc.c and store_manager.c (additional header files may be used to
group together data structures and operations needed in each process).
Each child process operates in a copy of the address space of the parent process
HMW_MAIN as it begins execution. It closes all pipe descriptors except
those that it needs in order to interact with the other child process(es)
and invokes one of the exec functions to execute the appropriate program
for the child process. Thus STORE_MANAGER would invoke, for example,
execlp("store_manager",arg1,arg2,arg3,NULL)
where
- arg1: character string representations of C_BOX[0],
- arg2: character string representations of RAND_BOX1[1],
- arg3: character string representations of RAND_BOX2[1]
are the arguments to be passed to the program in store_manager.c.
The file store_manager contains the executable code for store_manager.c.
Likewise RAND_PROC1 and RAND_PROC2 would invoke
execlp("rand_proc",arg1,arg2,arg3,arg4,NULL)
where
- arg1: the character string representations
of the identifier for the process (e.g., 1 for RAND_PROC1 and 2 for
RAND_PROC2),
- arg2: seed for the random number generator,
- arg3: the pipe descriptor
to read from (RAND_BOX1[0] for RAND_PROC1 and RAND_BOX2[0] for
RAND_PROC2),
- arg4: the pipe descriptor to write into (C_BOX[1] for both
processes)
are the arguments to the program in rand_proc.c.
The programs (or the function main() to be more precise) in
store_manager.c and rand_proc.c would accept the arguments from
execlp() and convert them into the respective integer values.
STORE_MANAGER maintains a table of pairs (SSTORE_ID, SSTORE_ELEM)
in STORE, where SSTORE_ID and SSTORE_ELEM are character strings.
In order to simplify the transmission of messages through the pipes
we will define SSTORE_ID and SSTORE_ELEM to be fixed-length strings.
For uniformity we shall use the following definitions :
const
STRING_LENGTH = 20;
SSTORE_SIZE = 10;
type
STRING_TYPE = array [1..STRING_LENGTH] of char;
SSTORE_ENTRY_TYPE = record
SSTORE_ID : STRING_TYPE;
SSTORE_ELEM : STRING_TYPE;
end;
SSTORE_TYPE = array [1..SSTORE_SIZE] of SSTORE_ENTRY_TYPE;
var
STORE : SSTORE_TYPE;
Since STORE is maintained by STORE_MANAGER and RAND_PROC1 and RAND_PROC2
are not supposed to access it directly, these declarations should be
local to STORE_MANAGER.
STORE_MANAGER initializes STORE before it starts processing requests for
read and update operations from RAND_PROC1 and RAND_PROC2. It assigns to
the SSTORE_ID component of each element of STORE a unique value that is
never modified by subsequent (read or update) operations. The values
chosen are fixed-length strings (of STRING_LENGTH characters) and may
represent internet host addresses such as "jedi.cis.temple.edu"
(padded with enough spaces at the end to make up a total of STRING_LENGTH
characters). This set of values should be made available to RAND_PROC1
and RAND_PROC2 (for example, through a header file specifying these values
that is attached to rand_proc.c and store_manager.c through #include
directives) to enable them to generate read and update requests that
can be satisfied. The SSTORE_ELEM component of each element of STORE
is assigned the same value - a fixed length string of 0's, consisting
of STRING_LENGTH 0's.
As stated above, STORE_MANAGER initializes STORE before it starts
accepting requests for read and update operations. The SSTORE_ID
component of each element is assigned a fixed value, and all the
SSTORE_ELEM components are initialized with a fixed-length string of
0's.
Read and update operations requested by RAND_PROC1 and RAND_PROC2
specify a value for the SSTORE_ID component (through the parameter WHO
in the functions SSTORE_READ() and SSTORE_UPDATE()). If an entry with
that value for the SSTORE_ID component is found in STORE, the operation is
performed on the entry, otherwise a response indicating failure is
generated. RAND_PROC1 and RAND_PROC2 select values for the parameter
WHO randomly from a list maintained in each process. This list
contains ALL values held in the SSTORE_ID components in STORE, and also an
additional value that is not present in STORE. Thus the list contains
SSTORE_SIZE + 1 values, and the value not contained in STORE is
selected, on the average, once every (SSTORE_SIZE + 1) trials, causing
the operations requested by the process to fail at the above rate.
Update operations specify (through the parameter WHAT) a value to be
assigned to the SSTORE_ELEM component of a specified entry in STORE,
obliterating the value currently held in it. We will stipulate that
RAND_PROC1 would ALWAYS use a string of 1's (of length STRING_LENGTH)
and RAND_PROC2, a string of 2's (also of length STRING_LENGTH), for the
parameter WHAT when requesting an update operation. Recall that the
SSTORE_ELEM component of each element of STORE is initialized with a
string of 0's by STORE_MANAGER. Thus the SSTORE_ELEM component of an
entry in STORE can hold one of three values - a string of 0's
indicating that the entry was never updated from the time it was
initialized, a string of 1's indicating that the entry was updated last
by RAND_PROC1, and a string of 2's indicating that the entry was
updated last by RAND_PROC2. This makes it easier to ascertain whether
the read operations returned the values last written into the entries
in STORE by scanning the log generated by RAND_PROC1 and RAND_PROC2.
Correctness requires that STORE_MANAGER serialize the read and update
operations and thus maintain the consistency of STORE.
RAND_PROC1 and RAND_PROC2 write into the file LOG.DAT the responses
received from STORE_MANAGER to their requests for read and update
operations. Since the log file is our primary source of information in
determining whether operations on STORE are performed consistently, we
must ensure that all the relevant information about each request and
the corresponding response are written to the log file. Each entry
in the log file should identify the writer (RAND_PROC1 or RAND_PROC2),
the operation requested (read or update), the parameters of the
operation, the status returned for the operation by STORE_MANAGER, and
a timestamp. Each entry may be written on a separate line for clarity.
The following are examples of the suggested format :
1 R jedi.cis.temple.edu 00000000000000000000 OK < timestamp >
2 U jedi.cis.temple.edu 22222222222222222222 OK < timestamp >
2 U yoda.cis.temple.edu 22222222222222222222 OK < timestamp >
1 R yoda.cis.temple.edu 22222222222222222222 OK < timestamp >
1 U none.cis.temple.edu 11111111111111111111 ERR < timestamp >
2 R none.cis.temple.edu -------------------- ERR < timestamp >
The last two operations fail because "none.cis.temple.edu" is not
a valid SSTORE_ID value in STORE.
STORE_MANAGER retrieves messages one at a time from C_BOX, carries out
on STORE the operation requested in the message, and places the response
in the pipe designated for the originator of the message. Since the
update operation requires one more operand than the read operation, a
message requesting an update operation would be longer than one asking
for a read operation. However, Unix pipes are byte-oriented and treat
data passing through them as raw streams of characters, oblivious to
any kind of structure it may be organized into. Thus STORE_MANAGER
would be able to retrieve the exact number of bytes making up a
message through a SINGLE read on C_BOX only if it could predict in
advance the type of operation on STORE (read or update) that would be
specified in the message. Since these operations are chosen at random by
RAND_PROC1 and RAND_PROC2, STORE_MANAGER would not be be able to
anticipate them, and would have to adopt an elaborate procedure to
retrieve one message at a time from C_BOX. We may simplify matters by
arranging to use messages of the same length (incurring some loss in
effective bandwidth) while requesting both read and update operations.
A message specifying a read operation is padded at the end with enough
spaces to make it as long as one asking for an update operation before
being written into C_BOX, and STORE_MANAGER ignores the dummy characters
while parsing the message. This makes for a simpler design,
accompanied, however, by a slight reduction in communication bandwidth.
The above discussion applies to messages exchanged through RAND_BOX1
and RAND_BOX2 as well. Response messages for all cases except that of
an invalid read operation have the same length, but the latter requires
fewer characters. All cases may, however, be handled in a uniform
manner by getting STORE_MANAGER to put in some padding in the messages
containing the response to invalid read operations.
The parent process HMW_MAIN, after creating the child processes,
prompts the user repeatedly to ask whether he wants statistical
information from either RAND_PROC1 or RAND_PROC2, or to have all
processes terminated.
If statistical information is requested, HMW_MAIN sends the signal
SIGUSR1, a signal with user defined semantics, to the appropriate
process, which in turn catches the signal and displays on the screen
the number of read and update operations it has completed. The response
from RAND_PROC1, for example, would look like
RAND_PROC 1 : Number of Reads = 8. Number of Updates = 6.
Since the signal catcher is not allowed to take any user defined
arguments, the variables recording the number of read and update
operations completed should be made global to it. When the process
returns from the signal catching function, it resumes its normal
operation, going back to where it was before being interrupted by the
signal.
If the user indicates that he would like all processes terminated,
HMW_MAIN sends SIGTERM signals to all three child processes, and waits
for each child to terminate, invoking one of the wait functions as many
times as necessary. Each child process informs the user of the
receipt the SIGTERM signal, and terminates itself invoking exit().
HMW_MAIN confirms the termination of a child process each time it
returns from the wait function, and finally invokes exit() to terminate
itself. Here is an example of screen output resulting from the user's
choice of terminating all processes :
RAND_PROC2 : Terminating in response to SIGTERM signal.
STORE_MANAGER : Terminating in response to SIGTERM signal.
HMW_MAIN : RAND_PROC2 terminated.
RAND_PROC1 : Terminating in response to SIGTERM sigal.
HMW_MAIN : STORE_MANAGER terminated.
HMW_MAIN : RAND_PROC1 terminated.
HMW_MAIN : Terminating after all child processes.
ingargiola@cis.temple.edu
amandala@astro.ocis.temple.edu