%font declarations % \font\normalfont=cmr12 \font\bold=cmbx12 \font\ital=cmsl12 \font\copyrightfont=cmfib8 % \font\headfont=cmcsc10 %used for page headers \font\headnumbfont=cmbx12 %used for numbers in page headers \font\footfont=cmr8 % \font\referencefont=cmti12 %used for book and journal titles in footnotes \font\chaptitlefont=cmss17 % \font\afont=cmr12 % \font\bfont=cmbx12 % \font\cfont=cmbx12 % \font\programfont=cmtt12 % \font\pf=cmtt12 % \font\problemfont=cmbx12 % \font\mathfont=cmmi12 \global\textfont0=\normalfont \global\textfont1=\mathfont \def\uncatcodespecials{\def\do##1{\catcode`##1=12 }\dospecials} \def\setupverbatim{\programfont \def\par{\leavevmode\endgraf} %\catcode`\`=\active \obeylines \uncatcodespecials \obeyspaces } {\obeyspaces\global\let =\ } %\input /users/walker/setup.standard \def\inputprogram#1{ \bigskip \hrule width5.5truein \bigskip \hsize=7.0truein \leftskip=-0.5truein \begingroup\setupverbatim \input #1 \endgroup \leftskip=0.0truein \hsize = 6.5truein \bigskip \hrule width5.5truein \bigskip} % This defines the date. % \def\today{\ifcase\month\or January\or February\or March\or April\or May\or June\or July\or August\or September\or October\or November\or December\fi \space\number\day, \number\year} %\def\today{May 10, 1996} % Program Macros % \newcount\programcounter \programcounter=0 \newcount\firstprogrampage \firstprogrampage=1 %0 = not first page of program %1 = new sample program starts on current page \def\programname {} % Definition of program \def\newprogram#1#2{ % #1 = program/file name % #2 = initial commentary \global\firstprogrampage = 1 \vfill\eject \advance \programcounter by 1 \noindent {\bold Program \number\programcounter: #1} \gdef\programname{#1} \global\firstprogrampage = 0 \noindent #2 {\parskip = 0pt \inputprogram{#1} } } % Definition of code segment \def\newcode#1#2{ % #1 = program/file name % #2 = initial commentary \global\firstprogrampage = 1 \vfill\eject \advance \programcounter by 1 \noindent {\bold Code Segment \number\programcounter: #1} \gdef\programname{#1} \global\firstprogrampage = 0 \noindent #2 {\parskip = 0pt \inputprogram{#1} } } % Annotation Header \def\ann{ \noindent {\ital Annotations for {\programfont \programname}:} } \def\i{\item{$\bullet$}} \def\ii#1{{\parskip = 0pt \itemitem{$\S$} #1 }} % Sample run \def\samplerun#1{ \goodbreak \noindent {\ital Sample Run of {\programfont \programname}:} {\parskip = 0pt \inputprogram {#1} }} %Header Declaration % \headline = {\ifnum\programcounter>0 \ifnum\firstprogrampage=1 \rm Sample Program \number\programcounter: \programname, continued \hfil \else\hfil\fi \else\hfil\fi} % Footer Declaration % \footline = {{\hsize=6.5truein \leftskip = 0pt \rightskip = 0pt \footfont Concurrency in C through Examples \hfil \today \hfil Page \number\pageno}} %---------------------------------------------------------------------------- \parindent = 20pt \parskip = 6pt \normalfont %Define Page Parameters % \raggedbottom \interlinepenalty=1000 \hsize=6.5truein %use 7.0truein for fuller page \vsize=9.5truein \voffset = -0.4truein \ \vfill \centerline {\chaptitlefont An Introduction to Concurrency } \bigskip \centerline {\chaptitlefont in Unix-based [GNU] C} \bigskip \centerline {\chaptitlefont Through Annotated Examples} \bigskip \bigskip \centerline {\bold by} \medskip \centerline {\bold Henry M. Walker} \medskip \centerline {\bold Grinnell College, Grinnell, IA} \vfill \centerline {\rm \copyright 2004 by Henry M. Walker} \noindent {\rm Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice. \noindent Use of all or part of this work for other purposes is prohibited. } %----------------------------------------------------------------------------- \newprogram {fork-1.c} {This program creates a new process and prints some process id's.} \ann \i The commentary for this and subsequent programs assumes a basic knowledge of C's standard libraries, I/O, control structures, procedures, and parameters. \i Process control procedures typically use the {\pf \#include $<$unistd.h$>$} library. On many systems, this also requires the {\pf \#include $<$sys/types.h$>$} library. \i Each process has a process identification number, which has type {\pf pid\underbar{~}t}. \i The {\pf fork} procedure spawns a new process, copying exactly the elements of the current process. The new process is called a {\ital child} process, and the previously existing process is called the {\ital parent}. \ii {That is, the newly created process gets a copy of the parent's data speace, heap, and stack.} \ii {Open file attributes are copied.} \i Both the parent and child continue execution at the point following the call to {\pf fork}. The behavior of the two processes is identical, except for the value returned by {\pf fork}: \ii {{\pf fork} returns the process id of the child to the parent, assuming the {\pf fork} was successful. (If a new process cannot be created, {\pf fork} returns $-1$ to the parent.)} \ii {{\pf fork} returns 0 to the child process.} \i After the {\pf fork} operation, the two processes execute independently. \i Since process operations can fail, sometimes leaving administrative and bookkeeping details behind, programs always should test such calls for errors and provide an appropriate and graceful exit if errors have occured. This is commonly done in two steps: \ii {{\pf perror()} writes an error message on standard error, based on an internal error coding variable -- {\pf errno}.} \ii {{\pf exit(1);} causes the current process to terminate and returns an integer variable ({\pf status}) to the operating system for further inspection. Usually, {\pf exit(0);} indicates no error has occured, while a nonzero value (e.g., {\pf exit(1);}) indicates some error has occurred.} \i Following error checking, the two processes (parent and child) usually go their separate ways. This is accomplished by testing the value of the returned process id. \i Any process may obtain its own process id with the function {\pf getpid()}. Similarly, a process may obtain the process id of its parent with {\pf getppid()}. \samplerun {fork-1.out} This sample run (from the machine {\ital babbage}) compiles and runs the program using the standard gcc compiler. After starting one program, both processes are generated and report their identification numbers. %----------------------------------------------------------------------------- \newprogram {fork-2.c} {Program illustrating interprocess communication using a Unix pipe to read and write. } \goodbreak \ann \i Interprocess communication in Unix may be accomplished at a low level using pipes. A Unix pipe is a circular buffer maintained by the operating system. Typically, one or more processes write data into the buffer; another process reads the data from the pipe. \i While Unix handles the internals of pipe communication, programs communicate through pipes at a slightly more conceptual level. More specifically, the use of pipes involves four main steps \itemitem {1.} An array of two integers is declared. \itemitem {2.} The array is initialized by the {\pf pipe} procedure. With this initialization, the first array element (subscript 0) provides an appropriate file descriptor for reading, while the second array element (subscript 1) provides an appropriate file descriptor for writing. \itemitem {3.} After the {\pf fork()} operation, both the reading and writing ends of the pipe are available to both processes. Traditionally, however, pipes are available for one-way communication only. Thus, the reading end of the pipe should be closed off in the writing process, and the writing end of the pipe should be closed off in the reading process. \itemitem {4.} Data are moved byte-by-byte through a pipe, using {\pf read} and {\pf write} system calls. \i The {\pf write} call requires three parameters, the output file number, a base address (e.g., a character string or an array of characters), and the number of characters to be written. \i The {\pf read} call requires three parameters, the input file number, a base address (e.g., a character string), and a number of bytes. Reading retrieves the next number of byes -- up to the size of the buffer. \samplerun {fork-2.out} When the program is compiled and run, the parent process writes data to the pipe and then terminates. The child process reads the string from the pipe and prints the result. The parent may start and finish either before or after the child, so the order of the output may differ. Further, once the parent process finishes, the shell prompt (e.g., {\pf babbage\%}) appears and {\pf dtterm} is ready for the next command. If the child has not yet completed its work, then the child's output may appear after the shell prompt. The above output shows both of these cases on subsequent runs. %----------------------------------------------------------------------------- \newprogram {fork-3.c} {Program uses {\pf write} and {\pf read} for integer values, illustrates local and global variables for forked processes, and requires the parent wait for the child process to finish.} \ann \i The {\pf pipe} operation initializes system-level I/O. In particular, {\pf write} and {\pf read} require the address of data for their second parameter and a number of bytes to transfer as their third parameter. \ii {Unlike {\pf printf}, both {\pf write} and {\pf read} require an address for the second parameter. Thus, the address operation \& is used here.} \ii {Since standard integers on MathLAN are 4 bytes long, the example shows the third parameter for both {\pf write} and {\pf read} as 4.} \i As previously stated, the {\pf fork} operation copies the entire process environment in creating the child process. Thus, after a child starts, the parent and the child have separate copies of all variables -- either local or global. Changes in one copy by one process has no affect the other. \i The {\pf wait()} system call suspends process activity until some child processes have completed. \i An alternative form of {\pf wait(pid)} requires a process identification {\pf pid} as parameter. In this case, {\pf wait(pid)} suspends execution of the process until the process with the designated id is finished. \samplerun {fork-3.out} While the message passing from parent to child guarantees that the values of data variables are changed in the parent before being printed by the child, the corresponding values in the child remain changed. This highlights that {\pf fork} creates distinct data spaces for the two processes. The {\pf wait} within the parent process guarantees that the parent will finish after the child. Thus, control will not return to the shell until all work is done, and the resulting shell prompt will come after other output. %----------------------------------------------------------------------------- \newprogram {fork-4.c} {Program which spawns two processes and which allows the two childred to communicate through standard input and standard output.} \ann \i To spawn two children, the main program uses {\pf fork} twice, following much the same approach discussed previously. \i Once a pipe is created and checked for error, the two children close the appropriate input or output end using {\pf close (fd[--])}, as before. \i To set standard input to reference the pipe, one uses {\pf dup2} to duplicate the pipe descriptor for input ({\pf fd[0]}) onto standard input, {\pf STDIN\underbar{~}FILENO)}. In most cases, {\pf dup2} copies the file descriptor onto the second. The testing handles some special cases: \ii {If the two arguments are equal (e.g., if {\pf fd[0] == STDIN\underbar{~}FILENO}, then duplicating the file descriptor would be unnecessary. Further, in this case, {\pf dup2} would return a single file descriptor. Thus, closing one would close the other -- an undesired result for this application.} \ii {In normal operation, {\pf dup2} returns the second file descriptor. Thus, an error must have resulted if {\pf (dup2(fd[0], STDIN\underbar{~}FILENO) != STDIN\underbar{~}FILENO}).} \i Setting standard output to the pipe similarly calls {\pf dup2}, matching the pipe input {\pf fd[1]} with {\pf STDOUT\underbar{~}FILENO)}. \i Once standard input and output reference a pipe, all the familiar I/O operations apply. \ii {{\pf printf} and {\pf scanf} perform formatted I/O.} \ii {{\pf gets} allows the reading of a full line of input.} \i By keeping track of each child process id, the parent process can wait for each child to finish by specify {\pf waitpid()} with the appropriate process id's as parameters. \samplerun {fork-4.out} %----------------------------------------------------------------------------- \newprogram {fork-5.c} {Program sets pipe ends to standard I/O and calls {\pf exec}s operations to run some other programs.} \ann \i This program spawns two child processes and maps the ends of a pipe to standard in/out, as in the previous example. \i Rather than writing separate application code for each child process, each child sets up standard I/O and then executes a separate, external program. \ii {Child 1 executes the Unix-utility {\pf sort}.} \ii {Child 2 executes the Unix-utility {\pf cat}.} \i Altogether, {\pf cat} reads the file {\pf "/home/walker/151s/labs/ia-senate"} which contains a list of members of the Iowa Senate for 1997-1998. These data are then sent through pipe as standard out. The result is the same as giving the command \hfil\break {\pf cat "/home/walker/151s/labs/ia-senate"} \hfil\break in a Unix-shell window. \i Similarly, {\pf sort} reads the data from standard input and orders the lines numerically according to the 6th column (skipping the first 5 columns). \i Coupling {\pf cat} and {\pf sort} through this pipe is equivalent to the Unix-shell command: \hfil\break {\pf cat "/home/walker/151s/labs/ia-senate" | sort -n +5} \i C contains six versions of {\pf exec} procedures to execute programs. Many details are available from system documentation by typing {\pf man exec} at a Unix-shell prompt. \i The sample call {\pf execlp ("sort", "sort", "-n", "+5", (char *) 0)} %\hfil\break illustrates the major elements of the {\pf execlp} call: \ii{{\pf execlp} takes several parameters. The first two specify the name of the program to be called. The ``p'' in {\pf execlp} specifies that the system will follow the normal search path to locate the program named.} \ii {The ``l'' in {\pf execlp} indicates that command-line arguments to the program will be specified as a list of string parameters. (Technically, the first parameter to {\pf execlp} is the program name, and the command line arguments follow. However, since the first argument of any program call is the program's name itself, the second parameter to {\pf execlp} always repeats the program name.) In this example, two additional parameters are given: {\pf "-n"} indicates sorting is to consider the values as numbers, and {\pf "+5"} indicates that ordering should be based on the sixth and later columns -- skipping over the first 5 columns of the output.} \ii {The final parameter to {\pf execlp} is always the null character {\pf (char *) 0}, which terminates the parameter list.} \ii {A call to {\pf execlp} does not return; the process terminates when the called program is done. Thus, the final statement for child 1, {\pf printf ("First child finished$\backslash$n")} is never executed.} \i Sorting can only finish when {\pf sort} knows it has read all data. This is accomplished when all processes close the pipe for writing. This is done explicitly at the start of child 1 ({\pf close (fd[1])}) and implicitly by the end of {\pf execlp("cat", ...)}. Since the parent process also could potentially write to this pipe, however, the parent also must close the same pipe for writing. Hence the final {\pf close (fd[1])} for the parent process. \i As a dutiful parent, the parent process waits until all its children are done before terminating itself. \noindent The raw data file, "/home/walker/151s/labs/ia-senate", is shown below: {\parskip = 0pt \inputprogram {/home/walker/151s/labs/ia-senate} } \samplerun {fork-5.out} \i The truncated listing shows that the file is listed and sorted by zip code -- the contents of the 6th column. %----------------------------------------------------------------------------- \newprogram {fork-6.c} {Program reads, filters, and sorts the system user/password file.} \ann \i This system user/password file may be viewed by the system command {\pf ypcat passwd}. This file contains an entry for each user in the following format: \medskip \leftline {\pf walker:rBhD6XLPGEe3c:207:201:Henry M. Walker:/home/walker:/bin/csh} \item {} On this line, the first entry -- before the first colon -- is the user name. The user's actual name appears between the fourth and fifth colons, with the first name first. \i This program program reads, filters, and sorts this file with three processes: \ii {One child process runs {\pf ypcat passwd}, reading the file and passing the result through a pipe with the child's standard output at one end and the file descriptor {\pf fpin} at the other end.} \ii {The main program reads from the {\pf fpin} pipe, filters reformats lines to extract username and owner name information, and writes the result to a file/pipe with file descriptor {\pf fpout}.} \ii {Another child process runs {\pf sort}, reading from a pipe connected to file descriptor {\pf fpout} at its input end and standard input at the child's end.} \i After declaring variables, the main program prints table headers. Further, the main calls {\pf fflush(stdout)} to guarantee that this output is printed to the screen before any further processing occurs. This guarantees the headers are printed before anything else. \i The system call {\pf popen} performs the common details for setting up a process and pipe: creating a pipe, spawning a child with {\pf fork}, closing the unused ends of the pipe, setting the child's input or output to standard I/O, {\pf exec}ing a shell to execute a command, and waiting for the fork/pipe setup to finish. \ii {The first parameter to {\pf popen} specifies the program/shell to execute.} \ii {The second parameter specifies the direction of communication with the pipe. A ``r'' indicates the child will write to standard output, so the main (parent) can read from the pipe; A ``w'' indicates the child will read from standard input throught the pipe.} \i The system call {\pf pclose} performs the common finish-up details at the end of a process: the I/O stream is closed, the parent waits for the child to return, and the exit status of the child is returned. \i The line extraction within the main/parent scans subsequent characters: \ii {The username occurs first in the user/password file and is terminated by a colon.} \ii {Three more fields, separated by colons, occur before the name field.} \ii {Names are given with the first name and last name, in that order, although middle names sometimes occur. Names usually are terminated by a comma or colon.} \ii {Miscellaneous information finishes out the line.} \item {} Processing proceeds character-by-character and field-by-field, with the relevant data being passed on. Each name is printed in a field of a standard length, so the output will be in columns. The last name is detected by reading successive characters, although the recording of letters in this last name is reset if another space is found. \noindent The following output is truncated to save paper. \samplerun {fork-6.out} %----------------------------------------------------------------------------- \newprogram {read-write-1.c} {A simple readers/writers program using a one-word shared memory.} \ann \i The {\pf mmap} procedure (from the $<$sys/mman.h$>$ library) sets up a shared memory segment and returns the base address for that segment. More generally, the {\pf mmap} function establishes a correspondence between a specified number of bytes in the process's address space with a separate block of memory. This allocation of a new memory segment has the following form: \smallskip \centerline {\pf base\underbar{~}address = mmap(0, num\underbar{~}bytes, protection, flags, -1, 0);} \smallskip \ii {The second parameter, {\pf num\underbar{~}bytes}, specifies the number of bytes to be allocated for the new segment.} \ii {The third parameter, {\pf protection}, specifies whether the segment may be used for reading, writing, executing, or other purpose. The various options are:} {\parindent = 60pt \item {} {\pf PROT\underbar{~}READ} -- page can be read \parskip = 1pt \item {} {\pf PROT\underbar{~}WRITE} -- page can be written \item {} {\pf PROT\underbar{~}EXEC} -- page can be executed \item {} {\pf PROT\underbar{~}NONE} -- page cannot be accessed } \itemitem {} For typical shared memory, both read and write permission is specified using the combination {\pf PROT\underbar{~}READ | PROT\underbar{~}WRITE} . \ii {The fourth parameter indicates further details of file allocation and file sharing. In {\pf read-write-1.c}, the combination {\pf MAP\underbar{~}ANONYMOUS | MAP\underbar{~}SHARED} indicates a new memory segment should be allocation (rather than allocating space from a file descriptor) and all writes to the memory segment should be shared with other processes.} \ii {The values of the other parameters provide flexibility for many applications. While the general use of {\pf mmap} is beyond the scope of this introduction, simple allocation of a main memory segment requires a 0 value in the first and last paramter. The value -1 in the next-to-last parameter indicates a new, internal file descriptor is needed -- the segment will not be part of an existing file.} \ii {Procedure {\pf mmap} returns the base address (starting location) of the memory segment.} \i Once memory is allocated with {\pf mmap}, and the base address {\pf shared\underbar{~}memory} is known, then the {\pf shared\underbar{~}memory} variable may be used as any address within a C program. In particular, {\pf *shared\underbar{~}memory} specifies the value stored at that address. \i In this program, the parent process writes successive data values to the shared memory, and the child process reads successive data values. The {\pf sleep} statements are added in an attempt to synchronize this data transfer. Once the parent puts a value (a square of an integer) into shared memory, it sleeps for a second to allow the child time to access that value. Similarly, a child delays its processing by one second to give the parent time to put a new value into shared memory. \samplerun {read-write-1.out} \i As hoped, the {\pf sleep} statements provide adequate time for the parent to write and the child to read, before new values are put into the shared memory. \i However, if the {\pf sleep} statement is removed from the parent (but retained in the child), then the all values are written by the parent before any are retrieved by the child. This is shown in the following sample run, where the child gets only the last value written by the parent -- the other values are lost. \samplerun {read-write-1.out-a} \samplerun {read-write-1.out-b} \i If the {\pf sleep} statement is removed from the child (but retained in the parent), then the child performs all of its reading before the parent makes any updates. Thus, most data from the parent arrive too late to be used by the child. %----------------------------------------------------------------------------- \newprogram {read-write-2.c} {A readers/writers program, using an intermediate buffer of 5 integer words, plus 2 index markers.} \ann \i This program follows the outline for a bounded buffer solution to the readers/writers problem, as given in Silberschatz and Galvin, {\ital OperatingSystems Concepts, Fifth Edition}, page 102. \i A logical {\pf buffer} is allocated in shared memory, and buffer indexes, {\pf in} and {\pf out}, are used identify where data will be stored or read by the writer or reader process. More specifically, \ii {{\pf *in} gives the next free place in the {\pf buffer} for the writer to enter data.} \ii {{\pf *out} gives the first place in the {\pf buffer} for the reader to extract data.} \i Writing to the {\pf buffer} may continue unless the buffer is full (i.e., \hfil\break {\pf (*in + 1) \% BUF\underbar{~}SIZE == *out}) and reading from the buffer may proceed unless the buffer is empty (i.e., {\pf *in == *out}). Both conditions are tested in spin locks. \i {\pf shared\underbar{~}memory} must be large enough for the {\pf buffer} and the variables {\pf in} and {\pf out}. As integers are being stored in the {\pf in} and {\pf out}, this implies shared memory must be 2 integers larger than the buffer of {\ital BUF\underbar{~}SIZE} integers. \ii {In the program, the {\pf buffer} occupies the first $n$ words of {\pf shared\underbar{~}memory}.} \ii {{\pf in} gives the address of word {\pf BUF\underbar{~}SIZE+1} of {\pf shared\underbar{~}memory}.} \ii {{\pf out} gives the address of word {\pf BUF\underbar{~}SIZE+2} of {\pf shared\underbar{~}memory}.} \i Since {\pf buffer} represents the base address of an array of integers, it is declared as a pointer to an integer. Similarly, {\pf in} and {\pf out} specify addresses of integers, so {\pf *in} and {\pf *out} specify the values stored at those addresses. \i The {\pf buffer} array starts at the beginning of the {\pf shared\underbar{~}memory} segment. Thus, {\pf buffer} may be initialized with the address of {\pf shared\underbar{~}memory}, where the cast {\pf (int*)} translates from the address type {\pf caddr\underbar{~}t} to the more familiar integer-addressing format. \i {\pf in} and {\pf out} are initialized by computing the appropriate address within {\pf shared\underbar{~}memory}. In each case, address type {\pf caddr\underbar{~}t} is converted to an integer form. For {\pf in}, the address will start after the {\pf buffer} array -- {\pf BUF\underbar{~}SIZE} words from the start of {\pf shared\underbar{~}memory}. The address for {\pf out} begins one word later. \i The starting buffer indices, {\pf *in} and {\pf *out}, identify the beginning of the buffer -- at position 0. \i The writer places a value in {\pf buffer[*in]} and increments the buffer array index. (For simplicity, the value produced is just the square of a sequence number.) \i The reader retrieves the value from {\pf buffer[*out]} and also increments the buffer array index. \i Following good practice, the parent waits for the child process to finish at the end. \samplerun {read-write-2.out} \i While the reader process starts, it then waits until the writer puts data in the buffer. However, the writer is blocked once the buffer is full (with 4 items -- the writer's test guarantees that one slot in the buffer will remain empty). %----------------------------------------------------------------------------- \newprogram {read-write-3.c} {A readers/writers program with a shared buffer and semaphores to coordinate buffer access.} \ann \i This program follows the same approach to a buffer in shared memory as the previous example. {\pf shared\underbar{~}memory} is declared and allocated with {\pf mmap}, and variables {\pf buffer}, {\pf in} and {\pf out} reference various parts of that shared memory. \i Writing to and reading from the buffer are protected by semaphores. Conceptually, the {\pf buf\underbar{~}used} keeps track of how many buffer elements are used, while {\pf buf\underbar{~}space} keeps track of how many empty spaces remain in the buffer. \i Practically, semaphores in Unix [GNU] C are part of the $<$sys/sem.h$>$ library. All semaphores are considered as part of a set or array and accessed through an integer identification number ({\pf semid} in this program). Work with semaphores follows three main steps: \ii {A set or array of semaphores are created with {\pf semget} .} \ii {Semaphores are initialized or otherwise controled by {\pf setctl} .} \ii {Semaphore operations are performed using {\pf semop} .} \i To clarify the logic of the program, these tasks are placed in separate, helping procedures. \i In the main program, the statement {\pf semid = sem\underbar{~}init()} creates and initializes a semaphore, and the semaphore's id is stored in {\pf semid} . \ii {As all semaphores in Unix [GNU] C are declared in arrays, this program defines index {\pf buf\underbar{~}used} for semaphore 0 -- the semaphore which will be used to keep track how much space within the buffer has been used.} \ii {Similarly, this program defines index {\pf buf\underbar{~}space} for semaphore 1 -- the semaphore which will be used to keep track how much empty space exists within the buffer.} \i Following standard operating system terminology, the operation {\pf P(semid, buf\underbar{~}used)} causes the process to wait if no space is used. Similarly, {\pf P(semid, buf\underbar{~}space)} causes the process to wait if no empty space remains. If the counts for these variables are nonzero, then the respective processes continue, decrementing the number of used items or the amount of space by 1. The alternative name for the {\pf P} operation is {\pf wait}. \i Also using standard terminology, the operation {\pf V(semid, buf\underbar{~}used)} increments the semaphore's count of used elements by increased by 1. Similarly, {\pf V(semid, buf\underbar{~}space)} increases the count of free space by 1. A common alternative name to the {\pf V} operation is {\pf signal} . \i The parent/writer process continues to put data within the buffer as long as space remains. The statement {\pf P(semid, buf\underbar{~}space)} prevents the writer from proceeding if the buffer is full (i.e., no space remains). After the writer places data in the buffer, the statement {\pf V(semid, buf\underbar{~}space)} updates the count of free space. \i The child/reader process uses the statement {\pf P(semid, buf\underbar{~}used)} to wait until the\break buffer is used to store some relevant data. After reading the data, the statement\break {\pf V(semid, buf\underbar{~}space)} indicates that one space within the buffer has become free. \i In the program, the {\pf sleep} statements in both the parent and child are added only to demonstrate different times of processing, making the output more interesting. \i Semaphore creation within procedure {\pf sem\underbar{~}init} utilizes the statement\hfil\break {\pf semget (IPC\underbar{~}PRIVATE, 2, IPC\underbar{~}CREAT $\vert$ 0600)} \ii {{\pf IPC\underbar{~}PRIVATE} indicates a private semaphore set is to be referenced, and the parameter {\pf 2} indicates this set will contain two semaphores.} \ii {The last parameter {\pf IPC\underbar{~}CREAT $\vert$ 0600} indicates this semaphore set is to be created and the user processes should have read/write access (code 0600).} \ii {{\pf semget} normally returns a new semaphore identification integer, although a negative response indicates an error has occurred.} \i Semaphore initialization involves setting specific values for each semaphore with the {\pf semctl} statement. \ii {The first parameter identifies the semaphore set, while the second parameter indicates which element of that set is being referenced.} \ii {The third parameter indicates the operation to be performed. {\pf SETVAL} sets the specific semaphore to the value that follows (e.g., {\pf BUF\underbar{~}SIZE} or 0), while {\pf IPC\underbar{~}RMID} removes the entire semaphore from the system. Another command option, {\pf SETALL}, sets all semaphores to the value that follows.} \i The procedure {\pf semop} is used to change the value of a semaphore. \ii {The first parameter one specifies which semaphore set is to be modified.} \ii {The second parameter gives an array of commands. As shown within the program's\break {\pf P} and {\pf V} procedures, a command involves setting three fields within a {\pf sembuf} structure (e.g, {\pf sops} in this program). {\pf sem\underbar{~}num} indicates which semaphore in the set to change. {\pf sem\underbar{~}op} indicates the operation, such as add or subtract 1 from the semaphore's value. Addition always proceeds as expected, while subtraction may result in blocking the process if the current value already is 0. For most purposes, setting {\pf sem\underbar{~}flg} to 0 provides an appropriate flag value.} \ii {The final parameter to {\pf semop} gives the number of operations to be applied to the semaphore. In both the {\pf P} and {\pf V} operations, only a single command is given. Thus, the {\pf sembuf} array {\pf sops} has size 1, and the last parameter to {\pf semop} is 1.} \samplerun {read-write-3.out} \i The two sample runs show several results of the reader and writer processes working independently. Sometimes, one process must wait for the other, while they both can work concurrently at other times. \i At the conclusion of the program, the parent waits for its child, and then the semaphore set is removed from the system. While normal program termination should clean up the system's semaphore table, this deallocation step provides additional assurance that semaphores will not accumulate after a program terminates. %----------------------------------------------------------------------------- \newprogram {read-write-4.c} {A readers/writers program with multiple readers and multiple writers communicating\break through a shared buffer, with synchronization achieved through semaphores.} \ann \i This program utilizes a shared buffer following the same shared-memory facilities (with {\pf mmap}) used in the previous programs. \i This program uses three semaphores, one for the amount of buffer space used, one for the amount of buffer space free, and one to guarantee that only one process actually accesses the buffer at a time. As in the previous program, these semaphores are declared in one semaphore set, and constants ({\pf buf\underbar{~}used}, {\pf buf\underbar{~}space}, and {\pf mutex}) are defined to help remember which semaphore index is which. \i Semaphores are created in procedure {\pf sem\underbar{~}create}, which calls the system procedure {\pf semget}, performs appropriate error checking, and returns the id of the semaphore set. \i A semaphore is initialized in procedure {\pf sem\underbar{~}init}, which sets a specific semaphore to a given value. While {\pf sem\underbar{~}init} simply calls {\pf semctl} with an extra {\pf SETVAL} parameter, the separation of the error checking from other processing makes the main program cleaner. \i The semaphore {\pf P} and {\pf V} operations used here follow the code from the previous program. \i The main program spawns {\pf NUM\underbar{~}WRITERS} processes for writing and saves the id's in an array {\pf proc}. Then the main program spawns {\pf NUM\underbar{~}READERS} processes for reading and adds the id's to the process id array {\pf proc}. \i As in the previous program, a writer process must wait to write until there is space in the buffer, and this is checked by the {\pf buf\underbar{~}space} semaphore. Similarly, a reader process cannot take data out of an empty buffer, and this is checked by the {\pf buf\underbar{~}used} semaphore. \i Since multiple writers and multiple readers may want to access the buffer at the same time, there is a possibility that two unconstrained processes might attempt to read or write from the same place in the buffer. This concurrent buffer access is prevented by the {\pf mutex} semaphore, which guarantees that only one process can actually use the buffer at a time. \i While the writers do not display their data directly on the output, the data are coded, so the first digit of a value indicates the writer process number. \i As in the previous program, a {\pf sleep} statement is added to the reader processes, so that various processes are blocked at various times. This seems to make the scheduling of processes more interesting. \i After the main program spawns all the writer and reader processes, it waits until all spawned processes terminate. This is done by keeping the child process ids in an array and then performing a {\pf wait} for each of these ids in turn. \samplerun {read-write-4.out} \i In this output, the interleaving of the writers may be inferred, in that readers take data from the buffer in the order the data are written, and the writer of each data item is known by the hundred's digit of that data. \end %----------------------------------------------------------------------------- \newprogram {.c} {.} \ann \i \samplerun {.out} \i %----------------------------------------------------------------------------- \newprogram {.c} {.} \ann \i \samplerun {.out} %----------------------------------------------------------------------------- \newprogram {.c} {.} \ann \i \samplerun {.out} %----------------------------------------------------------------------------- \newcode {.c} {.} \ann \i \samplerun {.out} \i %----------------------------------------------------------------------------- \end %----------------------------------------------------------------------------- %----------------------------------------------------------------------------- \newprogram {.cc} {.} \ann \i \samplerun {.out}