Chapter 3 Processes

3 CHAPTER Processes In this chapter we introduce the concepts of a process and concurrent execution; These concepts are at the very heart of modern operating systems. A process is is a program in execution and is the unit of work in a modern time-sharing system. Such a system consists of a collection of processes: Operating-system processes executing system code and user processes executing user code. All these processes can potentially execute concurrently, with the CPU (or CPUs) multiplexed among them. By switching the CPU between processes, the operating system can make the computer more productive. We also introduce the notion of a thread (lightweight process) and interprocess communication (IPC). Threads are discussed in more detail in Chapter 4. Exercises 3.1 Describe the differences among short-term, medium-term, and longterm scheduling. Answer: • Short-term (CPU scheduler)— selects from jobs in memory those jobs that are ready to execute and allocates the CPU to them. • Medium-term— used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off. • Long-term (job scheduler) —determines which jobs are brought into memory for processing. The primary difference is in the frequency of their execution. The shortterm must select a new process quite often. Long-term is used much less often since it handles placing jobs in the system and may wait a while for a job to finish before it admits another one. 15 16 Chapter 3 Processes 3.2 Describe the actions taken by a kernel to context-switch between processes. Answer: In general, the operating system must save the state of the currently running process and restore the state of the process scheduled to be run next. Saving the state of a process typically includes the values of all the CPU registers in addition to memory allocation. Context switches must also perform many architecture-specific operations, including flushing data and instruction caches. 3.3 Consider the RPC mechanism. Describe the undesirable circumstances that could arise from not enforcing either the "at most once" or "exactly once" semantics. Describe possible uses for a mechanism that had neither of these guarantees. Answer: If an RPC mechanism could not support either the “at most once” or “at least once” semantics, then the RPC server cannot guarantee that a remote procedure will not be invoked multiple occurrences. Consider if a remote procedure were withdrawing money from a bank account on a system that did not support these semantics. It is possible that a single invocation of the remote procedure might lead to multiple withdrawals on the server. For a system to support either of these semantics generally requires the server maintain some form of client state such as the timestamp described in the text. If a system were unable to support either of these sematics, then such a system could only safely provide remote procedures that do not alter data or provide time-sensitive results. Using our bank accunt as an example, we certainly require “at most once” or “at least once” semantics for performing a withdrawal (or deposit!) However, an inquiry into an account balance or other accunt information such as name, address, etc. does not require these semantics. 3.4 Using the program shown in Figure 3.24, explain what will be output at Line A. Answer: Please refer to the supporting Web site for source code solution. 3.5 What are the benefits and detriments of each of the following? Consider both the systems and the programmers’ levels. a. Symmetric and asymmetric communication b. Automatic and explicit buffering c. Send by copy and send by reference d. Fixed-sized and variable-sized messages Answer: a. Symmetric and asymmetric communication - A benefit of symmetric communication is that it allows a rendezvous between the sender and receiver. A disadvantage of a blocking send is that a rendezvous may not be required and the message could be delivered asynchronously; received at a point of no interest to the Exercises 17 sender. As a result, message-passing systems often provide both forms of synchronization. b. Automatic and explicit buffering - Automatic buffering provides a queue with indefinite length; thus ensuring the sender will never have to block while waiting to copy a message. There are no specifications how automatic buffering will be provided; one scheme may reserve sufficiently large memory where much of the memory is wasted. Explicit buffering specifies how large the buffer is. In this situation, the sender may be blocked while waiting for available space in the queue. However, it is less likely memory will be wasted with explicit buffering. c. Send by copy and send by reference - Send by copy does not allow the receiver to alter the state of the parameter; send by reference does allow it. A benefit of send by reference is that it allows the programmer to write a distributed version of a centralized application. Java’s RMI provides both, however passing a parameter by reference requires declaring the parameter as a remote object as well. d. Fixed-sized and variable-sized messages - The implications of this are mostly related to buffering issues; with fixed-size messages, a buffer with a specific size can hold a known number of messages. The number of variable-sized messages that can be held by such a buffer is unknown. Consider how Windows 2000 handles this situation: with fixed-sized messages (anything < 256 bytes), the messages are copied from the address space of the sender to the address space of the receiving process. Larger messages (i.e. variable-sized messages) use shared memory to pass the message. 3.6 The Fibonacci sequence is the series of numbers 0, 1, 1, 2, 3, 5, 8, .... Formally, it can be expressed as: f ib 0 = 0 f ib 1 = 1 f ib n = f ibn−1 + f i bn−2 Write a C program using the fork() system call that that generates the Fibonacci sequence in the child process. The number of the sequence will be provided in the command line. For example, if 5 is provided, the first five numbers in the Fibonacci sequence will be output by the child process. Because the parent and child processes have their own copies of the data, it will be necessary for the child to output the sequence. Have the parent invoke the wait() call to wait for the child process to complete before exiting the program. Perform necessary error checking to ensure that a non-negative number is passed on the command line. Answer: Please refer to the supporting Web site for source code solution. 3.7 Repeat the preceding exercise, this time using the CreateProcess() in the Win32 API. In this instance, you will need to specify a separate pro- 18 Chapter 3 Processes gram to be invoked from CreateProcess(). It is this separate program that will run as a child process outputting the Fibonacci sequence. Perform necessary error checking to ensure that a non-negative number is passed on the command line. Answer: Please refer to the supporting Web site for source code solution. 3.8 Modify the Date server shown in Figure 3.19 so that it delivers random one-line fortunes rather than the current date. Allow the fortunes to contain multiple lines. The date client shown in Figure 3.20 can be used to read the multi-line fortunes returned by the fortune server. Answer: Please refer to the supporting Web site for source code solution. 3.9 An echo server is a server that echoes back whatever it receives from a client. For example, if a client sends the server the string Hello there! the server will respond with the exact data it received from the client— that is, Hello there! Write an echo server using the Java networking API described in Section 3.6.1. This server will wait for a client connection using the accept() method. When a client connection is received, the server will loop, performing the following steps: • Read data from the socket into a buffer. • Write the contents of the buffer back to the client. The server will break out of the loop only when it has determined that the client has closed the connection. The date server shown in Figure 3.19 uses the java.io.BufferedReader class. BufferedReader extends the java.io.Reader class, which is used for reading character streams. However, the echo server cannot guarantee that it will read characters from clients; it may receive binary data as well. The class java.io.InputStream deals with data at the byte level rather than the character level. Thus, this echo server must use an object that extends java.io.InputStream. The read() method in the java.io.InputStream class returns −1 when the client has closed its end of the socket connection. Answer: Please refer to the supporting Web site for source code solution. 3.10 In Exercise 3.6, the child process must output the Fibonacci sequence, since the parent and child have their own copies of the data. Another approach to designing this program is to establish a shared-memory segment between the parent and child processes. This technique allows the child to write the contents of the Fibonacci sequence to the sharedmemory segment and has the parent output the sequence when the child completes. Because the memory is shared, any changes the child makes to the shared memory will be reflected in the parent process as well. This program will be structured using POSIX shared memory as described in Section 3.5.1. The program first requires creating the data structure for the shared-memory segment. This is most easily accomplished using a struct. This data structure will contain two items: (1) a fixed-sized array of size MAX SEQUENCE that will hold the Fibonacci values; and (2) the size of the sequence the child process is to generate Exercises 19 - sequence size where sequence size ≤ MAX SEQUENCE. These items can be represented in a struct as follows: #define MAX SEQUENCE 10 typedef struct { long fib sequence[MAX SEQUENCE]; int sequence size; } shared data; The parent process will progress through the following steps: a. Accept the parameter passed on the command line and perform error checking to ensure that the parameter is ≤ MAX SEQUENCE. b. Create a shared-memory segment of size shared data. c. Attach the shared-memory segment to its address space. d. Set the value of sequence size to the parameter on the command line. e. Fork the child process and invoke the wait() system call to wait for the child to finish. f. Output the value of the Fibonacci sequence in the shared-memory segment. g. Detach and remove the shared-memory segment. Because the child process is a copy of the parent, the shared-memory region will be attached to the child’s address space as well. The child process will then write the Fibonacci sequence to shared memory and finally will detach the segment. One issue of concern with cooperating processes involves synchronization issues. In this exercise, the parent and child processes must be synchronized so that the parent does not output the Fibonacci sequence until the child finishes generating the sequence. These two processes will be synchronized using the wait() system call; the parent process will invoke wait(), which will cause it to be suspended until the child process exits. Answer: Please refer to the supporting Web site for source code solution. 3.11 Most UNIX and Linux systems provide the ipcs command. This command lists the status of various POSIX interprocess communication mechanisms, including shared-memory segments. Much of the information for the command comes from the data structure struct shmid ds, which is available in the /usr/include/sys/shm.h file. Some of the fields of this structure include: • int shm segsz — size of the shared-memory segment • short shm nattch — number of attaches to the shared-memory segment 20 Chapter 3 Processes • struct ipc perm shm perm — permission structure of the shared-memory segment The struct ipc perm data structure (which is available in the file /usr/include/sys/ipc.h) contains the fields: • unsigned short uid —identifier of the user of the shared-memory segment • unsigned short mode —permission modes • key t key (on Linux systems, key)— user-specified key identifier The permission modes are set according to how the shared-memory segment is established with the shmget() system call. Permissions are identified according to the following: Mode Meaning 0400 Read permission of owner. 0200 Write permission of owner. 0040 Read permission of group. 0020 Write permission of group. 0004 Read permission of world. 0002 Write permission of world. Permissions can be accessed by using the bitwise AND operator &. For example, if the statement mode & 0400 evaluates to true, the permission mode allows read permission by the owner of the shared-memory segment. Shared-memory segments can be identified according to a user-specified key or according to the integer value returned from the shmget() system call, which represents the integer identifier of the shared-memory segment created. The shm ds structure for a given integer segment identifier can be obtained with the following shmctl() system call: /* identifier of the shared memory segment*/ int segment id; shm ds shmbuffer; shmctl(segment id, IPC STAT, &shmbuffer); If successful, shmctl() returns 0; otherwise, it returns -1. Write a C program that is passed an identifier for a shared-memory segment. This program will invoke the shmctl() function to obtain its shm ds structure. It will then output the following values of the given shared-memory segment: • Segment ID • Key Exercises 21 • Mode • Owner UID • Size • Number of attaches Answer: Please refer to the supporting Web site for source code solution.