Leo's Garage

Reference Model실시간 시스템에서 우리는 다음과 같은 Reference Model을 선정할 수 있다. Periodic Task Model$\theta_i$: Phase$p_i$: Period$e_i$: Execution Time$D_i$: Relative Deadline from the beginning of the period.분석의 용이를 위해서 기본적인 가정을 하는 경우가 있는데, $D_i = p_i$로 가정하는 경우가 있다. 여기서는 몇 가지 전제를 하고 이야기를 하려고 하는데 모든 Task들은 독립적이다. (서로 공유자원을 사용하지 않는다.)여기에는 aperiodic Task나 sporadic Task가 존재하지 않는다.언제든지 Peemption할 수 있다.Context Switch..

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: 단일 프로세서 환경에..

Real Time System을 공부하다보면, Scheduler라는 걸 학습하게 된다.이것은 왜 필요하게 되었을까? 자원은 한정되어 있고, 요청은 많아지기 때문에CPU, Memory, Bus 등 시스템 자원은 유한하다. 동시에 여러 작업이 실행을 요구하는 상황에서, "누가 먼저, 얼마나 오래 실행되는가?"를 정할 필요가 있다.이것이 바로 Scheduling 문제의 본질이다. Scheduler 진화 배경시대시스템 구조스케줄링 필요성해결책1950s단일 프로세스없음 (순차적 실행)수동 제어1960sMultiprogramming 등장CPU idle 줄이기 위해 Task 전환 필요Round Robin, FCFS 등1970sReal-Time OS 등장Task마다 데드라인 생김Rate Monotonic, EDF20..

구분MutexSemaphoreSpinLock역할상호 배제 (Mutual Exclusion)자원 개수 제한 + 동기화빠른 상호 배제 (Busy-wait)대기 방식Sleep (Block, Context Switch 발생)Sleep (Block, Context Switch 발생)CPU 점유 (Spin, Context Switch 없음)멀티코어 적합성 코어 간 경쟁 발생 시 지연시간 증가제한된 자원 관리 시 유용멀티코어에서 짧은 보호구역에 적합실시간성우선순위 역전(Priority Inversion) 위험지연 발생 가능, 예측성 낮음짧고 결정적인 시간 내 Lock/Unlock사용 예시장시간 접근 필요 자원 (ex. 설정 데이터)Buffer, Queue, Rate Control인터럽트 핸들러, 짧은 크리티컬 섹션우..

앞 서 Monolithic Design Approach에 대해서 알아보았다. 말한 것과 같이 Monolithic Design Approach는 구성 요소를 구분하기 보다는 하나의 Binary 형태로 모든 기능 요소를 구성하는 특징이 있다. 만들기 쉽고, 특히나 빠른 개발이 필요한 상황에서는 빛을 발하기 쉽다. (프로토 타입 개발)그러나 이러한 개발방법은 유지보수가 어렵고, 해당 개발을 기준으로 파생 제품을 만들고자 할 때 어려움이 생긴다.가령 데이터 통신 프로토콜 함수 부분과 통신 처리 부분, 연산 부분이 모두 하나로 합쳐져 있는 구조라면, 통신 프로토콜이 변경되었다고 해서 간단하게 그 부분만 수정하기 어려울 수 있다는 것이다. 게다가 Super Loop를 주로 사용하는 개발방법으로 복잡한 시스템을 개발..