Leo's Garage

Mutually exclusive resource sharing위의 경우 A Resource에 두 Task가 동시에 접근이 가능한 경우인데, 이 경우 A의 값이 정상적으로 업데이트 되지 못한다. 아래의 경우는 Mutually Exclusive가 적용된 케이스로 A가 최종적으로 2로 업데이트 되게 된다.Unbounded Priority Inversion우선순위 반전 개념높은 우선순위 작업이 낮은 우선순위 작업에 의해 지연될 때 발생즉, 높은 우선순위 작업이 낮은 우선순위 작업에 막혀서 실행되지 못하는 현상반전의 발생 조건주로 동기화(Synchronization) 중 발생상호 배제(mutual exclusion)때문에 Job간에 지연 발생 가능 가령 낮은 우선순위 작업이 자원을 갖고 있는 상태에서, 높은 우..

앞 선 장에서는 Fixed Priority 스케줄러 기반의 Server에 대해 알아보았다. 이제는 Dynamic Priority에서 Server를 알아보자.Constant Utilization ServerKey Idea서버는 $u_s$라는 예산을 받게 되는데, 이는 요청된 Request의 Deadline에 따라서 해당 $u_s$만큼 받는 구조이다.초기화$e_s = 0$, $d_s=0$ (서버 예산과 마감시간 초기화)요청 도착 시 (at time $t$)Queue가 비어있지 않으면 -> Queue에 추가$t 아무것도 안함 (Queue에 추가만)그 외의 경우$d_s=t+\frac{e}{u_s}$$e_s=e$(새 요청만큼 서버 예산 설정)현재 시간이 $d_s$가 되었을 때, Queue에 요청이 있다면, 맨 앞..

Types of Aperiodic RequestsSoft aperiodic Task:푸아송 분포와 같이 랜덤하게 요청지수 분포처럼 랜덤한 실행 시간일반적으로 User Request를 모델링한다.Firm aperiodic Tasks(Sporadic Tasks:각각 요청된 Job은 확실한 Deadline 내에 끝나야한다.2개의 연속 요청 사이에는 최소한의 간격이 존재WCET Bound가 있다.일반적으로 위급한 상황을 모델링한다.그렇다면 이런 Aperiodic Task는 어떻게 처리해야 하는가? 1. Interrupt Handling특징: Aperioic Task가 발생 시, 즉시 인터럽트 핸들러에서 처리장점: 매우 짧은 응답 시간단점: Periodic Task가 방해 받아 Deadline Miss 발생 가능..

Why analytical methods?MeasurementWCET 보장 불가: Branch, Loop Count, Cache hit/miss에 따라 시간 변동 -> 모든 경로 실측 불가능시간과 비용소모: 반복 실행과 시뮬레이션이 매우 비싸고 오래걸림Design Phase 적용 불가: 실행 가능한 코드 & 환경 준비 후에 측정 가능Analysis(정적 분석 기법)의 장점WCET 보장: 최악의 실행시간을 안전하게 상한으로 계산 가능 (Safe Bound 제공)자동화 가능: 대부분 분석은 자동화 도구 수행 가능Design Phase 적용 가능: 코드 작성 초기에 분석 가능 Basic Analysis MethodBasic Construct: 단순 대입문 Ex. i=0, a=b+cSequential Con..

EDF with Practical Environment EDF with deadlines less than the periods$$D_i$$\sum_{j=1}^{n}\frac{e_j+p_j-D_j}{p_j}\leq 1\,\,increase\,\,execution\,\,time$$$$\sum_{j=1}^{n}\frac{e_j}{D_j}\leq 1\,\,\,decrease\,\,period$$ EDF with Non-preemptable Code SectionLow Priority의 NPS(Non-preemptable code section)은 High Priority Task를 Block한다.$$b_i=max_{j=i+1}^{n}NPS\,\,\,D_i1. $\sum_{j=1}^{n}\frac{e_j}{p..

EDFEDF (Earliest Deadline First) Scheduler는 Real Time System에서 널리 사용되는 Dynamic Priority Based Scheduling Algorithm이다. 각 Job의 Deadline에 따라 우선순위를 결정하며, Deadline이 가장 빠른 Job부터 먼저 실행된다.핵심개념요소설명우선순위 결정 기준마감 시간이 가까울수록 우선순위가 높음작업(Task)실시간 작업: (도착 시간, 실행 시간, 마감 시간) 정보를 가짐스케줄링 방식동적(Dynamic): 시간이 지남에 따라 우선순위가 바뀜선점 가능성선점형(Preemptive) 구현 가능 – 새로운 작업이 더 이른 마감시간을 가지면 실행 중인 작업을 중단하고 실행 장점Optimality: 단일 프로세서 환경에..

느낀점 Problem Statement전통적인 MAC(Medium Access Control) 프로토콜과 제안하는 것과 차이는?논문에 따르면 전통적인 MAC 프로토콜은 센서 네트워크에 적합하지 않다. 이는 센서 네트워크가 기존 Ad hoc 네트워크와 근본적인 면에서 다르기 때문이다. 주요 차이점은 아래와 같다.트래픽 특성: 전통적인 프로토콜은 네트워크 트래픽이 본질적으로 무작위라고 가정하는 경향이 있다. 그러나 이 가정은 센서 네트워크에서는 적용되지 않는다. 센서 네트워크의 메시지는 주로 주기적이며 유한한 지연이 보장되어야 한다. 목표: 전통적인 CSMA 및 그 변형은 시스템 처리량 극대화에 초점을 맞춘다. 센서 네트워크에서는 최적화 목표가 원시 처리량에서 타이밍 제약 조건을 충족하는 비 중복 데이터..

느낀점 Problem Statement어떻게 Voltage Scheduling 기술이 실시간 시스템의 전력소모를 최소화할 수 있는가?Voltage Scheduling 기술은 프로세서의 속도를 줄임으로써 에너지 소비를 최소화한다. 휴대 기기에게 배터리 수명을 연장하는 효과적인 방법이다. 이 기술은 전력 소비율($P$), 공급 전압($V_s$), 클럭 주파수($f$) 간의 관계를 활용한다. 이 관계는 대략 $P = C \cdot V_s^2 \cdot f$로 설명된다. 프로세서 속도와 주파수($f$)는 공급 전압($V_s$)에 거의 비례하기 때문에, 전력 소비율은 공급 전압의 세제곱에 대략 비례하게 된다. ($P = K \cdot V_s^3$, 여기서 $K$는 상수). 따라서 공급 전압을 낮춰 프로세서 속..

느낀점 Problem StatementRealTime Task의 "Parallellization freedom"은 OpenCL 및 OpenMP와 같은 최신 병렬 컴퓨팅 프레임워크에서 Task를 여러 가지 방법으로 병렬화할 수 있게 해주는 개념이다. 예를 들어 한 차선 추적 프로그램은 단일 스레드, 두 개의 스레드, 세 개의 스레드, 네 개의 스레드로 실행될 수 있다. 이러한 프레임워크에서는 각 Task 병렬화되는 스레드의 수인 "Prallelization option"을 신중하게 결정해야 다중 CPU 코어를 더 잘 활용하여 스케줄 가능성을 극대화할 수 있다. 이 논문은 특히 Global EDF(G-EDF) 스케줄링 환경에서 Task 병렬화 옵션을 최적으로 할당하는 방법을 제안한다.병렬화 자유가 G-ED..

느낀점 이 논문은 멀티프로세서 실시간 시스템에서의 응답시간 분석의 복잡성과 한계를 뛰어넘기 위한 정교한 수학적 모델을 제시했다는 점에서 인상 깊었다.간섭과 워크로드를 정량적으로 상한 처리하며 반복적으로 응답시간을 수렴시키는 방식은 논리적이고 적용 가능성도 높다고 느꼈다.특히 slack을 활용해 분석 정확도를 점진적으로 높이는 방식은 단순한 이론을 넘어서 실용적인 해법임을 보여준다. Problem Statement멀티프로세서 하에서 Real Time Scheduling 분석의 근본적인 문제가 무엇일까? (논문 발행 기준으로) 최근 몇 년 동안 일반 및 임베디드 시스템 시장에서 단일 프로세서 칩에서 멀티코어 컴퓨팅 장치로 점진적인 전환이 일루어졌다. 이러한 추세에 따라 실시간 커뮤니티에서는 고전적인 스케줄링..