Operating System Learning Notes (3) Process and Thread

Posted on 2021-10-14 Edited on 2024-11-19 In OS Waline:

Why do we need a process?
What is the process and what does it consist of?
How does the process solve the problem?

Concept and characteristics of the process

Process concept

In a multiprogram environment, allowing multiple programs to execute concurrently, they will lose their closeness and have the characteristics of intermittency and non-reproducibility.

To this end, the concept of process is introduced in order to better describe and control the execution of the program, and achieve the concurrency and sharing of the operating system (the two most basic characteristics).

In order for the program (including data) involved in concurrent execution to run independently, a special data structure must be configured for it, called the Process Control Block (PCB).

The system uses PCB to describe the basic situation and running state of the process, and then controls and manages the process.

Correspondingly, the process image (process entity) is composed of three parts: the program segment, the relevant data segment and the PCB.

The so-called creation process is actually the PCB that creates the process image, and the undo process is essentially the PCB that undoes the process.

It is worth noting that the process image is static, the process is dynamic, and the PCB is the only sign of the existence of the process.

From different perspectives, processes can have different definitions. A more typical definition is:
A process is an execution of a program.
A process is the activity that occurs when a program and its data are executed sequentially on a processor.

A process is a process in which a program with independent functions runs on a data set. It is an independent unit of the system for quota and scheduling. (This requires an accurate understanding of system resources, which refer to the “time” of processors, memory, and other devices serving a process. For example, processor resources are accurately understood as processor time slices)

Characteristics of the process

The process is proposed by the concurrent execution of multiple programs. It is two completely different concepts from the program. The basic characteristics of the process are proposed by comparing the sequential execution of a single program, which is also the most basic requirement for process management.

Dynamics. A process is an execution of a program. It has processes such as creation, activity, suspension, and termination, and has a certain life cycle. Dynamics is the most basic feature of a process.
Concurrency. Multiple process entities exist in memory at the same time and can run simultaneously for a period of time. Concurrency is an important feature of processes and an important feature of operating systems. ** The purpose of introducing processes is to enable programs to execute concurrently with programs of other processes **.
Independence. The process entity is a basic unit that can run independently, obtain resources independently and accept scheduling independently. ** Any program that has not established a PCB cannot participate in the operation as an independent unit **.
Asynchronous. Due to the mutual restriction of processes, the process has intermittent execution, that is, the process advances at an unpredictable speed. Asynchrony will lead to the non-reproducibility of the execution result. For this reason, the operating system must configure the corresponding process synchronization mechanism.
Structural. Each process is configured with a PCB to describe it. From a structural point of view, the process entity is composed of program segments, related data segments, and PCBs.

State and transition of processes

During the life cycle of the process, due to the mutual restrictive relationship between the processes in the system and the changes in the operating environment of the system, the state of the process is also constantly changing (a process will experience several different states). Usually, the process has 5 states., the first three are the basic states of the process.

Running state. The process is running on the processor. In a uniprocessor environment, at most one process is running at a time.
Ready state. The process has obtained all resources except the processor, and once it has obtained the processor, it can run immediately.
Blocked state. Also known as waiting state, the process is waiting for an event and pauses, such as waiting for a resource (** excluding the processor **) to be available or waiting for input and output to complete. Even if the processor is idle, the process cannot run.
Create state. The process is being created and has not yet been transferred to the ready state. The creation of a process usually requires multiple steps. First, apply for a blank PCB, and fill in some information about controlling and managing the process to the PCB; then the system allocates the necessary resources for the process to run, and finally changes the process to the ready state.
End state. The process is disappearing from the system, which may be due to the normal end of the process or an interruption for other reasons. When a process needs to end its operation, the system must first set the process to end state, and then further process resource release and recycling.

Note the distinction between the ready state and the waiting state. The ready state refers to the lack of only a processor and can run immediately as long as the processor resources are obtained, while the waiting state refers to the process needing other resources or waiting for an event.
The reason for separating the processor from other resources is that in the time-slice rotation mechanism of the time-sharing system, each process is assigned a time slice of several milliseconds, that is, the process gets the processor time very short and very frequently., the process actually switches to the ready state frequently during operation.

Organization of the process

A process is an independent running unit and the basic unit for quota and scheduling in the operating system. It consists of the following three parts, the core of which is the Process Control Block (PCB).

Process control block

When the process is created, the operating system will create a PCB for it, which will then be resident in memory, can be accessed at any time, and deleted at the end of the process. The PCB is a part of the process entity and the only sign of the existence of the process.

When the process executes, the system knows its current status and priority through its PCB, so that the operating system can control and manage it.

When scheduling a process, it is necessary to set the site where the process resumes operation according to the processor state information stored in its PCB, and find its program and data according to the memory address of the program and data in its PCB.
During the operation of the process, when it needs to synchronize, communicate or access files with the cooperating process, it also needs to access the PCB.
When the process is suspended for some reason, the processing and environment of its breakpoint need to be saved in the PCB

The system always controls the process through the PCB, that is, the system can only perceive the existence of the process through the PCB of the process.

PCB mainly includes process description information, process control and management information, quota list and processor related information.

Process description information. Process Identifier: Identifies each process, and each process has a unique identification number. User Identifier: The user to whom the process belongs. The process identifier is mainly used for sharing and protection services.
Process control and management information. Process current status: describes the status information of the process as the basis for processor scheduling. Process priority: describes the priority of the process to preempt the processor. Processes with higher priority can obtain the processor first.
quota list. Describes information about the memory address space or virtual address space, the list of files opened, or the device used.
Processor related information, also known as processor context, mainly refers to the values of each register in the processor. When a process is in the execution state, much of the processor’s information is in the registers. When a process is switched, the processor state information must be saved in the corresponding PCB so that when the process is re-executed, execution can continue from the breakpoint.

There are linking methods and indexing methods for organizing PCBs. The linking method links PCBs in the same state into a queue, and different states correspond to different queues. The PCBs of processes in a blocking state can also be arranged into multiple blocking queues according to their blocking reasons. The indexing method organizes processes in the same state into an index table, and the entries in the index table point to the corresponding PCB.

Program segment

A program segment is a piece of program code that can be scheduled to be executed by the CPU by the process scheduler. Note that a program can be shared by multiple processes, that is, multiple processes can run the same program.

Data segment

The data segment of a process can be the original data source of the program processing corresponding to the process, or it can be the intermediate or final result generated when the program is executed.

Process control

The main function of process control is to effectively manage all processes in the system. It has functions such as creating processes, canceling existing processes, and realizing process conversion.

In the operating system, the program segment used for process control is generally called primitive. The characteristic of primitive is that no interruption is allowed during execution, and it is an inseparable basic unit.

Creation of a process

Allows one process to create another process. At this time, the creator is also called the parent process, and the created process is called the child process. The child process can inherit the resources owned by the parent process. When the child process is revoked, the resources it obtained from the parent process should be returned to the parent process. In addition, when revoking the parent process, all its child processes are usually also revoked.
The process of creating a new process in the operating system is as follows (creation primitive):

Assign a unique process identifier to the new process and apply for a blank PCB (PCB is limited). If the PCB application fails, the process creation fails.
Allocate the resources needed by the process to run, such as memory, files, I/O devices, etc. (reflected in the PCB). These resources are either obtained from the operating system or only obtained from the parent process. If there are insufficient resources, it is not a creation failure, but a creation state, waiting for resources.
Initialize the PCB, including initialization flag information, initialization processor status information, initialization processor control information, and setting process priority.
If the process Ready Queue can accommodate the new process, insert the new process into the Ready Queue and wait to be scheduled for execution.

Termination of the process

The practices that cause the process to terminate mainly include: normal end, indicating that the task of the process has been completed and is ready to exit the operation; abnormal end, indicating that the process has encountered some kind of exception during operation, making the program unable to continue to run, such as storage area out of bounds, protection error, Illegal instruction, privileged instruction error, run timeout, arithmetic operation error, I/O failure, etc.; External intervention: refers to the process that stops running at the request of the outside world, such as operator or operating system intervention, parent process request, parent process termination Wait.
The termination primitive is as follows:

According to the terminated process identifier, retrieve the PCB of the process and read the status of the process from it.
If the terminated process is in a running state, immediately terminate the execution of the process and give the processor quota to other processes.
If the process has a descendant process, its descendant process shall be terminated.
Return all resources owned by the process, either to its parent process or to the operating system.
Remove the PCB from the queue where it is located.

Process blocking and wakeup

The process that is being executed, because some of the expected events do not occur, the process changes itself from the running state to the blocking state by calling the blocking primitive. It can be seen that when blocking, it is an active behavior of the process itself, and therefore only in the running state. The process may become blocked. The blocking primitive is as follows:

Find the PCB of the process to be blocked
Protect its site, change its state to blocking state, stop operation
Insert the PCB into the waiting queue for the corresponding event, and schedule the processor resources to other ready processes.

When the event expected by the blocked process occurs, the wake primitive is called by the process concerned.

Find the corresponding PCB in the waiting queue for the event
Remove it from the waiting queue and set its status to ready state
Insert the PCB into the Ready Queue and wait for dispatch.
The blocking primitive and the wake primitive must appear in pairs. If a Block primitive is called in a process, a corresponding warkup primitive must be arranged in the cooperating or other related process.

Process communication

Process communication refers to the exchange of information between processes. PV operations are low-level communication methods, and high-level communication methods refer to communication methods that transmit large amounts of data with high efficiency. There are three main types of high-level communication methods:

Shared storage

There is a shared space that can be directly accessed between communicating processes. Information exchange between processes is achieved by reading and writing to this shared space.

Synchronous mutual exclusion tools (such as PV operations) are required when reading or writing to a shared space.

Shared storage is divided into two types. The sharing of low-level methods is based on the sharing of data structures; the sharing of high-level methods is based on the sharing of storage areas.

The operating system is only responsible for providing shared storage space and synchronous mutual exclusion tools for communication processes, and data exchange is completed by user-arranged read and write instructions.

Message passing

Data exchange between processes is based on formatted messages. If there is no shared space that can be directly accessed between the communicating processes, the message passing method provided by the operating system must be used to realize process communication.

Data is exchanged through two primitives provided by the system to send and receive messages.

This method hides the details of communication and is currently the most widely used Inter-Process Communication method. In the microkernel operating system, the communication between the microkernel and the server adopts message passing.

Direct communication method, the sending process directly sends the message to the receiving process and hangs it on the message buffer queue of the receiving process. The receiving process retrieves messages from the message buffer queue.
Indirect communication method, the sending process sends the message to an intermediate entity, and the receiving process obtains the message from the intermediate entity, which is generally called “mailbox”.

Pipeline (shared file) communication

The so-called pipe refers to a shared file used to connect a read process and a write process to achieve communication between them, also known as a pipe file.

The sending process that provides input to the pipeline sends a large amount of data into the write pipeline in the form of a character stream, while the receiving process that receives the output of the pipeline receives data from the pipeline. In order to coordinate communication between two parties, the pipe-to mechanism must provide the ability to coordinate the following three aspects: mutual exclusion, synchronization, and determination of each other’s existence.

In essence, a pipeline is also a type of file, but unlike ordinary files, pipelines can overcome two problems of using file communication.

Limit pipe size. In practice, a pipe is a fixed-size buffer, which prevents its size from growing unchecked. There are also problems with using a single fixed buffer, such as when the pipe is full, in which case subsequent write calls to the pipe get blocked waiting for some data to be read.
The read process may also work faster than the write process. When the pipe is empty, a subsequent read call will be blocked by default.

Reading data from the pipeline can only be a one-time operation. Once the data is read, it frees up space for writing more data. The pipeline can only take half-duplex communication, that is, it can only be transported one way at a time.

Thread and multithreaded models

Basic concepts of threads

The purpose of introducing processes is to better enable multi-program concurrency, improve resource utilization and system throughput, while the purpose of introducing threads is to reduce the time and space overhead paid by the program during concurrent execution and improve the concurrency performance of the operating system.

The most direct understanding of threads is “lightweight process”. It is a basic CPU execution unit and the smallest unit of program execution flow. It consists of thread ID, program counter, register set, and stack.

Thread is an entity of a process, the basic unit of independent scheduling and allocation by the system, the thread itself does not have system resources, only a little essential resources in operation, but it can share all the resources with other threads belonging to the same process.

One thread can create and undo another thread, and multiple threads in the same process can execute concurrently.

Due to the mutual restriction between threads, threads will also be intermittent during operation. Threads also have three basic states: running, ready, and blocking.

After the introduction of threads, the connotation of processes has changed. Processes only serve as allocation units for system resources other than the CPU, while threads serve as allocation units for processors.

Comparison of threads and processes

Scheduling. Simply put, some things that require multiple processes can be done with multiple threads. In traditional operating systems, the basic unit of resource and independent scheduling is a process, and context switching is required for each scheduling, which is expensive. After the introduction of threads, the cost of thread switching is much lower than that of processes in the unit of independent scheduling of line cities.
Concurrency. Multiple threads in the same process can execute concurrently, improving system resource utilization and system throughput.
Own resources. A process is the basic unit of having resources in the system, while a thread does not have system resources (only one essential resource that can guarantee independent operation), but a thread can access the system resources of the process it belongs to, which is mainly manifested in belonging to the same process. All counties have the same address space.
Independence. Each process has its own address space and resources. In addition to sharing global variables, other processes are not allowed to access them. Threads in a process are invisible to other processes. Different threads in the same process are created to improve concurrency and cooperation with each other. They share the address space and resources of the process.
System overhead. To create or cancel a process, the system must allocate and recover PCB and other resources, such as Memory Space, I/O devices, etc., which is very expensive. Process context switching is involved when switching processes, while thread switching only needs to save and set a small amount of register content, which is very small overhead.
Support multi-processor system. For traditional single-threaded processes, no matter how many processors there are, the process can only run on one processor, while multi-threaded processes can run multiple threads in the process on multiple processors.

Properties of a thread

A process in a multi-threaded operating system is no longer a basic execution entity, but it still has an execution-related state. The so-called process in the “execution” state actually means that one of the threads in the process is executing.

The main properties available are as follows:

A thread is a lightweight entity that does not own system resources, but each thread has a unique identifier and a thread control block that records the field state such as registers and stacks for thread execution.
Different threads can execute the same program. That is, when the same service program is called by different users, the system can create them into different threads.
Each thread in the same process shares the resources owned by that process.
A thread is an independent scheduling unit of a processor. In a single-CPU computer, threads can use the CPU interchangeably, and in a multi-CPU system, each thread can occupy different CPUs.
After a thread is created, it begins its life cycle until it terminates.

Thread state and transitions

Execution state: The thread has acquired the processor and is running.

Ready state: The thread has various execution conditions, and it can be executed immediately after obtaining the CPU.
Blocked state: The thread is in a suspended state due to an event blocking its execution.

Thread organization and control

Thread control block

Similar to processes, the system also configures a thread control block TCB for each thread, usually including:

Thread identifier.
A set of registers. Includes program counters, status registers, and general purpose registers.
Thread running state. Used to describe what state the thread is in.
Priority.
Thread-specific storage area. Thread switching is used to save the scene.
stack pointer.

Threads in the same process completely share the address space and global variables of the process. Each thread can access each unit of the process address space, so one thread can read and write or even clear the stack of another thread.

Thread creation

There are functions (or system calls) to create and undo threads in the system

When the user program starts, usually only one thread called “initialization thread” is executing, and its main function is to create a new thread.

Termination of thread

When a thread completes its own task or is forced to terminate due to an exception during operation, the terminating thread calls the corresponding function to perform the termination operation. However, some threads (mainly system threads) will continue to run without being terminated once they are established.

Usually, the thread is terminated and does not immediately release the resources it occupies. Only when other threads in the process execute the separation function, the terminated thread is separated from the resources, and the resources can be used by other threads at this time.

Threads that are terminated but have not yet released resources can still be called by other threads to resume the terminated thread.

Thread implementation

The implementation of threads can be divided into two categories: user-level threads (ULT) and kernel-level threads (KLT).

User-level threads are actually commonly referred to as coroutines. In fact, they are also threads

User-level threads (coroutines)

In user-level threads, all work related to thread management is done by the application in user space, and the kernel is unaware of the existence of threads.

An application can be designed as a multi-threaded program by using the thread library. Usually, the application starts from a single thread and starts running in that thread. At any time it runs, a new thread running in the same process can be created by calling a derived routine in the thread library.

For a system with user-level threads, the scheduling is still process-by-process, and each process takes turns executing a time slice. Assuming that process A contains one user-level thread and process B contains 100 user-level threads, the running time of threads in process A will be 100 times that of threads in process B, so it is essentially unfair to threads.

Advantages of this implementation:
Thread switching does not need to go to kernel space, saving the cost of mode switching.

The scheduling algorithm can be process-specific, and different processes can choose different scheduling algorithms for their own threads according to their own needs.
The implementation of user-level threads is independent of the operating platform, and the code that manages threads is part of the user process.

Disadvantages of this implementation:
When a thread executes a system call, not only is the thread blocked, but all threads in the process are blocked.

Can not take advantage of multiprocessor, the kernel is allocated to a process at a time only one CPU, so only one thread in the process can execute.

Kernel level threads

Kernel-level threads also run under the support of the kernel, and all the work of thread management is also implemented in kernel space. Kernel space also sets up a thread control block for each kernel-level thread, according to which the kernel senses the existence of a thread and controls it.

Advantages of this implementation:

It can take advantage of multiprocessors, and the kernel can schedule multiple threads within a process at the same time.
If a thread in a process is blocked, the kernel can schedule other threads in that process to occupy the processor, and can also run threads in other processes.
The kernel supports threads with small data structures and stacks, thread switching is faster and less overhead.
The kernel itself can also use multi-threading technology.

Cons: ** Thread switching in the same process requires switching from User Mode to Kernel Mode **.

Combination mode

The kernel supports the creation, scheduling, and management of multiple kernel-level threads, while allowing user programs to establish, schedule, and manage user-level threads.

Some kernel-level threads correspond to multiple user-level threads, which is achieved by user-level threads to reuse kernel-level threads.

Multithreaded model

Some systems support both user threads and kernel threads. Due to the different connection methods between the two, the following three different multi-threading models have been formed.

Many-to-one model

Map multiple user-level threads to a kernel-level thread. These user threads generally belong to a single process. The scheduling and management of threads is done in user space. User threads need to be mapped to a kernel thread only when they need to access the kernel, and only one thread is allowed to be mapped at a time.
Advantages: Thread management is performed in user space, which is highly efficient
Disadvantages: If one thread blocks accessing the kernel, the entire process will be blocked; at any time, only one thread can access the kernel, and multiple threads cannot run on multiple processors at the same time.

One-to-one model

Map each user-level thread to a kernel-level thread.
Advantages: After each process is blocked, another kernel-level thread is allowed to be scheduled
Disadvantages: Every time a user thread is created, a kernel thread is required, which is expensive

Many-to-many model

Map n user-level threads to m kernel-level threads

Features: It overcomes the shortcomings of low concurrency in the many-to-one model, and overcomes the shortcomings of the one-to-one model that a user process occupies too many kernel-level threads and costs too much.