CN1328877C - Sharing route realizing and sheduling method - Google Patents

Abstract

The invention relates to a thread realization and scheduling method in a data processing operation platform, and relates to a shared thread realization and scheduling technology which can avoid or reduce kernel thread switching, make full use of processor efficiency, and reduce system resource consumption. The method adopts the following steps: to complete the setting of the thread control block and the thread binding thread creation, start the thread activation of operation, accept the thread operation triggered by the event and transfer to the running state, complete the thread state switching, ready and run queue management, etc. Thread scheduling and clearing of thread data, release of thread ID, and exit of threads that adjust the number of system threads. The method of the invention fully reduces the switching time of threads; and without increasing the consumption of system resources, fully utilizes system resources and provides a huge number of thread mechanisms to ensure the consumption of threads in multi-thread programming.

Description

Shared thread implementation and scheduling methods

technical field

The invention relates to a method for realizing and scheduling a shared thread in a data processing operation platform. Specifically, it relates to a shared thread implementation and scheduling method that can avoid or reduce kernel thread switching, fully utilize processor efficiency, and reduce system resource consumption.

Background technique

In a typical multitasking operating system, the memory space of the system is divided into user space and kernel space by hardware. User programs can only run in the user space. When the kernel needs to be used, special trap instructions need to be executed. The traditional process multitasking system is based on such a structure. All the information of the process control structure is in the kernel space, and each process switching will involve access to the kernel space.

Multithreading technology allows a program to execute multiple tasks simultaneously and share resources in the process space. Unlike traditional multitasking operating systems that use processes as units, threads are lightweight entities, and a considerable part of the thread structure is in user space, allowing fast access. It is precisely because of this characteristic of threads that multithreading technology has been widely used. Compiling multithreaded programs can obtain the following benefits: make full use of the concurrent capabilities of multiprocessors to obtain excellent performance; improve the throughput and responsiveness of programs ; Reduce inter-process communication overhead and effectively use system resources; without modifying the program, it can be used on a single processor or multiple processors.

Threads are implemented by writing a thread library. Currently, there are two thread library implementation methods. The first method is to write a user-level library, which depends on existing kernel functions. The most important library calls are executed in user space; the second method is to write a kernel-level library. Most library calls run in kernel space and require system calls. support. Certain implementations of the POSIX standard fall into the first approach, while OS/2 and Win32 threads fall into the second. Since the operating system kernel only understands the process structure (there is a lightweight process LWP in the later stage), one of the main tasks of the thread library is to bind the thread to the process or LWP recognized by the kernel in a certain way, so that the kernel realizes the thread. concurrent. As the number of threads increases, the system will face two problems. One is that the increase in the number of threads will consume the number of kernel-bound processes (LWP), and this kernel resource is limited; May cause access overhead to the kernel, the time spent switching is completely extra. In view of the above problems, there are certain limitations in the practical application of multithreading. First, the number of threads should not be too large. Second, when the number of threads reaches a certain number, the overall performance of the system cannot be improved, or even decline. At the same time, each thread is an independent running entity, but in the entire life cycle of the thread, the thread does not work all the time, and a lot of time is spent waiting for available resources, which is undoubtedly a waste.

Contents of the invention

The purpose of the present invention is to propose a shared thread implementation and scheduling method, fully reduce the thread switching time; and under the premise of not increasing the consumption of system resources, make full use of system resources, provide a huge number of thread mechanisms, to reduce multi-thread programming Consumption on threads.

The threads involved in this method are divided into two types, user threads and system threads, wherein user threads are threads implemented by this method, system threads are thread mechanisms provided by other thread libraries, and user threads are built on system threads. The threads mentioned below refer to user threads.

The composition of thread includes several main parts of thread identification, thread entry and event receiving area, these parts are managed by thread control block, and thread control block is in user space. The implementation and scheduling method of the entire thread is as follows:

A method for implementing and scheduling a shared thread, using the following steps:

1. Thread creation to complete the setting and thread binding of the thread control block. The setting of the thread control block includes

Thread entry setting, event receiving area address application and thread state initialization;

2. Thread activation;

3. The thread is running; it enters the running state triggered by the acceptance event, and binds to the system thread. After the current event processing is completed, it returns to the idle state and separates from the system thread.

4. Thread scheduling, thread scheduling includes the following steps:

a. The thread system maintains the ready thread queue and the running thread queue;

b. Each thread is created by the main thread and other threads;

c. When the idle thread is triggered by an event, the sender of the event will transfer the receiving thread from the idle state to the ready state while sending the event, and put the thread into the ready thread queue;

d. The system thread is blocked and waits on the ready thread queue. Once a thread enters the ready thread queue, the system threads are bound to the ready thread one by one in order, and the thread is transferred to the running thread queue; the thread state is changed to the running state , and then the control is transferred to the thread entry, and the event that triggers this operation is input at the same time, and the thread runs;

e. After the thread finishes processing the current event, check whether there are other events in its event receiving area. If so, the thread will be transferred from the running thread queue to the ready thread queue; if not, the thread will exit the running thread queue and its status transition to idle state;

f. Every time the thread state is switched, it is accompanied by the recalculation of the number of system threads. According to the current total number of threads, the number of ready threads, the number of running threads, the number of idle threads, and the number of system threads, calculate whether it needs to be increased or decreased the number of system threads;

5. Thread exit;

The exit of the thread is to clear the thread data, release the thread ID, and adjust the number of system threads.

In the shared thread implementation and thread creation of the scheduling method, the setting of the thread entry includes determining the thread identifier of a unique thread, the definition of the thread entry address and the designation of the thread entry parameters.

In the thread activation of the shared thread implementation and scheduling method, the thread activation can be performed at the same time as the thread is created, or by the caller after the thread is created.

The triggering event for thread execution of the shared thread implementation and scheduling method can be a message between threads, information input from the outside world or thread activation.

The thread implementation and scheduling method proposed by the present invention is applied in a multi-thread system, and has the following beneficial effects:

(1) The thread structure data is located in the user space, and the thread operation (creation, switching, exit) does not involve any access to the kernel space, and the speed is fast.

(2) The number of threads is not limited by system resources, and a huge number of threads can be provided.

(3) Only running threads occupy the system thread resources, and the threads will release the system thread resources as much as possible after finishing the current event processing, so that the system thread resources can be fully utilized.

(4) In the thread life cycle, multiple threads share one system thread, so that the number of system threads is greatly reduced compared with the number of threads, thereby reducing the switching time of system threads and improving the operating efficiency of the system.

Description of drawings

Fig. 1 is the structural representation of thread control block of the present invention;

Fig. 2 is a schematic diagram of thread state switching of the present invention;

Fig. 3 is a schematic diagram of thread scheduling of the present invention;

Fig. 4 is a schematic diagram of the thread running and scheduling flow in the present invention.

In the accompanying drawings, a is an idle thread, b is a ready thread, c is a running thread, d is a blocked thread, and e is a system thread.

Specific implementation method

Specifically speaking, the implementation and scheduling method of the entire thread is:

1. Thread creation

The creation of thread mainly completes the setting of thread control block and thread binding. The setting of thread control block includes the setting of thread entry (thread entry is the starting point of code execution when the thread is scheduled, and can be represented by the address pointing to the starting point), The setting of the thread entry is to save the address in the thread control block; the application and initialization of the event receiving area (the event receiving area is a memory buffer, and its application is to obtain an available memory space, and set the content in it as the initial state), these tasks are completely done in user space, and do not involve any access to kernel space, so the efficiency is very high. Thread binding is mainly based on the current thread usage status to determine whether to create a new system thread to participate in thread scheduling. This operation provides the corresponding metalanguage externally.

2. Thread activation

After the thread is created, it is in the initial state and needs to be triggered by an event to work. This initial trigger is called the activation of the thread. Before the thread is activated, the received event will not be processed. Thread activation can be done at the same time as the thread is created, or it can be done explicitly by the caller after the thread is created. Activation of a thread is a thread state switching operation (switching from an initial state to another state).

3. Thread running

The running of threads is triggered by events, and the types of events can be various, mainly including messages between threads, external input, etc. The thread activation mentioned above is also a kind of event. When an event is triggered, the thread enters the running state and is bound to the system thread. After processing the current event, it returns to the idle state and separates from the system thread.

4. Thread scheduling

Thread scheduling is the main part of this method. Thread scheduling mainly completes the following functions: thread state switching, thread ready thread queue management, thread running thread queue management, and corresponding enqueue and dequeue operations. The thread scheduling proposed by this method is not completed by an independent entity, and all running threads in the thread system jointly complete the scheduling work of the entire thread mechanism. The specific work is as follows:

(1) Thread system maintains data structures: ready thread queue data structure and running thread queue data structure;

The maintenance of these two data structures is completely a data operation, including adding a data to the queue or pool,

Or take out a piece of data from the queue and the pool, where the queue maintains the order of the data entering the queue, using the first-in first-out principle, while the pool does not need to maintain such an order.

(2) Each thread can be created by the main thread (inherent system thread in the process) and other threads. The creation of threads is realized through thread creation primitives.

(3) When an event is triggered by an idle thread, the sender of the event will transfer the receiving thread from the idle state to the ready state while sending the event (putting the event into the event receiving area of the receiving thread), and put the thread in the ready state. into the ready thread queue.

(4) The system thread blocks and waits on the ready thread queue. Once a thread enters the ready thread queue,

Then the system threads are bound to the ready thread one by one in order, and the thread is transferred to the running thread queue, the thread state is converted to the running state, and then the control right is transferred to the thread entry, and the event that triggers this operation is input at the same time, and the thread runs ( handling of events).

(5) After the thread finishes processing the current event, check whether there are other events in its event receiving area. If there is, the thread is transferred from the running thread queue to the ready thread queue; if not, the thread exits the running thread queue, and its state transitions to the idle state.

(6) When each thread state is switched, it is accompanied by the recalculation of the number of system threads. According to the current total number of threads, the number of ready threads, the number of running threads, the number of idle threads, and the number of system threads, calculate whether it needs to be increased or not. Reduce the number of system threads.

5. Thread exit

The exit of the thread completes the clearing of the thread data, the release of the thread ID, and adjusts the number of system threads.

As shown in Figure 1, it shows the structure of the thread control block, including thread identification, thread entry address, thread entry parameters, event receiving area address, thread status, thread attributes and other thread data; each part is described as follows:

The thread ID is used to uniquely determine a thread, and can replace the thread entity in the thread enqueue operation, and can be used for addressing when sending messages between threads. The thread ID must be unique within the process, which can be realized through a unified allocation mechanism. After the thread exits, the ID release allows reuse.

The thread entry address is used to pass in the control right when the thread is running, and the form of the entry can be defined by yourself.

The thread entry parameter is used to pass in the parameters specified when the thread is created.

The address of the event receiving area is used to store the events that trigger the thread to run. The receiving area maintains the order of event arrival to ensure that the events that arrive first are processed first.

The thread state is used to specify the behavior of different stages of the thread life cycle. The state is cyclic and switchable. See the description in Figure 2 for details.

The attributes of the thread are used to describe some inherent properties of the thread, which are specified when the thread is created, and some attributes can be modified during the running of the thread.

Other data of the thread, this part can be processed by itself according to the specific implementation.

Figure 2 describes the various states and transitions that a thread has throughout its lifetime. Throughout the life of the thread, the state of the thread includes: initial state, idle state, ready state, running state, blocked state, and closed state.

Initial state: The thread is in this state after it is created. In the initial state, the thread is not run, and only the thread activation operation can make the thread leave the initial state. When activated, there is no event in the event receiving area of the thread, and the state transitions to the idle state; otherwise, when activated and there is an event in the event receiving area of the thread, it transitions to the ready state.

Idle state: This state indicates that there is no event in the event receiving area of the thread, and this state is converted to the ready state when an event is triggered; when an external thread terminates the operation, it is converted to the closed state.

Ready state: This state means that after the thread is activated, an event is triggered, and the thread enters the ready thread queue to wait to run. When the thread reaches the head of the queue and is bound by a system thread, the state changes to the running state; when an external thread terminates the operation while waiting to run, it turns to the closed state.

Running state: When the thread is bound by the system thread, it enters the running state. After running, if there is no event processing, it will go to the idle state; otherwise, it will go to the ready state.

Blocking state: When a thread calls a blocking operation during running, the state is changed to a blocking state. After the blocking is over, it will continue to enter the running state, unless the thread exits by itself or is terminated externally, which will switch the thread to the closed state.

Closed state: When the thread is terminated or exited within the lifetime, it will switch to the closed state.

Figure 3 shows the thread scheduling and running process. details as follows:

When the thread is created, it is in the initial state, and the thread enters the scheduling process after activation. If no event is currently triggered, the thread is always in an idle state (a in Fig. 3 ), and is separated from the system thread (e in Fig. 3 ).

·When an event triggers a certain idle thread, the idle thread is hung into the ready thread queue (b in Fig. 3) and queued up to wait for binding.

There are one or more system threads blocked on the ready thread queue (d in Figure 3), when there are threads in the ready thread queue, wake up a system thread bound to it, hang it into the running thread queue, and the thread runs ( As shown in c) in Figure 3.

When the thread returns after processing the current event, it is cleared from the running thread queue. According to whether there is a follow-up event, it decides to switch its state to idle or ready, and separates from the system thread.

· If a running thread makes a blocking call, it will be marked as blocked, which is used in operations such as its being terminated externally.

·If the running thread requests to exit or is terminated externally, the system thread bound to it will implement separation and termination operations according to the running status of the thread.

Through the thread scheduling as shown in Figure 3, you can clearly see how the threads run. First of all, thread scheduling is performed at each state switch, and it will not be scheduled during thread running. Therefore, thread scheduling is performed at the user level and does not involve system thread switching, so this scheduling is very safe. . Second, the scheduling of threads is closely related to the triggering of events. It can be said that the scheduling of threads is driven by events. Third, thread scheduling involves the binding and separation of threads and system threads, and this process is carried out dynamically.

Claims (4)

1. A shared thread implementation and scheduling method is characterized in that the shared thread implementation and scheduling method adopts the following steps: (1) Thread creation, to complete the setting and thread binding of the thread control block, the setting of the thread control block includes thread entry setting, event receiving area address application and thread state initialization; (2) Thread activation; (3) Thread running; triggering by accepting events, it enters the running state and binds with the system thread. After the current event processing is completed, it returns to the idle state and separates from the system thread. (4) thread scheduling, thread scheduling includes the following steps: a. The thread system maintains the ready thread queue and the running thread queue; b. Each thread is created by the main thread and other threads; c. When the idle thread is triggered by an event, the sender of the event will transfer the receiving thread from the idle state to the ready state while sending the event, and put the thread into the ready thread queue; d. The system thread is blocked and waits on the ready thread queue. Once a thread enters the ready thread queue, the system threads are bound to the ready thread one by one in sequence, and the thread is transferred to the running thread queue; the thread state is changed to the running state , and then the control is transferred to the thread entry, and the event that triggers this operation is input at the same time, and the thread runs; e. When the thread finishes processing the current event, check whether there are other events in its event receiving area. If so, the thread will be transferred from the running thread queue to the ready thread queue; if not, the thread will exit the running thread queue, and its status transition to idle state; f. Every time the thread state is switched, it is accompanied by the recalculation of the number of system threads. According to the current total number of threads, the number of ready threads, the number of running threads, the number of idle threads, and the number of system threads, calculate whether it needs to be increased or decreased the number of system threads; (5) Exit of thread; The exit of the thread is to clear the thread data, release the thread ID, and adjust the number of system threads. 2. The shared thread implementation and scheduling method according to claim 1, wherein the setting of thread entry during thread creation includes: determining a thread ID of a unique thread, definition of thread entry address, and specification of thread entry parameters. 3. The shared thread implementation and scheduling method according to claim 1, characterized in that the activation of the thread during thread activation can be performed at the same time as the thread is created, or can be performed by the caller after the thread is created. 4. The shared thread implementation and scheduling method according to claim 1, characterized in that, the triggering event of thread running may be a message between threads, information input from the outside world or thread activation.