Coding은 데이터 압축, 암호화, 오류감지 및 수정, 데이터 전송 및 저장에 사용되는 이론이다. 주된 목적은 데이터의 패턴을 분석해서 압축하여 통신을 가능하게 하는 것이다. 1. Source coding: Data compression데이터 압축의 목적으로 사용되는 coding의 경우, 가장 빈번하게 나오는 결과에는 짧은 표현을, 가장 덜 발생하는 결과에는 상대적으로 긴 표현을 주어 압축한다.(ex. 모스 부호가 한국인에게는 가장 유명하다) DefinitionsSource code란 부호화된 데이터라고 보면된다.$c(x)$ : codeword of x$l(x)$ : $c(x)$의 길이$D*$ : D-ary alphabet으로 만들 수 있는 source code의 집합 (유한한 길이) Code를 평가하..

Real-time OS에 대한 소개와 Static RTOS, UNIX-like RTOS에 대해 다룬다. 1. RTOS?Predictable + well structured real-time application의 구현을 간단하게 해주는 resource management + abstraction을 RTOS라고 한다.Predictable : worst-case delay를 statically determine할 수 있음Resource management & abstraction : 제한적인 HW 자원을 multiplexing + 일관된 interface General purpose PC와 다른 점은 크게Full control (no kernel-level)Compile time에 시스템 config. 결정..

Uniprocessor(가정)에서 하나의 system 내에 서로 다른 중요도를 가진 system이 있을 때, 스케쥴링하는 방법에 대한 설명이다. 가령 자율주행 차량의 ABS와 스테레오 음향 시스템을 생각해 보면, ABS가 훨씬 중요함을 알 수 있다. WCET에 대한 정의도 다를 수 있다. Certification requirements가 다를 경우, 동시에 진행되는 task임에도 다른 WCET 측정 방법이 진행된다. 현재 주로 사용 중인 방법은 space-time partitioning으로 각 서브시스템 마다 time slot을 할당해 관리하고 있다. (Isolation을 통한 분석이 진행되었다.) 다만, High criticality system의 경우, 너무 보수적으로 WCET를 측정하다 보니, WC..

앞에서는 uniprocessor 환경이었고 이제는 multiprocessor 환경이다. Multiprocessor에는 칩 성능에 따라 크게 3가지 종류가 있다.identicaluniform heterogeneousunrelated heterogeneousSpeed : 동일Capability : 동일Speed : 다름Capability : 동일Speed : 다름Capability : 다름 Multiprocessor 환경에서 스케쥴링이 어려운 이유는 task마다 한개의 processor를 사용하기 때문이다. 대표적으로 두 가지 스케쥴링 방식이 있다.Partitioned schedulingTask가 statically 코어에 할당됨코어 당 하나의 ready queue가 있음Uniprocessor schedul..

Priority inversion 문제와 이를 해결하기 위한 동기화 프로토콜에 대한 설명이다. 1. Priority InversionPriority-based preemptive scheduling에서 priority는 task의 중요도나 긴급하게 실행해야 함을 의미한다. Priority inversion은 high priority task가 low priority task에 의해 실행이 되지 못하는 경우를 말한다. 대부분의 경우 해로운 것은 아니나, 특정 상황에서 심각한 지연이 발생할 수 있다. Shared resource에 대한 mutex나 non-preemptive sub-system access와 같은 이유로 발생할 수 있다. 가령 화성의 패쓰파인더는 이 문제로 제어 불능 상태에 바졌던 적이 있다..

스케쥴링 가능성을 분석하는 방법에 대해 배운다. 또한, 이론적으로 가능하더라도 현실적으로 불가능할 수 있다는 사실을 알아야 한다. 우선, 스케쥴링 분석 여부에 따라 Exact와 Only sufficient로 나뉘게 된다.Exact : 모든 Task가 스케쥴링 가능하며, analysis 가능함Only Sufficient : 일부 Task가 스케쥴링 가능하며, analysis 가능함 보다 쉬운 이해를 위해 지금부터는 다음의 가정을 사용한다. 반대로 말하면, 다음의 내용이 실제 구현에 있어 고려할 내용임을 의미한다.Single processorHard deadlineIndependent periodic tasks$d_i = p_i$PreemptableNo overhead for context switch 1...

Set of tasks가 deadline과 함께 주어지면, real-time scheduling을 통해 policy에 따라 computing 자원에 task를 할당하게 된다. 목표는 deadline을 최대한 충족하는 것이다. 스케쥴링 알고리즘을 제안할 수도, 스케쥴 가능성(schedulability)을 분석할 수도 있다. Schedulability란 real-time 시스템이 모든 task의 deadline을 충족시킬 수 있는 지를 의미한다. 이를 만족하기 위해 스케쥴링을 통해 task의 실행 순서를 결정한다. 1. Priority-based 스케쥴링Task-level fixed-priority (TFP) 스케쥴링 : 각 task에 고정된 priority 부여Job-level fixed-priority ..

Embedded system이 복잡해지고 interconnected되면서 다양한 산업에 사용되게 된다. 그러다 보니 새로운 개념이 되었고, 이를 Cyber-Physical Systems (CPS)라 부르게 된다. 1. CPS란 무엇인가?Cyber/computational components에 의해 controll되고 integrated되는 physical system을 말한다. 이러한 시스템은 physical system의 실시간 데이터를 기반으로 의사결정을 내리며, 자율주행 차량, 스마트 그리드 등 다양한 분야에 활용된다. 기존의 embedded system과의 가장 큰 차이는 다음과 같다. 기존에는 서브 시스템 간의 black box 관계를 가졌던 것과 다르게 CPS는 서로 open protocol로..

1. 임베디드 시스템이란?특정 기능 수행을 위해 설계된 컴퓨터 시스템으로 general purpose PC와는 다르다. 종종 하드웨어와 소프트웨어가 통합된 형태로 존재한다. 2. 실시간 시스템이란?결과의 correctness도 중요하지만, 더 중요한 것은 시간 내에 결과가 도출되는 것이다. Deadline을 맞출 수 있다면, 몇가지 task를 포기하는 것도 가능하며 대표적으로는 자율 주행 차량과 웹 서버 등이 있다. 임베디드 시스템과 실시간 시스템의 차이는 다음과 같다.Real-time embeddedReal-time, but not embeddedEmbedded, but not real-timeNuclear reactor controlFlight controlMobile phoneDroneStock t..