Introduction

This is a collection of my notes from operating systems lectures.

Process

A process is the fundamental unit of work (activity) managed by the operating system, competing for computer system resources to execute a program. A process establishes links to the necessary computer system resources and enables control over their state in relation to program execution. The state of a process can change, including the program's execution state and most resources associated with it. Changes in process execution may involve data segments, stack segments, CPU register states, etc. Thus, a process is the essential context needed to execute a program.

The concept of a process is tied to concurrent processing. Multiple processes (independent tasks) may exist within a system, making it crucial to maintain information on which resources are allocated for each task.

Components of a Process

Program

A program is a set of instructions and, in this sense, is an element of a process, located in its code segment (also known as the text segment). Generally, a program remains unchanged during execution.

Resource

A resource is any system element that may be required for processing. Examples include the processor, memory, or files (data). Common resources are associated with the hardware elements of a computer system. However, it is the operating system that defines an element as a resource through management structures and allocation, recovery procedures, etc.

Moreover, some resources are created by the operating system's kernel. Such resources are often called virtual, such as a file, a virtual input-output device provided by the OS. On a hardware level, this concept doesn’t exist—at that level, one might discuss disk sectors where data is stored.

Kernel Operations in Process and Resource Management

Process creation and deletion operations directly affect processes but also indirectly involve resources, as creating a process requires allocating specific resources. A process is initially created by another process and may share most resources with it.

Resource allocation and release operations create links between processes and resources.

Elementary input-output operations also involve resources but are unrelated to their allocation or release; they are access operations to allocated resources. Not all access operations to allocated resources require kernel support. For instance, memory access is handled at the machine level, with the kernel only engaged when irregularities are detected.

Interrupt handling procedures, in turn, respond to external events or certain internal states. They may indirectly cause changes in process or resource states, although these changes aren’t always directly triggered by the interrupt handling procedure. Due to the need for speed, the immediate effect of an interrupt handler may be to record an event, while the actual system response, which may change a process or resource state, occurs later.

Managers

For conceptual or design purposes, parts of the kernel code handling processes and resources are separated as managers. Thus, we refer to a Process Manager handling process functions and a Resource Manager managing resource states and process requests.

Process Manager - controls process states for efficient and safe shared resource use.

Resource Manager - allocates resources based on process tasks, system state, and overall system policy.

Process and Resource Descriptor

Process Descriptor (Process Control Block, PCB) - records the process state during monitoring and control by the process manager.

Resource Descriptor - stores information on the availability and occupancy of a given resource type.

Management requires data structures to track process and resource states, their connections, and resource needs.

A process state data structure is called a process descriptor or process control block. The collection of this information for all processes is known as the process table. Static tables are seldom used in modern systems because they limit the number of processes and waste memory if fewer processes are active.

Due to resource diversity, the term resource descriptor is conceptual rather than definitive, and the structure of resource descriptions can vary widely depending on the resource type. Often, this structure is shaped by decisions at the processor architecture level (e.g., memory) or design choices.

What is in a Process Descriptor?

The necessary information enabling proper process management can vary depending on the design objectives of the operating system or the adopted implementation solutions. For example, in systems for personal computers, the owner ID or accounting information may be unnecessary. Access rights may be implemented differently depending on the resource protection concept in use.

Some of this information is essential in every descriptor. The process state is needed to make decisions about the future of the process (e.g., process removal and resource release, swapping the process from physical memory to auxiliary memory, or vice versa). The program counter and register states are necessary to restore the context of a given process. Scheduling information for processor allocation allows for proper process sequencing and decision-making by the scheduler. Memory management information enables memory protection, specifically preventing the process from interfering with areas outside its address space. I/O state information, including data on allocated devices and lists of open files, allows the operating system to manage these resources, control access, and recover them after the process terminates.

Process States

Depending on the program’s execution status and resource availability, the following general process states can be distinguished:

New — forming the process, i.e., gathering the necessary resources for starting execution, except for the processor (CPU time quantum). After formation, it waits to be admitted to the ready queue.

Running — executing the process’s program instructions and resulting changes in the states of the relevant system resources.

Waiting — pausing the program’s instructions due to needing additional resources, awaiting data, or waiting for the environment to reach the appropriate state (e.g., external devices or other processes).

Ready — waiting for the allocation of a processor time quantum (all required resources except the processor are available).

Terminated — finishing program execution, releasing most resources, and waiting for the possibility of relaying termination information to other processes or the operating system’s kernel.

Remaining in the terminated state (called zombie in Unix-like systems) is due to retaining certain process information post-termination (e.g., exit status). Complete removal of the process could mean freeing memory and losing this information.

Process State Transition Cycle

Transition from the ready state to running depends on the decision of the process-scheduling module (processor scheduler), which is based on process priorities. If there is only one processing unit (processor) in the system, only one process can be in the running state, while the remaining processes are in other states (in particular, in the ready state).

Transitioning directly from running to ready indicates preemption of the process from the processor. Preemption can result from:

In a time-sharing system, a process receives only a time quantum to execute subsequent instructions. The time quantum is measured by a timer interrupt, and upon quantum exhaustion, a context switch occurs, and another process receives the next time quantum (round-robin scheduling).

In a system with dynamic priorities, the timer interrupt or other kernel-handled event marks times for recalculating process priorities. If a preemptive approach to processor allocation based on priority is used, the highest-priority process receives the processor.

What Comprises a Resource Descriptor?

Resource information can include various attributes, which may not be meaningful without considering the specific resource type or at least certain classes. Generally, a resource may be available in multiple units (e.g., memory), and information about these units must be in the descriptor.

Connections between resource units and the processes to which they are allocated or waiting are also important. In this model, it’s assumed that information on allocated resources is stored in the process descriptor, while information on allocation waits is stored in the resource descriptor; however, this assumption is more conceptual than implementational. In practice, information on connections may exist in both structures if required for management.

Another consideration is the implementation of the process queue. Processes can be connected in a queue using pointers in the process descriptor. Therefore, a pointer or ID of the next (or previous) process in the queue can be stored in the waiting process descriptor. The process list attribute in the resource descriptor can thus point to the head of such a queue, i.e., a pointer to the descriptor of the first process, and that descriptor will contain a pointer to the next process’s descriptor.

Resource Classification

Based on usage:

Based on recoverability:

Based on access mode:

To establish general rules for resource management, it is necessary to classify resources. Management methods depend largely on the resource’s classification.

Some resources can be recovered after a process ends, such as memory. However, other resources are consumed during processing, like energy (essential in portable devices) or processor time before a critical section (not the processor itself or processor time in general), which is important in real-time systems. The resources in these examples are not generated by system processes. However, data or synchronizing signals generated as a result of processing can be considered non-reusable resources.

If a resource can be recovered, the method of recovery may be crucial, especially for certain issues like deadlock. A preemptible resource can be taken away from a process (e.g., the CPU), while a non-preemptible resource must be returned by the process itself. From the system’s perspective, this means waiting until the process holding the resource reaches a state where it no longer needs it (for example, after printing, the process returns the printer, but not the paper or toner).

Some resources can be concurrently used by multiple processes; for instance, a program code segment can be read and executed by multiple processes simultaneously. There are also resources available in exclusive mode, accessible to only one process at a time (e.g., a printer or process descriptor in the process table).

Process Queues

Job queue: (Polish: kolejka zadań, English: job queue) - all system processes.

Ready queue: (Polish: kolejka procesów gotowych, English: ready queue) - processes ready to run, located in main memory.

Device queue: (Polish: kolejka do urządzenia, English: device queue) - processes waiting for I/O operations to complete.

Queue of processes waiting for synchronization signals: for example, processes waiting on a semaphore.

A process's state largely depends on the availability of system resources. Depending on resource availability, a process is either running or waiting (in states NEW, READY, WAITING). While waiting, a process enters a queue for the desired resource. Frequently, upon leaving one queue, it moves to another—such as leaving the device queue to enter the ready queue.

Queuing processes involves placing them on a specific list. As previously mentioned, process lists are built using special fields in the process table, where each process on the list has its next and/or previous process recorded.

In this context, the term job queue may seem inaccurate—it is more like a set or table of tasks.

Processor Allocation Queue Diagram

After leaving the running state (exiting the processor), depending on the reason for stopping, the process moves to one of the queues. After the time quantum expires, the process (in the ready state) simply goes to the end of the ready queue, and the next process is selected from the front of the queue for execution. Thus, the processor switches to the context of a new process. Frequent context switching with minimal waiting time in the ready queue allows processes to interact with the user in real time, giving the impression that only their tasks are being executed. Therefore, users do not experience discomfort even when system resources are actually shared among multiple concurrent processes.

If the process leaves the processor for reasons other than the end of the time quantum, it enters the waiting state, which involves placing it in a queue for a particular event. There can be many such queues, e.g., each external device or synchronization mechanism may have its own queue.

Context Switching

As previously mentioned, when one process leaves the running state, the processor is made available to another process, and a context switch occurs. Context switching involves saving the state of the process releasing the processor (saving context) and loading the state of another process (restoring context). The context generally includes the state of resources that one process releases for another to use. In the simplest case, this is the processor state, i.e., the contents of the registers. Certain registers in the processor do not form part of the process’s context but hold values defining the system state. Such values do not need to be saved or restored, but unrestricted modification of these registers by a process is not permitted.

This type of context occupies minimal memory space and is stored in the process descriptor. Context switching thus involves updating the relevant process descriptor with the context information of the process being removed from the processor, then loading the processor registers with appropriate values from the descriptor of the process to be executed next.

Context switching time is essentially wasted from the perspective of processor usage since no user program is executed during this time. To reduce switching time, processors often provide support for this operation through specific instructions or more complex mechanisms at the architectural level.

Scheduler (Polish: Planista)

Short-Term Scheduler (Polish: Planista krótkoterminowy, CPU Scheduler) - Manages the allocation of the CPU to ready processes.

Medium-Term Scheduler (Polish: Planista średnioterminowy) - Manages the swapping of processes between main memory and external storage (e.g., disk).

Long-Term Scheduler, Job Scheduler (Polish: Planista długoterminowy, planista zadań) - Manages loading new programs into memory, controls the number of tasks in the system, and selects tasks to balance resource utilization.

The question left unanswered is, "Which process will run next?" or "Which ready process will undergo a context switch?" This decision is the task of the short-term scheduler.

The general role of schedulers (scheduling programs) is to select processes from a set to optimize system processing. However, optimization criteria can vary widely.

In terms of resource utilization optimization, load balancing is discussed, specifically for the CPU and external devices. Such balancing enables optimal resource usage. Otherwise, bottlenecks may develop, such as with the CPU or an external device. Processes that primarily use the CPU (e.g., those requiring extensive computations) are called CPU-bound. Processes that spend most of their time waiting for input-output operations are called I/O-bound (e.g., a text editor). Selecting only processes from one of these groups can create bottlenecks in heavily used resources, thereby lowering the utilization of other resources. In interactive systems, response time is critical; too long a response time can lead to user impatience and irrational behavior.

In different types of systems, the role of each scheduler may vary. In interactive systems, the role of the long-term scheduler decreases (or even disappears), while the short-term scheduler's role increases. In batch systems, the opposite is true.

Process State Transition Cycle with Swapping

Context switching analysis shows that a process relinquishes the CPU, so the CPU state must be saved in a control block. Process swapping in memory means removing one process from memory to allocate memory to another. Resuming processing requires saving memory areas for later restoration. This data is written to a designated swap area on the disk or a swap file. Typically, a waiting process is removed from memory, but a ready process can also be removed. To differentiate process states in memory from those on the swap device, a process in memory is called active, while a process on the swap device is called suspended.

In the process state transition graph, in addition to states resulting from swapping, the roles of schedulers are considered. The decision to admit a new process to the system is made by the long-term scheduler (LS). The transition from the ready state to the running state results from a decision by the short-term scheduler (STS). The medium-term scheduler (MTS) handles swapping, deciding which processes to remove from memory and which to reload. Considering swapping, memory can be considered a preemptible resource. Without swapping, taking memory from a process would mean its removal, thus making memory a non-preemptible resource.

Process Handling

Creating a Process

Terminating a Process:

Basic operations on processes include creating, terminating, changing state, and changing priority. Not all process operations are available to applications.

Creating and terminating processes are available operations. A process is created by another process, establishing parent-child dependencies. In Unix-like systems, per the POSIX standard, the fork function is used, implemented in Linux through the more general clone function. In Windows 2000/XP systems, one of several functions is used: CreateProcess, CreateProcessAsUser, CreateProcessWithLogonW, or (in later versions) CreateProcessWithTokenW.

Process termination results either from the program’s end or external intervention. In POSIX-compliant systems, a process notifies the system of its end by calling exit or abort. The kill function is used to terminate a process by another process or by the OS kernel. In Windows 2000/XP, there are two functions: ExitProcess and TerminateProcess.

Process Handling Part 2

Suspending and Resuming a Process

Changing Priority:

Waiting for Process Termination:

There are no functions in the application interface that allow unrestricted process state changes. Suspend and resume operations (related to swapping) are available within the process manager but may be exposed for suspending and resuming processes. Their effect is to transition to the waiting or ready state, respectively. An expected event after suspension is a resume function call. In POSIX-compliant systems, this effect can be achieved by using the kill function with the appropriate signals. In Windows, such functions are available for threads.

Priority changes are also not always freely possible. In POSIX-compliant systems, the nice function only changes a part of the process priority, while the actual priority value depends on other factors. This will be discussed further under process scheduling.

Resource Operations

Basic resource operations may not be directly available to applications. Creating or deleting a descriptor is an internal matter for the manager. Resource unit allocation results from a process request, but often indirectly due to other operations (e.g., creating a process). Recovery of units typically follows process termination.

Threads

A thread (lightweight process, LWP) is an object within a heavyweight process, with its own control flow and shared resources allocated to the process, shared with other threads in that process:

The concept of a thread is associated with resource sharing. Each process (a heavyweight process, in contrast to a lightweight one or thread) receives resources from the appropriate manager and keeps them at its disposal. Resources allocated to a process are used for sequential execution of a program, but additional resource requests may arise during execution. If the requested resource is unavailable, the process is blocked (enters a wait state). However, another independent segment in the process may not require the requested resource for execution. While it would be possible to change the instruction sequence in the program and execute this independent segment earlier, another resource may be required for its execution. Resource availability depends on the entire system’s state, and it’s unknown which resources will be available when needed for a specific segment.

In a program, it’s helpful to identify such independent segments and inform the system that they can be executed in any order or even concurrently, depending on available resources. Such an isolated segment is referred to as a thread. A thread primarily uses resources allocated to the process, sharing them with other threads in the process. A resource that a thread competes for with other threads is the processor, as it is responsible for executing program segments. Each thread has its own control context, which includes the instruction pointer, processor register state, and stack. Each thread must have its own stack to store return addresses from subroutines and allocate local variables.

Thread Implementation

Kernel-Level Thread Implementation - At the kernel level, the operating system kernel creates appropriate structures (a control block) to maintain the thread state.

User-Level Thread Implementation - User-level threads involve structures related to thread states being created in the process's address space.

Creating additional threads within the same process and switching contexts between them is generally less costly than with heavyweight processes, as it requires fewer resources to be allocated or modified. This is because threads within the same process share most of the address space (data segment, code segment), open files, and signals, meaning no additional memory management actions are necessary. Threads can even be organized in such a way that the kernel is unaware of their existence, with thread descriptors maintained in the process's memory, and all operations performed in user mode.

Alternatively, kernel-managed threading, where the kernel maintains descriptors and handles context switching between threads, is also an option.

Regardless of the implementation method, providing adequate synchronization mechanisms for threads within a process is essential in multithreaded management.

Kernel-Level Thread Implementation

A thread has its own control block in the operating system kernel, which includes:

Features of kernel-level threading:

Managing threads at the kernel level (system mode) means all calls to thread handling mechanisms require kernel services, increasing the time cost. The kernel must also maintain thread control blocks (descriptors), which, if static tables are used, can constitute a significant memory cost.

On the other hand, awareness of threads in the process allows the kernel to manage resources more efficiently, improving their utilization.

User-Level Thread Implementation

The thread descriptor resides in a thread table in the memory of the given process (the kernel is unaware of threads).

Features of user-level threading:

Implementing threads via a user-level library increases context-switching speed but results in the kernel allocating processor time to processes without awareness of threads. Thus, if a process has more threads, the processor time per thread is reduced compared to a process with fewer threads.

A challenge arises if a process enters a wait state when one thread requests an I/O operation or gets stuck on some synchronization mechanism with other processes. The scheduler treats such a process as waiting until the operation completes, even though other threads (unknown to the kernel) could continue executing.

Some operating systems distinguish between user-mode and kernel-mode threads. In Solaris, a "thread" refers to a user-mode thread, while a kernel-mode thread is referred to as a "lightweight process." In Windows, the term "fiber" (lightweight thread) corresponds to a user-mode thread, while "thread" refers to a kernel-mode thread. This distinction allows certain kernel-mode threads to manage programs where user-mode threads switch without kernel knowledge. Kernel-mode threads can thus be considered virtual processors for user-mode threads.

Context Switching Between Threads

The context between two lightweight processes is switched by the kernel. Each lightweight process executes a user-mode thread (fiber), depicted by a continuous arrowed line. For each lightweight process, there is a current fiber. In executing the code of such a fiber, a function can be called to save the current context and then restore a different (previously saved) context, provided an appropriate descriptor for the restored context is available at the call point. Therefore, each lightweight process can potentially execute any of the fibers, symbolized by the dashed line.

Thread Management

Creating a thread:

Deleting a thread:

Pausing and resuming a thread:

Changing thread priority:

Waiting for a thread to finish:

Thread/Process Implementation in Linux

In the Linux kernel, threads are not distinguished from processes.

Processes can share resources such as:

Process descriptors (structured as struct task_struct) are stored in a bidirectional, cyclic task list.

In Linux, a child process is created using the clone function, which is also used to implement the fork function in the POSIX standard.

When creating a new process with clone, it’s possible to specify which resources of the parent process should be shared with the child. Depending on the scope of shared resources, the newly created process can be regarded as either a thread or a heavyweight process. Typical threads will share the address space, open files, and other file system information (such as the current directory, root directory tree) and signal handling procedures.

Thus, the distinction between heavyweight and lightweight processes is reduced to the scope of shared resources.

Process (Thread) States in the Linux System

Process (Thread) State Cycle in Linux

The state cycle in Linux is straightforward and aligns closely with the general process state model. The main difference is the separation of two waiting states — one responds to signals, and the other ignores them. TASK_STOP can also be considered a unique type of waiting state. A distinguishing feature in Linux is the lack of a distinct representation between the ready and running states in the process descriptor, even though they are, in fact, different states.

Process in Windows 2000/XP

A process serves as the execution environment for threads.

The structures used to describe a process include:

In Windows, a process gathers resources required by the threads it contains. Process information resides in the EPROCESS structure, which includes the main control block (KPROCESS). Both structures are accessible in kernel mode and contain numerous pointers to other structures (including those describing threads). Part of the process description — the process environment block (PEB) — is within the address space accessible in user mode.

Threads in Windows 2000/XP

Threads (not processes) compete for CPU time and are managed by the short-term scheduler.

Basic resources required for thread execution (e.g., memory) are allocated to the process and shared among all threads within that process. The most important resource allocated to each thread is the CPU. All processing and the resulting state changes occur within a thread. Thread descriptor structures are similar to those of processes.

Thread States in Windows 2000/XP

Thread State Cycle in Windows 2000/XP

In Windows, both the ready and standby states correspond to the ready state in general state-change models.