Chapter 3 Flashcards
Interprocess Communication
Processes executing concurrently in the operating system may be either inde-pendent processes or cooperating processes. A process is independent if it does not share data with any other processes executing in the system. A process is cooperating if it can affect or be affected by the other processes executing in the system. Clearly, any process that shares data with other processes is a cooperating process.
There are several reasons for providing an environment that allows process cooperation:
•Information sharing. Since several applications may be interested in the same piece of information (for instance, copying and pasting), we must provide an environment to allow concurrent access to such information.
•Computation speedup. If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the others. Notice that such a speedup can be achieved only if the computer has multiple processing cores.
•Modularity. We may want to construct the system in a modular fashion, dividing the system functions into separate processes or threads, as we discussed in Chapter 2.
Cooperating processes require an interprocess communication (IPC) mechanism that will allow them to exchange data— that is, send data to and receive data from each other.
There are two fundamental models of interprocess communication: shared memory and message passing. In the shared-memory model, a region of memory that is shared by the cooperating processes is established. Processes can then exchange information by reading and writing data to the shared region. In the message-passing model, communication takes place by means of messages exchanged between the cooperating processes. The two communications models are contrasted in Figure 3.11. Both of the models just mentioned are common in operating systems, and many systems implement both. Message passing is useful for exchanging smaller amounts of data, because no conflicts need be avoided. Message passing is also easier to implement in a distributed system than shared memory.
(Although there are systems that provide distributed shared memory, we do not consider them in this text.) Shared memory can be faster than message passing, since message-passing systems are typically implemented using system calls and thus require the more time-consuming task of kernel intervention.
In shared-memory systems, system calls are required only to establish shared-memory regions. Once shared memory is established, all accesses are treated as routine memory accesses, and no assistance from the kernel is required.
In Section 3.5 and Section 3.6 we explore shared-memory and message-passing systems in more detail.
MULTIPROCESS ARCHITECTURE—CHROME BROWSER
Many websites contain active content, such as JavaScript, Flash, and HTML5 to provide a rich and dynamic web-browsing experience. Unfortunately, these web applications may also contain software bugs, which can result in sluggish response times and can even cause the web browser to crash. This isn’t a big problem in a web browser that displays content from only one web-site. But most contemporary web browsers provide tabbed browsing, which allows a single instance of a web browser application to open several websites at the same time, with each site in a separate tab. To switch between the different sites, a user need only click on the appropriate tab. This arrangement is illustrated below:
A problem with this approach is that if a web application in any tab crashes, the entire process—including all other tabs displaying additional websites— crashes as well.
Google’s Chrome web browser was designed to address this issue by using a multiprocess architecture. Chrome identifies three different types of processes: browser, renderers, and plugins.
•The browser process is responsible for managing the user interface as well as disk and network I/O. A new browser process is created when Chrome is started. Only one browser process is created.
•Renderer processes contain logic for rendering web pages. Thus, they contain the logic for handling HTML, Javascript, images, and so forth. As a general rule, a new renderer process is created for each website opened in a new tab, and so several renderer processes may be active at the same time.
•A plug-in process is created for each type of plug-in (such as Flash or QuickTime) in use. Plug-in processes contain the code for the plug-in as well as additional code that enables the plug-in to communicate with associated renderer processes and the browser process.
The advantage of the multiprocess approach is that websites run in iso-lation from one another. If one website crashes, only its renderer process is affected; all other processes remain unharmed. Furthermore, renderer pro-cesses run in a sandbox, which means that access to disk and network I/Ois restricted, minimizing the effects of any security exploits.
IPC inter process communication in Shared-Memory Systems
Interprocess communication using shared memory requires communicating processes to establish a region of shared memory. Typically, a shared-memory region resides in the address space of the process creating the shared-memory segment. Other processes that wish to communicate using this shared-memory segment must attach it to their address space. Recall that, normally, the oper-ating system tries to prevent one process from accessing another process’s memory. Shared memory requires that two or more processes agree to remove this restriction. They can then exchange information by reading and writing data in the shared areas. The form of the data and the location are determined by these processes and are not under the operating system’s control. The pro-cesses are also responsible for ensuring that they are not writing to the same location simultaneously.
pro-ducer–consumer problem
A producer process produces information that is consumed by a con-sumer process. For example, a compiler may produce assembly code that is consumed by an assembler. The assembler, in turn, may produce object mod-ules that are consumed by the loader. The producer–consumer problem also provides a useful metaphor for the client–server paradigm. We generally think of a server as a producer and a client as a consumer. For example, a web server produces (that is, provides) web content such asHTMLf i les and images, which are consumed (that is, read) by the client web browser requesting the resource.
One solution to the producer–consumer problem uses shared memory. To allow producer and consumer processes to run concurrently, we must have available a buffer of items that can be f i lled by the producer and emptied by the consumer. This buffer will reside in a region of memory that is shared by the producer and consumer processes. A producer can produce one item while the consumer is consuming another item. The producer and consumer must be synchronized, so that the consumer does not try to consume an item that has not yet been produced.
Two types of buffers can be used
The unbounded buffer places no prac-tical limit on the size of the buffer. The consumer may have to wait for new items, but the producer can always produce new items. The bounded buffer assumes a f i xed buffer size. In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.
Let’s look more closely at how the bounded buffer illustrates interprocess communication using shared memory. The following variables reside in a region of memory shared by the producer and consumer processes:
#define BUFFER SIZE 10 typedef struct{ . . .
}item;
item buffer[BUFFER SIZE];
int in = 0;
int out = 0;
IPC in Message-Passing Systems
Message passing provides a mechanism to allow processes to communicate and to synchronize their actions without sharing the same address space. It is particularly useful in a distributed environment, where the communicating processes may reside on different computers connected by a network. For example, an Internetchatprogram could be designed so that chat participants communicate with one another by exchanging messages.
A message-passing facility provides at least two operations:
send(message) and receive(message) Messages sent by a process can be either f i xed or variable in size. If only fixed-sized messages can be sent, the system-level implementation is straight-forward. This restriction, however, makes the task of programming more difficult. Conversely, variable-sized messages require a more complex system-level implementation, but the programming task becomes simpler. This is a common kind of tradeoff seen throughout operating-system design.
If processes P and Q want to communicate, they must send messages to and receive messages from each other: a communication link must exist between them. This link can be implemented in a variety of ways. We are concerned here not with the link’s physical implementation (such as shared memory, hardware bus, or network, which are covered in Chapter 19) but rather with its logical implementation. Here are several methods for logically implementing a link and the send()/receive()operations:
•Direct or indirect communication
•Synchronous or asynchronous communication
•Automatic or explicit buffering
direct communication
Under direct communication, each process that wants to communicate must explicitly name the recipient or sender of the communication. In this scheme, the send() and receive() primitives are defined as:
•send(P, message)—Send amessageto process P.
•receive(Q, message)—Receive amessagefrom process Q.
A communication link in this scheme has the following properties:
•A link is established automatically between every pair of processes that want to communicate. The processes need to know only each other’s identity to communicate.
•A link is associated with exactly two processes.
•Between each pair of processes, there exists exactly one link.
This scheme exhibits symmetry in addressing; that is, both the sender pro-cess and the receiver process must name the other to communicate. A variant of this scheme employs asymmetry in addressing. Here, only the sender names the recipient; the recipient is not required to name the sender. In this scheme, thesend()andreceive()primitives are def i ned as follows:
•send(P, message)—Send amessageto processP.
•receive(id, message)—Receive amessagefrom any process. The vari-ableidis set to the name of the process with which communication has taken place.
The disadvantage in both of these schemes (symmetric and asymmetric) is the limited modularity of the resulting process def i nitions. Changing the identif i er of a process may necessitate examining all other process def i nitions.
All references to the old identif i er must be found, so that they can be modif i ed to the new identif i er. In general, any such hard-coding techniques, where iden-tif i ers must be explicitly stated, are less desirable
indirect communication in messages
With indirect communication, the messages are sent to and received from mailboxes, or ports. A mailbox can be viewed abstractly as an object into which messages can be placed by processes and from which messages can be removed. Each mailbox has a unique identification. For example,POSIX message queues use an integer value to identify a mailbox. A process can communicate with another process via a number of different mailboxes, but two processes can communicate only if they have a shared mailbox. The send() andr eceive()primitives are defined as follows:
•send(A, message)—Send amessageto mailboxA.
•receive(A, message)—Receive amessagefrom mailboxA.
In this scheme, a communication link has the following properties:
•A link is established between a pair of processes only if both members of the pair have a shared mailbox.
•A link may be associated with more than two processes.
•Between each pair of communicating processes, a number of different links may exist, with each link corresponding to one mailbox.
Now suppose that processes P1, P2, and P3all share mailbox A. Process P1 sends a message to A, while both P2and P3execute are ceive()from A. Which process will receive the message sent by P1? The answer depends on which of the following methods we choose:
•Allow a link to be associated with two processes at most.
•Allow at most one process at a time to execute areceive()operation.
•Allow the system to select arbitrarily which process will receive the mes-sage (that is, either P2or P3, but not both, will receive the message). The system may def i ne an algorithm for selecting which process will receive the message (for example, round robin, where processes take turns receiv-ing messages). The system may identify the receiver to the sender.
A mailbox may be owned either by a process or by the operating system.
If the mailbox is owned by a process (that is, the mailbox is part of the address space of the process), then we distinguish between the owner (which can only receive messages through this mailbox) and the user (which can only send messages to the mailbox). Since each mailbox has a unique owner, there can be no confusion about which process should receive a message sent to this mailbox. When a process that owns a mailbox terminates, the mailbox disappears. Any process that subsequently sends a message to this mailbox must be notif i ed that the mailbox no longer exists.
In contrast, a mailbox that is owned by the operating system has an exis-tence of its own. It is independent and is not attached to any particular process.
The operating system then must provide a mechanism that allows a process to do the following:
•Create a new mailbox.
•Send and receive messages through the mailbox.
•Delete a mailbox.
The process that creates a new mailbox is that mailbox’s owner by default.
Initially, the owner is the only process that can receive messages through this mailbox. However, the ownership and receiving privilege may be passed to other processes through appropriate system calls. Of course, this provision could result in multiple receivers for each mailbox.
Synchronization
Communication between processes takes place through calls to send()and receive()primitives. There are different design options for implementing each primitive. Message passing may be either blocking or nonblocking— also known as synchronous and asynchronous. (Throughout this text, you will encounter the concepts of synchronous and asynchronous behavior in relation to various operating-system algorithms.) •Blocking send. The sending process is blocked until the message is received by the receiving process or by the mailbox.
•Nonblocking send. The sending process sends the message and resumes operation.
•Blocking receive. The receiver blocks until a message is available.
•Nonblocking receive. The receiver retrieves either a valid message or a null.
Different combinations ofsend()andreceive()are possible. When both send()andreceive()are blocking, we have a rendezvous between the sender and the receiver. The solution to the producer–consumer problem becomes trivial when we use blockingsend()andreceive()statements. The producer merely invokes the blockingsend()call and waits until the message is delivered to either the receiver or the mailbox. Likewise, when the consumer invokesreceive(), it blocks until a message is available. This is illustrated in Figures 3.14 and 3.15.
Buffering
Whether communication is direct or indirect, messages exchanged by commu-nicating processes reside in a temporary queue. Basically, such queues can be implemented in three ways:
•Zero capacity. The queue has a maximum length of zero; thus, the link cannot have any messages waiting in it. In this case, the sender must block until the recipient receives the message.
•Bounded capacity. The queue has f i nite length n; thus, at most n messages can reside in it. If the queue is not full when a new message is sent, the message is placed in the queue (either the message is copied or a pointer to the message is kept), and the sender can continue execution without waiting. The link’s capacity is f i nite, however. If the link is full, the sender must block until space is available in the queue.
•Unbounded capacity. The queue’s length is potentially inf i nite; thus, any number of messages can wait in it. The sender never blocks.
POSIX Shared Memory
SeveralIPCmechanisms are available forPOSIXsystems, including shared memory and message passing. Here, we explore thePOSIX APIfor shared memory.
POSIXshared memory is organized using memory-mapped f i les, which associate the region of shared memory with a f i le. A process must f i rst create a shared-memory object using theshm open()system call, as follows:
fd = shm open(name, O CREAT | O RDWR, 0666);
The f i rst parameter specif i es the name of the shared-memory object. Processes that wish to access this shared memory must refer to the object by this name.
The subsequent parameters specify that the shared-memory object is to be cre-ated if it does not yet exist (O CREAT) and that the object is open for reading and writing (O RDWR). The last parameter establishes the f i le-access permissions of the shared-memory object. A successful call toshm open()returns an integer f i le descriptor for the shared-memory object.
Once the object is established, theftruncate()function is used to conf i gure the size of the object in bytes. The call ftruncate(fd, 4096);
sets the size of the object to 4,096 bytes.
Finally, themmap()function establishes a memory-mapped f i le containing the shared-memory object. It also returns a pointer to the memory-mapped f i le that is used for accessing the shared-memory object.
The programs shown in Figure 3.16 and Figure 3.17 use the producer– consumer model in implementing shared memory. The producer establishes a shared-memory object and writes to shared memory, and the consumer reads from shared memory.
Mach Message Passing
As an example of message passing, we next consider the Mach operating system. Mach was especially designed for distributed systems, but was shown to be suitable for desktop and mobile systems as well, as evidenced by its inclusion in the macOSand iOSoperating systems, as discussed in Chapter 2.
The Mach kernel supports the creation and destruction of multiple tasks, which are similar to processes but have multiple threads of control and fewer associated resources. Most communication in Mach—including all inter-task communication—is carried out by messages. Messages are sent to, and received from, mailboxes, which are called ports in Mach. Ports are f i nite in size and unidirectional; for two-way communication, a message is sent to one port, and a response is sent to a separate reply port. Each port may have multiple senders, but only one receiver. Mach uses ports to represent resources such as tasks, threads, memory, and processors, while message passing provides an object-oriented approach for interacting with these system resources and services. Message passing may occur between any two ports on the same host or on separate hosts on a distributed system.
Associated with each port is a collection of port rights that identify the capabilities necessary for a task to interact with the port. For example, for a task to receive a message from a port, it must have the capability MACH PORT RIGHT RECEIVEfor that port. The task that creates a port is that port’s owner, and the owner is the only task that is allowed to receive messages from that port. A port’s owner may also manipulate the capabilities for a port.
This is most commonly done in establishing a reply port. For example, assume that task T1 owns port P1, and it sends a message to port P2, which is owned by task T2. If T1 expects to receive a reply from T2, it must grant T2 the rightMACH PORT RIGHT SENDfor port P1. Ownership of port rights is at the task level, which means that all threads belonging to the same task share the same port rights. Thus, two threads belonging to the same task can easily communicate by exchanging messages through the per-thread port associated with each thread.
When a task is created, two special ports—the Task Self port and the Notify port—are also created. The kernel has receive rights to the Task Self port, which allows a task to send messages to the kernel. The kernel can send notif i cation of event occurrences to a task’s Notify port (to which, of course, the task has receive rights).
Themach port allocate()function call creates a new port and allocates space for its queue of messages. It also identif i es the rights for the port. Each port right represents a name for that port, and a port can only be accessed via a right. Port names are simple integer values and behave much likeUNIXf i le descriptors. The following example illustrates creating a port using thisAPI:
mach port t port; // the name of the port right mach port allocate( mach task self(), // a task referring to itself MACH PORT RIGHT RECEIVE, // the right for this port &port); // the name of the port right Each task also has access to a bootstrap port, which allows a task to register a port it has created with a system-wide bootstrap server. Once a port has been registered with the bootstrap server, other tasks can look up the port in this registry and obtain rights for sending messages to the port.
The queue associated with each port is f i nite in size and is initially empty.
As messages are sent to the port, the messages are copied into the queue. All messages are delivered reliably and have the same priority. Mach guarantees that multiple messages from the same sender are queued in f i rst-in, f i rst-out (FIFO) order but does not guarantee an absolute ordering. For instance, messages from two senders may be queued in any order.
Mach messages contain the following two f i elds:
•A f i xed-size message header containing metadata about the message, including the size of the message as well as source and destination ports.
Commonly, the sending thread expects a reply, so the port name of the source is passed on to the receiving task, which can use it as a “return address” in sending a reply.
•A variable-sized body containing data.
Messages may be either simple or complex. A simple message contains ordinary, unstructured user data that are not interpreted by the kernel. A complex message may contain pointers to memory locations containing data (known as “out-of-line” data) or may also be used for transferring port rights to another task. Out-of-line data pointers are especially useful when a message must pass large chunks of data. A simple message would require copying and packaging the data in the message; out-of-line data transmission requires only a pointer that refers to the memory location where the data are stored.
The functionmach msg()is the standardAPIfor both sending and receiving messages. The value of one of the function’s parameters—either MACH SEND MSGorMACH RCV MSG—indicates if it is a send or receive operation.
We now illustrate how it is used when a client task sends a simple message to a server task. Assume there are two ports—clientandserver—associated with the client and server tasks, respectively. The code in Figure 3.18 shows the client task constructing a header and sending a message to the server, as well as the server task receiving the message sent from the client.
Themach msg()function call is invoked by user programs for performing message passing.mach msg()then invokes the functionmach msg trap(), which is a system call to the Mach kernel. Within the kernel,mach msg trap() next calls the functionmach msg overwrite trap(), which then handles the actual passing of the message.
The send and receive operations themselves are f l exible. For instance, when a message is sent to a port, its queue may be full. If the queue is not full, the message is copied to the queue, and the sending task continues. If the port’s queue is full, the sender has several options (specif i ed via parameters tomach msg():
1. Wait indef i nitely until there is room in the queue.
2. Wait at most n milliseconds.
3. Do not wait at all but rather return immediately.
4. Temporarily cache a message. Here, a message is given to the operating system to keep, even though the queue to which that message is being sent is full. When the message can be put in the queue, a notif i cation message is sent back to the sender. Only one message to a full queue can be pending at any time for a given sending thread.
The f i nal option is meant for server tasks. After f i nishing a request, a server task may need to send a one-time reply to the task that requested the service, but it must also continue with other service requests, even if the reply port for a client is full.
The major problem with message systems has generally been poor perfor-mance caused by copying of messages from the sender’s port to the receiver’s port. The Mach message system attempts to avoid copy operations by using virtual-memory-management techniques (Chapter 10). Essentially, Mach maps the address space containing the sender’s message into the receiver’s address space. Therefore, the message itself is never actually copied, as both the sender and receiver access the same memory. This message-management technique provides a large performance boost but works only for intrasystem messages.
Windows
modularity to increase functionality and decrease the time needed to imple-ment new features. Windows provides support for multiple operating envi-ronments, or subsystems. Application programs communicate with these sub-systems via a message-passing mechanism. Thus, application programs can be considered clients of a subsystem server.
The message-passing facility in Windows is called the advanced local pro-cedure call (ALPC) facility. It is used for communication between two processes on the same machine. It is similar to the standard remote procedure call (RPC) mechanism that is widely used, but it is optimized for and specif i c to Windows.
(Remote procedure calls are covered in detail in Section 3.8.2.) Like Mach, Win-dows uses a port object to establish and maintain a connection between two processes. Windows uses two types of ports: connection ports and communi-cation ports.
Server processes publish connection-port objects that are visible to all pro-cesses. When a client wants services from a subsystem, it opens a handle to the server’s connection-port object and sends a connection request to that port.
The server then creates a channel and returns a handle to the client. The chan-nel consists of a pair of private communication ports: one for client–server messages, the other for server–client messages. Additionally, communication channels support a callback mechanism that allows the client and server to accept requests when they would normally be expecting a reply. When anALPCchannel is created, one of three message-passing techniques is chosen:
1. For small messages (up to 256 bytes), the port’s message queue is used as intermediate storage, and the messages are copied from one process to the other.
2. Larger messages must be passed through a section object, which is a region of shared memory associated with the channel.
3. When the amount of data is too large to f i t into a section object, anAPIis available that allows server processes to read and write directly into the address space of a client.
The client has to decide when it sets up the channel whether it will need to send a large message. If the client determines that it does want to send large messages, it asks for a section object to be created. Similarly, if the server decides that replies will be large, it creates a section object. So that the section object can be used, a small message is sent that contains a pointer and size information about the section object. This method is more complicated than the f i rst method listed above, but it avoids data copying. The structure of advanced local procedure calls in Windows is shown in Figure 3.19.
It is important to note that theALPCfacility in Windows is not part of the WindowsAPIand hence is not visible to the application programmer. Rather, applications using the WindowsAPIinvoke standard remote procedure calls.
When theRPCis being invoked on a process on the same system, theRPCis handled indirectly through anALPCprocedure call. Additionally, many kernel services useALPCto communicate with client processes.
Pipes
A pipe acts as a conduit allowing two processes to communicate. Pipes were one of the fist IPC mechanisms in early UNIX systems. They typically pro-vide one of the simpler ways for processes to communicate with one another, although they also have some limitations.
1. Does the pipe allow bidirectional communication, or is communication unidirectional?
2. If two-way communication is allowed, is it half duplex (data can travel only one way at a time) or full duplex (data can travel in both directions at the same time)?
3. Must a relationship (such as parent–child) exist between the communi-cating processes?
4. Can the pipes communicate over a network, or must the communicating processes reside on the same machine?
