CN1811719A

CN1811719A - Method for detecting and intervening deadlock of single-threading microprocessor

Info

Publication number: CN1811719A
Application number: CN 200610055169
Authority: CN
Inventors: 吴允平; 蔡声镇; 吴进营; 苏伟达; 李汪彪
Original assignee: Fujian Normal University
Current assignee: Fujian Normal University
Priority date: 2006-02-22
Filing date: 2006-02-22
Publication date: 2006-08-02

Abstract

The invention relates to a deadlock detection and intervention method of a single-thread microprocessor. The purpose is to provide a simple and effective deadlock detection method for tasks in the system and solve the deadlock phenomenon in the system. Main steps: before starting the task to obtain CPU time, start the timer resource and initialize the physical memory unit timer used; in the timer interrupt service program, according to the current running status of the task, the physical memory unit timer is accumulated and timed; the currently running Unless the task ends normally, it will continuously check its CPU usage time in a loop. If it exceeds the set maximum running time, it will be considered that a deadlock has occurred, thus ending the deadlocked task and giving the CPU time to subsequent tasks to continue execution . This technology only uses a small amount of resources, a global flag bit, a timer of a physical memory unit, and timer resources to complete deadlock detection.

Description

A kind of Deadlock Detection of single-threading microprocessor and interference method

Technical field

The present invention relates to the microprocessor technology field, relate in particular to a kind of Deadlock Detection and the interference method of the typical case of single-threading microprocessor system as single-chip microcomputer.

Background technology

The thread of microprocessor is meant an implementation of program, and in single-threading microprocessor such as single-chip microcomputer, program is current can only carry out an instruction.This single-threading microprocessor advantages such as little, powerful, cheap and exploitation is convenient because of its volume have been widely used in some portable, long-range unattended duty instrument and meter systems.

Described deadlock, it has been generally acknowledged that be present in more with the corresponding multithreaded microprocessor of single-threading microprocessor in, be that each thread in two or more threads is all waiting for that another one thread wherein discharges certain common resource of using and is blocked, and makes each thread all can't continue next step implementation.It has been generally acknowledged that, the generation of deadlock must be satisfied four necessary conditions: (resource can only be distributed to certain task or free time of determining in mutual exclusion, resource can not be that two tasks occupy simultaneously), must seize that (resource is seized, can only be occupied its task discharge voluntarily), take and wait for and (occupy the other new resources of task requests of some resource, and these resources occupy for other tasks), circular wait (exists one group of resource request { P1, P2, Pn}, wherein P1 waits for the resource that P2 occupies, P2 waits for the resource that P3 occupies,, Pn waits for the resource that P1 occupies).The generation meeting of deadlock has brought great danger to system, directly causes system crash, can't normally move.Since nineteen sixty-five Dijkstra proposes the deadlock problem, through years of development, on multithreaded microprocessor, accumulated some reasonable Deadlock Detection and interventions, the method for software aspect is arranged, the method that hardware aspect is also arranged is as Petri net, automat and graph theory etc.; These methods are mainly reflected in three aspects: prevention, and to avoid and detect and recover, these are handled all is that resource with the consumption microprocessor is a cost as thread, internal memory etc.

The structures shape of single-threading microprocessor its satisfied most of conditions in deadlock four key elements, can not seize and take also wait task as mutual exclusion, resource finishes, and because software systems and hardware are closely related, every next execution in step often depends on the state of outside level signal, and this has satisfied the another one condition of deadlock again: circular wait.Therefore, the deadlock of this type of microprocessor needs a detection method efficiently, and can carry out the mechanism that the oneself intervenes, recovery system function after deadlock takes place.But because the resource of single-threading microprocessor is less, as typical MCS-51 single-chip microcomputer, 256 byte RAM and 2 timers are only arranged in the sheet, the PIC series monolithic of Microchip company, 1K left and right sides byte RAM and 2-4 timer etc. only in its sheet, can't mention in the same breath with multithreaded microprocessor, so in the multi-threaded system be that the Deadlock Detection and the interfering system of cost obviously can not be applied in the single-threading microprocessor system with the resource.

In sum, need a kind of simple and practical, single-threading microprocessor deadlock detection method that resource requirement is few.

Summary of the invention

The purpose of this invention is to provide a kind of with task run maximum time demand as the main Rule of judgment of Deadlock Detection, thereby can carry out Deadlock Detection to task in the system of this type of clue execution, the deadlock detection method of the single-threading microprocessor of the normal operation of safeguards system simple and effectively.

The objective of the invention is by the following technical solutions to realize with step.

1) chip external memory is preserved maximum working time of the demand of each specific tasks of single-threading microprocessor, read-write modification according to its system configuration.

2) single-threading microprocessor system on-chip timer resource, as task timing resource, when regularly interrupting taking place, interrupt service routine is to n task timing of current operation.

When 3) n task takies CPU time and handle, be interrupted maximum working time of the demand of checking whether its CPU time that has taken surpassed that this task allows.If surpassed, think that then deadlock situation has taken place n task, intervene then and recover the resource that n task used.

Because the present invention has adopted above-mentioned measure, make the present invention compared with prior art, effectively having overcome in the multi-threaded system with the resource is the Deadlock Detection and the interfering system shortcoming of cost, and be successfully applied to the Deadlock Detection and the interference method of single-threading microprocessor single-chip microcomputer in the single-threading microprocessor system, both simple and practical, save a large amount of resources again, performance is significantly improved, thereby solves the deadlock situation in this type systematic.

Description of drawings

Fig. 1 is a single-threading microprocessor deadlock detection method structural representation of the present invention.

Fig. 2 is a single-threading microprocessor task module deadlock detection method process flow diagram of the present invention.

Fig. 3 is a single-threading microprocessor Deadlock Detection timing process flow diagram of the present invention.

Embodiment

Fig. 1 is a Deadlock Detection structural representation of the present invention, and data storage device 101 is preserved the maximum CPU time demand of each specific tasks among the figure, can set in advance, also can dynamically adjust in program operation process.N task run of single-threading microprocessor 102 expression current tasks take the All Time of CPU; only when processor interrupts taking place; just give interrupt service routine CPU time uses temporarily; interrupt service routine carries out processing such as scene protection; after finishing, give current n task CPU time again and continue to use CPU time.Resource 103 is important physical resources of the present invention during the microprocessor physical set, is operated in interrupt mode, the CPU service time of depriving current task when interrupting taking place.

Fig. 2 is a task module deadlock detection method process flow diagram of the present invention.The present invention is described in more detail below in conjunction with accompanying drawing 2.

Step 201: before n the task run, global flag position of system assignment and physical memory timer, wherein the global flag position is used to refer to that n task is current to have obtained CPU service time, and the physical memory timer is used for CPU time timing that this task is used.

Step 202: outside sheet, read maximum working time the data-carrier store, and be saved in the appointment physical memory addresses corresponding to n task.Be used for the Rule of judgment parameter that this task is used CPU time this maximum working time.

Step 203:, pick up counting from the numerical value of some settings to the physical memory timer initializing resource of system assignment.

Step 204: the global flag position to system assignment is provided with, and the indication CPU time is used by n task.In the timer interrupt service routine, whether this zone bit has determined CPU timing service time to n task.

Step 205: allow maximum CPU to compare service time to the CPU time of n task use and this task of setting, deadlock situation has taken place if the timing result of current physical memory timer resource greater than the maximum time demand of setting, then illustrates; If do not surpass the maximum time demand, then continue to carry out the code operation of this task.

Step 206: n task used the CPU time of microprocessor, finishes corresponding task, withdraws from up to normally finishing.If circulation is carried out once normally not finish and withdrawed from, then jump to step 205.

Step 207: when n task generation deadlock, force to finish this task, in this step n the employed resource of task reinitialized, be convenient to the continuation operation of next order n task by step 205.Fig. 3 is a single-threading microprocessor Deadlock Detection timing process flow diagram of the present invention.Among the figure, the CPU working time that current task has been deprived in step 301 expression timing interruption, handing to regularly, interrupt service routine uses.In the step 302, the n task physical memory timer resource of normal operation is added up to handle, thereby obtain the CPU time that this task is used.

Claims

1. A single thread microprocessor system deadlock detection and intervention method is characterized in that said method comprises the following steps:

[1] Before the task obtains the CPU usage time, initialize the task running flag and the timer of the physical memory unit, and read the set maximum CPU demand time from the data memory according to its system configuration;

[2] In the timing interrupt service program of the microprocessing, according to the task running state flag bit, the task timer of the physical memory unit is accumulated and timed;

[3] The task obtains CPU time. Unless it ends normally, check in a loop whether the CPU time occupied by the task exceeds the set maximum CPU demand time. If it exceeds, it means that the current task has a deadlock phenomenon, and its CPU usage is forcibly terminated. The time is given to the follow-up tasks to continue execution.

2. The detection and intervention method according to claim 1, characterized in that the data storage stores the maximum CPU required time of each task.

3. The detection and intervention system according to claim 1, wherein each independent task has an independent global flag bit for indicating whether the current task obtains CPU running time.

4. The detection and intervention system according to claim 1, wherein each independent task has an independent timer for indicating the physical memory unit of the CPU usage time occupied by the current task.

5. According to the detection and intervention system according to claim 1, it is characterized in that the timing process of the current task using the CPU time is completed in the timer interrupt service program of the microprocessor.