C191-Terms-Chapter-3 Flashcards
process
An instance of a program being executed by an OS. Ex: When a user opens a new application like a web browser or text editor, the OS creates a new process.
process control block (PCB)
The OS keeps track of each process using a process control block (PCB): A data structure that holds information for a process, including the current instruction address, the execution stack, the set of resources used by the process, and the program being executed.
The PCB is the concrete representation of a process.
new state
A newly created process is placed into the new state before the process is allowed to compete for the CPU.
Ex: The OS may want to regulate the number of processes competing for the CPU.
terminated state
A process is placed into the terminated state when execution can no longer continue but before the PCB is deleted.
Ex: The OS may want to examine the final state of a process that committed a fatal error.
suspended state
A process may be placed into the suspended state even though the CPU and all resources are available.
Ex: The OS may want to stop a process to allow debugging or to regulate performance.
context switch
The CPU is always running one process at a time. Multiple processes can share a single CPU by taking turns.
A context switch is the transfer of control from one process to another. Each time a p stops running to allow another one to resume, the OS must save all info about the stopped p. This info is restored when p gets to run again.
The info that needs to be saved is the CPU state, which consists of all values held in any CPU regs and hardware flags.
One of the regs is the pc, which determines the next instruction to execute after p is restored.
physical CPU
A real hardware instance of a CPU
virtual CPU
A CPU that the process assumes is available only to itself.
Structuring an application as processes allows independence from the:
Number of CPUs: A physical CPU is a real hardware instance of a CPU. Multiple processes may run on one physical CPU using a technique known as time sharing. Each process is given a virtual CPU: A CPU that the process assumes is available only to itself.
Type of CPU: A virtual CPU can be just an abstraction of the physical CPU or it can be software that emulates the behavior of a different CPU.
Benefits of virtual CPUs
Independence from the number and type of CPUs provides several crucial benefits:
Multi-user support: Multiple users, each represented by one or more separate processes, can share the same machine without being aware of each other.
Multi-CPU transparency: An app written to use multiple CPUs will run correctly, perhaps more slowly if only one CPU is available.
Portability: An application compiled for one type of CPU can run on a different CPU without being modified or even recompiled.
Using multiple cooperating processes instead of one has several important advantages:
The interfaces between the processes are simple and easy to understand.
Each process can be designed and studied in isolation.
The implementation reduces idle time by overlapping the execution of multiple processes.
Different processes can utilize separate CPUs, if available, thus speeding up the execution.
Two ways exist to organize all PCBs:
An array of structures. The PCBs are marked as free or allocated, which eliminates the need for any dynamic memory management. The main drawback is a lot of wasted memory space to maintain a sufficient number of PCB slots.
An array of pointers to dynamically allocated PCBs. The pointer array wastes little space and can be made much larger than the array of structures. The drawback is the overhead of dynamic memory management to allocate each new PCB and to free the memory when the process terminates.
waiting list
A waiting list is associated with every resource and contains all processes blocked on that resource because the resource is not available.
ready list (RL)
A list containing all processes that are in the ready state and thus are able to run on the CPU.
The RL also includes the currently running process. The RL maintains all processes sorted by their importance, which is expressed by an integer value called priority.
The RL can be a linked list where the priority of a process is the current position in the list. The RL can also maintain processes in different lists sorted by priorities.
process creation hierarchy
A graphical representation of the dynamically changing parent-child relationships among all processes. The process creation hierarchy changes each time a process is created or destroyed.
create process function
Allocates a new PCB, fills the PCB entries with initial values, and links the PCB to other data structures in the system:
destroy process function
Destroys a process by freeing the PCB data structure and removing any references to the PCB from the system.
Depending on the OS, the destroy function may also destroy all of the process’s descendants to prevent having “orphan” processes in the system.
The destruction of the entire hierarchy of descendants is accomplished by calling destroy(c) recursively on all children c of p.
The destroy() function performs the following steps:
- After calling destroy(c) on all child processes, remove p from either the RL or from the waiting list of a resource.
- Remove p from the list of the calling process’s children.
- Release all memory and other resources, close all files, and deallocate the PCB.
- Call the scheduler to choose the next p to run. The call must be made outside of the destroy(p) function to ensure that the scheduler executes only once, after the entire hierarchy of processes has been destroyed.
resource control block (RCB)
A data structure that represents a resource. Its fields include resource_description, state, and waiting_list.
request resource function
Allocates a resource r to a process p or blocks p if r is currently allocated to another process.
If r is currently free, the state of r is changed to allocated and a pointer to r is inserted into the list of other_resources of p.
If r is not free, the calling process p is blocked. p’s PCB is moved from the RL to the waiting_list of r. Since the calling process, p, is now blocked, the scheduler must be called to select another process to run.
release resource function
Allocates the resource r to the next process on the r’s waiting list. If the waiting list is empty, r is marked as free.
If r’s waiting_list has no processes then the state of r is changed to free and p continues executing.
If the waiting list of r is not empty then the process q at the head of the list is allocated r, the state of q is changed to ready, and q is moved from the waiting_list to RL.
Since a new process (q) is now on RL, the scheduler must be called to decide which process (p or q) should continue to run.
scheduler function
determines which process should run next and starts the process. The scheduler function is called at the end of each of the process and resource management functions: create, destroy, request, and release.
Assuming the RL is implemented as a priority list, the scheduler() function performs the following tasks:
- Find the highest priority process q on the RL.
- Perform a context switch from p to q if either of the following conditions is met:
The priority of the running process is less than the priority of another process. This condition is true when the scheduler() is called from create() or release(). In these cases, process q could have a higher priority than p.
The state of the running process p is blocked. This is true when the scheduler() is called from request() and the resource is unavailable.
thread
A thread is an instance of executing a portion of a program within a process without incurring the overhead of creating and managing separate PCBs.
thread control block (TCB)
A data structure that holds a separate copy of the dynamically changing information necessary for a thread to execute independently.
The replication of only the bare minimum of information in each TCB, while sharing the same code, global data, resources, and open files, is what makes threads much more efficient to manage than processes.
independent process
If it does not share data with any other processes executing in the system.
cooperating process
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.
interprocess communication (IPC)
The 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.
shared memory
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.
message passing
In the message-passing model, communication takes place by means of messages exchanged between the cooperating processes.
browser process
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, so several renderer processes may be active at the same time.
plug-in process
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.
sandbox
A contained environment (e.g., a virtual machine).
Renderer processes run in a sandbox, which means that access to disk and network I/O is restricted, minimizing the effects of any security exploits.
unbounded buffer
Places no practical limit on the size of the buffer. The consumer may have to wait for new items, but the producer can always produce new items.
bounded buffer
Assumes a fixed buffer size. In this case, the consumer must wait if the buffer is empty, and the producer must wait if the buffer is full.
producer
A process role in which the process produces information that is consumed by a consumer process.
consumer
A process role in which the process consumes information produced by a producer process.
communication link
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.
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
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 a message to process P.
receive(Q, message)—Receive a message from process Q.
symmetry addressing
Both the sender process and the receiver process must name the other to communicate.
asymmetry in addressing
Here, only the sender names the recipient; the recipient is not required to name the sender. In this scheme, the send() and receive() primitives are defined as follows:
send(P, message)—Send a message to process P.
receive(id, message)—Receive a message from any process. The variable id is set to the name of the process with which communication has taken place.
The disadvantage of symmetry and asymmetry addressing
the limited modularity of the resulting process definitions. Changing the identifier of a process may necessitate examining all other process definitions.
All references to the old identifier must be found so that they can be modified to the new identifier.
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.
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() and receive() primitives are defined as follows:
send(A, message)—Send a message to mailbox A.
receive(A, message)—Receive a message from mailbox A.
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.
rendezvous
When both send() and receive() are blocking, we have a rendezvous between the sender and the receiver.
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 a finite length of 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 finite, however. If the link is full, the sender must block it until space is available in the queue.
Unbounded capacity
The queue’s length is potentially infinite; thus, any number of messages can wait in it. The sender never blocks.
blocking
In interprocess communication, a mode of communication in which the sending process is blocked until the message is received by the receiving process or by a mailbox and the receiver blocks until a message is available. In I/O, a request that does not return until the I/O completes.
nonblocking
A type of I/O request that allows the initiating thread to continue while the I/O operation executes.
In interprocess communication, a communication mode in which the sending process sends the message and resumes operation and the receiver process retrieves either a valid message or a null if no message is available.
In I/O, a request that returns whatever data is currently available, even if it is less than requested.
synchronous
In interprocess communication, a mode of communication in which the sending process is blocked until the message is received by the receiving process or by a mailbox and the receiver blocks until a message is available. In I/O, a request that does not return until the I/O completes.
asynchronous
In I/O, a request that executes while the caller continues execution.
advanced local procedure call
The message-passing facility in Windows is called the advanced local procedure 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 specific to Windows.
Like Mach, Windows uses a port object to establish and maintain a connection between two processes. Windows uses two types of ports: connection ports and communication ports.
When an ALPC channel is created, one of three message-passing techniques is chosen:
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.
Larger messages must be passed through a section object, which is a region of shared memory associated with the channel.
When the amount of data is too large to fit into a section object, an API is available that allows server processes to read and write directly into the address space of a client.
pipe
A pipe acts as a conduit allowing two processes to communicate. Pipes were one of the first IPC mechanisms in early UNIX systems. They typically provide one of the simpler ways for processes to communicate with one another, although they also have some limitations.
Ordinary pipes
Ordinary pipes allow two processes to communicate in standard producer-consumer fashion: the producer writes to one end of the pipe (the write end) and the consumer reads from the other end (the read end).
As a result, ordinary pipes are unidirectional, allowing only one-way communication. If two-way communication is required, two pipes must be used, with each pipe sending data in a different direction.
An ordinary pipe cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it creates via fork().
anonymous pipes
Ordinary pipes on Windows systems are termed anonymous pipes, and they behave similarly to their UNIX counterparts: they are unidirectional and employ parent-child relationships between the communicating processes.
In addition, reading and writing to the pipe can be accomplished with the ordinary ReadFile() and WriteFile() functions.
The Windows API for creating pipes is the CreatePipe() function, which is passed four parameters. The parameters provide separate handles for (1) reading and (2) writing to the pipe, as well as (3) an instance of the STARTUPINFO structure, which is used to specify that the child process is to inherit the handles of the pipe. Furthermore, (4) the size of the pipe (in bytes) may be specified.
Named pipes
Named pipes provide a much more powerful communication tool. Communication can be bidirectional, and no parent-child relationship is required.
Once a named pipe is established, several processes can use it for communication. In fact, in a typical scenario, a named pipe has several writers.
Additionally, named pipes continue to exist after communicating processes have finished. Both UNIX and Windows systems support named pipes, although the details of implementation differ greatly.
Named pipes on UNIX
Named pipes are referred to as FIFOs in UNIX systems. Once created, they appear as typical files in the file system.
A FIFO is created with the mkfifo() system call and manipulated with the ordinary open(), read(), write(), and close() system calls. It will continue to exist until it is explicitly deleted from the file system.
Although FIFOs allow bidirectional communication, only half-duplex transmission is permitted. If data must travel in both directions, two FIFOs are typically used. Additionally, the communicating processes must reside on the same machine.
Named pipes on Windows
Named pipes on Windows systems provide a richer communication mechanism than their UNIX counterparts.
Full-duplex communication is allowed, and the communicating processes may reside on either the same or different machines.
Additionally, only byte-oriented data may be transmitted across a UNIX FIFO, whereas Windows systems allow either byte- or message-oriented data. Named pipes are created with the CreateNamedPipe() function, and a client can connect to a named pipe using ConnectNamedPipe().
Communication over the named pipe can be accomplished using the ReadFile() and WriteFile() functions.
message
In networking, a communication, contained in one or more packets, that includes source and destination information to allow correct delivery.
In message-passing communications, a packet of information with metadata about its sender and receiver.
port
A communication address; a system may have one IP address for network connections but many ports, each for a separate communication.
In computer I/O, a connection point for devices to attach to computers. In software development, to move code from its current platform to another platform (e.g., between operating systems or hardware systems). In the Mach OS, a mailbox for communication.
bootstrap port
In Mach message passing, a predefined port that allows a task to register a port it has created.
bootstrap server
In Mach message passing, a system-wide service for registering ports.
connection port
In Windows OS, a communications port used to maintain connection between two processes, published by a server process.
communication port
In Windows OS, a port used to send messages between two processes.
section object
The Windows data structure that is used to implement shared memory.
multicore
Multiple processing cores within the same CPU chip or within a single system.
concurrency
A concurrent system supports more than one task by allowing all the tasks to make progress.
parallelism
A parallel system can perform more than one task simultaneously. Thus, it is possible to have concurrency without parallelism.
Before the advent of multiprocessor and multicore architectures, most computer systems had only a single processor, and CPU schedulers were designed to provide the illusion of parallelism by rapidly switching between processes, thereby allowing each process to make progress. Such processes were running concurrently, but not in parallel.
Identifying tasks
A challenge for multicore systems.
This involves examining applications to find areas that can be divided into separate, concurrent tasks. Ideally, tasks are independent of one another and thus can run in parallel on individual cores.
Balance
A challenge for multicore systems.
While identifying tasks that can run in parallel, programmers must also ensure that the tasks perform equal work of equal value.
In some instances, a certain task may not contribute as much value to the overall process as other tasks. Using a separate execution core to run that task may not be worth the cost.
Data splitting
A challenge for multicore systems.
Just as applications are divided into separate tasks, the data accessed and manipulated by the tasks must be divided to run on separate cores.
Data dependency
A challenge for multicore systems.
The data accessed by the tasks must be examined for dependencies between two or more tasks. When one task depends on data from another, programmers must ensure that the execution of the tasks is synchronized to accommodate the data dependency.
Testing and debugging
A challenge for multicore systems.
When a program is running in parallel on multiple cores, many different execution paths are possible. Testing and debugging such concurrent programs is inherently more difficult than testing and debugging single-threaded applications.
Data parallelism
Focuses on distributing subsets of the same data across multiple computing cores and performing the same operation on each core.
Task parallelism
Involves distributing not data but tasks (threads) across multiple computing cores. Each thread is performing a unique operation.
Different threads may be operating on the same data, or they may be operating on different data.
An example of task parallelism might involve two threads, each performing a unique statistical operation on the array of elements.
The threads again are operating in parallel on separate computing cores, but each is performing a unique operation.
user threads
User threads are supported above the kernel and are managed without kernel support.
kernel threads
Kernel threads are supported and managed directly by the operating system. Virtually all contemporary operating systems—including Windows, Linux, and macOS—support kernel threads.
Green threads
A thread library available for Solaris systems and adopted in early versions of Java—used the many-to-one model.
two-level model
One variation on the many-to-many model still multiplexes many user-level threads to a smaller or equal number of kernel threads but also allows a user-level thread to be bound to a kernel thread.
Many-to-many model
Multiplexes many user-level threads to a smaller or equal number of kernel threads.
The number of kernel threads may be specific to either a particular application or a particular machine (an application may be allocated more kernel threads on a system with eight processing cores than on a system with four cores).
Many-to-one model
Maps many user-level threads to one kernel thread. Thread management is done by the thread library in user space, so it is efficient.
However, the entire process will block if a thread makes a blocking system call. Also, because only one thread can access the kernel at a time, multiple threads are unable to run in parallel on multicore systems.
Very few systems continue to use the model because of its inability to take advantage of multiple processing cores, which have now become standard on most computer systems.
One-to-one model
Maps each user thread to a kernel thread. It provides more concurrency than the many-to-one model by allowing another thread to run when a thread makes a blocking system call. It also allows multiple threads to run in parallel on multiprocessors.
The only drawback to this model is that creating a user thread requires creating the corresponding kernel thread, and a large number of kernel threads may burden the performance of a system.
Linux and Windows OSs use this model.
signal
Used in UNIX systems to notify a process that a particular event has occurred. A signal may be received either synchronously or asynchronously, depending on the source of and the reason for the event being signaled.
All signals, whether synchronous or asynchronous, follow the same pattern:
A signal is generated by the occurrence of a particular event.
The signal is delivered to a process.
Once delivered, the signal must be handled.
A signal may be handled by one of two possible handlers:
- A default signal handler.
- A user-defined signal handler.
default signal handler
The signal handler that receives signals unless a user-defined signal handler is provided by a process.
A handler that the kernel runs when handling that signal.
user-defined signal handler
The signal handler created by a process to provide non-default signal handling.
The default signal handler can be overridden by a user-defined signal handler that is called to handle the signal.
Signals are handled in different ways. Some signals may be ignored, while others (for example, illegal memory access) are handled by terminating the program.
asynchronous procedure calls (APCs)
The APC facility enables a user thread to specify a function that is to be called when the user thread receives a notification of a particular event.
As indicated by its name, an APC is roughly equivalent to an asynchronous signal in UNIX.
However, whereas UNIX must contend with how to deal with signals in a multithreaded environment, the APC facility is more straightforward, since an APC is delivered to a particular thread rather than a process.
Examples of synchronous signals:
include illegal memory access and division by 0. If a running program performs either of these actions, a signal is generated.
Synchronous signals are delivered to the same process that performed the operation that caused the signal.
Examples of asynchronous signals:
When a signal is generated by an event external to a running process, that process receives the signal asynchronously.
Examples of such signals include terminating a process with specific keystrokes (such as <control><C>) and having a timer expire. Typically, an asynchronous signal is sent to another process.</C></control>
Thread cancellation
Involves terminating a thread before it has completed. For example, if multiple threads are concurrently searching through a database and one thread returns the result, the remaining threads might be canceled.
target thread
A thread that is to be canceled. Cancellation of a target thread may occur in two different scenarios:
Asynchronous cancellation. One thread immediately terminates the target thread.
Deferred cancellation. The target thread periodically checks whether it should terminate, allowing it an opportunity to terminate itself in an orderly fashion.
Asynchronous cancellation
One thread immediately terminates the target thread.
Deferred cancellation
The target thread periodically checks whether it should terminate, allowing it an opportunity to terminate itself in an orderly fashion.
cancellation point
The default cancellation type is deferred cancellation. However, cancellation occurs only when a thread reaches a cancellation point.
Most of the blocking system calls in the POSIX and standard C library are defined as cancellation points, and these are listed when invoking the command man pthreads on a Linux system.
For example, the read() system call is a cancellation point that allows cancelling a thread that is blocked while awaiting input from read().
cleanup handler
A function that allows any resources a thread has acquired to be released before the thread is terminated.
Pthread function that’s invoked when a thread is canceled. This function allows any resources a thread may have acquired to be released before the thread is terminated.
thread-local storage (or TLS)
Threads belonging to a process share the data of the process. Indeed, this data sharing provides one of the benefits of multithreaded programming.
In some circumstances, each thread might need its own copy of certain data, and such data is called thread-local storage.
lightweight process
An intermediate data structure between the user and kernel threads.
To the user-thread library, the LWP appears to be a virtual processor on which the application can schedule a user thread to run.
Each LWP is attached to a kernel thread, and it is kernel threads that the operating system schedules to run on physical processors.
If a kernel thread blocks (such as while waiting for an I/O operation to complete), the LWP blocks as well. Up the chain, the user-level thread attached to the LWP also blocks.
scheduler activation
It works as follows: The kernel provides an application with a set of virtual processors (LWPs), and the application can schedule user threads onto an available virtual processor. Furthermore, the kernel must inform an application about certain events.
upcall
Used by the kernel to inform an application about certain events.
upcall handler
Upcalls are handled by the thread library with an upcall handler, and upcall handlers must run on a virtual processor.
signal
In UNIX and other operating systems, a means used to notify a process that an event has occurred.
