• Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.
  • This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.

preface

In the usual development process, we often use multithreading to solve problems. For example, we typically use multiple threads to execute asynchronously for network requests and other time-consuming operations. But what exactly is multithreading? What problem is multithreading supposed to solve? Is multithreading true concurrency? In this article, we will explore these questions. This article mainly explores the principle of multi-threading, leaving the specific use for later exploration.

Threads and processes

  • Process: A process is only in the system can run independently and as the basic unit of resource allocation, it is composed of a set of machine instructions, data and stack, is an entity can run independently.
  • Thread: A thread is the basic unit of a system that runs and schedules independently. A thread is smaller than a process and has almost no system resources.

We have heard many versions of the definition of processes and threads, but it is not very helpful to understand threads and processes. Why don’t threads own resources, but processes do? There are many similarities between the two at run time, so why introduce threads after processes? Let’s explore it together.

1.1 Operating System Overview

Before exploring threads and processes, let’s take a look at the operating system. Operating system is a connection user and computer hardware system interface, through the operating system, users can more convenient, fast, safe and reliable control of computer hardware and run their own programs. Its function can refer to the following figure:

There are many types of operating systems, but in general the goals include efficiency, convenience, extensibility, and openness. The most important of these are effectiveness and convenience.

  • There are two aspects to effectiveness
    • Improve the utilization of system resources, such as cpus and I/O devices, to keep these resources busy.
    • Improve the system throughput, through reasonable organization of computer workflow, further improve the utilization of resources, shorten the program running cycle.
  • Convenience mainly means that the user can use the computer system more conveniently. For example, the machine code of 0 and 1 is needed at the beginning, then some packaged commands are used, and then the use of graphical user interface is used to make the computer easy to learn and use.

To achieve these goals, the operating system went through the process of manual operation -> single-channel batch system -> multi-channel batch system. There were also developments in time-sharing and real-time systems, but they were not related to the introduction of processes, so I won’t cover them here.

  • Manual operation mode: that is, at the beginning of the tape and paper type computer, manual loading and unloading operations are needed at this time, the utilization rate of resources and the execution efficiency of the program are relatively low.
  • Single channel batch processing system: With the development of computer technology, in order to improve resource utilization, people develop offline input/output mode. Single-channel batch processing system is the application of this method, a batch of jobs are offline input to tape, and equipped with a supervisor in the system, by the supervisor to control the execution of the job. Its processing process is as follows:

A single-channel batch system can place a batch of jobs on tape, which are then loaded into memory under the control of a monitor and executed by a computer. When one job is finished, the next job is executed until all jobs are finished. Because only one operation is maintained from beginning to end, this system is called a single-channel batch system. For example, the program runs like this:

  • Multichannel batch system: Single-channel batch system solved the problem of manual loading and unloading zone, but one can only perform a job, if the job runtime need I/O operations, so the CPU is idle, the same CPU, I/O is also free, which creates a free resources, and due to low speed I/O devices, CPU utilization significantly reduced, There will be unnecessary waiting for subsequent assignments. Therefore, a multichannel batch processing system was created to improve the utilization of resources.

The following is the operation of program A, program B, program C and program D to show the process:

As can be seen from the figure, when program A makes I/O requests, program C can start execution, and the UTILIZATION of CPU is also greatly improved. Two or more programs can use CPU for concurrent execution in the same time period.

The above brief introduction of the development of operating system, in fact, whether multi-channel batch system, or real-time, time-sharing system, have several characteristics, concurrency, sharing, virtual and asynchronous, of which concurrency is the most important feature, the other three characteristics are based on the premise of concurrency. Here’s a brief introduction to these features:

  • Concurrency is when two or more events occur at the same time. Another concept to distinguish is parallelism, which is when two or more events occur at the same time. In a multichannel batch system, it means that more than one program is running at the same time macroscopically at a time.
  • Sharing means that resources in the system can be shared by multiple concurrently executing processes (threads) in memory. The corresponding resources are called shared resources, which can be divided into mutually exclusive sharing mode and simultaneous access mode.
  • Virtuality refers to the transformation of a physical entity into several logical counterparts by some technique. The former is real, while the latter is virtual, allowing the user to feel that they exist, such as virtual memory.
  • Asynchronism is because in the process of concurrent execution, each process is not completed in a single flow, and some processes focus on CPU calculation, while others focus on I/O. It is likely that the job that enters memory first will be completed and the memory that enters it will be completed first. This is the asynchronism of the operating system.

1.2 Origin of processes and threads

Through the introduction of multi-channel batch processing system, it can be found that the utilization rate of CPU and other resources is indeed improved. However, if we look at the execution process of each program separately, the execution of the program is still sequential, that is, when THE CPU executes, THE I/O cannot be executed, and when the I/O request is made, the CPU is idle. If programs can be executed concurrently, resource utilization can be greatly improved.

Processes are introduced to solve such problems. After the process is introduced, the CPU computing program and I/O program each create a process, the two processes can be executed concurrently. Thus, the CPU and I/O devices can be started at the same time to achieve parallel work. In addition, each program can also be set up a process, after the establishment of the process, each program can also achieve concurrent execution, but also can improve the utilization of resources and system throughput.

In summary, the import process serves two purposes:

  • 1. Separate processes can be established for different programs to achieve concurrent execution of programs
  • 2, for the same program, can respectively establish CPU calculation and I/O program process, in order to achieve CPU calculation and I/O concurrency, reduce CPU idle.

Difference between process and program:

  • Structure features: the program refers to a group of computer can recognize the instructions, can not run independently, the program to run independently need to configure the process Control Block PCB(Progress Control Block); A process is an independent entity that contains program segments, program related data segments, and process control blocks (PCBS)

  • Dynamic: A program is an ordered set of instructions stored on a medium, such as a disk, that does not have dynamic properties. A process is essentially an execution of a process entity.

  • Concurrency: Multiple process entities can be stored in memory and run at the same time. Programs cannot run independently, let alone concurrently

  • Independence: Process entity is a basic unit that can operate independently, allocate resources independently and receive scheduling independently. The procedure does not establish PCB can not run independently.

  • Asynchrony: processes move at independent, unpredictable speeds; The program cannot run independently.

From the above, we can say that a process is an execution of a program, an activity that occurs when a program and its data are executed on a processor. During this activity, processes are allocated the necessary resources and are scheduled by the system. Thus we can understand the statement at the beginning of this article – processes are the system’s basic unit of resource allocation and scheduling.

Processes are introduced to enable concurrent execution of multiple programs, improve resource utilization and system throughput, and processes have independent resources. This also causes a problem, the system when operating processes, will cause a large space and time overhead, such as:

  • The creation process allocates necessary memory and other resources to it and establishes the corresponding PCB
  • To cancel a process, reclaim its resources and cancel the PCB
  • Before switching a process, save the CPU environment of the current process and set the CPU environment of the new process

In order to reduce this consumption of time and space, people thought of whether the two properties of the process could be treated separately, that is, as the basic unit of resource allocation, but not frequently scheduled and switched, and as the basic unit of scheduling and switching, but does not own resources. Therefore, the concept of threads was introduced.

Thread, as the basic unit of program running and system scheduling, has much less system overhead than process when it is created, cancelled and switched. Usually, a process can contain multiple threads. The differences between threads and processes are as follows:

  • System scheduling: process scheduling will cause process switching, which costs a lot. When the thread of the same process is switched, the process switching cost is not low, but when the thread of one process is switched to the thread of another process, it will also cause the process switching
  • Concurrency: Both processes and threads are concurrent. But introducing threads can improve concurrency even more. For example, a system is only one file handling process, if no threads are introduced, when the process is blocked, need to use other file handling process will need to wait, and after introducing the thread, multiple threads can exist in the process of file, even if the running threads blocked, can also have other threads continue to provide services, This improves file service quality and system throughput.
  • Owning resources: Processes have their own resources; Threads generally do not own resources, but can access the resources of the process they belong to. Threads belonging to the same process share the resources of the process.
  • System overhead: Process creation, cancellation, and switchover all require resource allocation or reclamation, as well as PCB creation or reclamation. Threads do not. So in terms of overhead, processes are much higher than threads.

1.3 Status of processes and threads

Both processes and threads have three basic states: ready, executing, and blocking. The three states are explained as follows:

  • Ready: When a process has allocated resources other than CPU, it can execute as soon as it gets another CPU. This state is called ready. The processes in this state form a queue, known as the ready queue.
  • Running: The process has acquired the CPU and the state in which the program is executing is called running.
  • Blocked: For some reason, the executing process can not continue to execute, so it abandons the CPU and is in the suspended state. That is, the process is blocked. This state is called the blocked state.

The transformation diagram of the three states is as follows:

For administrative purposes, there are also two common states, created and terminated

  • Creation state: The creation state means that the process has been successfully created (PCB successfully created), but has not entered the memory and cannot be scheduled. At this moment, the process is in the creation state. Once it enters the memory, the process is in the ready state
  • Termination status: when the end of a process of natural, or unable to overcome the error, or by the system and other have to terminate power process termination, terminate the process into the state, the process is unable to perform, but still keep a record in the operating system, until the other processes to complete the termination status after the process of information extraction, the operating system will be deleted the process.

The transformation diagram of the five states is as follows:

Second, resource snatch

In the previous section, we explored the origins and states of processes and threads, and found that threads are in many ways very similar to traditional processes, except that they don’t own resources. In subsequent explorations, we focused on threads.

Threads of asynchrony enables the resource utilization, and improving system throughput greatly, but in the process of asynchronous execution, the execution speed of different thread is not the same, so he took to the problem of critical resources resources plundered for example, we often see rob tickets problems, is a classic resources plundered. The following is shown in pseudocode:

db.ticketCount = 5; Ticket. Count = db.ticket; // See the current ticket quantity of passenger A's ticket step in thread A a.buuyticket (1); ticket.count = ticket.count - 1; db.ticketCount = ticket.count; // Write the remaining ticket step of passenger B into the database, in thread B b.buuyticket (1); ticket.count = ticket.count - 1; db.ticketCount = ticket.count; // Write the number of tickets left in the databaseCopy the code

If the above steps are carried out separately, the results are all 4, there is no problem; Even if you do it all together, if you do it sequentially, like A before B, or B after A, you get 3, which is what you would expect. However, if the following order is executed, the result is problematic:

A.buyTicket(1); // The count obtained by A is 5 b.box ticket (1); Ticket. count = ticket.count - 1; Tick. count-1 in A, the result is 4 tick. count = tick. count-1. TicketCount -1 in B, the result is 4 db.ticketCount = ticket.count; Db. ticketCount = ticket.count; // B writes database count to 4Copy the code

As can be seen from the above pseudocode, the final count written into the database is 4, but in fact, after two ticket purchases, the result should be 3, which is obviously not the result we expect, and this is the problem of multi-threaded resource grabbing.

In the example above, threads A and B work together to change the margin count of the ticket. This constitutes A grab by threads A and B for count, which is A shared resource. To prevent data corruption caused by resource grabbing, we need to ensure that A and B’s access to count is mutually exclusive. That is, when A accesses count, B cannot access it, and when B accesses count, A cannot access it. At this point, count becomes a critical resource, that is, a resource to which the processes have mutually exclusive access.

Third, thread safety

Resource snatching, as described in the previous section, has the greatest potential to cause a serious problem, namely thread safety. As the example above, a multithreaded environment, due to the presence of concurrency, most likely cause data inconsistencies, and that in the actual development process will lead to serious consequences, such as display tickets and balance, but in fact tickets had been sold out, it also highlights the importance of thread safety.

In order to ensure thread safety, it is necessary to ensure that the access of each thread to critical resources is mutually exclusive. There are now two ways to ensure mutually exclusive access to threads, atomic instructions and thread synchronization.

  • Atomic instruction: most systems will provide some single instruction atomic instruction, the execution of a single instruction will not be interrupted, so the use of atomic instruction is very convenient, but only suitable for relatively simple and specific occasions, for complex scenes atomic instruction is inadequate.
  • Thread synchronization: When one thread accesses a resource, other threads cannot. This atomizes access to the resource.

In fact, thread synchronization is to coordinate the execution sequence of multiple related threads, so that concurrent execution can effectively share resources and cooperate with each other. At present, the main way to achieve thread synchronization is locking. Each thread tries to acquire the lock before accessing the critical resource, and then it can access the critical resource. When access to the resource is complete, the lock needs to be released. When a lock is occupied, the thread waits until the lock is available again.

conclusion

This article introduces some of the basic concepts of multithreading, such as processes and threads, resource grabbing, and thread safety. There are many concepts that have not been described in this blog, such as the classification of locks and the cause of deadlocks, which will be explored in subsequent chapters. For the concept in this article, the description is incorrect, welcome to correct.