Leo's Garage

느낀점 Problem StatementQ-RAM(QoS 기반 자원 할당 모델)이 다루는 근본적인 문제(Fundamental Problem)는 동시에 실행되고 동일한 자원 유형을 놓고 경쟁하는(Run Concurrently and Contend for the same resource types) 여러 애플리케이션에 자원을 할당하는(Allocate Resources)것이다. 이러한 애플리케이션은 타이밍, 신뢰성, 보안 제약 조건은 물론 애플리케이션 별 품질 요구사항을 만족해야 한다.Q-RAM은 특히 다음과 같은 시스템 요구사항을 충족하기 위해 자원을 할당하는 분석 모델로 제시된다.Timeliness, Reliable Delivery Schemes, Cryptographbic Security, Data Q..

느낀점 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 분석의 근본적인 문제가 무엇일까? (논문 발행 기준으로) 최근 몇 년 동안 일반 및 임베디드 시스템 시장에서 단일 프로세서 칩에서 멀티코어 컴퓨팅 장치로 점진적인 전환이 일루어졌다. 이러한 추세에 따라 실시간 커뮤니티에서는 고전적인 스케줄링..

느낀점Stack 메모리의 효율적 사용이라는 실용적 문제를 수학적으로 분석한 점이 인상 깊었다. Fixed Priority Scheduling 환경에서 공유 Stack 모델의 안전성과 효율성을 정량적으로 입증해주며, 직관적으로 설명해준다는 점이 좋았다. Problem Statement이 논문에서는 실시간 시스템에서 발생하는 Priority Inversion, Deadlock, 그리고 Blocking 문제를 해결하기 위해 기존의 Priority Ceiling Protocol(PCP)를 확장한 새로운 정책인 Stack Resource Policy(SRP)와 Minimal SRP(MSRP)를 제안한다. 실시간 시스템에서는 우선순위 기반 스케줄링 시 발생하는 대표적 문제:Priority Inversion (우선..

느낀점이 논문은 실시간 시스템 이론의 초석이 된 고전으로, 이 논문이 출판된 이래로 이 내용은 수많은 실시간 스케줄링 알고리즘의 기반이 되었다. 특히 Rate-Monotonic과 Deadline-Driven Scheduling은 오늘날에도 널리 사용되고 있다. 증명 내용 단계 단계가 간단명료하고 직관적이어서 이해하기에 어렵지 않았다. 잘 쓴 논문이란 이런 것인가 하는 생각과 더불어 도대체 이런 아이디어는 어떻게 생각해내는지 궁금하다. Problem Statement본 논문은 Hard Real-Time Environment에서 단일 프로세서 위에서 동작하는 Multi Programming Task들의 Scheduling 문제를 다룬다. 이 환경에서 모든 Task들이 정해진 Deadline 내에 반드시 완료..

느낀점 사전 필요 지식멀티프로세서 실시간 시스템에서 공유 자원에 대한 상호 배타적 접근과 관련하여 데이터 무결성을 보장하고 예측 가능한 타이밍을 유지하기 위해서 여러 자원 공유 프로토콜이 개발되었다. 기존 멀티프로세서에서 자원 공유 프로토콜은 크게 두 가지 범주로 분류할 수 있다.1. 서스펜션 기반(Suspension-based) 프로토콜: 자원 요청이 즉시 충족되지 않으면 Task가 스케줄러에 의해 전환(Switch Away)된다. 이는 빈번한 Context Swtiching을 야기하여 상당한 Overhead를 발생시킬 수 있다.2. 스핀 기반(Spin-based) 프로토콜: Task는 자원이 부여될 때까지 해당 프로세서에서 자원을 적극적으로 대기(Spin)한다. Spin Lock은 복잡성이 낮아서 실..

느낀점 기존의 GFB와 BAK 테스트가 완벽하지 않다는 점을 실제 반례와 함께 명확히 보여줘서 이해가 쉬웠다.새로운 BCL 테스트는 수학적으로도 설득력 있고, heavy task가 있을 때 훨씬 실용적이라는 점이 인상 깊었다.전체적으로 복잡한 이론을 실험과 함께 잘 설명해줘서 멀티코어 스케줄링 연구의 흐름을 배우기에 좋은 논문이었다. Background Knowledge본 논문을 이해하는데 필요한 여러 측면의 시각을 정리해보겠다. Multi Processor 하드웨어 플랫폼이 임베디드 시스템에서 널리 사용되고 있으며, 실시간 어플리케이션을 스케줄링할 때 글로벌 스케줄링 방식을 사용할 수 있다. 글로벌 스케줄링에서는 스케줄링 알고리즘이 Task를 프로세서와 동적으로 할당하며, Task는 실행 중에 다른 프..

느낀점현재 보고 싶은 논문이 있는데, 해당 논문에 나온 몇 가지 개념들을 익히기 위해서 이 논문을 리뷰하고 있다. 문제 정의나 해결하는 방법에 대해서는 큰 어려움없이 쉽게 읽히고 이해가 간다. Problem Statement실시간 시스템에서 공통적으로 사용되는 동기화 방식(세마포어, 모니터 등)은 Priority Inversion(우선순위 역전) 문제를 유발할 수 있다특히, High Priority Task가 Low Priority Task에 의해 Blocking되는 상황 발생기존 연구에서는 Deadlock 방지가 미흡했고, Blocking 시간의 Worst-Case 분석이 어려웠다. 목표: 실시간성 보장을 해치지 않으면서, 우선순위 역전 문제와 Deadlock을 해결할 수 있는 효율적이고 분석 가능한 ..