Linux 2.4 process scheduling analysis content summary:
● Foreword: Background, Characteristics and Application Value of Technology
● Ready process selection algorithm
● Related data structure
● Scheduling related part of the scheduler and other core applications: The call relationship of the function of the function is implemented, and the basic functions of each function will be described.
● Some problems of Linux 2.4 scheduling system: Analyze the advantages and disadvantages of the selected technology from the perspective of operating system principles and possible improvements
I. Introduction
1. Technical background: Scheduling system has a very important impact on the overall performance of the operating system, embedded system, desktop system, and high-end servers are different for scheduler requirements.
2. Features: The core is not sewage, the scheduling algorithm is simple and effective.
3. Application value: In an open source operating system, Linux has developed most significant, so far, it has occupied considerable share in the low-end server market. From the latest Linux 2.6 system, there are two main ways in the development direction of Linux: embedded systems and high-end calculations.
two. Related data structure
In Linux, the process is represented by Task_Struct, all processes are organized into the two-way linked list of init_task as the header (see [include / linux / sched.h] set_links () macro), the chain list is unique. All CPUs are organized to an array of schedule_data (afterwards). The process can be accessed between the process and the running CPU (see below).
All running processes (task_running) are organized to two-way linies that are running with Runqueue_Head, and the scheduler always looks for the most suitable scheduled process. Runqueue_head is also unique in the system.
These data structures related to the scheduler work are described below.
1. Init_TSS
TSS, Task State Segment, 80x86 platform-specific process running environment, although Linux does not use TSS, but save the information described by TSS in TSS_STRUCT array init_TSS in the CPU number index, the process switches, where the value will Get updates.
2. Task_struct
In Linux, threads and processes use the same core data structure, it can be said that only processes in the built in 2.4, which contain lightweight processes. A process uses a task_struct structure in the core, including a large number of information describing the process, where information related to the scheduler mainly includes the following:
I. State
Linux's process status is mainly divided into three categories: Task_Running, equivalent to operational state and ready state); hang-truck_interruptible, task_uninterruptible, and task_stopped; uncomfortable (task_zombie), the scheduler mainly processed The process that can be run and hang in two states, where Task_Stopped is also specifically used by IPC signals such as Sigstp, and Task_Zombie refers to the "zombie" process that has been exited and temporarily not recovered by the parent process.
Ii. NEED_RESCHED
The Boolean value is used in the scheduler to indicate that the process needs to be scheduled (see "Scheduler Workflow").
Iii. Policy
In Linux 2.4, the process's scheduling policy can have three options: SCHED_FIFO (advanced first-release scheduling unless there is a higher priority process application operation, the process will remain running to exit to let CPUs), SCHED_RR (Rotation Scheduling, the process is scheduled to be placed at the end of the running queue to ensure that other real-time processes have the opportunity to run), SCHED_OTHER (General Timed Scheduling Policy). In addition, policy also includes a SCHED_YIELD bit, and when set, the POLIC is set to actively discard the CPU. IV. RT_PRIORITY
Used to characterize the priority of real-time processes, from 1-99, non-real-time processes should be 0. This property will calculate the weight of the schedule (see "Ready Process Selection Algorithm").
v. counter
This property records that the process is also allowed to operate (in units of CPU clock values, each process is related to the NICE value, the smaller the nice, the higher the priority, the higher the priority The CPU time allowed by the process is also relatively relatively relatively relatively), and participate in the Ready Process Select Algorithm. In Linux 2.4, each (non-SCHED_FIFO real-time) process is not allowed to run greater than a certain time piece, once the timeout is timeout, the scheduler will force the other process to run (see "Scheduler Workflow")
Vi. Nice
User-dominated process priority will participate in the Ready Process Select Algorithm, and this value also determines the length of the process of the process (see below).
VII. CPUS_ALLOWED
A CPU that can be used for the process is used in the form of a bit vector (see "scheduler workflow").
Viii. CPUS_Runnable
The CPU currently running the process is represented in the form of a bit vector (1). If not running on any CPU, it is all 1. This property is combined with the cpus_allowed attribute to quickly determine if the process can schedule to run (bit "and") on a CPU.
IX. Processor
The current (or recent) CPU number is located.
x. thread
Used to save process execution environments (value of each register and IO operation permission map), the content is similar to TSS. Since TSS is indexed in the CPU ID, and Linux cannot predict that the process replaced will run on which CPU is running on the next time, this information cannot be saved in TSS.
