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..

Cartersian product Binary relation a set of oredered pair로 나타낸다. set이기 때문에 set의 연산이 모두 가능하다. Binary relation은 두개의 pair의 관계를 나타낸 것이고 3개면 ternary, 4개면 quaternary라 한다. 표기는 다음처럼 한다. Ternary relation 4개일 때, n-ary일 때 모두 같다. Properties of Binary relations Reflexive relation (a,a)가 R에 있는 경우 Symmetric relation (a,b)가 R에 있으면 (b,a)도 있는 경우 Empty set U={}인 경우에도 성립한다. 대신 reflexive는 만족하지 않는다. S={(a,a)}면 symmet..

Permutation $$n(n-1)(n-2)...(n-r+1)=\frac{n!}{(n-r)!} = P(n,r)$$ #Example 하루에 한과목씩 7일동안 공부하려고 한다. 공부가 필요한 과목은 수학, 화학, 물리, 경제이다. 최소한 7일동안 각 과목을 한번씩 공부할 경우의 수는 얼마인가? A) 한번도 공부하지 않는 경우를 가정해 전체 경우에서 빼주면 된다. 전체의 경우: $4^7$ let $A_1$: 수학 한번도 공부 안하는 경우 $A_2$: 화학 한번도 공부 안하는 경우 $A_3$: 물리 한번도 공부 안하는 경우 $A_4$: 경제 한번도 공부 안하는 경우 그러면 정답은 $4^7 - |A_1 \cup A_2 \cup A_3 \cup A_4|$이다. $|A_1 \cup A_2 \cup A_3 \cup ..

개념적인 이야기가 많아서 그냥 나열해서 설명한다. $X$와 $Y$가 disjoint면, $X \cap Y = \emptyset$ Combinations of sets $P-Q$ : difference $\{a,b,c\}-\{a,b,d\} = \{c\}$ $P \oplus Q$ : symmetric difference $\{a,b,c\} \oplus \{a,c,d\} = \{b,d\}$ P와 Q에 동시에 속하지 않는 element이다. $\overline{Q}$ : complement Q의 여집합 Power set $P(\{a,b\}) = \{\{\}, \{a\}, \{b\}, \{a,b\}\}$ 집합의 크기가 $k$이면, $2^k$의 elements를 가짐 Properties of Sets Finite ..

Entropy $$H(X) = - \sum p(x) log p(x)$$ Properties of H $H(X) \geq 0$ $H_b(X) = log_b a H_a(X)$ Conditioning reduces entropy $H(X|Y) \leq H(X)$ (w/ eq. iff X and Y are independet) $H(X_1, X_2, ..., X_n) \leq \sum H(X_i)$ (w/ eq. iff $X_i$ are independent) $H(X) \leq log |X|$ (w/ eq. iff X is uniformly distributed over X) $H(p)$ is concave in $p$ Relative Entropy $$D(p||q) = \sum p(x) log \frac {..

AEP 덕분에 $X_i$가 iid인 경우에, $nH(X)$ bit만 있으면 데이터를 표현할 수 있었다. 그런데 RV가 iid가 아니거나 stationary RV라면 어떻게 될까? 우선 프로세스는 크게 Stochastic process와 Stationary process로 나뉜다. Stochastic process Joint distribution으로 표현 가능한 경우이다. 가령 Entropy의 stochastic process는 다음처럼 나타낼 수 있다. Stationary process 시간에 따라 distribution이 변하지 않는 경우이다. Markov Chain 바로 직전의 결과만이 현재에 영향을 주는 경우를 말한다. Initial state와 transition matrix가 중요하다는 것을 ..

대수적 균등 분할 원리라 하며, 큰 수의 법칙과 밀접한 관련이 있다. 장기간에 걸쳐 확률적 과정의 결과가 어떻게 나타나는지 다룬다. Convergence of Random Variable $X_i$가 iid이며 $E(X_1)=E(X_2)=...=E(X_n)$을 만족한다고 가정하자. 이때 $\overline{X_n}=\frac{1}{n}(X_1+...+X_n)$이라고 하자. 그러면 대수의 법칙에 의해서 $n→\infty$, $\overline{X_n}→\mu$가 된다. 우리는 그러면 $\overline{X_n}$을 다음을 만족하는 RV라고 생각해볼 수 있다. 두가지 type(strong, weak)으로 수렴이 인식된다. Types of Convergence 수렴의 종류는 구체적으로 4가지로 구분된다. A..