Operating System : RM(Rate-Monotonic) Algorithm

---

RM/EDF?

Rate-Monotonic(RM) / Earliest-Deadline-First(EDF) 이란?

” Real-Time CPU RM_Logic 의 특징인 Priority-based RM_Logic 방법. “

• Rate-Monotonic 은 Task 각각의 Period 길이에 따라 Priority 를 부여.
  
• Earliest-Deadline-First 는 말 그대로 Task 들의 Deadline 에 중점을 두고 Priority 부여.
  
  

RM?

Rate-Monotonic(RM) 이란?

” Period(수행 주기) 가 짧은 process 일수록 Higher Priority 를 부여하고, 반대로 Period(수행 주기) 가 긴 process 일수록 Lower Priority 를 부여하는 방식이다. “

• 후에 나올 EDF Algorithm 과는 달리 Priority 의 변동이 없기 때문에
  가장 Optimal(최적) 한 Static-priority RM_Logic 방식이다.
• 각 Process 의 Period 는 미리 지정되어 있으며, 이를 기반으로 Priority를 계산한다.
• 모든 Process 는 단일 CPU에서 주기적으로 구동되어야 하며, Process 의 수행 시간 (Execute Time)은 일정해야 한다. (즉, 변함이 없어야 한다.)
• Context Switching 은 무시한다.
• n개의 process 가 있을 때, CPU 사용율의 상한은 다음 공식으로 계산이 가능하다.
  

  
  출처: 위키백과 wiki
  
  

RM 예제

# Rate-Monotonic Algorithm 예제

출처: 위키백과 wiki

• 위 예제에 대하여 부가 설명을 하자면,
  
  1. Interval(시간적인 간격 - 여기서는 ‘공간’ 이라 하겠다.) 안에 모든 execution 을 더한 것이 Interval 과 같거나 작으면 된다고 생각 할 수 있다.
  2. 쉽게 이야기 해서 ,
     

- 지하철(공간, Interval) 이 있다.
- 지하철의 크기보다 지하철을 타려는 사람(Execution)이 적다면,
- 지하철을 못타거나 밀려나는 사람(Deadline miss) 은 없을 것이다.

- 개인적으로 이렇게 이해를 했는데 비유가 괜찮았는지 모르겠다.

* 내일은 EDF(Earliest Deadline First) 로 돌아오도록 하겠다.

Task Lists

• Build CarefreeLife’s dev blog
• Post Every night
• Grow up