From a static point of view, an operating system is a collection of programs and tables. From a dynamic point of view, operating systems are processes that execute dynamically and concurrently. The concept of process is actually a product of the development of the concept of procedure. Therefore, the concept of “process” can be derived from analyzing the basic characteristics of the program.
Sequential program refers to that several operations in the program must be executed in a certain order, and there is a certain relationship between the data and state before and after each operation. In early programming, programs were usually executed sequentially.
In multiprogram system, the running environment of program has changed greatly. Mainly reflected in:
(1) Resource sharing. In order to improve the utilization rate of resources, the resources in the computer system are no longer used by one program, but by multiple programs.
(2) Concurrent execution or parallel execution of the program. Logically allowing multiple programs with different users to run in parallel; Allow parallel running between segments that perform different operations within a user program; Allows different programs within the operating system to run in parallel. Physically: multiple programs are stored in internal memory, and I/O devices are shared by multiple programs alternately; In the case of a multiprocessor system, multiple programs run on their own processors with overlapping execution times. In a uniprocessor system, the execution of a program is represented by a number of programs running interspersely on the processor.
In fact, in a multiprogram system, the parallel execution of programs and resource sharing complement each other. On the one hand, only when programs are allowed to execute in parallel, can there be the problem of resource sharing. On the other hand, only effective resource sharing can make concurrent execution of programs possible. In this way, the processing power of the computer system and the utilization rate of the machine can be enhanced. Concurrent operations actually work like this: Most segments simply require that operations be ordered in time, meaning that some operations must precede others, which is ordered, but some of them can be done simultaneously.
1. Definition and classification of processes
A process is an execution of a program that can be executed concurrently with other programs. A Process usually consists of a program, data, and a Process Control Block (PCB). PCB describes the basic condition of a process and is the only sign that a process exists.
The difference between a program and a process is that a program is a static sequence of instructions and a process is a set of resources reserved for the thread that executes the program.
Process can be divided into system process and user process according to different nature; Parent and child processes.
2. Process state model
2.1. Three-state model
The discontinuity of the process determines that the process has at least three states:
(1) Ready state. When the process has allocated all the necessary resources except CPU, as long as it can obtain a processor, it can execute immediately, called the ready state of the process. In a system, more than one process can be in a ready state at the same time, usually in a queue called a ready queue.
(2) The execution state means that the process has acquired the processor and its program is being executed. In a uniprocessor system, only one process can be in execution state.
(3) Blocking state refers to the process due to the occurrence of an event (such as request I/O, application for buffer space, etc.) and suspended execution of the state, that is, the execution of the process is blocked, so called this suspension state is blocked, sometimes also known as “waiting” state, or “sleep” state. Blocking processes are usually placed in a queue, called a blocking queue.
The state of the process changes as it progresses and as the outside world changes. For example, a ready process is selected by the process scheduler to enter the execution state; A process in the execution state enters the wait state because it is waiting for an event to occur. A process in the wait state enters the ready state when it waits for an event to arrive. The states of processes can change dynamically, but a blocked process cannot directly enter the execution state, and a ready process cannot directly enter the blocking state. At any given moment, any process can be in one of these states and only one of them. The process status changes as follows:
(1) Running state → waiting state
When a process starts a peripheral while running, it becomes a state waiting for the peripheral to transmit information. When a process applies for resources (main storage space and peripheral devices cannot be satisfied) during operation, it becomes the waiting state. When a process fails during operation (program error or main memory read/write error), it becomes the waiting state.
(2) Waiting state → ready state
Wait for the process of peripheral device transmission to end after peripheral device work is finished. When the waiting resource can be satisfied (another process returns the resource), the waiting resource ends. After the fault queues, the process waiting for the intervention finishes waiting. Any process that finishes waiting must first become ready to be allocated to the processor before it can run.
(3) Running state → ready state
Forces a process to temporarily relinquish the processor when it has run out of time to use it, and also forces a running process to relinquish the processor when a more preferred process is running. When a process that is in the wait state for its own or external reasons relinquishes the processor, its state becomes ready.
(4) Ready state → running state
A process that is waiting to be allocated a processor. The system selects one of the ready processes according to a selected strategy and lets it occupy the processor. The selected process becomes runnable.
2.2. Five-state model
The five-state model of process introduces new state and termination state
3. Mutual exclusion and synchronization
3.1 Synchronization between processes
In an asynchronous environment, a group of concurrent processes send messages to each other, cooperate with each other, and wait for each other to make each process execute at a certain speed, which is called process synchronization. In other words, synchronization makes each process execute in a certain order and speed in an asynchronous environment.
3.2 Mutual exclusion between processes
One or more segments of a group of concurrent processes that share a common resource so that they must be executed in an interleaved order. That is, mutex ensures that a critical resource is accessed by only one process at a time.
3.3 critical resources
Some resources in the system can be used by multiple processes at the same time, and some resources, called Critical resources (CR), can be used by only one process at a time, such as printers, public variables, and tables.
3.4 Principles of critical area management
A Critical Section (CS) is the Section of a process that performs operations on Critical resources. The principles of mutually exclusive critical section management are as follows:
(1) Free to let in. If no process is in the critical area, if any process requests to enter the critical area, it is allowed to enter immediately.
(2) Busy is waiting. When an existing process enters its critical region, other processes trying to enter their own critical region must wait to ensure that all processes enter the critical region mutually exclusive.
(3) Limited wait. When several processes require to enter the critical area, one process should enter the critical area within a limited time, that is, they should not wait for each other and no one should enter the critical area;
(4) let the right wait. A process waiting to enter a critical section must release its CPU.
3.5. Semaphore mechanism
In 1965, Dutch scholar Dijkstra proposed the semaphore mechanism, which is an effective tool for process synchronization and mutual exclusion. 6) Integer semaphore and PV operation semaphore is an integer variable, and different values are assigned according to different control objects. Semaphores fall into two categories.
● Common semaphore: achieve mutual exclusion between processes, initial value = 1 or the number of resources.
● Private semaphore: synchronization between processes, initial value = 0 or a positive integer.
** The physical meaning of the semaphore S is: S≥0 represents the number of available resources, S < 0 its absolute value represents the number of processes in the blocking queue waiting for the resource. 支那
PV operation is a common method to implement process synchronization and mutual exclusion. PV operations are low-level communication primitives that are indivisible during execution. P applies for a resource, and V releases a resource.
4. Process communication and pipe procedure
4.1. Process communication
Communication refers to the exchange of information between processes. According to the content of communication, it can be divided into control information exchange and data exchange. The exchange of control information is called low-level communication, and the synchronization and mutual exclusion of processes are realized through semaphore communication, which belongs to low-level information. The exchange of data is called advanced communication. The types of advanced communication are shared storage systems and messaging systems and pipe communications. Advanced communication has direct communication and indirect communication.
4.2, monitor
Brinsh Hansen and Hoare proposed another synchronization mechanism, the tube process. A pipe is composed of some shared data, a set of operations on shared data that can be performed by concurrent processes, initial code, and access rights. That is, a set of procedures that share data and operate on it constitute a pipe. A process can call the pipe whenever it needs resources, and at most one process can actually enter the pipe at any one time. The rest have to wait. A pipe provides a mechanism that allows multiple processes to share abstract data types safely and efficiently.
4.3 Process scheduling and deadlocks
4.3.1 Process scheduling
Process scheduling is processor scheduling (also known as context transformation). Its main function is to determine which process to assign the processor to at what time. On some operating systems, a job is scheduled at high, medium, and low levels from submission to completion.
4.3.2 Scheduling method
There are two kinds of scheduling modes: deprivation mode and non-deprivation mode
- Non-deprivation mode: once a job or process occupies the processor, other processes cannot take the processor away from the process until the process itself enters the blocking state due to the invocation of primitive operations, or the time slice runs out and gives up the processor;
- The deprivation mode is: when the priority of a process in the ready queue is higher than that of the current executing process, the process scheduling immediately occurs and the processor is transferred.
4.3.3 Scheduling algorithm
(1) First Come and First Server (FCFS) scheduling algorithm, also known as First In and First Out (FIFO)
Ready queues are queued on a first-come-first-served basis.
(2) Priority number scheduling
The priority number reflects the priority of the process, and the ready queue is queued by priority number. There are two ways of prioritizing, static and dynamic. Static priority indicates that the priority of a process is determined before the process is executed and remains the same during the process execution, while dynamic priority can be changed during the process execution.
(3) Round Robin
Ready queues queue in FCFS mode. Each process does not occupy the processor for more than a specified time unit (time slice), if it does, it will release its occupied CPU and queue to the end of the ready queue, waiting for the next schedule. At the same time, the process scheduler dispatches the first process in the current ready queue.
4.3.4, deadlocks
A deadlock is when two or more processes wait indefinitely for each other to request resources already held by the other and cannot continue. Deadlocks are an error state that wastes system resources and can cause the entire system to crash. Therefore, deadlocks should be prevented and avoided as much as possible.
Deadlocks are caused by resource competition and illegal process sequence. The four necessary conditions for a deadlock are the mutual exclusion condition, the request hold condition, the inalienable condition and the loop condition.
Solve deadlocks strategy: deadlock handling strategy mainly has four kinds: the ostrich policy (i.e. ignoring strategy), prevention strategies (destruction of one of the four necessary conditions of deadlock), avoid strategy (dynamically allocate resources carefully, to avoid deadlock), detect and remove dead lock (once a deadlock occurs, the system not only can detect, also can remove).
4.4, thread
A thread is an entity in a process and a basic unit that is allocated and scheduled independently by the system. In operating systems where threading is introduced, there are usually several threads per process. A thread can share all the resources owned by a process with other threads belonging to the same process. Threads have many of the characteristics of traditional processes, called light-weight processes. Call a traditional Process a heavy-weight Process. A thread can create another thread, and multiple threads in the same process can execute concurrently. Threads also have three basic states: ready, running and blocking.