Scheduling Algorithms for Multiprogramming in a Hard- Real-Time Environment

Scheduling Algorithms for Multiprogramming in a Hard- Real-Time Environment 

C. L. LIU 

Project MAC, Massachusetts Institute of Technology 

AND 

JAMES W. LAYLAND 

Jet Propulsion Laboratory, California Institute of Technology

abstract

단일 프로세서에서 에서 멀티 프로그램의 스케쥴링의 문제의 view point는 프로그램의 기능이 요구하는 특징 성격에대한 서비스를 보장하는것이다 ? 이 것은 보여준다. 최저화된 고정 순위 스케쥴러의 프로세스가 프로세서의 사용률을 70%까지 상한선까지 사용한다. 이것은 또한 보여준다.  완전한 프로세서의 사용을 위해서는 그들의 현재 데드 라인에서 다이나믹한 우선순위를 할당해야 한다고 보여준다. 이 두가지 스케쥴러의 조합또한 설명한다.

// 고정 순위 스케쥴러 , 데드라인에 따른 다이나믹 스케쥴러, 이두가지를 섞은 스케쥴러 설명하는 논문 at 하드 리얼타임 멀티 프로그래밍 환경에서 

1. Introduction 

1973년 고전 논문 

컴퓨터를 효율적으로 사용하기 위해서는 (time critical control)스케쥴링을 신중하게 해야한다.

이런걸 "pure process control"이라고 말하고 그리고 이논문에서 복합적인 스케쥴링 평가에대한 백그라운드를 제공한다.

두가지 종류의 스케쥴링 알고리즘을 연구하였다. both are priority driven and preemptive; meaning that the processing of any task is interrupted by a request for any higher priority task. The first algorithm studied uses a fixed priority assignment and can achieve processor utilization on the order of 70 percent or more. The second scheduling algorithm can achieve full processor utilization by means of a dynamic assignment of priorities. A combination of these two algorithms is also discussed. 

2. Background

스케줄링에 관련된 이전 연구들 

3. The Environment

하드 리얼 타임 환경에서 프로그램 behavior에 관련된 어떠한 분석적인 결과를 얻기 위해서는 환경에 대한 확실한 가정이 필요하다 모든 가정이 완전할 필요는 없다. 

A1

모든 task들은 하드 데드라인을 주기적으로 가지게 되며, 각각의 요청은 서로 일정한 간격을 가지게 된다. 

A2

Deadlines consist of run-ability constraints only--i.e, ? 각각의 task는 다음 요청이 일어나기 전에 완료되어야 한다. //큐잉 문제 해결

A3

각각의 task는 독립적이다. 초기상태나 다른 task의 요청에 대하여 의존적이지 않다. 

A4 

task의 런타임은 일정하다. 다양한 시간을 가지지 않는다. 여기서 말하는 런타임이란 프로세서가 방해없이 실행되는 시간을 말한다. // task의 최대 실행 시간을 알 수 있다. 

A5

시스템의 모든 nonperiodic tasks 특별하다. 그들은 초기화나 고장 수리 루틴이다. 이들은 테스크의 우선순위를 변경할수 있고 이들은 데드라인을 가지지 않는다. 

A scheduling algorithm is a set of rules that determine the task to be executed at a particular moment. The scheduling algorithms to be studied in this paper are preemptive and priority driven ones. This means that whenever there is a request for a task that is of higher priority than the one currently being executed, the running 

task is immediately interrupted and the newly requested task is started. Thus the specification of such algorithms amounts to the specification of the method of assigning priorities to tasks. A scheduling algorithm is said to be static if priorities are assigned to tasks once and for all. A static scheduling algorithm is also called a fixed 

priority scheduling algorithm. A scheduling algorithm is said to be dynamic if priori ties of tasks might change from request to request. A scheduling algorithm is said to be a mixed scheduling algorithm if the priorities of some of the tasks are fixed yet the priorities of the remaining tasks vary from request to request. 

4. A Fixed Priority Scheduling Algorithm 

이 장에서 우리는 최적화된 static scheduling algorithm의 우선 순위 할당 룰을 유도 할것이다. 중요한 컨샙은 테스크의 critical instant를 결정 한다는것이다. 작업에 대한 요청의 마감은 같은 작업에 대한 다음 요청의 시간으로 정의됩니다. 같은 데스크 집합은 같은 스케쥴링 알고리즘을 따르게 되고 테스크 t가 데드라인까지 요청을 처리 하지 못하면 overflow라고 부른다. 스케쥴링 알고리즘은 feasible 하다고 하는것은 스케쥴링 동안 overflow가 발생하지 않은 경우 이다. 우리는 요청과 해당 요청에 대한 응답의 끝 사이의 시간 간격으로 특정 작업에 대한 요청의 response time 을 정의합니다. 가장많은 response time을 가지는 task를 critical instant라고 정의 한다. critical time zone은 critical instant의 시작부터 끝까지의 시간이다. // 용어 정의 

THEOREM 1. A critical instant for any task occurs whenever the task is requested simultaneously with requests for all higher priority tasks. 

// 어떠한 테스크가 동작중에 더 높은 우선순위 테스크의 요청을 받으면 critical instant가 된다.

PROOF

Let ~'i, ~'2, • • • , Tm denote a set of priority-ordered tasks Tm이 가장 낮은 우선순위를 가진다. 가정한다 t1에서 tm을 위한 특정 요청이 발생했다.