In the operating system, the concept of process and thread is set to describe the concurrent execution of program logic. This is an introductory article on processes and threads. The concepts of processes and threads are introduced from the following five aspects.

  • Process and thread definitions
  • A description of processes and threads in an operating system
  • Multi-layer scheduling of processes
  • Synchronization mechanism between processes/threads
  • Communication mechanism between processes/threads
  • How do I avoid deadlocks between processes and threads

One, process and thread definition

  • Process: A process is the basic unit of owning resources and scheduling in the operating system
  • Thread: Thread is the basic unit of scheduling in the operating system. Threads cannot own resources and can be regarded as lightweight threads.

Two, the operating system of the process and thread description

1. Process and thread Entities Description Processes and threads are running entities in the OS and are basic units of scheduling and dispatching.

  • OS defines PCBS (Proccess Control blocks) describing process entities
  • The OS defines the TCP Thread control block (TCP), which describes the Thread entity. The OS must create the PCB and TCP when creating a process or Thread. The content stored in PCB and TCP are similar in height. This paper only describes the specific content of PCB, and the related content of TCP can be compared. The main contents of PCB are as follows: (1) Process identifier, which is mainly used for the operating system and users to locate different processes, and is the unique identification of the process. (2) processor state, which saves the information related to the current processor register when process switchover occurs. Processor state information is also used to recover field information during process scheduling. (3) Process scheduling information, mainly saving the same statistics of service process scheduling. For example, the current process status, process priority, executed CPU time, waited CPU time, process blocking cause and other information. (4) Process control information: mainly saves information related to process execution, such as :(1) memory address of program and data, (2) synchronization and communication mechanism, (3) list of resources required by process and thread operation

2. State description of processes and threads

  • Created state: The state in which the process was created when the operating system allocated space such as PCB to the thread
  • Ready: After the process is created, it has obtained all required resources except the CPU
  • Execution: A process in the ready state switches to execution after obtaining the CPU time slice. When the process consumes all the time slices, it switches to the ready state to wait for the next time slice allocation.
  • Blocked: A process in the executing state. An event occurs that causes the process to suspend execution. The CPU execution time is abandoned and the process enters the blocked state. Such as competing for critical resources, waiting for IO and other events. A process in the blocked state will enter the ready state to wait for the CPU to allocate a time slice after obtaining the waiting resource.
  • ** Destruction state: After the ** process completes its execution logic, it enters the destruction state and reclaims memory and allocated resources.

Three, the process of multi-layer scheduling

Switching an executable file from a hard disk to an execution process in memory involves the following two layers of scheduling. (1) Job scheduling: Job scheduling is the process of scheduling an execution file from a hard disk to a process in memory. The process that has undergone this scheduling is in the ready state waiting to allocate CPU resources. There are many classical algorithms that can be used when multiple job requests are scheduled

  • First come, first served algorithm: Scheduling is performed in the order in which job requests are scheduled
  • Priority scheduling algorithm: Each job has a priority and is scheduled according to the priority of the job
  • Short Job finite algorithm: Finite scheduling of jobs with short execution times.

(2) Process scheduling: Process scheduling refers to the process in which the ready process queuing in the ready queue obtains CPU time slice resources. The process scheduling algorithm is the focus that needs to be introduced. It mainly includes two categories from a larger direction:

  1. Based on the priority scheduling algorithm, the scheduling algorithm is mainly divided into the following four concepts

    • Static priority scheduling: Static priority means that the priority assigned to the process is immutable throughout the run, and is initialized from start to finish.
    • Dynamic priority scheduling: The priority of process scheduling can change dynamically depending on the situation at run time. For example, giving priority to processes that queue too long. This will prevent the starvation process.
    • Preemptive scheduling: If the priority of the current executing process is less than that of the queued process, the current executing process will give up CPU time and exit the execution.
    • Non-preemptive scheduling: once the current process has acquired CPU execution time, it does not give up CPU time for priority reasons. Unless the execution is terminated or something unusual happens.

  2. Time slice based scheduling algorithm The time slice based scheduling algorithm arranges ready processes into a queue and allocates a specified time slice resource to each ready process in the queue. If the process is not finished within the specified time slice, the process is added to the end of the queue again to wait for the next time slice resource allocation. The above is just a general idea of scheduling algorithm based on time slice, which is too rough in the actual industrial scene. The following introduces a more commonly used scheduling algorithm of multi-level feedback queue with greater practical value

  • Multi-level feedback scheduling algorithm:
  1. It can be seen from the figure that the algorithm has N ready queues for scheduling. When the process enters the ready state, it enters the level 1 ready queue to wait for the CPU to allocate time slice resources. If the execution is not completed within the current time slice resource, it enters the level 2 ready queue. The subsequent scheduling process and so on.
  2. A process in a level 2 ready queue can schedule a CPU only if there are no processes in the level 1 ready queue.
  3. When scheduling from the advanced ready queue to the CPU, more time slice resources are acquired. TN>T3>T2>T1.

The advantages of multi-level feedback scheduling algorithm are generally reflected in the following three points:

  1. Suitable for short interactive tasks. Interactive tasks typically require very short execution times and can be completed in a level 1 queue, requiring very low response latency
  2. In the process of multi-level scheduling, short jobs can be scheduled in 1-2 time slices at most. Turnaround times are still short
  3. Long jobs can be rotated to advanced ready queues, which may result in more CPU execution time. Do not starve due to short work process, long work can not allocate CPU resources.

4. Synchronization mechanism between processes/threads

Synchronization between processes and between threads is basically the same. This article introduces the concept of synchronization using synchronization between threads and threads as an example.

  • The concept of thread synchronization: threads do not execute in isolation, but in an orderly and coordinated fashion.

  • The classic process synchronization problem:

    1. Consumer and producer issues The consumer thread and producer thread access a critical resource pool with a total size of N simultaneously. When the number of resources in the resource pool is N, the producer thread cannot add data to the resource pool, and the critical resource pool is considered full. When the number of resources in the resource pool is 0, the consumer thread cannot take data from the resource pool, and the critical resource pool is marked as empty. In such a scenario, three points need to be implemented: – Consumer thread and producer thread access to the critical resource pool is mutually exclusive. – When the critical resource pool is full, the producer thread’s data entry operation must be blocked and the data entry operation can be continued until the critical resource pool is not full. – When the critical resource pool is empty, the consumer thread’s data entry operation must be blocked and the data entry operation can be continued until the critical resource pool is not empty. Solution: Mutex and condition variables

    2. Dining for philosophers

    As can be seen from the picture above, five philosophers are sitting around a round table, with a chopstick to each philosopher’s right and left. When philosophers want to have a meal, they try to pick up the nearest chopstick. Hold chopsticks one by one like this. When the philosopher took a pair of chopsticks, he began to eat. When you’re done, put all your chopsticks back and start thinking about philosophy.So why construct such a philosopher’s dining scene? The main purpose is to build a deadlock scene caused by improper synchronization of threads. If philosophers pick up the chopsticks on their left side at the same time, when philosophy tries to pick up the chopsticks on the right side again, all philosophers are unable to get a chance to eat and fall into deadlock. This is also a deadlock problem in process synchronization. The solution to the deadlock in the philosopher’s problem above is (1) to allow a maximum of four philosophers to hold chopsticks on the same side at the same time (2) to allow a philosopher to hold two chopsticks at the same time, not just one. As you can see, the above solution is to avoid deadlock situations by setting restrictions.

    3. Reader-writer problem For a file, there are multiple threads reading and writing simultaneously. Under these conditions, access to files is required to be uncluttered. The reader thread and writer thread must meet the following requirements:

    • Access to files is mutually exclusive between the reader and writer threads
    • Access to files is mutually exclusive between writer threads
    • Access to files between reader threads does not require a mutex solution: read/write locks

How to avoid deadlocks between processes/threads

This section introduces deadlocks from the perspective of threads. Thread deadlocks are problems caused by improper thread synchronization. This section will analyze the causes of thread deadlocks, the necessary conditions of thread deadlocks, and the three aspects of avoiding thread deadlocks. 1. The causes of thread deadlocks are studied by philosophers’ dining problems

  • Competition for shared resources: the philosopher’s chopsticks are shared resources. There would be no deadlock problem if philosophers had a private pair of chopsticks.
  • Improper order of progress between processes: Competing for shared resources does not always result in a deadlock. In the philosopher’s dining problem, if we can avoid picking up the chopsticks on the same side at the same time, this running sequence can be avoided. Deadlock will not occur. Although processes compete for shared resources, deadlocks can be avoided by pushing them in the right order.

2. Necessary conditions for the occurrence of thread deadlocks There are four necessary conditions for a deadlock to occur. A deadlock can occur when all four conditions are met.

  • Mutually exclusive condition: a thread has exclusive access to resources. When it obtains resources, it monopolizes the resources and does not allow other threads to access the shared resources
  • A request and hold condition that does not release the occupied resource if a thread requests a new resource after it has acquired it
  • Without stripping conditions, a thread that has acquired a resource does not abandon the resource because other threads compete for it. It can only be used up or released voluntarily
  • Loop condition: when a deadlock occurs between threads, there must be a loop link between threads -> resources. For example, thread P1 waits for a resource occupied by thread P2, and thread P2 waits for a resource occupied by thread P1

3. Ways to avoid deadlocks

  • Deadlock prevention: Prevent deadlocks by breaking the conditions necessary to cause deadlocks
  • Deadlock avoidance: When allocating resources to a thread, calculate whether the thread is safe after the allocation. Resources are allocated if they are in the secure state, otherwise they are not allocated. A typical algorithm for avoiding deadlocks is the banker algorithm. This is a classic way to prevent deadlocks
  • Detect and contact deadlocks: This method does not provide any means of preventing or avoiding deadlocks when processes compete for resources. It only provides a mechanism for discovering deadlocks, and after the deadlocks are generated, the deadlocks are contacted by killing the thread.

Communication mechanism between processes/threads

Synchronization between processes/threads is actually a communication mechanism, but synchronization mechanism is only a small data communication. The communication mechanism described here deals with large data transfers. This section uses the communication mechanism between processes as an example

  • Shared storage system A shared storage system is a common storage space for multiple processes to communicate by modifying or reading the same area.
  • Messaging system A messaging system is a system in which processes exchange information through formatted data packets, most easily understood as computer network data packet exchange. Communication between applications on different computers is also a scenario of process communication
  • Pipeline communication A “pipeline” is a file that connects a reader process to a writer process for communication between them. A sending process that feeds a pipe (a shared file) a large amount of data into the pipe as a stream of characters, and a receiving process that receives output from the pipe reads a large amount of data.