CIS 307: Spring 97: Guidelines for the solution of Homework 2
We have four processes - HMW_MAIN, RAND_PROC1, RAND_PROC2, and
STORE_MANAGER. HMW_MAIN first opens the LOG.DAT file,
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 TABLE, and processes serially requests for read and
update operations on TABLE 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 from
HMW_MAIN the descriptors for LOG.DAT and the pipes.
RAND_PROC1 and RAND_PROC2 execute identical algorithms
but use different seeds for the random number generator [use as seeds
their process ids]. 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 the function representing the appropriate
child process with the appropriate file descriptors.
Thus STORE_MANAGER would be invoked as follows:
-
store_manager(C_BOX[0],RAND_BOX1[1],RAND_BOX2[1])
Likewise RAND_PROCi would be invoked as:
-
rand_proc(RAND_BOXi[0],CBOX[1])
The STORE_MANAGER maintains a table of pairs (TABLE_ID, TABLE_ELEM)
in TABLE, where TABLE_ID and TABLE_ELEM are character strings.
In order to simplify the transmission of messages through the pipes
we will define TABLE_ID and TABLE_ELEM to be fixed-length strings.
For uniformity we shall use the following definitions :
const
TABLE_ID_SIZE = ..;
TABLE_ELEM_SIZE = ..;
TABLE_SIZE = ..;
type
STRING_TYPE_ID = array [0..TABLE_ID_SIZE-1] of char;
STRING_TYPE_ELEM = array [0..TABLE_ELEM_SIZE-1] of char;
TABLE_ENTRY_TYPE = record
TABLE_ID : STRING_TYPE_ID;
TABLE_ELEM : STRING_TYPE_ELEM;
end;
TABLE_TYPE = array [0..TABLE_SIZE-1] of TABLE_ENTRY_TYPE;
var
TABLE : TABLE_TYPE;
Since TABLE 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.
NOTE: Since the RAND_PROC processes must generate at random operations
on stocks such as IBM, HONDA, etc. and it is not likely that such names
are generated at random, we suggest that you cheat! Here is how:
Keep in RAND_PROCi a table NAMES with TABLE_SIZE entries, where each entry
is the name of a stock. Then generate at random a number in the range
0 .. TABLE_SIZE+1. If the number j is in 0..TABLE_SIZE-1, then it identifies
the name NAMES[j]. If it is TABLE_SIZE or TABLE_SIZE+1, then it is
an illegal name and the STORE_MANAGER should respond appropriately also
to this illegal request.
STORE_MANAGER initializes TABLE before it starts processing requests for
read and update operations from RAND_PROC1 and RAND_PROC2. It assigns to
the TABLE_ID component of each element of TABLE a unique value that is
never modified by subsequent (read or update) operations. The values
for TABLE_ID and for TABLE_ELEM
are read from the initialization file (say, INIT.DAT).
The set of TABLE_ID values, as seen above, should be made
available to RAND_PROC1
and RAND_PROC2 to store in the NAMES array and
enable them to generate read and update requests.
As stated above, STORE_MANAGER initializes TABLE before it starts
accepting requests for read and update operations.
Correctness requires that STORE_MANAGER serialize the read and update
operations and thus maintain the consistency of TABLE.
RAND_PROC1, RAND_PROC2, and STORE_MANAGER write into the file LOG.DAT
records describing the messages they send and receive.
Since the log file is our primary source of information in
determining whether operations on TABLE 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 have a timestamp and identify the process
recording the message,
the operation requested (read or update), the parameters of the
operation, the status returned for the operation by STORE_MANAGER.
Each entry may be written on a separate line for clarity.
Here is the suggested format of the log file. Field will be separated by
one space:
- Timestamp: [cols 1..19] obtained with getclock and
saved into a timespec structure.
Then written out as two unsigned integers separated by a period [respectively
for the field tv_sec and tv_nsec]. It takes 9+1+9 coluns (i.e. 19).
- Process id: [cols 21..25] the process id of process logging the message.
It takes 5 columns.
- Operation: [cols 27..27] the kind of operation, either R or U. It takes one
column.
- ReturnCode: [cols 29..31] the result of the operation, either "OK "
or "ERR". It takes three columns.
- Who: [cols 33..42] the id of the element being considered. It takes
10 columns.
- What: [cols 44..52] the value being mentioned. It takes 7 columns.
The following is an example of the suggested format with a first row
enumerating the columns.
1234567890123456789012345678901234567890123456789012
855513140.485751000 6859 R OK IBM 16375
STORE_MANAGER retrieves messages one at a time from C_BOX, carries out
on TABLE 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 TABLE (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 directly to the screen, for example, would look like
-
RAND_PROC 1 : Completed Reads = 8; Requested Reads =9; Completed Updates = 6; Requested 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.
Because of our assumption that the operations on TABLE are slow,
the STORE_MANAGER is not easy to write. We need to separate the beginning
of READ/UPDATE operations from their end, and allow other activities to
take place in the interim. Since the completion of the operations occurs
after one or more seconds,
we need to schedule all such completions using an agenda
as we did in our first homework. Only this time we will need to use
a real time clock with the alarm function. The handler for the
completion of the alarm will take care of what needs to be done at completions.
The code in the main portion of the STORE_MANAGER function will
manipulate the data shared with the handler and then re-enable the alarm.
ingargiola@cis.temple.edu
Pradeep Pappachan