PRIORITY INHERITANCE PROTOCOLS - AN APPROACH TO REAL-TIME SYNCHRONIZATION

被引:846
作者
SHA, L
RAJKUMAR, R
LEHOCZKY, JP
机构
[1] CARNEGIE MELLON UNIV,DEPT COMP SCI,PITTSBURGH,PA 15213
[2] CARNEGIE MELLON UNIV,DEPT STAT,PITTSBURGH,PA 15213
[3] CARNEGIE MELLON UNIV,PITTSBURGH,PA 15213
关键词
Priority inheritance; priority inversion; realtime systems; scheduling; synchronization;
D O I
10.1109/12.57058
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
A direct application of commonly used synchronization primitives such as semaphores, monitors, or the Ada rendezvous can lead to uncontrolled priority inversion, a situation in which a higher priority job is blocked by lower priority jobs for an indefinite period of time. In this paper, we investigate two protocols belonging to the class of priority inheritance protocols, called the basic priority inheritance protocol and the priority ceiling protocol. We show that both protocols solve this uncontrolled priority inversion problem. In particular, the priority ceiling protocol reduces the worst case task blocking time to at most the duration of execution of a single critical section of a lower priority task. In addition, this protocol prevents the formation of deadlocks. We also derive a set of sufficient conditions under which a set of periodic tasks using this protocol is schedulable. © 1990 IEEE
引用
收藏
页码:1175 / 1185
页数:11
相关论文
共 14 条
[1]  
GOODENOUGH JB, 1988, 2ND P ACM INT WORKSH
[2]   EXPERIENCE WITH PROCESSES AND MONITORS IN MESA [J].
LAMPSON, BW ;
REDELL, DD .
COMMUNICATIONS OF THE ACM, 1980, 23 (02) :105-117
[3]  
LEHOCZKY J, 1987, P IEEE REAL TIME SYS
[4]  
LEHOCZKY JP, 1989, P IEEE REAL TIME SYS
[5]  
LEHOCZKY JP, 1986, ACM PERFORM EVAL REV, V14
[6]  
LEINBAUGH DW, 1980, IEEE T SOFTWARE JAN
[7]   A NOTE ON PREEMPTIVE SCHEDULING OF PERIODIC, REAL-TIME TASKS [J].
LEUNG, JYT ;
MERRILL, ML .
INFORMATION PROCESSING LETTERS, 1980, 11 (03) :115-118
[8]   SCHEDULING ALGORITHMS FOR MULTIPROGRAMMING IN A HARD-REAL-TIME ENVIRONMENT [J].
LIU, CL ;
LAYLAND, JW .
JOURNAL OF THE ACM, 1973, 20 (01) :46-61
[9]  
Mok A. K., 1983, THESIS MIT
[10]  
RAMAMRITHAM K, 1984, IEEE SOFTWARE JUL