Operating System : TFP / JFP

Real-Time System?

Real-Time System 이란?

• 논리적 결과 뿐만 아니라 결과가 도출되는 시간도 정확해야 하는 System.
  
  

Real-Time System의 종류

Real Time System 의 종류 두 가지

1. Soft real-time
   • Deadline 이 중요하지만 조금씩 miss 되더라도 system은 정상적으로 동작 할 수 있는 System. 안전상의 문제는 없다.
     (대신 유저의 만족감이나 서비스의 quality가 떨어질 수 있다.)
     ex. 스마트폰 앱, 네트워크 통신 등
2. Hard real-time
   • Deadline을 지키지 못하면 안전에 문제가 생긴다.
     요구되는 deadline을 어떤 일이 있더라도 지켜야 하는 System.
     ex. 항공기, 자율주행 자동차 등

Real-time Scheduling?

Real-time Scheduling 이란?

• 수많은 Tasks 들을 실행시키기 위해 필요한
  Computing Resources들을 Scheduling algorithm에 맞추어 적절히 할당하는 것.

Real-time Scheduling 설계 방법

Real-time Scheduling 의 기반이 되는 설계 방법 두 가지

1. Scheduling Algorithm design
   • Deadline 과 같은 시간적 요인을 만족하기 위해 Tasks 들의
     실행 순서를 결정해야 한다.
     
     
2. Schedulability analysis
   • Scheduler 에 의해 platform 에서 실행되는 주어진 taskset 이
     어떠한 deadline miss 없이 Scheduled 될 수 있는지 증명한다.
   • 최악의 경우의 수를 분석해야 한다.
     (안전과 직결된 문제이기 때문에 최악의 상황은 피할 수 있도록 설계해야 한다.)
     –> Analyze worst-case situation
     

TFP vs JFP
< Priority-based Real-time Scheduling >

Task-level fixed-priority (TFP)

• Task-level Fixed Priority : Real-Time System 에서 일반적으로 사용되는 스케줄링 알고리즘
각각의 작업(task)에 대해 priority(priority)를 지정하고, priority가 높은 작업부터 실행되도록 한다.
  
• 각 작업은 fixed priority를 가지며, 작업의 중요도와 긴급성에 따라 priority 가 결정된다.
  높은 priority의 작업은 낮은 priority를 가진 작업보다 먼저 실행
  priority가 같은 작업들은 동일한 priority 레벨에서 순환 할 수 있다.
• 이 알고리즘에서는 작업이 실행될 때 CPU를 독점하는 경우가 있을 수 있다.
  이러한 경우 다른 작업들이 실행되지 않아 대기 상태가 될 수 있으므로, 이를 방지하기 위해 preemption 기법을 사용한다.

  즉, 높은 priority를 가진 작업이 실행 중인 상태에서
  더 높은 priority를 가진 새로운 작업이 들어오면, 실행 중인 작업을 중단하고 새로운 작업을 실행한다.

• Task-level Fixed Priority 알고리즘은
  priority 인버전(priority inversion) 문제가 발생할 수 있다.
  
• 이는 높은 priority를 가진 작업이 낮은 priority 작업에 의해 사용 중인 공유 자원(CPU...)을 기다리는 경우, 높은 priority를 가진 작업이 낮은 priority 작업보다 priority가 낮아져서 실행이 지연되는 현상` 을 말한다.
  
• 이러한 문제를 해결하기 위해 (ex. EDF - Earliest Deadline First Algorithm)
  같은 기법들을 사용한다.

Job-level fixed-priority (JFP)

• Job-level Fixed Priority : 배치 처리 시스템에서 사용되는 Scheduling Algorithm
각 Process에 대해 미리 정해진 Priority를 할당하고, 이를 기반으로 다음에 실행할 Process를 선택하는 Scheduling Algorithm.
  
• 각 작업은 fixed priority를 가지며, 작업의 중요도와 긴급성에 따라 priority 가 결정된다.
  높은 priority의 작업은 낮은 priority를 가진 작업보다 먼저 실행
  priority가 같은 작업들은 동일한 priority 레벨에서 순환 할 수 있다.
  
• priority가 높은 작업이 지속적으로 실행, 낮은 priority 작업은 대기할 수 있다.
  » 기아(starvation) 현상
  
• 이러한 문제를 해결하기 위해서는 priority가 동적으로 조정되는 알고리즘을 사용하는 것이 좋다. (ex. EDF - Earliest Deadline First Algorithm)
  
  

——— TFP와의 차이점 ———

• Job-level Fixed Priority 알고리즘과 Task-level Fixed Priority 알고리즘은 우선순위 기반 스케줄링 알고리즘이라는 공통점이 있지만, 작업과 task 단위로 구분되는 것 외에도 중요한 차이점이 있다.

• 가장 중요한 차이점은 스케줄링의 정확성과 예측 가능성이다.
  Job-level Fixed Priority 알고리즘은 작업별 우선순위를 사용하여 스케줄링을 수행한다.
  따라서 작업별 처리 시간이 길어질수록, 다음 작업의 우선순위가 높아질수록 예측이 어려우며 스케줄링 오버헤드가 커질 수 있다.

• 반면에, Task-level Fixed Priority 알고리즘은 각 task에 우선순위를 할당하므로, 예측 가능성이 높다. task 간의 상대적인 우선순위를 고려하여 스케줄링을 수행하기 때문에 스케줄링 오버헤드를 줄이고, 시스템 전체적인 성능을 향상시킬 수 있다.

따라서, Job-level Fixed Priority 알고리즘은 작업의 개수와 우선순위 변화에 따른 예측 불가능성이 높지만,
Task-level Fixed Priority 알고리즘은 작업의 개수와 우선순위 변화에 따른 예측 가능성이 높다.

긴 글 읽어주셔서 감사합니다. 혹시 잘못된 정보가 있다면 알려주시면 감사하겠습니다!!

Task Lists

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