Cubic Spline Interpolation

Piecewise Polynomial

• 임의의 함수 y=f(x)의 근사
• 일정 간격으로 1차(직선)으로 근사 (linear interpolation) 시의 문제점
  • 각 근사 구간의 교점마다 그래프가 각진 형태로 나타남
  • 근사식의 오차가 크게 나타남
• 2차 식으로 근사 시
  • 그래프의 오차는 다소 줄어듦
  • 구간 접점의 문제는 해결 x
• n차 미분이 가능할수록 구간별 연결이 부드럽지만, 과할 경우 진동 문제 존재

Cubic Spline Condition

• 3차 다항식 $a_j+b_j(x-x_j)+c_j(x-x_j)^2+d_j(x-x_j)^3$를 구간별로 분할한 함수 $S,\ S_1,\ ...,\ S_j, S_{j+1},\ S_{n-2},\ S_{n-1}$
• 각 구간별 함수의 접점이 연속(Piecewise)할 것을 요구
• 연결점에서 연속되기 위한 조건 (for all j=0, 1, .. ,n-1)
  • $S_j(x_{j+1})=f(x_j)$
  • $S_{j+1}(x_{j+1})=f(x_{j+1})$
  • 1차 미분 : $S'_j=S'_{j+1}$
  • 2차 미분 : $S''_j=S''_{j+1}$
• 전체 함수의 개수가 갖는 계수는 총 4n개이므로
  • 2n개의 함수 연속 조건
  • n-1개의 1, 2차 미분 연속 조건
  • 총 4n-2개의 연속 조건을 갖게 됨 (2개가 더 있어야 계수의 계산이 가능)
  • 이를 위해 2개 조건을 더 추가 (Boudary Condition)
• Natural Boundary Condition : $S''(x_0)=S''(x_n)=0$ (기울기는 있으나 휨은 없음)
  • free boudary condition이 있는 곡선을 natural spline이라고 함
• ex. (1, 2), (2, 3), (3, 5)를 지나는 natural cubic spline을 구할 것
  • [1, 2]의 구간에서 $S_0(x)=a_0+b_0(x-1)+c_0(x-1)^2+d_0(x-1)^3$
  • [2, 3]의 구간에서 $S_1(x)=a_1+b_1(x-2)+c_1(x-2)^2+d_1(x-2)^3$
  • $f(1) = 2 = a_0,\ f(2)=3=a_0+b_0+c_0+d_0$
  • $f(2) = 3 = a_1,\ f(3)=5=a_1+b_1+c_1+d_1$
  • $S'_0(2)=S'_1(2)\rarr b_0+2c_0+3d_0=b_1$
  • $S''_0(2)=S''_1(2)\rarr 2c_0+6d_0=2c_1$
  • natural boundary condition
    • $S_0''(1)=0\rarr 2c_0=0$
    • $S_1''(3)=0\rarr 2c_1+6d_1=0$

• Cubic Spline의 계수 찾기

• $(x-x_j) = h_j$로 정의

  • $a_{j+1}=a_j+b_jh_j+c_jh_j^2+d_jh_j^3$
  • $b_{j+1}=b_jh_j+2c_jh_j+3d_jh_j^2$
  • $c_{j+1}=c_j+3d_jh_j$

• $c_j, c_{j+1}$을 안다고 할 때

  • $a_{j+1}=a_j+b_jh_j+\frac{h_j^2}{3}(2c_j+c_{j+1})$
  • $b_{j+1}=b_j+h_j(c_j+c_{j+1})$
  • b에 대해 정리하면 $b_j=\frac{1}{h_j}(a_{j+1}-a_j)-\frac{h_j}{3}(2c_j+c_{j+1})$
    • $b_{j-1}$에 대해 $b_{j-1}=\frac{1}{h_{j-1}}(a_{j}-a_{j-1})-\frac{h_{j-1}}{3}(2c_{j-1}+c_j)$
    • 식을 정리하면 $b_j=b_{j-1}+h_{j-1}(c_{j-1}+c_j)$

• $b_j-b_{j-1}$을 대입하여 정리하면
  $\rarr h_{j-1}c_{j-1}+2(h_{j-1}+h_j)c_j+h_jc_{j+1}=\frac{3}{h_j}(a_{j+1}-a_j)-\frac{3}{h_{j-1}}(a_j-a_{j-1})$

  • a, h값을 알면 c를 계산 가능
  • a, c를 이용하여 b 계산 : $b_j=\frac{1}{h_j}(a_{j+1}-a_j)-\frac{h_j}{3}(2c_j+c_{j+1})$
  • c, h를 이용하여 d 계산 : $c_{j+1}=c_j+3d_jh_j$

Secant Method

• newton method : $p_n=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}$
• secant method : newton method의 미분항(f')를 근사
  • $f'(p_n)\simeq\frac{f(p_n)-f(p_{n-1})}{p_n-p_{n-1}}$
  • $\Rarr p_{n+1}=p_n-f(p_n)\cdot\frac{p_n-p_{n-1}}{f(p_n)-f(p_{n-1})}$
  • 장점 : 미분항이 없음 = 개발 시 용이
  • 단점 : 초반 point 수가 두개 ($p_n,\ p_{n-1}$), newton method보다는 느림

False Position (Ragula Falsi)

• 기존의 Secant method는 계산에 따라 진동하면서 수렴할 위험 존재
• 두번째 point인 $p_1$을 계산 기준점으로 삼아 uniform하게 수렴하도록 계산

Order of Convergence

• $\{p_n\}^\infty_{n=0}$이 p로 수렵할 때
• $lim_{n\rarr\infty}\frac{|p_{n+1}-p|}{|p_n-p|^{\alpha}}=\lambda$에서 계수 $\alpha$가 수렴 형태를 결정
  • $\lambda$ : error constant
  • $\alpha=1, \lambda<1$ : linearly convergent
    • 식이 p=0으로 수렴한다고 할 때, $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|}=0.5$
  • $\alpha=2$ : quadratically convergent
    • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|^2}=0.5$
  • secant method의 경우 $p_n$의 계수가 $\frac{1+\sqrt{5}}{2}$
• bisection method / fixed-point method
  • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|}=\lambda$ : $\lambda$가 작을수록 빠른 수렴 / 0.5면 bisection
  • $|p_n|\simeq\lambda^2|p_0|$
• newton method
  • $lim_{n\rarr\infty}\frac{|p_{n+1}|}{|p_n|^2}=\lambda$
  • $|p_n|\simeq\lambda^{2^n-1}|p_0|^{2^n-1}$

Newton's Method

• Fixed Point method의 특별 case(가장 빠른 수렴)
• newton method가 불가능한 경우 보통 bisection method 사용 (fixed point method는 상대적으로 잘 쓰이지 않음)

• Taylor Polynomal
  • 계산된 fixed point p에 대해서
  • $f(p)=f(p_0)+(p-p_0)f'(p_0)+\frac{(p-p_0^2)}{2}f''(\zeta(p))$
  • $\zeta(p)$는 p~p0 사이엥 위치
• p가 f(x)의 근이면 f(p)=0
  • 이 경우 $0=f(p_0)+(p-p_0)f'(p_0)+\frac{(p-p_0)^2}{2}f''(\zeta(p))$
  • 2차항은 error 취급 : $0\simeq f(p_0)+(p-p_0)f'(p_0)$ (p : 근사해)
  • p에 대해 정리하면 $p\simeq p_0-\frac{f(p_0)}{f'(p_0)}\equiv p_1$
• Newton's method
  • $p_n=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}(n\geq1)$을 반복하여 근사해로 수렴
  • 이때 $p_n=g(p_{n-1})$이므로, $g(p_{n-1})=p_{n-1}-\frac{f(p_{n-1})}{f'(p_{n-1})}$로 표기할 수도 있다.
    

    

  • 곡선의 근을 구하기가 힘들다는 점에서 곡선에 접하는 접선의 근을 반복적으로 계산하여 곡선의 근으로 수렴한다.
• 장점 : 매우 빠른 수렴
• 단점 : 적절한 point 선정 필요 / 실제 개발 시 미분을 요구하므로 계산이 복잡해짐
• Convergence theorem
  • 위 식에서 $g(x)=x-\frac{f(x)}{f'(x)}$
  • Converence rate : $g'(x)=\frac{f(x)f''(x)}{[f'(x)]^2}$
  • 고정점에서 f(p)=0이므로 newton's method의 수렴 속도는 0으로 수렴 (매우 빠르다)

Memory Transfer

• 메모리에 데이터를 읽거나 쓸 때 필요한 버스(신호)
  • Address
  • Data
  • Control(Read, Write, etc...)
• 데이터의 이동
  • DR << M[AR] : address + data + control(read)
    • DR : Data Register
    • AR : Address Register - 메모리의 AR 주소에 해당하는 데이터
  • M[AR] << R1 : address + data + control(write)
    • 1번 레지스터의 내용 전체를 AR주소로 Write
    • 레지스터는 일부만 접근할 수 없으므로 반드시 전체를 복사
• 레지스터와 메모리의 차이
  • 레지스터는 항상 데이터가 출력중 : BUS와 Load 신호로 입-출력 조정
  • 메모리는 Control Signal을 통해 입-출력 조정

Arithmetic Microoperations

• Add operation
  • R3 << R1 + R2
  • 덧셈 : 모든 산술연산의 기본 ex. 뺄셈 : R3 << R1 - R2 = R1 + (R2' + 1)
  • Full-Adder
    • A + B + Cin = S + Cout
    • 아랫 자리에서의 올림수 Cin이 입력에 추가되고, 윗 자리로의 올림수 Cout이 출력에 추가
    • Ripple Adder : 전가산기 다수를 연결 - 구조가 단순하지만, 자리수가 커질수록 연산이 느려짐
      

      

  • Binary adder-subtractor
    

    

    • M 신호가 0이면 adder, 1이면 subtractor로 동작
    • M이 1일 경우 XOR에 1 입력으로 인해 B의 숫자는 2의 보수로 출력되고, Carry in에 1이 들어가 감산기로 동작 (R3 << R1 - R2 = R1 + (R2' + 1))
  • Binary incrementer
    • 반가산기(Carry in이 없음)의 한쪽 값에 항상 1이 들어감

Logic Microoperations

• 산술이 아닌 논리이므로 carry 없이 입력만으로 계산
  

  

  • 각 논리연산 (AND, OR, XOR, Not...)의 결과를 MUX로 출력 선택
  • n-bit unit : bit 개수만큼의 mux 연결

Shift Microoperation

• Shift operation의 종류
  • Logical, shl/shr (0 채우기)
  • Circular, cil/cir (rotational shift)
  • Arithmetic shift, ashl/ashr
    • ex. signed two's complement number (MSB가 1이면 -, 0이면 +)
    • shift right : sign bit는 변하지 않고, 해당 자리를 제외한 MSB를 sign으로 채움
      • ( ex. 1000 >> 1100 , 0111 >> 0011)
    • shift left : LSB는 0으로 채워짐, 나머지는 왼쪽으로 shift
      • ( ex. 0111(7) > 1110(-2, overflow), 1011(-5) >> 0100(6) )
      • Overflow check : (MSB) XOR (MSB 바로 아래 bit) = 1이면 overflow
• Shift circuit
  

  

  • S = 0 >> MUX의 0 input 출력 : A2 A1 A0 IR
  • S = 1 >> MUX의 1 input 출력 : IL A1 A2 A3

Fixed-Point Iteration

• $a\leq x\leq b$ 안에 정의된 f(x)가 f(p)=0인 값이 있다고 할 때, p=g(p)인 함수를 설정

• fixed point(고정점) : $p\in [a,b]$인 범위에서 g(p)=p인 [a,b] 범위 내의 함수 g가 있다고 할 때, g는 [a,b] 내에 고정점 p를 갖고 있다고 한다.

• Bisectional Method를 통해 얻은 근사해 $f(p_n)=0$을 구했을 때, 고정점으로 변환 시 $p_{n+1}=g(p_n)$으로 변환할 수 있다(iteration)

  • 이 n값을 무한으로 보내면 $p=g(p)$로 극한값을 구할 수 있다.

• y=x와 y=g(x)의 교점이 없는 경우 고정점 p는 존재하지 않음

  • bisectional method : (근이 있다면) 반드시 수렴하나, 계산이 느림(횟수가 많음)
  • Fixed-point : 적절한 함수 g(x)를 찾아야 하나, 계산이 빠르다

• $[0,1]$에서 $g(x) = 3^{-x}$의 함수를 정의할 때, $g'(x) = -3^{-x}log3$이므로 g(x)는 [0, 1]의 범위에서 감소함을 알 수 있다.

  • 그렇기 때문에 함수 g(x)는 [0, 1]의 영역(x범위)에 [0, 1]의 치역(y범위)를 갖고, 그 범위 내에서 감소하기 때문에 fixed point를 갖게 됨을 알 수 있다.

• 함수의 분포에 따라 범위 내에서 fixed point는 여러개일 수 있다.

  • 범위 [a, b] 내에서 [a, b] 범위로 연속하는 함수 g는, 미분값의 절대값이 1보다 작으면 유일한 fixed point를 갖게 된다.

  • [a, b] 범위의 x에서 $|g'(x)| < 1$를 만족하면 g의 fixed point는 하나만 존재한다.

  • 증명 : fixed point가 하나가 아닐 경우

    • $|p-q|=|g(p)-g(q)|=|g'(\zeta)||p-q|$ ( 평균값 정리 )
      < |p-q| (위의 정의에 따라서) 이므로 모순

• ex. f(x) = x-cosx = 0일 때

  • f(x)에서 x = cos(x) >> x가 fixed point
  • $p_{n+1}=cos(p_n)$의 극한을 구할 때 수렴 확인 - 약 p=0.739일 때 p=cos(p)의 식을 만족

• ex2. $g\in C[a,b]$이고, 모든 $x\in [a,b]$에 대해 $g(x)\in [a,b]$일 때, 함수 g가 고정점을 [a,b] 내에 갖는지?

  • C[a,b] : [a,b] 범위에서 연속인 함수의 집합 (continuous)

  • 입력 - 출력이 모두 [a,b]의 범위에 있는 함수 g를 의미

  • case 1. g(a) = a, g(b) = b >> 고정점이 반드시 존재

  • case 2. case 1이 아닌 경우

    • h(x)=g(x) - x로 정의하면, h(a)h(b) < 0 으로 IVP 성립 : g(c)-c=0으로 fixed point 존재한다.

• ex3. $x^2-x-1$

  • case 1. $x=x^2-1$ : $g(x) = x^2-1$
  • case 2. $x^2=x+1\rarr x=\sqrt{x+1}$ : $g(x)=\sqrt{x+1}$
  • case 2.를 이용한 풀이 :
    • x=0일 때 g(x) 값 계산
    • g(x) = x인 $x_1$값 계산
    • $g(x_1)$ 계산 후 과정 반복
    • 오차가 일정 이하가 되는 지점에서 해 계산

• $x^2-x-1=0$
• case 1. $x^2 = x+1 \rarr g(x) = \sqrt{x+1}$
  • x=0에서 반복 시작
    • g(0) 계산값을 g(0)=x로 대입
    • 계산된 x값을 다시 g(x)에 대입
    • 해당 과정을 일정 오차 이하기 될때까지 반복
      

      

    • 미분 계산 : $g'(x)=\frac{1}{2\sqrt{x+1}}$ - x가 -3/4보다 클 때 미분값은 항상 1보다 작게 되어 하나의 fixed point만 존재
• case 2. $x^2 = x+1 \rarr g(x) = 1+1/x$
  • 미분 계산 : $g'(x)=-1/x^2$이므로 x>1일 때 항상 $|g'(x)|<1$
  • 고정점 계산
    • $p_0=1\rarr p_1 = 2$
    • $p_1=2\rarr p_2=1.5$
    • $p_2 = 1.5\rarr p_3=1.666...$
    • $p_3=1.666\rarr p_4 = 1.6$
      

      

    • 위 과정을 반복
• Contraction Rate
  • 계산된 fixed point에서 g(x)의 미분값
  • Contraction Rate가 작을수록 빠르게 수렴 = 정확한 해에 더 빠르게 도달

• $x^3+4x^2-10$을 fixed point form으로 변환시 가능한 변환 형태

  • $x=x-x^3-4x^2+10$

  • $x=\sqrt{10/x-4x}$

  • $x=\frac{1}{2}\sqrt{10-x^3}$

  • $x=\sqrt{\frac{10}{4+x}}$

  • $x=x-\frac{x^3+4x^2-10}{3x^2+8x}$

• 1은 발산, 2는 허수가 되어 fixed point 게산 불가
• 5번의 경우가 가장 빠르게 fixed point로 접근하나, 상식적으로 생각 가능한 경우는 아님

• fixed point eq.의 수렴 증명
  • unique한 fixed point의 존재 조건에 의해 $|g'(x)|\leq k<1$
  • 즉 n번째 fixed point에 대해 $|p_n-p|\leq k|p_{n-1}-p|$
    • 이 계산을 0번째 fixed point(초기값)까지 반복하면 $|p_n-p|\leq k^n|p_0-p|$
  • k가 1보다 작기 때문에 반복(n)을 무한히 반복하면 오차 $|p_n-p|$는 0으로 수렴
• Corollary to the convergence result
  • $n\geq1$인 n에 대해 $|p_{n+1}-p_n|=|g(p_n)-g(p_n-1)|\leq k|p_n-p_{n-1}|$
    $...\leq k^n|p_1-p_0|$
  • $m>n\geq1$일 때, $|p_m-p_n|=|p_m-p_{m-1}+p_{m-1}-p_{m-2}+...+p_{n+1}-p_n|$
    $...\leq k^{m-1}|p_1-p_0|+k^{m-2}|p_1-p_0|+...+k^n|p_1-p_0|$
    $...\leq k^n(1+k+k^2+...+k^{m-n-1})|p_1-p_0|$
  • m이 무한으로 갈 때 위 식이 무한등비수열의 합이므로, $|p-p_n|=\frac{k^n}{1-k}|p_1-p_0|$
  • $\therefore |p-p_n|=\frac{k^n}{1-k}|p_1-p_0|\leq\epsilon$의 식으로 반복 회수 계산 가능

Root finding problem

• $f(x)=0$의 식을 만족하는 함수 f에 대해 근(해)를 찾는 과정
  • 이 식을 함수 f의 영점(zero) 라고 함.

Bisectional Method

• 중간값 정리(Intermediate Value Theorem, IVT)
  • 함수 f(x)가 [a, b] 범위 내에 정의 (f는 연속)
  • $f(a)f(b) < 0$이면 그 범위 내에 $f(p)=0$인 p가 존재
• bisectional method
  • $a_1=a, b_1=b$로 정의, a-b 사이의 중간점 p를 이용
  • $p_1 = \frac{a_1+b_1}{2}$
  • $f(a_1)f(p_1), f(p_1)f(b_1)$ 종 IVP를 만족하는 구간에 대해 위 과정을 반복
  • 오차가 일정 이하가 될 때 해당 값을 근으로 설정
• 오차
  • 절대오차(absolute error) : $p_N - p_{N-1} < \epsilon$
  • 상대오차(reletive error) : $|p_N - p_{N-1}|/|p_N| < \epsilon$
• Bisection method의 convergence rate
  • 수렴의 빠르기
  • $|p_n-p|\leq\frac{b-a}{2^n}$
  • $\therefore$ bisection method는 $O(\frac{1}{2^n})$의 빠르기로 수렴
  • Error bound : Convergence rate를 이용한 반복 회수 예측
    • $|p_N-p|\leq2^{-N}(b-a)<\epsilon=10^{-m}$
    • $-Nlog2<-m\rarr N>\frac{m}{log2}$

What Operating Systems Do

• 컴퓨터 시스템의 구조 : Hardware (CPU, mem, I/O, ...) > Operating System > Application (Compiler, Browser, SDK, ...) > User

• 사용자 관점에서의 운영체제

  • 간편한 실행, 빠른 속도
  • 모바일 기기의 발전으로 UI의 형태도 다양화 ex. 윈도우(키보드 + 마우스) >> 스마트폰(터치스크린)
  • 사용자 관점이 없는 HW 역시 존재 ex. Embedded System

• 시스템 관점의 운영체제

  • 시스템과 유저가 1:N 관계
  • 자원 활당 및 관리 역할
  • HW / 유저 프로그램 사이의 조율

• 운영체제의 정의

  • 좁은 의미 : OS 동작 시 상주하는 프로그램(커널)

Computer System Organization

• 버스 : CPU, 디스크, 메모리, USB 등의 다수 기기를 연결

• 컨트롤러 : 컴퓨터 주변 기기를 제어

• 버퍼 메모리 : 각 컨트롤러의 결과 저장

• 드라이버 : CPU가 명령을 내릴 때 동작 방식 등을 정의

• [ CPU - 메모리 - 버퍼 ] 및 [ IO - 버퍼 ]의 과정으로 각각 통신

• 인터럽트
  • 주변 디바이스들이 CPU에게 이벤트 발생을 알려 주는 것 (ex. HDD의 읽기 완료 신호)
  • Interrupt Service Routine(ISR) : 인터럽트 발생 시 동작해야 하는 명령어
    • 인터럽트 벡터 : ISR이 저장된 주소, 실행하여야 하는 ISR 함수의 메모리 위치를 기록한 Array
  • 인터럽트 발생 시 : > 수행하던 작업 일시 중지 > 인터럽트 처리 > 복귀 후 작업 재실행
  • SW적인 인터럽트도 존재 : Exception(예외)
• Interrupt handling
  • 인터럽트 발생 시 OS는 작업 중이던 프로그램의 상태를 저장
  • 어떤 인터럽트가 발생했는지 확인할 필요
    • Polling : 디바이스별로 확인, 최근에는 거의 쓰이지 않음
    • Vectored Interrupt System : 각 번호(index)에 해당하는 인터럽트 확인
• 인터럽트 발생 순서 (I/O Device)
  1. CPU(OS) : driver에게 I/O request 명시
  2. Driver : I/O 컨트롤러에 맞는 명령어 실행
  3. I/O 컨트롤러 : 명령 수행
     • CPU : 다른 작업 수행 및 다른 Event 확인
  4. I/O 컨트롤러 : 작업 완료 후 CPU에게 인터럽트
  5. CPU : I/O 컨트롤러의 인터럽트 index에 맞는 ISR 탐색
  6. CPU : 이전 작업 저장 후 인터럽트 실행
  7. CPU : 인터럽트 처리 완료 후 작업 상태로 복귀

• I/O Structure
  • System Call : 사용자 프로그램 대신 운영체제가 디바이스 신호를 처리
  • Device-Status Table : 디바이스에 번호를 부여하여 인터럽트 발생 시 어떤 디바이스에서 발생했는지 정확한 판단
• Storage Structure
  • 메인 메모리 : Random Access, 휘발성 - 휘발되는 데이터를 별도 저장 필요
  • Secondary Storage : HDD, SSD 등 메인 메모리를 보조하여 비휘발성 저장
  • 스토리지 계층
    

    

    • 스토리지 별로 가격, 속도, 휘발성이 모두 다름
    • 최상위에 즉시 사용할 데이터 저장
• Modern Computer (폰 노이만 구조)
  
  • 캐시 메모리 : CPU 내에서 명령어 로드, 데이터 기록
  • 메인 메모리 : 실제 명령어가 위치
  • DMA(Direct Memory Access)
    • 디바이스에서 데이터 복사 시 CPU의 연산 부담 및 위험성을 경감
    • 디바이스에서 메모리로 데이터를 복사하는 별도 프로세스 할당
    • CPU가 디바이스 데이터 request를 보내면, 디바이스는 DMA를 통해 메모리로 데이터 복사 후 완료 신호만 보내서 CPU의 처리 부담 완화

Multiprocessor

• 병렬 시스템이라고도 부름
  • 고성능 : 다양한 어플리케이션을 각 프로세스에 할당 가능
  • 신뢰성 : 한 어플리케이션이 동작 실패 시에도 다른 프로세스는 계속 동작
• 멀티프로세싱의 종류
  • 동기 : 각 프로세서가 한 작업을 분할 처리
  • 비동기 : 각 프로세서가 다른 작업(I/O, 계산 등)
• 멀티코어
  • 1개 프로세서 안에 다수 Local Cache와 CPU 코어 배치

Operating System Operations

• 운영체제의 동작
  • Bootstrap
    • 실행 직후 시스템을 초기화
    • 커널을 실행
  • Kernel : 시스템 데몬(daemon) 실행
    • 데몬 : 시스템 소프트웨어 실행 (ex. 새 프로세스 생성)
  • 연결된 디바이스들이 실행되면서 인터럽트 발생
    • CPU에서는 인터럽트를 통해 하드웨어 설정

• 멀티프로그래밍(Batch System)
  • CPU가 처리할 작업들을 한번에 할당하여 OS가 스케줄링(Scheduling)
  • 고가의 자원을 다수 사용자가 공유하여 사용할 때
• 시분할(multitasking)
  • Batch System의 경우 다수 프로그램을 하나로 묶어서 처리
  • 시분할의 경우 동작하는 각 프로그램별로 실행 시간을 제한하여 주기적으로 전환
  • 시분할 스케줄링 과정에 시간을 재기 위한 Timer Interrupt 필요
  • 메모리 크기 이상의 프로그램 동작을 위해 가상 메모리 개념 사용
• Dual Mode (Multimode)
  • 운영체제 동작 시 프로그램들은 서로 영향을 끼치지 않게 해야 함
  • User / Kernel Mode : 운영체제 /사용자가 실행하는지 확인하기 위해 Mode bits가 하드웨어에서 지원
  • Privileged Instructions : 커널 모드에서만 동작하는 특정 명령어
  • User - Kernel Mode 전환
    • User > Kernel : System Call
    • System Call 후 복귀는 인터럽트로 호출

Resource Management

• Process Management
  • Process : 운영체제가 관리하는 개체
    • Program : Passive Entity / Process : Active Entity
  • Process 동작에 필요한 자원
    • CPU, Mem, I/O, 파일 등
    • Initialize Data
  • 운영체제는 종료된 Process의 자원을 회수
  • 1개 스레드당 1개의 Program Counter(PC)가 할당
    • PC : 처리하는 명령어(Instruction)의 주소를 저장
• OS의 Process Management
  • 유저 및 시스템 프로세스를 생성 및 삭제
  • 프로세스를 중간에 멈추고 재시작
  • 프로세스 간의 공유 자원 접근 동기화
  • 프로세스 간의 통신 관리
  • 교착(Deadlock) 발생 방지

• Memory Management(MM)

  • 실행하는 프로그램의 명령어는 메모리에 할당
  • 메모리 사용을 요구하는 프로세스 확인 및 관리
  • 프로세스의 데이터 사용 시점 확인, 필요 없는 데이터는 잠시 공간 확보 후 필요할 때 할당

• File-System Management

  • 파일 및 폴더의 생성 및 실행, 수정 지원
  • 파일의 소유권 / 그룹에 따라 접근 관리

• Mass-Storage Management

  • 외부 저장소(HDD, USB 등) 연결 시 마운트/언마운트
  • 속도가 서로 다른 저장소 스케줄링
  • Caching : 자주 사용하는 파일일수록 CPU에 가까운 저장소로 이동

Security / Protection / Virtualization

• Protection : OS 내의 프로세스 혹은 유저가 시스템 자원에 접근하는 것을 제어

• Security : 내/외적 공격에 대한 방어 ex. Overflow, 바이러스

  • 유저 구분 : User ID, security ID - 파일 접근 권한 제어
  • Group ID : 해당 그룹에 속하는 유저들의 권한 제어
  • Privilege escalation : 유저가 임시로 상위 권한 접근 - 보안 면에서 많은 고려 필요

• Virtualization
  • Eumlation
    • 가상머신을 구동하고자 하는 HW가 실제 사용중인 HW와 다를 때 사용
    • 매우 느린 속도
  • Virtualization
    • 가상 OS와 실 환경이 동일한 HW 사용

Computing Environments

• 기존의 컴퓨팅 환경

  • Standalone 모델
  • 프로그램도 대부분 local 환경
  • 네트워크 환경의 발달로 local device에서 웹의 thin client 역할로 변화

• 모바일 : 스마트폰, 태블릿 등

  • GPS, 기울기 등의 데이터를 수집 가능
  • Apple IOS / Google Android가 대표적

• Client-Server 모델

  • 중앙의 서비스 제공자(Server)과 주변의 데스크톱, 스마트폰 등의 단말 장비(Client)로 구분
  • 예 : 데이터베이스, 파일 공유 등

• Peer-to-Peer 모델

  • 서버/클라이언트 구분 대신 각 클라이언트를 서로 연결, 서로가 서비스 제공자이자 소비자

• 클라우드 컴퓨팅

  • 컴퓨터에서 사용하던 서비스를 네트워크로 제공
  • ex. AWS, GCP, Azure 등
  • Public Cloud : 유저가 사용 가능한 클라우드 영역 ex. AWS EC2 컴퓨팅 모듈 등
  • SaaS : 인터넷을 통한 어플리케이션 제공
  • PaaS : 어플리케이션을 동작 가능한 환경(플랫폼)을 클라우드에 구축

• 임베디드 세스템

  • 항상, 실시간으로 동작하는 시스템
  • 특정한 목적으로 한정된 시스템

Feedback

• Op-amp 피드백
  • $V_-=\frac{R_R}{R_R+R_F}V_{out}$
  • $A_v(V_{in}-V_-)=V_out$
  • $A_vV_{in}=[1+\frac{R_R}{R_R+R_F}A_v]V_{out}$
  • $\therefore \frac{V_{in}}{V_{out}}=\frac{A_v}{1+R_2A_v/(R_1+R_2)}$
• Feedback 회로
  

  

  • $V_s=V_i+kV_o$
  • $V_o=AV_i\rarr V_s=V_i(1+kA_v)$
  • $\frac{V_o}{V_s}=\frac{V_s}{(1+kA_v)}$ : 피드백에 의해 Gain 감소
    • Gain이 무한대 $\rarr\frac{1}{1+K}$(feedback 영향만 존재)
  • 입력 임피던스
    • $V_i=I_sR_i$
    • $I_s=\frac{V_i}{R_i}=\frac{V_s}{(1+kA_v)R_i}$
    • 입력저항이 $(1+kA_v)$만큼 증가한 효과
  • 출력 임피던스 (V_s=0)
    • $i_o=\frac{V_o-AV_i}{R_o}=\frac{V_x+kA_vV_x}{R_o}=\frac{(1+kA_v)V_o}{R_o}$
    • 출력 임피던스가 $1/(1+kA_v)$로 작아지는 효과

• 2-port network
  

  

• $V_1,\ V_2,\ I_1,\ I_2$ 중 2개의 값을 알면 나머지 값을 판단 가능
• ex. 위의 1k를 $R_1$, 아래 1k를 $R_2$라고 할 때
  

  

  • $I_1,\ V_2$를 알 때

  • $\begin{bmatrix} V_1\\ I_2 \end{bmatrix}$ $=\begin{bmatrix} a & b\\ c & d \end{bmatrix}$ $\begin{bmatrix} I_1\\ V_2 \end{bmatrix}$

  • $a=\frac{V_1}{I_1}|_{V_2=0},\ b=\frac{V_1}{V_2}|_{I_1=0},\ c=\frac{I_1}{I_2}|_{V_2=0},\ a=\frac{I_2}{V_2}|_{I_1=0}$

  • a : $V_2$가 그라운드 $\therefore a=R_1||R_2$

  • b : $I_1$ 영향 x ($I_1$이 들어가는 선과 $R_1-R_2$접점이 끊어졌다고 판단)
    $b=\frac{R_2}{R_1+R_2}$

  • c : $I_1=\frac{V_1}{R_1||R_2},\ I_2=-\frac{V_1}{R_1}$
    $\rarr\frac{I_2}{I_1}=-\frac{R_1||R_2}{R_1}$

  • d : $\frac{1}{R_1+R_2}$

• 피드백회로 변환 $(A=10, k=0.5)$
  

  

  • $V_i'=\frac{R_i}{R_1||R_2+R_i}V_i$
    $\rarr A_v'=\frac{R_i}{R_1||R_2+R_i}A_v$
  • $R_1,\ R_2,\ R_i=1k,\ A_v=10$일 때 $A_v'=20/3\simeq6.67$
  • $A_f=\frac{A_v}{1+kA_v}$
    $=\frac{6.67}{1+6.67\times0.5}\simeq1.54$
  • $R_{if}=1.5k\times(1+kA)\simeq6k$

6. The Frequency Response Design Method

1. Frequency Response

• 주파수 응답 : 선형시스템에 sinusoidal 입력이 들어갔을 때의 응답
  • 입력 $u(t)=Asin(w_0t)$
  • 초기값 0일 때 출력 $Y(s)=G(s)\frac{Aw_0}{s^2+w_0^2}$
  • G(s)가 n개의 pole을 갖는다고 할 때,
    $Y(s)=\frac{\alpha_1}{s-p_1}+\frac{\alpha_2}{s-p_2}+...+\frac{\alpha_n}{s-p_n}+\frac{\alpha_0}{s+jw_0}+\frac{\alpha_0^*}{s-jw_0}$
  • $\alpha_0=\lim_{s\rarr -jw_0}G(s)\frac{Aw_0}{s^2+w_0^2}=-\frac{A}{2j}G(-jw_0)$
  • $\alpha_0^*=\frac{A}{2j}G(jw_0)$
• 주파수 응답 $y(t)$
  $=\alpha_1e^{-p_1t}+\alpha_2e^{-p_2t}+...+\alpha_ne^{-p_nt}+\frac{A}{2j}[G(jw)e^{jw_0t}-G(-jw)e^{-jw_0t}]$
  $=\alpha_1e^{-p_1t}+\alpha_2e^{-p_2t}+...+\alpha_ne^{-p_nt}+|G(jw_0)|Asin(w_0t+\phi)$
  • $\phi=tan^{-1}\frac{Im[G(jw_0)]}{Re[G(jw_0)]}$
  • 안정적인 시스템 응답이 steady state가 되는 경우, pole 항은 모두 소거 :
    $y(t)=|G(jw_0)|Asin(w_0t+\phi)=AMsin(w_0t+\phi)$
  • 주파수 응답 특성(Frequency Response Characteristics) : 시스템의 sinusoidal 입력에 따른 고유한 Magnitude, Phase의 주파수 응답 특성

• Bode Plot : 사인파 입력의 주파수가 변화함에 따라 응답의 Magnitude, Phase 변화를 각각 나타내는 그래프

  • x축(주파수) : log scale
  • y축(Magnitude) : log scale
  • y축(phase) : linear scale
  • Compensator 설계에 활용 가능
  • 각 시스템의 bode plot은 더해질 수 있다.
  • log scale이므로 광범위한 응답특성 표현 가능

• System $G(jw)=\frac{\vec{s_1}\vec{s_2}}{\vec{s_3}\vec{s_4}\vec{s_5}}$일 때

  • $\vec{s}=re^{j\theta}$
  • $M=|G(jw)|,\ \phi=\angle G(jw)$
  • $logM=log\sum r,log\angle G(jw)=j(\sum\phi)loge$
  • $|G|_{db}=10log\frac{P_2}{P_1}=20log\frac{V_2}{V_1}$

• Bode Form : 시스템 인수의 상수값이 1

  • $KG(s)=K\frac{(s-z_1)(s-z_2)...}{(s-p_1)(s-p_2)..}$
    $\rarr KG(jw)=K_o\frac{(jw\tau_1+1)(jw\tau-2)...}{(jw\tau_a+1)(jw\tau_b+1)...}$

• 전달함수 형태
  • $K_0(jw)^n$
  • $(jw\tau+1)^{\pm1}$
  • $[(\frac{jw}{w_n})^2+2\zeta(\frac{jw}{w_n})+1]^{\pm1}$

• ex. Class-1 : $K_0(jw)^n$

  • (dB) $M=20log|K_0(jw)^n|=20log|K_0|+20nlogw$
  • $\angle(jw)^n=n\times90\degree$
  • Magnitude : $K_0=1,\ n=1$이라고 하면, 20dB/decade의 기울기를 갖는 직선 그래프 생성
    

    

  • Phase : $n\times90\degree$의 x축과 평행한 직선 그래프

• ex. Class-2, 1st-order : $jw\tau+1$

  • Magnitude
    

    

    • $w\tau<<1\rarr log|jw\tau+1|\simeq0$
    • $w\tau+1>>1\rarr log|jw\tau+1|\simeq log|\tau|+log|jw|$
    • $w\tau=1$ : Break Point
      • $M=20log|j+1|=20log\sqrt{2}\simeq3dB$
    • $((w=1/\tau),0dB)$ 좌표를 기준으로 0dB/dec, 20dB/dec 기울기의 점근선 형성
    • $(jw\tau+1)^{-1}$ 의 경우 -3dB 점을 기준으로 -20dB/dec 기울기로 감소하는 그래프 형성
  • Phase
    

    

    • $w\tau<<1\rarr 0\degree$
    • $w\tau+1>>1\rarr 90\degree$
    • Break Point : $w\tau=1\rarr 45\degree$
    • 점근선의 기울기, $90\degree,\ 0\degree$의 점근선을 기준으로 하는 곡선 그래프 형성

• ex. Class-3, 2nd-order term : $[(\frac{jw}{w_n})^2+2\zeta(\frac{jw}{w_n})+1]^{\pm1}$

  • Magnitude
    

    

    • $w<<w_n\rarr log|G(jw)|\simeq0$
    • $w>>w_n\rarr G(jw)\simeq(jw/w_n)^{\pm2}$
      $log|G(jw)|\simeq\pm2log|1/w_n|\pm2log|jw|$
    • $w=w_n\rarr log|G(jw)|\simeq log((2\zeta)^{\pm1})$
    • breakpoint에서 $20log(2\zeta)^{\pm1}$ 지점을 통과
  • Phase
    

    

    • 차단주파수 전후로 0, 180도의 위상, breakpoint에서 $\angle G(jw)=-\angle j2\zeta$
    • $zeta$가 1에 가까울 수록 완만하게, 0에 가까울수록 급격하게 그래프 변화

• Bandwidth : Closed-Loop Transfer function
  • Amplitude가 1 > 0.707로 감소할 때의 주파수
  • 이 때 Magnitude는 약 -3dB
  • 전력이 50% 이하로 감소

• Bode Plot 작성
  1. Magnitude : 전달함수를 Bode Form으로 조절 : $KG(jw)=K_o\frac{(jw\tau_1+1)(jw\tau-2)...}{(jw\tau_a+1)(jw\tau_b+1)...}$
  2. 주파수를 0으로 근사시켜 기울기 확인 후, 주파수 w=1일 때 점근선 작성
  3. 각 breakpoint에서의 점근선 작성 : 먼저 작성한 점근선 그래프에 breakpoint 주파수를 대입하여 그 지점을 지나는 점근선으로 작성
  4. 기울기가 감소, 혹은 증가할 때 Bode Plot 곡선은 교차점에서 $\pm3dB$ 차이나는 지점을 지나게 된다.
  5. Phase : 주파수를 0으로 근사시켜 출발점 위상 확인
  6. zero를 지나면 +90, pole을 지나면 -90도씩 변화하는 점근선 작성
  7. Phase Bode Plot 작성 : 곡선은 변화하는 점근선의 중간점을 지남

2. Neutral Stability

• $KG(s)$의 전달함수에서 얻은 Bode Plot으로 Closed-Loop system의 안정도 판별
  • Closed-Loop system의 root locus 작성시
    모든 점에서 $1+KG(s)=0\rarr |KG(s)|=1$, $\angle G(s)=180\degree$
  • 허수축 위를 지날 때 (neutral stability) : $|KG(jw)|=1$, $\angle G(jw)=180\degree$

• $G(s)=\frac{1}{s(s+1)^2}$에서 $\angle G(jw)=-180\degree$일 때,
  • K=2이면 $|KG(jw)|=1$
  • K<2이면 $|KG(jw)|<1$ : Stable
  • K>2이면 $|KG(jw)|>1$ : Unstable
  • 즉 $\angle G(jw)=-180\degree$일 때 $|KG(jw)|<1$ 이면 Stable
• 만약 $G(s)=s(s+1)^2$이면 $\angle G(jw)=-180\degree$일 때 $|KG(jw)|>1$ 이면 Stable

• Bode Plot의 경우 Gain이 1 (위상이 180도)인 지점을 여러번 지날 수 있어 안정도 판별에 어려움 존재
• Nyquist 안정도 판별법을 대신 사용

3. Nyquist Stability

• 편각의 원리
  

  

  • 전달함수 H(s)에서 s가 임의의 궤적 C1을 따를 때,
  • H(s)의 궤적은 s의 궤적 C1 안에 속하는 Zero - Pole 개수 차이만큼 원점을 포함하여 회전하는 궤적이 된다.
  • zero가 더 많으면 시계방향, pole이 더 많으면 반시계방향
• $C_1$궤적을 RHP 모두를 포함하는 궤적으로 가정
  

  

  • RHP에 zero 존재 : 시계방향 궤적
  • RHP에 pole 존재 : 반시계방향 궤적
• 전달함수 $T(s)=1+KG(s)=1+K\frac{b(s)}{a(s)}=\frac{a(s)+Kb(s)}{a(s)}$일 때
  • G(s)의 RHP Pole = 1+KG(s)의 RHP pole
  • closed-loop의 RHP Pole = 1+KG(s)의 RHP zero
  • N = Z-P
    • N : 원점을 포함하며 시계방향으로 회전하는 궤적 수
    • Z, P : T(s)의 RHP zero, pole 개수
    • Z = N+P이므로, T(s)의 RHP zero가 없다면 G(s)의 RHP pole이 없으므로 안정된 시스템이다.

• Nyquist Plot의 작성법
  1. RHP 궤적 $C_1$을 3개 영역에 나누어 KG(s)분석
     • $0\rarr j\infty$
     • $-j\infty\rarr0$
     • RHP를 따라 이동하는 Big Arc
       • 무한의 반지름을 따라 이동하므로 $KG(j\infty)$계산
       • $KG(j\infty)$ 는 pole 차수가 더 클때 0, pole, zero 차수가 동일하면 상수
  2. KG(s)의 Bode Plot 작성
     • breakout point의 좌표 확인
  3. Bode Plot을 기반으로 Nyquist Plot 작성
     • Bode Plot에서 위상 0도일 때의 Gain = + 방향 X축에서의 시작 좌표
     • 위상 변화에 따라 Gain 크기가 궤적의 반지름
  4. 궤적의 Loop 내에 포함되는 원점의 개수 확인

• ex. $G(s)=\frac{1}{s(s+1)^2}$
• s가 매우 작은 값이 될 때, $G(s)\simeq \frac{1}{s}$로 근사
  • r이 0으로 근사 시 매우 큰 값이 된다
  • r이 무한으로 증가하면 궤적은 원점 근처를 지난다
  • 위상 $\phi$는 -90~ 90도로 이동하는 궤적이므로 G는 반시계방향 (90 ~ -90도)으로 이동하는 궤적이 된다.
  • Bode plot 작성 시 w값이 -90에 가까울 수록 Gain이 커지고, -180도에서 0, 이후로 급격히 작아지므로 3사분면에서 시작하여 w=1 지점을 끼고 원점으로 수렴하는 궤적이 나타난다.