Application skills/Application of time slice rotation algorithm in single chip computer programming

rain

Application skills/Application of time slice rotation algorithm in single chip computer programming [Copy link]

Abstract : This paper proposes a software design method that uses a time slice round-robin algorithm to improve the programming of single-chip microcomputer systems and realize a multi-tasking mechanism. An example of using this algorithm to program in an MCS-51 hierarchical distributed system is given.
	Keywords : time slice multitasking mechanism single chip microcomputer system
	The traditional single-task programming idea requires simple programming, clear ideas, and a short development cycle for obvious sequential control requirements; but it is difficult to meet the requirements for problems with more tasks and complex control functions. Therefore, it is necessary to improve the traditional single-task design idea. The time slice round-robin algorithm is a commonly used algorithm for implementing multi-task scheduling. In this algorithm, the system arranges all tasks in a queue in order, and each time the CPU is assigned to the task at the head of the queue, and it is ordered to execute a time slice, forming a multi-task effect of taking turns to run at the micro level and executing at the macro level. The author introduced a multi-task mechanism in the user controller program of the program-controlled intercom system, a hierarchical distributed control system based on a single-chip microcomputer. The time slice round-robin algorithm greatly improved the program structure and realized effective control of 32 independent users. This programming idea can also be applied to the software design of other hierarchical distributed control systems with single-chip microcomputers as the core.
	1 System composition
	The program-controlled intercom system is a multi-level distributed system based on MCS-51, in which the user controller is one level. The overall structure of the whole system is shown in Figure 1.
	The main controller uses the AT89C52 single-chip microcomputer as the core to expand the non-volatile memory and other functional devices, completes the programming and storage of the intercom relationship of each user in the system, and controls the user module in real time according to the intercom relationship. The user controller uses the AT89C52 single-chip microcomputer as the core to expand the user interface module. Each user controller is responsible for managing and controlling the 32 user machines at the next level.
	The information exchange between the main controller and the user controller adopts the master-slave serial communication. The main controller queries the 8 user controllers in turn, and each user controller only responds to the commands related to this module. The user controller is connected to the user machine through a twisted pair to reduce the system cost. The transmission distance between the user machine and the user controller is far, up to 8km. In order to ensure the correct transmission of data in a complex environment, the communication between the two uses DTMF coding.
	2 Task allocation and time slice division
	2.1 Determination of User Controller Subtasks
	The user controller needs to manage 32 independent user machines in real time. On the one hand, it receives the call signals from the user machines in real time, processes them, and transmits them to the main controller; on the other hand, it sends the called information to the user machines according to the system working status.
	There are two types of signals that the user controller receives from the user machine. One type is the DTMF coded signal, which is used to detect whether the user machine needs to call other user machines. The number of bits of data transmitted between the user machine and the controller is not equal. It takes at least 104ms to send each bit of DTMF coded data, with the sending time and idle time accounting for half each. The other type is speech. The multiplexing of DTMF coded signals and voice signals can reduce the line cost of the system.
	After each communication, in order for the user controller to start receiving the next round of DTMF coded data, the user machine needs to send a start signal to the user controller - the hang-up signal. The working power of the user machine is directly extracted from the user line. When voice and DTMF codes are transmitted, the user line has a certain working current (greater than 20mA). The hang-up signal makes the current on the user line close to zero (less than 5mA). After the user controller detects this change in the circuit on the user line, it enters a new round of DTMF coded data communication. The duration of the hang-up signal is 78ms.
	The user controller sends only DTMF coded data to the user machine to tell the user machine who is calling it.
	To complete a calling process (even if the call time is zero), at least 2×104ms (receiving and sending DTMF encoding time) + 78ms (hang-up time) = 286ms are required; to complete a called process, at least 2×104ms = 208ms are required. If the request of each user machine cannot be responded to in real time. To solve this problem, a multi-task mechanism is introduced in the user controller program design process. To facilitate the scheduling of the task scheduler, the operation of the user machine is subdivided into 16 word operations according to the user operation process. Each sub-operation constitutes a sub-task. The user sub-task allocation table is shown in Table 1.
	2.2 Time Slice Division
	In the round-robin algorithm of time slices, the size of the time slice has a great impact on system performance. If the time slice is too large, so large that each task can be completed within one time slice, the round-robin algorithm of time slices will degenerate into the FCFS algorithm. The determination of the time slice usually takes into account three factors: the number of tasks, the system's response time requirements, and the system's processing capacity.
	In this system, the user controller needs to manage and control 32 user machines, which should be divided into 32 time slices. At different times, each user machine is in different working conditions, and the user controller needs to execute different user machine tasks, and the processing time is also different. In order to shorten the program running time, the time slice is set to be variable, and the length of the time slice depends on the workload of each user machine subtask. However, the communication time requirements between the user controller and the user machine are very strict. For example, the DTMF sending timing time is 104ms, including 52ms sending time and 52ms idle time, so the user controller must inspect each user machine once within 52ms to correctly receive the encoded data of the user machine. In other words, a task scheduling cycle should not be greater than 52ms. In order to meet the time requirements for communication between the user machine and the controller, the entire task scheduling cycle is precisely timed.
	Taking into account the three factors related to time slice division in this system: the computing speed of the microcontroller itself, the number of user machines, and the signal transmission requirements between the user machines and the controller, the task scheduling cycle is determined to be 26ms. That is, within 26ms, the user controller must execute the tasks of the 32 user machines at the next level once. Generally, one task takes one time slice to complete, and a longer task can take multiple time slices. For example, subtask No. 14 (sending the second DTMF coded data) requires 4 time slices to complete.
	In order to grasp the operation status of each user machine in real time, a buffer is opened in the memory of the user controller as a task record table for the task scheduler to use. The task record table is set with three items: user number, subtask number and time slice number, as shown in Table 2.
	3 Software Design
	3.1 Design of Task Scheduler
	Based on the above analysis, the functions of the task scheduler can be determined as follows: (1) Call each user subtask according to the user machine number; (2) The time to complete a scheduling cycle does not exceed 26 ms, and the 26 ms is accurately timed at the end of each cycle; (3) At the beginning of the scheduling cycle, read the DTMF codes and on/off status of all users for processing by each user subtask; (4) Before the end of the scheduling cycle, send the DTMF code to the user machine based on the user subtask processing result.
	The flow of the scheduling program is shown in Figure 2.
	3.2 Design of User Subtasks
	The user subtask processes the data in the user buffer and stores the processing results in the result unit. Each subtask does not directly exchange data with the external input and output interface. The input and output of the interface are completed by the task scheduler calling a special subroutine at the beginning and end of the scheduling cycle. The switching of user subtasks is completed in each subtask according to the operation process. The user's operation is subdivided into 16 sub-operations, and there are 16 subtasks accordingly. Figure 3 is the flow chart of subtask No. 14.
	At the beginning (0ms) and middle (52ms) of this subtask, a DTMF data sending buffer is set to allow and prohibit the sending of DTMF codes respectively. At the end of this subtask, the second DTMF value is calculated based on the data to be sent in the user buffer, and the scheduling data of the user in the task record table is modified to point to its next subtask. The design ideas of other subtasks are similar to this subtask.
	This paper introduces the multi-tasking concept of modern operating systems into the single-chip real-time control system, uses the time slice round-robin scheduling algorithm to improve the traditional single-chip programming concept, and applies it to the hierarchical distributed system based on MCS-51, effectively completing the control of 32 independent users. Practice has proved that this structure is clear and the scheduling is flexible, which is suitable for systems with complex timing requirements and strong real-time requirements.