A Predictable and Preemptible, Prioritized Spin Lock Algorithm
Date Issued
2005
Date
2005
Author(s)
Lin, James Ching-I
DOI
en-US
Abstract
Since the inception of multiprocessing, one of the biggest concerns have been regarding how to improve the busy-wait synchronization techniques of multiprocessor systems. Incorporating multiple CPUs with shared memory access and coordinating them with their interrupt response management has been difficult to do and has led to a wide array of research regarding spin locks. This paper focuses on a spin lock algorithm that is based upon a prioritized queuing spin lock mutual exclusion algorithm for real-time systems. Busy-wait synchronization techniques must take into account other factors when it is designed for real-time systems, thus adding yet another aspect into the difficulty of designing such algorithms. There are many similar previous works of spin lock algorithms that this paper will make use of. All of them will be briefly discussed in detail. Some ideas to be discussed include preemptibility, implementing a spin-lock queue that is predictable based upon higher priority using a pointer to the lock holder, comparing the priority of the processors wishing to acquire the lock to ensure that higher priority processors are processed first, and updating the queue based on priorities while the processor is busy servicing interrupts. The proposed algorithm’s scheduling concept will be simulated using the MOSS Scheduling Simulator to show the efficiency of this algorithm as compared to the previous algorithms this paper is based upon. A conclusion will be reached regarding the effectiveness of the proposed algorithm as well as suggestions for further research. This paper will be organized in the following fashion. Chapter 1 will be an overview of the concept and purpose. Chapter 2 will review in some detail some of the previous algorithms that have inspired this paper. Chapter 3 will discuss in detail the proposed algorithm. Chapter 4 will discuss the experimental procedures. Chapter 5 will compare the experimental results. Finally, Chapter 6 will be the conclusion of this paper.
Subjects
旋轉鎖定
互斥
中斷
擷取鎖定
釋放鎖定
spin lock
mutual exclusion
preemption
acquire_lock
release_lock
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-94-R92921124-1.pdf
Size
23.31 KB
Format
Adobe PDF
Checksum
(MD5):3337a16e51eca3f6c1d94fdc02f501da