Numerical Integration

• 수치적 적분은 $\int$대신 $\sum$을 쓰는 원리

Trapezoidal Rule

• 적분 구간의 일부인 [a, b]구간의 적분을 가정 (구분구적법과 유사)
  • $\int_{x_0}^{x_2}f(x)dx\simeq (x_2-x_0)\frac{[f(x_0)+f(x_2)]}{2}$
• 해당 구간의 Linear Lagrange Polynomial $P_1(x)=\frac{x-x_1}{x_0-x_1}f(x_0)+\frac{x-x_0}{x_1-x_0}f(x_1)$
• Lagrange Method $x_1,\ x_2$를 shifting
  • $L_0=\frac{h-x}{h},\ L_1=\frac{x}{h}$
  • $\int_{x_0}^{x_2}f(x)dx\simeq (2h)\frac{[f(x_0)+f(x_2)]}{2}$
• three-point rule 적용(x-h, 0, x+h)
  • taylor polynomial : $f(x)=f(x_1)+f'(x_1)(x-x_1)+\frac{f''(\zeta)}{2}(x-x_1)^2$
  • a : $\int_{x_0}^{x_2}f(x)=f(x_1)\cdot 2h+\frac{f''(\zeta_x)}{2}(x-x_1)^2$
  • b : $[f(x_0)+f(x_2)]h=2hf(x_1)+[f''(\zeta_1)+f''(\zeta_2)]\frac{h^3}{2}$
  • error = a-b = $\int_{x_0}^{x_1}\frac{f''(\zeta)}{2}(x-x_1)^2-\frac{[f''(\zeta_1)+f''(\zeta_2)]}{2}h^3$
    $=h^3[\frac{f''(\eta)}{3}-\frac{[f''(\zeta_1)+f''(\zeta_2)]}{2}]$
• Error 발생 $\int^h_{-h} f(x)dx\simeq h\frac{[f(h)+f(-h)]}{2}$
  • f(x)=1인 경우 : a=2h, b=2h
  • f(x)=x인 경우 : a=b=0
  • f(x)=$x^2$인 경우 : $\frac{2}{3}h^3\not ={h^3}$(error 발생)

Simpson's Rule

• [a, b]구간을 세 점 (x0, x1, x2)로 가정
• shifting : $x_0=-h,\ x_1=0,\ x_2=h$
  • $\int_{-h}^hf(x)\simeq h\frac{f(-h)+4f(0)+f(h)}{3}$
  • 혹은 $\int_{x_0}^{x_2}f(x)dx=2hf(x_1)+\frac{h^3}{3}f''(x_1)+\frac{f''''(\zeta)}{60}h^5$
• Trapizoidal Rule의 degree of precesion은 1이지만, simpson은 4(전자는 2차식, 후자는 5차식부터 오차 발생)
• Composite Simpson's rule
  

  

  • 함수를 일정 구간으로 나누어 Simpson's Rule을 여러번 적용
  • $I(f)=\int^b_af(x)dx,$
  • $T_n(f)=h[\frac{f(x_0)+f(x_1)}{2}+\frac{f(x_1)+f(x_2)}{2}+...+\frac{f(x_{n-2})+f(x_{n-1})}{2}+\frac{f(x_{n-1})+f(x_n)}{2}$
    $=h[\frac{f(x_0)}{2}+f(x_1)+...+f(x_{n-1})+\frac{f(x_n)}{2}]$
  • 오차 = $nO(h^3)$ - 간격이 줄어 h가 감소하므로 오차가 대폭 줄어듦

Gaussian Quadratic

• $\int f(x)dx\simeq c_1f(x_1)+c_2f(x_2)$
• Simpson's rule의 변형으로, 양 끝점을 구분부적 하는 대신 구간 내 임의 두개의 점으로 구분구적을 진행
• 미지수 $c_1,\ c_2,\ x_1,\ x_2$를 알기 위한 4개 방정식 필요
• 5개 점(a, x1, 0, x2, b)이 대칭형이라 가정
  • x1 = -x2
  • c1 = c2

Numeriacal Differenctiation

• $f(x)=P_n(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Pi(x-x_n)=P_n(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Phi(x)$
• 미분 근사
  • $f'(x)=lim_{h\rarr0}\frac{f(x+h)-f(x)}{h}\simeq\frac{f(x+h)-f(x)}{h}$
  • 계산이 단순함
  • 수렴이 느림 = 근사 정확도가 낮음
  • h에 정비례로 오차도 작아짐 (1차 수렴)
• Higher Order method : Lagrange method
  • $f(x)=\Sigma f(x_k)L_k(x)+\frac{f^{n+1}(\zeta(x))}{(n+1)!}\Pi(x-x_n)$
  • 앞의 항은 $P_n(x)$, 뒤의 항은 Error
  • 미분값 $f'(x)=\sum^n_{k=0}f(x_k)L'_k(x)+D_x[\Phi(x)]f^{n+1}(\zeta(x))+\Phi(x)D_x[f^{n+1}(\zeta(x))]$
    • j번째 미분항 $f'(x_j)=\sum^n_{k=0}f(x_k)L'_k(x_j)+\frac{f^{n+1}(\zeta(x_j))}{(n+1)!}\Pi^n_{k=0, k\not ={j}}(x_j-x_k)$
    • 오차를 특정하기보다는 Error Bound를 계산한다.
  • n이 중가할수록 error는 감소

Three-Point Formula

• Lagrange Polynomial (3 basis) : 3개 점을 이용한 근사식
  • $L_0=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)}$
  • $L_1=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}$
  • $L_2=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
• 3-point method : 3개 점이 일정 간격이라 가정 $x_1 = x_0+h,\ x_2=x_0+2h$
  • Lagrange method의 분모항은 모두 $2h^2$으로 통일됨
  • shifting : 3개 점 중 하나를 0으로 치환
• 3-point method를 적용한 미분식
  • $f'(x_0)=\frac{1}{h}[-\frac{3}{2}f(x_0)+2f(x_0+h)-\frac{1}{2}f(x_0+2h)]+\frac{h^2}{3}f'''(\zeta_0)$
  • $f'(x_0+h)=\frac{1}{h}[-\frac{1}{2}f(x_0)+\frac{1}{2}f(x_0+2h)]+\frac{h^2}{6}f'''(\zeta_1)$
  • $f'(x_0+2h)=\frac{1}{h}[\frac{1}{2}f(x_0)-2f(x_0+h)+\frac{3}{2}f(x_0+2h)]+\frac{h^2}{3}f'''(\zeta_2)$
  • h가 절반 >> error항은 2차식이므로 오차는 1/4로 감소
• 미분식 간소화
  • $f'(x_0)\simeq\frac{-3f(x_0)+4f(x_1)-f(x_2)}{2h}$ (back-order form)
  • $f'(x_1)\simeq\frac{-f(x_0)+f(x_2)}{2h}$ (central form)
  • $f'(x_2)\simeq\frac{f(x_0)-4f(x_1)+3f(x_2)}{2h}$ (forward-order form)
  • 세 식이 대칭 구조를 이룸
  • 분자의 계수 합이 0이어야 함

• $\tilde{x}=x-x_1\ (x_1=x+h)$로 정의
  • Largrange Polynomial $f(x)\simeq f(x_0)L_0(x)+f(x_1)L_1(x)+f(x_2)L_2(x)$를
  • $f(x)\simeq f(x_0)L_0(\tilde{x})+f(x_1)L_1(\tilde{x})+f(x_2)L_2(\tilde{x})$로 치환
  • $L_0(\tilde{x})=\frac{\tilde{x}(\tilde{x}-h)}{2h^2}$
• five point formula
  • $f'(x_0)=\frac{1}{12h}(f(x_0-2h)-8f(x_0-h)+8f(x_0+h)-f(x_0+2h))+\frac{h^4}{30}f^{(5)}(\zeta)$
    • midpoint formula - 가운데 점의 미분
    • $\zeta=[x_0-2h, x_0+2h]$
  • $f'(x_0)=\frac{1}{12h}[-25f(x_0)+48f(x_0+h)-36f(x_0+2h)+16f(x_0+3h)-3f(x_0+4h)]+\frac{h^4}{5}f^{(5)}(\zeta)$
    • endpoint formula - 왼쪽 끝점에서 미분
    • $\zeta=[x_0, x_0+4h]$
  • Error식이 4차 - Order of Convergence = 4
• Order of Convergence 계산
  • Error $E_h=Ch^\alpha$라고 할 때 Order of convergence = $O(h^2)$
  • h값이 1/2로 감소한다고 할때 이전 값은 2h이므로 $E_2h=C(2h)^\alpha$
  • error의 감소분은 $\frac{E_2h}{E_h}=2^\alpha$
  • $\alpha$의 계산은 $log\frac{E_2h}{E_h}/log2$로 구할 수 있음 (Error Of Convergence)

Application of the Formula

• ex. $f(x)=xe^x$
  • f(1.8) = 10.889365, f(1.9) = 12.703199, f(2.0) = 14.778112, f(2.1) = 17.148957, f(2.2) = 19.855030
  • h=0.1, x=1.9 기준으로 한 3-point endpoint formila
    $f(x)=\frac{1}{0.2}[-3f(1.9)+4f(2.0)-f(2.1)]$

파이썬의 특징

• 인터프리터 언어 : 컴파일 과정이 없음
  • 파이썬 코드는 인터프리터를 통해 .pyc라는 binary 파일로 변환
  • Cross-Platform으로 동작 가능
• Dynamic Typing(Duck Typing) : 타입 명시가 필요 없음
• 단순한 문법

파이썬의 Value :

• 프로그램에 의해 사용될 수 있는 객체 표현
  • 숫자 : 정수(Int), 실수(Float), 허수(3+j), Boolean(True, False)
    • 허수는 .real, .imag로 실/허수를 분리해낼 수 있음

문자열

• "" / '' - 한 줄
• """ """ - 여러 줄
• 특수문자는 (키보드 ￦ 표시)뒤의 문자로 입력 가능
• 문자열 메소드
  • ''.join : 문자열을 인자와 함께 이어 붙임
  • split('') : 문자열을 인자 기준으로 나눔
  • float, int : 문자열을 숫자로 (int의 경우 진수 지정 가능)
  • strip / lstrip / rstrip : 양옆 / 왼쪽 / 오른쪽 공백 제거
  • whitespace : 공백 문자로 처리하는 문자를 확인
  • find, rfind : 시작/끝에서 문자를 찾아 인덱스 반환 (없으면 -1)
  • startswith, endswith : 해당 문자열로 시작/끝나는지 여부

리스트(배열) : [], list()

• C와 달리 여러 타입의 값이 같이 들어갈 수 있음
• [ 1, "123", [1,2,3] ]
• 파이썬의 리스트 인덱스는 음수로도 가능
  • 리스트 처음의 인덱스는 0 혹은 -(리스트 길이)
  • 리스트 마지막 인덱스는 (리스트 길이 - 1) 혹은 -1
• 슬라이스 : 리스트의 일부분을 추출해낼 수 있음
  • range와 유사하게 동작
  • a = [1,2,3,4,5]
  • a[:] = [1,2,3,4,5]
  • a[:2] = [1,2]
  • a[1:3] = [2,3]
• 파이썬 리스트 함수
  • x=[1,2,3], y=[4,5,6]
  • len(x) : 리스트의 길이 반환 (3)
  • x[len(x):] = y, x 리스트의 뒤에 y를 연결할 수 있음
    • [1,2,3,4,5,6]
    • x.extend(y), x[2:3] = y로도 가능
    • x+y로도 가능
  • x[:0] = [1,2,3] : x 리스트의 앞에 [1,2,3]으로 연장
    • [4,5,6,1,2,3]
  • x.append(10) : 리스트 끝에 추가
    • [1,2,3,10]
  • x.insert(n, element) : n번째 인덱스 앞에 element 추가
    • x.insert(0,-1) = [-1,1,2,3]
  • del x[] : 리스트 원소를 지울 수 있음
    • del x[1] = [1,3]
    • del x[:] = []
  • x.remove(2) : x리스트 안의 원소 2를 지움
    • [1,3]
  • x.reverse() : 리스트 x를 역순으로 정렬
    • [3,2,1]
  • z = [1,3,2] - z.sort() 리스트를 크기순으로 정렬
    • [1,2,3]
    • z를 변화시키며 리턴값 없음
  • y = sorted(z) : 정렬된 새 리스트를 반환
    • z = [1,3,2], y=[1,2,3]
  • in : 값이 리스트에 있는지 확인
    • 1 in [1,2,3] : True
    • 5 in [1,2,3] : False
    • 5 not in [1,2,3] : True
  • min, max : 리스트 내의 최대/최소값 반환
  • x.index(1) : 해당 원소가 존재할 경우 인덱스 반환
    • 0
  • k = [1,1,1,2,2,3] - k.count(1) : k 리스트 내의 원소 개수 반환
    • 3

튜플 : (), tuple()

• 수정 불가능한 리스트
• (1,) : 하나의 원소를 갖는 튜플 - (1)는 정수 1임
• 튜플의 활용 : 변수 선언의 간소화
• extend unpacking * : *이 붙은 원소는 길이가 맞지 않는 모든 값을 흡수

x=1
y=2
z=3
w=4
#에서
(x,y,z,w)=(1,2,3,4)#로

# Extend unpacking
a, *b, c = (1,2,3,4,5)
'''
a=1
b=[2,3,4]
c=5
'''
a,b,c,*d=(1,2,3)
'''
a=1
b=2
c=3
d=[]  : 빈 리스트
'''

딕셔너리 : {}, dict()

• 키 - 값 관계를 갖는 자료 구조
• d = {1:"one", 2:"two}일 때, d[1] = "one"을 반환

세트 : set()

• 중복이 없는 자료 구조
• set([1,2,3,4,1,2,3,4]) = set([1,2,3,4])
• |, & : 합집합, 교집합 계산
• -: 차집합
• ^ : XOR 연산과 동일
• frozenset([]) : Immutable한 set
  • set 안의 set을 구현하기 위해 사용
  • seta = {1,2, frozenset([3,4,5])}
    • set은 unique한 값을 갖는 객체를 해쉬로 구현하는데, set은 Mutable하므로 값이 바뀔 수 있어 set 안의 set 구현이 불가능. 이로 인해 set in set을 구현하기 위해 frozenset이 필요

파이썬 객체

• 프로그램이 조작 가능한 데이터
• Scala : Int, Float, Bool, None - 분리 불가능한 최소 단위
  • None : 반환값이 없는 함수에 사용(None을 반환)
• Non-scala ; List, Tuple, Dictionary, defined Class - Scala Type에 기반해서 만들어지는 자료형
• Type() : 자료형 변환이 가능(C의 type-casting)
• 값과 변수
  • Value : 값을 표현
  • Variable : 데이터가 저장된 곳을 이름으로 표현
  • 값을 변수에 할당하여 사용 (Variable = Value : pi = 3.14)
    • 만약 x=3으로 할당 후, x=4로 할당하면, x = 3의 연결이 끊어지고, 4와 x가 bind됨
    • 3의 값은 python에서 자체적으로 메모리를 정리해줌
  • del(x) : 변수 x를 삭제
• 객체 복사
  • 파이썬의 모든 변수는 레퍼런스(포인터)로 동작
    • a=3, b=3의 코드를 가정
    • C의 경우 a, b의 메모리 공간에 각각 3을 저장
    • python의 경우 a, b가 3의 값을 갖는 객체의 주소를 가리킴
    • a=4가 될 경우, c는 a변수의 메모리 공간을 지우고 4를 넣지만, python은 4의 값을 갖는 객체를 만들고, 그 주소를 a가 가리키게 됨
    • 리스트 역시 각 위치가 포인터로 동작
      • [1, 2, 3]은, 리스트의 0, 1, 2번째 인덱스가 각각 1,2,3의 값을 갖는 객체를 가리키는 상태
      • shallow copy : 리스트를 대입한 후 연산을 할 경우, 같은 리스트 변수에도 영향을 줌

li1 = [1,2,3]
li2 = li1 #shallow copy

li2 = li1 * 2 # li1, li2 모두 [2,4,6]

# Deep copy : 분리하여 복사
import copy
li2 = copy.deepcopy(li1)

• 파일 객체
  • open('파일명', '읽기/쓰기 여부')로 호출
  • 존재하는 파일을 쓰기로 호출할 경우, 덮어쓰는 식으로 파일 작성

Immutable / Mutable

• 파이썬의 객체 분류 기준
• Immutable : Number, Boolean, Tuple
• Mutable : List, Set, Dictionary
• Object ID : id() 함수는 객체의 id를 반환
  • Immutable한 객체들의 id는 모두 동일
  • Mutable 객체(ex. list)의 경우 매번 새로 생성되므로 다른 id 할당
  • is 연산자로 두 객체가 완전히 같은지 확인 가능
    • ==는 두 객체의 값을 비교

주석

• 코드가 어떻게 동작하는지를 설명
• 실제 코드에는 영향을 주지 않음
• # : 한 줄 / ''' ''' : 여러 줄

# comment in one line

'''
comment
in
lines
'''

파이썬의 코딩 스타일 - PEP 8

• 개발 편의를 위한 코딩 규칙
• 모듈명, 패키지명 : 모두 소문자로, 필요할 때만 _로 구분 (imp, sys)
• 함수, 변수명 : 모두 소문자로, 가독성을 위해 언더바 사용 (my_func(), my_var)
• 클래스명 : 각 단어마다 대문자로 시작(MyClass)
• 상수 : 모두 대문자, 가독성을 위해 언더바(MY_CONSTANT)
• 들여쓰기 : tab 대신 스페이스 4번으로 사용할 것
• 비교 : True, False와 직접적인 대조를 하지 말 것
  • if my_var == True >> if my_var
  • if my_var == False >> if not my_var

머신러닝

• 프로그램을 만들 때의 접근법
  1. 풀어야 할 문제 분석
  2. 알고리즘 구성
  3. 알고리즘 구현(By 프로그래밍 언어) 및 시험
• 머신러닝의 정의
  • 외부의 프로그램 없이 데이터를 이용하여 컴퓨터에게 학습 능력을 부여하는 것
• 머신러닝의 발전
  • 처음 퍼셉트론 개념은 약 1950년 시작
  • (1970) 단순한 알고리즘 표현도 어렵다는 점을 확인
  • (1980) Back-Propagation 알고리즘 발견
  • (2010 ~ ) Alexnet 등 다양한 딥 러닝 알고리즘 발전
• 딥 러닝의 성공 조건 : 데이터, 알고리즘, 연산
  • 알고리즘 : Backpropagation 등의 알고리즘 발전
  • 데이터 : 머신러닝은 데이터를 기반하므로 매우 많은 양의 데이터 필요
  • 연산능력 : GPU / TPU / NPU 등 머신러닝을 위한 연산 능력 발전
• 머신 러닝의 종류
  • 지도 학습 : Label된 데이터의 학습 ex. 스팸 필터, 선형 회귀, ...
  • 비지도 학습 : Unlabel된 데이터의 학습 ex. 데이터 클러스터
  • 강화 학습 : 모델과 환경 사이의 행동과 피드백에 기반 ex. 로봇, AI 게이밍, ...

Instruction Code

• 프로그램 : 명령어의 집합
• 컴퓨터 동작: 레지스터 내의 데이터를 처리하는 microoperation들의 과정
• 명령어
  • 컴퓨터를 위한 microoperation의 조합
  • 명령어는 데이터에 메모리로 저장
  • Op Code(Operation Code)
    • Add, Sub와 같은 명령어를 정의하는 bit 모음
    • n개의 비트는 $2^n$개의 명령어를 할당
    • 명령어 = opcode + 주소
• 메모리
  • 한 파트에는 명령어, 다른 파트에는 data (Harvard Architecture)
  • ex. 4096 word memory > 주소 할당을 위해 최소 12bit 필요
    • word당 16 bit 할당 > op code에 4 bit 할당 가능
  • binary operand : 명령어가 사용하는 데아터
  • Program register / Accumulator : 명령어 결과를 임시 저장
    • Ex. AC에 100이 저장 / 명령어가 Opcode(Add) + Address에 100이 저장되어 있을 경우 AC에는 200이 저장됨
• 명령어 주소
  • 명령어 주소 format : I + OpCode + Address
  • I : Indirect mode bit
  • direct address : 주소 필드가 명령어 주소를 가리킴
  • indirect address : 주소 필드가 명령어 주소가 저장된 주소를 가리킴
    • 장점 : Address 주소의 범위를 확장시켜 더 큰 메모리에 접근 가능
    • 단점 : 주소 접근이 2번 이루어지므로 direct 대비 느림

Computer Register

• 작성된 명령어는 연속된 주소에 저장 후 특정 시점에 실행
• 제어 유닛이 시작 주소의 명령을 읽어들임 > 실행 후 다음 주소를 계산 (카운터 레지스터가 필요)
• 컴퓨터 Control Logic의 레지스터
  • Accumulator(AC) : 명령어의 Source(출발지) 이자 Destination(결과 저장)
  • Instruction Register(IR) : 메모리에서 읽어들인 명령어 저장
  • Data Register(DR) : 메모리에서 읽어들인 데이터 저장
  • Temporary Register(TR) : 임시 저장소
    • AC, DR, TR, IR은 메모리 word와 크기 동일
  • Program Counter(PC) : 다음에 실행되는 명령어의 주소 저장
  • AR(Address Register) : 실제 실행 중인 명령어의 메모리 주소를 저장 - 다음 명령어 실행 시 PC의 값이 AR로 전달
    • PC, AR은 메모리의 Address Field와 동일한 크기
  • Input/Output Register(INPR / OUTR) : 외부 장치 데이터를 주고받기 위한 통로

Computer Instruction

• 컴퓨터 명령어는 크게 3가지로 분류
  • memory reference
  • register reference
  • I/O instruction
• memory reference
  • I-field를 기준으로 direct(0), indirect(1) 동작으로 나뉨
  • AND, ADD, Load/LDA, Store/STA, Branch/BUN, branch&save/BSA, Increment/ISZ 등 메모리에 접근하는 명령어
• register reference
  • MSB 4자리가 0111로 시작하는 명령어
  • AC, E 레지스터를 clear, complement, circulate, Increment, branch 등
• I/O instruction
  • 인터럽트, AC 입/출력 등

• Control Logic Gate
  

  

  • IR 명령어(D0~D7)은 Opcode가 디코더를 거쳐 Control Logic Gate에 동작 명령어를 지정
  • IR Address의 경우 memory reference 명령어의 동작을 위해 전달
  • T0~T15에는 Sequence Counter(SC)와 디코더를 통해 클록당 값을 증가시키면서 순서대로 신호 할당
    • T15 이후에는 CLR신호를 통해 다시 T0부터 동작
  • HALT(정지) 명령어 이전까지 계속해서 동작
• fetch&decode
  

  

  • 각 클록(T)마다 SC는 1씩 증가
  • T0 : AR < PC, SC < SC+1
    • PC값을 AR에 Load해야 함
    • T0 신호는 BUS의 2(010)와, AR LD에 연결
  • T1 : IR < M[AR], PC < PC+1, SC < SC+1
    • 메모리 데이터를 IR에 LD해야 하므로 BUS 7(111)에 연결
    • IR에 연결해야 하므로 IR LD에 연결
    • PC를 증가시켜야 하므로 PC INR에 연결
  • T2 : D < Decode IR(12-14), AR < IR(0-11), I < I(15), SC < SC+1
    • decode값은 combinational logic이므로 신호 연결이 필요 없음
    • IR값을 AR에 연결해야 하므로 BUS 5(101)과 AR LD에 연결
    • IR(15)에 I LD 연결
• PC를 1 증가시키는 이유
  • 보통 특정 명령어 수행 후 그 다음 명령어는 연속된 주소에 할당
  • PC값을 AR에 할당 후 다음 동작과 함께 PC를 증가시켜 clock 절약 가능
• register reference 명령어
  • D7I'으로 동작(D7=1, I=0)
  • 1클록마다 데이터를 읽어온다고 가정,
  • T0 : AR < PC
  • T1 : IR < M[AR], PC < PC+1
  • T2 : IR decode, 데이터 전달
  • D7I'T3B11
    • IR 내용이 0111 / 1000 / 0000 / 0000
    • 결과 I + Opcode가 7(0111)인 경우 T3이 동작
    • B11만 1이므로 7xxx Clear AC(CLA)로 동작
  • register reference 명령어의 동작 symbol을 r로 정의
    • r = $D7I'T3$
    • B값(address bit 위치)에 따라 다른 명령어 수행
• memory reference 명령어
  • BUN(Branch Unconditionally) : 지정 주소로 복귀
  • BSA(Branch and Save Return Address)
    • PC+1에는 BSA 다음에 실행할 명령 저장
    • BSA 주소부터 시작하여 subroutine 동작
    • subroutine 마지막에는 1 BUN (BSA 주소) 저장 : 완료 후 PC+1 주소로 복귀하여 다음 명령 수행

I/O, Interrrupt

• 입/출력 기기와 컴퓨터 사이에는 인터페이스가 존재
  • 컴퓨터에서는 입/출력 레지스터(INP/OUTR)까지만 데이터 전송
  • 인터페이스가 기기와 컴퓨터 사이의 데이터 통신 조절
  • FGI/O : 데이터의 입/출력 Flag
    • FGI = 0 : 컴퓨터 사용중 / FGI = 1 : 새로운 입력 가능
• I/O 명령어
  • INP / OUT : 입/출력
  • SKI / SKO : FGI/O 존재 시 명령어 생략(PC + 1)
  • ION / IOF : 인터럽트 flag(R) on/off
• 인터럽트
  • 현재 동작하던 명령을 별도로 저장 후, Interrupt Cycle 수행
  • FGI/O = 1이 되면 R flag = 1로 set
  • 일반 명령어 Cycle은 R'T0, R'T1, ...의 양식으로 표현
  • 처음 명령어를 Load하는 구간(T0~T2)에는 R이 set되지 않음
    • T0'T1'T2'(IEN)(FGI+FGO) 일 때 R < 1
    • FGI/FGO가 동시에 high일 경우의 처리 순서는 ISR(인터럽트 서비스 루틴)에 따라 결정
  • 인터럽트 Cycle은 RT0 - RT1 - RT2 - ...
    • RT0 : AR < 0, TR < PC
    • RT1 : M < TR, PC < 0
    • RT2 : PC < PC + 1, IEN < 0, R < 0, SC < 0
      • IEN은 추후에 다시 1로 설정됨

Boolean Example

• 각 명령어의 Boolean 표현은 해당 동작을 하는 모든 operation의 합으로 표현
  • ex. load AR to BUS : < AR로 표현되는 모든 식의 합
  • = D4T4+D5T5
• ALU Load
  • AC에 Load되는 모든 데이터는 ALU를 거쳐 들어옴
  • +1(Increment), CLR는 AC에 직접 처리됨

CPU scheduler

• ready queue 내의 프로세스를 선택하는 방식
• CPU 스케줄링 이 동작하게 되는 프로세스의 경우의 수
  • running > waiting
  • running > ready
  • waiting > ready
  • 프로세스 제거
  • 1, 4의 경우 non-preemptive / 2, 3은 preemptive scheduling
• Dispatcher
  • 기존 프로세스의 상태를 PCB에 저장/불러오기
  • dispatch latency - dispatcher가 프로세스를 중단하고 다른 프로세스를 실행하기까지의 시간

Scheduling criteria

• 스케줄러의 성능 요인
  • CPU utilizationn : 가능한 CPU를 최대로 사용
  • Throughput : 시간당 사용 가능한 프로세스 수
  • Trunaround time : 프로세스가 실제 실행될때까지의 시간
  • waiting time : 프로세스가 ready queue에서 대기하는 시간
  • response time : request 요청에서 실제 응답까지의 시간
• FCFS(first come, first served)
  • 프로세스가 진입하는 순서대로 처리
  • process : burst time 가정
    • P1 : 24 / P2 : 3 / P3 : 3
  • 간트 차트 : 프로세스의 시작 / 종료 시간을 표현
    • ex. P1, P2, P3 순 진입
      

      

      • P1의 대기시간 = 0 (즉시 시작)
      • 평균 대기 시간 = (0+24+27) / 3 = 17
    • P2, P3, P1 순 진입
      

      

      • P1의 대기 시간 = 6
      • 평균 대기 시간 = (0+3+6)/3 = 3
  • FCFS의 단점 : convoy effect
    • burst time이 긴 프로세스 진입 시 다른 작업도 크게 지연
• SJF(Shortest Job First)
  • burst time이 짧은 작업 먼저 : wating time이 가장 짧음
  • burst time을 알아야 하는 문제 존재
    • 시스템의 burst time 예측 방법 : 이전 process 실행 기록을 통한 예측
      • $\tau_{n=1}=\alpha t_n+(1-\alpha)\tau_n$
      • $t_n$ : 실제 burst time
      • $\tau_n$ : 이전에 예측했던 burst time
      • $0\leq\alpha\leq1$(보통 0.5)

• SRTF : SJF의 preemptive version
  • 먼저 동작한 프로세스가 동작 중
  • 새로운 프로세스 동작 시 남은 시간보다 새 프로세스 시간이 짧은 경우 이전 프로세스를 중단하고 새 프로세스 처리
• Round Robin
  • 각 프로세스에 time quantum (q) 부여
  • 모든 프로세스의 대기 시간은 (n-1)q 이하
  • timer interrupt : 일정 시간이 지나면 다음 프로세스를 위해 발생
  • q가 매우 커짐 - FIFO / q가 매우 작아짐 - 프로세스 전환을 위한 overhead 과다
  • SJF 대비 turnaround는 크지만, response는 좋은 편

• Priority Scheduling
  • 우선순위 순으로 처리
  • 우선순위가 낮은 프로세스가 실행되지 않을 수 있음(Starvetion)
    • 해결책 : Aging - 시간에 따라 프로세스 우선순위를 높임
• Multilevel Queue
  • 우선순위가 다른 프로세스들의 배치
  • 우선순위에 따라 real-time, system, interactive, batch process queue로 나누어 할당
  • multilevel feedback queue
    • 프로세스가 처리에 따라 다른 큐로 옮겨질 수 있음
    • ex. 높은 우선순위 큐에서 다 처리되지 못한 경우, 한 단계 낮은 큐로 이동하여 처리

Thread Scheduling

• 스레드는 user-level, kernel-level로 나뉘어짐
• Many-to-one, Many-to-many의 경우 스레드 라이브러리가 동작시킬 유저 스레드를 관리
  • PCS(Process-Contention Scope) : 유저 스레드 간의 스케줄링
  • SCS(System-Contention Scope) : 커널 스레드간의 스케줄링
• Pthread : 스레드 라이브러리, PCS/SCS 스레드 생성을 관리
  • 리눅스, MACOS의 경우 SCS로만 생성 가능

MultiProcessor Scheduling

• Symmetric Multiprocessing(SMP)
  • common ready queue : global한 ready queue의 프로세스 하나를 각 코어에 나누어 할당
  • per-core run queues : 각 코어가 별개의 프로세스 할당
• 최근에는 한 프로세스에 여러 코어가 할당(멀티코어 프로세스)
  • 멀티스레드 / 하이퍼스레딩
    • 각 코어에 1개 이상의 HW 스레드 할당
    • 한 스레드는 연산(compute)와 메모리 접근(memory stall)을 번갈아 처리
    • 멀티스레딩을 이용, 한 스레드가 memory stall할 때 다른 스레드로 전환하여 compute
  • 멀티스레딩의 고려점
    • SW상의 스레드는 OS를 통해 HW 스레드로 할당
    • 코어는 각 HW스레드를 나누어 처리
• Load Balancing
  • SMP의 경우 모든 CPU가 효율적으로 작업 분배를 할 필요 존재
  • Push migration : 각 프로세스 작업을 확인해 특정 프로세스에 작업이 몰릴 경우 다른 프로세스로 분배
  • Pull migration : 작업이 없는 프로세스가 다른 프로세스 작업을 가져와서 처리(work stealing)
• Processor Affinity
  • 어떤 프로세서에 할당하냐에 따라 작업 속도가 달라질 수 있음
  • soft affinity : OS가 특정 스레드가 특정 프로세스에 작업할 수 있게 제안 (반드시 동작하지는 않음)
  • Hard affinity : OS가 특정 프로세스에 affinity가 있는 스레드를 할당시킴
  • ex. CPU cache : CPU 캐시의 접근속도가 메모리 대비 매우 빠르기 때문에, 직전에 작업했던 프로세스에 계속 할당시켜 주는 것이 다른 프로세스에 할당하는 것보다 더 빠름
  • ex2. NUMA architecture : multi CPU - memory가 물리적으로 분리된 환경 - 간접적 연결보다 직접적으로 연결된 CPU-memory의 처리가 훨씬 빠르게 나타남

Real-Time CPU scheduling

• realtime schedule의 경우 적정 시간 내에 동작하지 못할 경우 실패로 처리
• soft real-time : 작업이 매우 높은 우선 순위를 갖고 실행
• hard real-time : 작업은 반드시 적정 시간 내에 실행
• Event latency : event가 발생 후 작업에 들어가기까지의 시간
  • Interrupt Latency : 인터럽트 종류 파악 - Context Switch - ISR 접근까지의 시간
  • Dispatch Latendcy : 프로세스가 가능한 상태가 된 후(인터럽트 직후) 프로세스 실행까지의 시간
• Priority-based scheduling
  • 프로세스가 주기적 시간 p마다 들어온다고 가정
  • 프로세스 실행까지의 제한 시간(deadline) d를 가정
  • 프로세스의 처리 시간을 t로 가정
  • $0\leq t\leq d\leq p$여야 함
• Rate Monotonic Scheduling
  

  

  • rate p가 짧을수록 빠른 처리
  • 우선순위가 낮은 작업 중 높은 작업 진입 시 일시 정지 후 처리
  • 프로세스 작업 중 같은 프로세스가 재진입 시 deadline miss로 실행 실패
    

    

    • 실행 중이던 프로세스는 처리 시간을 모두 마치지 못해 실패
    • 새로 들어오는 프로세스는 설계에 따라 다름
      • 먼저 실행중인 프로세스가 우선한 경우 이전 프로세스에 의해 실행 deadline을 마치지 못해 실패
      • 새 프로세스가 우선하는 경우 계속 동작 (이전 프로세스만 실패)
  • EDF(Earliest Deadline First)
    

    

    • deadline이 짧은 프로세스를 우선

OS scheduling

• Linux
  • 선점형, 우선순위 기반
  • 우선순위 기준 : 시분할, real-time은 별도로
  • 우선순위 변수 : nice (100 ~ 140) - nice to process, 낮을수록 우선
  • CPU별로 run queue를 할당
• Windows
  • 우선순위 기반의 선점형
  • real-time class를 별도 할당
  • 0번 우선순위 : 메모리 관리

Algorithm Evaluation

• little's law
  • 평균 큐 길이 n, 평균 대기 시간 W, 평균 arrival rate $\lambda$일 때,
  • $n=\lambda\times W$
• Simulation
  • 제한된 queue model
  • 각 모델을 직접 동작시키면서 성능 통계를 계산

Multicore Programming

• 스레드 : CPU 활용을 위한 기본 단위
  • 멀티프로세스의 단점 : 동일 기능의 각 프로세스마다 code, data, file을 각각 할당하므로 처리 부담 증가
  • multithread
    • 프로세서 내의code, data, file은 공유한 상태로 레지스터, 스택, PC 등은 나누어 할당
    • 멀티프로세싱 대비 연산 비용이 적음
    • 같은 프로세스 자원을 공유하므로 shared memory / message passing보다 자원 공유가 쉬움
• Multicore programming 시 고려할 점
  • 작업 분할, 데이터 분할, 데이터 의존성
  • 불완전할 시 프로세스 간 데이터 의존으로 인해 속도 저하
• Concurrency / Parallelism
  • Concurrency : 다수의 작업이 동시에 수행(시분할)
    • 단일 코어에서 task 1, task 2, task 3...을 번갈아가며 조금씩 처리
  • Parallelism : 다수의 작업이 동시에, 독립적으로 수행
    • 코어 1 : task 1 / 코어 2 : task 2 ...
    • data parallel : 동일 데이터를 분할, 각 코어가 동일한 동작 수행 (ex. 1~100까지 더할 때 1~25 / 26~50 / ... 로 연산 데이터를 나눔)
    • task parallel : 작업을 분할하여 각 코어에 할당
• Amdahl's Law
  • 동시성 프로그래밍으로 얻을 수 있는 성능 향상
  • $speedup\leq[S+\frac{1-S}{N}]^{-1}$ ( S : 병렬화 불가 부분, N : 코어 수 )
    • ex. S=25%, N=2 >> speedup은 최대 약 1.6배
    • 코어 N이 무한히 증가 >> 속도는 1/S로 수렴

Multithread model

• 스레드의 종류
  • User thread : POSIX, window, java thread library
  • Kernel thread
• Many-to-One
  • user thread : kernel thread = N:1
  • 멀티코어에서도 각 스레드가 병렬 처리되지 않을 수 있음
  • 구현이 쉬움
  • Ex. Solaris, GNU
• One-to-One
  • user thread : kernel thread = 1:1
  • 병렬 처리 가능, 높은 동시성
  • 높은 Overhead : kernel thread가 많이 할당되어야 함
• Many-to-Many
  • user thread : kernel thread = N:M
  • 구현이 복잡하여 최근에는 잘 쓰이지 않음
• two-level : 여러 multithread model을 혼합하여 사용

Thread Library

• Pthread
  • POSIX 표준에 따른 스레드 생성 및 동기화 API
    • POSIX API는 실제 구현이 아닌 동작 방식만 나타냄
  • UNIX 계열 OS에서 사용
• Java Thread
  • JVM에 의해 관리
  • thread class의 extend 혹은 Runnable 인터페이스의 implement로 스레드 생성

Implicit Thread

• Thread 구현에 필요한 노력을 경감
• Thread Pool
  • 일정량의 스레드를 미리 생성
  • Pool 내의 빈 스레드에 작업 할당
  • 예측 가능한 범위 내에서 스레드 동작 가능
• Fork-Join
  • 분할-정복법
  • 여러 개의 thread로 나눈 후(fork), 스레드 종료를 대기(join)
• OpenMP
  • C, C++, 포트란의 컴파일러 명령어와 API
  • #pragma omp parallel로 병렬 처리가 가능한 부분을 선언

#pragma omp parallel for
for(i=0;i<N;i++)
{
  c[i] = a[i] + b[i];
  // fork-join 방식으로 각 스레드에 0~N의 구간을 나누어 처리
}

Threading Issue

• 스레드 fork와 exec
  • 프로세스 내의 한 스레드에서 fork > 새로운 프로세스 생성
    • fork 시 복사된 프로세스에는 해당 스레드만 유지하거나, 모든 스레드를 같이 복사할 수 있음
  • exec 호출 : 호출한 main thread 외에는 kill
• Signal Handling
  • Signal : Linux/Unit의 프로세스 이벤트
    • 인터럽트가 HW적 event라면, Signal은 SW적 Event
    • Signal Handler가 Signal을 전달
    • dehault handler : Process 생성 시 같이 생성
  • Signal의 전달 방식
    • 시그널이 발생한 스레드에 전달
      • memory violation, divide by zero 등
      • Synchronous Signal : 발생한 스레드가 명확한 Signal
    • 프로세스 내의 모든 스레드에 전달
      • Crtl+C 명령어(Linux의 강제 종료 명령어) 등
    • 특정 스레드에 모든 시그널 전달
  • 스레드 동작 시 시그널 유발
    • 시그널을 처리하기 위해 bitmask 사용 (시그널을 처리할 / 하지 않을 스레드 지정)
• Thread Cancellation
  • 외부에서 스레드를 강제 종료
  • Asynchronous cancellation : 모든 target thread를 즉시 삭제
  • Deferred cancelation : 스레드가 삭제 가능할 때 제거
    • 스레드가 중요 자료를 접근하고 있을 때 삭제 시 문제를 방지하기 위함
    • 기본 cancellation type
• Thread - Local Storage
  • TLS라고도 함
  • 멀티스레드는 같은 메모리를 참조
  • Local 변수는 함수 내에서만 선언
  • TLS는 특정 스레드 내에서만 사용
• Scheduler Activation
  • M:M thread model의 Issue
  • Lightweight Process(LWP) : 가상의 process를 통해 user - kernel thread 연결
    • upcall : kernel thread를 갖고 있는 LWP가 user thread에 할당된 경우, 새 LWP를 호출하여 해당 문제를 해결

Process

• Batch system의 Job / 시분할 시스템의 task, program
• Process : 실행 중인 프로그램
  • 실제 코드 (text section)
  • program counter : 현재 상태 추적
  • 데이터 저장 및 함수 호출을 위한 메모리 스택, 힙
• OS의 system call로 프로세스의 생성/삭제 구현
• 메모리 상의 프로세스 할당
  

  

  • 시작 위치에는 text 저장(작성된 코드)
  • 그 위에 data(const, global 변수)
  • 그 위에 heap(malloc 등의 동적 할당)
  • stack : 지역 변수 / 함수 call
  • text, data, heap은 주소값이 작은 > 큰 쪽으로 할당
  • 스택의 경우 주소값이 큰 > 작은 쪽으로 할당
• 프로세스 상태
  

  

  • new : 프로세스 생성
  • running : 명령 실행
  • waiting : 특정 이벤트 전까지 대기
  • ready : 프로세서에 할당되기 전의 대기 상태
  • terminated : 프로세스 삭제

• Process Control Block(PCB)
  

  

  • task control block이라고도 함
  • 각 프로세스에 대한 정보 저장
    • 프로세스 상태
    • program counter : 다음 명령어의 위치
    • 프로세스의 우선 순위
    • 메모리 정보
    • 사용된 CPU, 클락 등의 정보
    • 프로세스에 할당된 I/O, 파일 정보
  • process간의 교환 : Interrupt 혹은 System Call로 이루어짐
    

    

• Threads
  • 한 프로세스당 여러 개의 program counter 할당
  • 스레드 정보를 저장 가능한 공간 필요
    • ex. linux task_struct

  pid t_pid; /* process identifier */
  long state; /* state of the process */
  unsigned int time_slice /* scheduling information */
  struct task_struct *parent; /* this process’s parent */
  struct list_head children; /* this process’s children */
  struct files_struct *files; /* list of open files */
  struct mm_struct *mm; /* address space of this process */
  

Process Scheduling

• CPU 활용을 최대한으로 하는 것이 목적
• Queue 자료구조를 이용하여 관리
  • Job queue : 시스템 내 모든 프로세스
  • ready queue : ready / waiting 상태의 프로세스
  • device queue
    

    

    • 각 장치별로 queue head 존재
    • 프로세스가 device 사용 요청 시 해당 queue에 PCB가 연결
• 프로세스의 동작 순서
  

  

  • 생성된 프로세스는 ready queue로 할당
  • 동작하는 프로세스는 CPU로 이동
  • I/O request 시 > I/O queue 할당 후 I/O 접근
  • time slice expire > ready queue 할당 후 CPU 할당
  • child fork / interrupt > 작업 후 ready queue 할당
• scheduler
  • 프로세스가 I/O를 많이 쓰는지, CPU를 많이 쓰는지를 판단(I/O bound, CPU bound)
  • short term(CPU scheduler)
    • 현재 프로세스 바로 다음에 할당할 프로세스 선택
  • Long term(job scheduler)
    • 데이터센터 등 대형 시스템에서 사용
    • 다수의 작업을 모아서 한번에 효율적으로 처리
• Context Switch
  • 프로세스 상태를 저장하고 새 프로세스로 전환
  • 상태를 저장 - 불러오고 새로 실행하는 과정의 overhead가 매우 큼
    • 파일 입/출력을 많이 하는 프로그램이 느린 이유

Operations on Process

• Process Create
  • 부모 프로세스는 자식 프로세스를 생성
    • 트리 자료구조를 형성
    • 부모 프로세스는 자식 프로세스의 관리 가능(권한, 공유 등)
    • 부모-자식 프로세스의 동시 동작시 대기 혹은 병렬 처리 가능
  • 새 프로세스 생성 시, 부모 프로세스를 복사 후 프로그램 실행
    

    

    • UNIX의 프로세스 생성 명령어 - fork()
    • 자식 프로그램은 exec()명령어로 프로그램 실행
    • 부모 프로세스 wait : 자식 프로세스가 종료할 때까지 대기
• Process Terminate
  • 완료 시 exit 후 상태 데이터를 반환
  • 자원을 과도하게 사용하는 등 프로세스 종료가 필요할 경우 abort()도 가능
  • cascading termination : 부모 프로세스가 먼저 종료시 하위 프로세스도 종료
  • 자식 프로세스가 사라져도 자원 회수 등을 위해 PCB는 여전히 존재
    • 부모 프로세스는 wait()으로 exit될 때까지 대기해야 함
    • wait 없이 프로세스 종료 시 : Zombie Process
    • wait 없이 부모 프로세스 종료 시 : Orphan Process

interprocess communication

• 프로세스 간의 정보 교환
• 교환 모델
  

  

  • message passing : 커널에서 제공하는 메세지 큐를 이용한 정보 교환
  • shared memory : 프로세스 간 공유 공간 할당
  • Producer-Consumer Problem
    • 데이터의 생산자(Producer)와 소비자(Consumer) 관계
    • 버퍼를 한정할지(bound), 안할지(unbound)의 문제
• Shared memory
  • 통신하고자 하는 프로세스 간에 공유하는 메모리
  • OS가 아닌 사용자 level에서 통신 조절
  • 같은 메모리에 다른 프로세스가 동시에 조작 시 문제 존재
  • 프로그래밍이 어려우나
• Message Passing
  • send / receive를 이용하여 프로세스 간에 데이터 전송
  • 프로세스 간의 링크 설정 필요
  • 2개 이상의 프로세스 연결 / 통신 방향(단방향, 쌍방향) 등을 고려

• direct Communication
  • 데이터를 받을 프로세스 명시 send/receive(process, message)
  • pid가 바뀔 경우 접근 불가
• Indirect Communication
  • mailbox(port)를 이용한 데이터 공유
  • 같은 process 연결에서 여러 개의 link 형성 가능
  • mailbox 생성 > 데이터 교환 > mailbox 삭제 과정으로 진행

• Synchronization
  • Blocking : 데이터 송신 / 수신 중 한쪽이 끝날때까지 다른쪽은 불가
  • non-blocking : 송/수신에 제한 x, 오류 방지를 위해 데이터가 없는 경우 return 등으로 다른 행동을 하기 위한 별도 조치 필요
• Buffering : 링크 사이의 메세지 큐
  • zero cap. : 큐 용량 x, 송/수신 중 하나가 끝나야 함
  • bound cap. : 정해진 용량, 큐가 모두 차면 대기
  • unbound cap. : 중단 없이 전송 가능

IPC system

• POSIX
  • 통신할 각 process 내에 shared memory 생성
  • map 된 메모리에 메세지 작성(sprintf)
  • 받는 쪽은 해당 주소에서 데이터를 읽어옴
• Windows
  • LPC(local procedure cell) : 일종의 mailbox
  • client - server 사이에 connect port(연결 요청)
  • client/communication port(일종의 양방향 통신, message passing)
  • shared section object(공유 메모리 역할)
• Remote Procedure Call
  • 상대방 프로세스로 특정 동작을 요청
  • Stub : 두 프로세스 사이에 서로 다른 parameter, return 규칙을 알맞게 변환
  • Matcmaker : 프로세스 연결을 위한 Port 지정
• Pipe
  • 부모 - 자식 프로세스 간의 데이터 교환
  • pipe라는 파일 객체로 데이터 관리
    

    

  • fd[0] : write / fd[1] : read
  • named pipe : 부모-자식 관계와 무관하게 통신

OS Services/Interface

• OS의 기능
  • 사용자 관점
    • User Interface(UI) : CLI, GUI, 터치스크린, Batch 등
    • 프로그램 실행
    • I/O 동작 : 파일, 디바이스의 동작
    • 파일 시스템 manipulation
    • 통신 : local 혹은 외부 네트워크로의 접근
    • 에러 검출 : HDD Bad Sector 등
  • 시스템 관점
    • 자원 할당 : CPU 사이클, 메모리, 파일 등
    • Logging : 컴퓨터 자원 및 유저 활동의 추적
    • Protection / Security
• User Interface
  • CLI ( Command Line Interface )
    • 커널 혹은 시스템 프로그램에 의해 동작
    • 보안 문제를 방지하기 위해 Linux/Unix의 경우 Command를 별도 실행 파일로 만들어 두고 shell 자체는 최소한의 기능으로 유지
  • GUI
    • 사용자의 편의 중심
    • 대개 마우스, 모니터, 키보드로 구성
    • 아이콘이 파일, 프로그램 등을 나타냄

System Call

• 운영체제가 제공하는 일종의 인터페이스

• 보통 C/C++로 작성되며, Win32, POSIX, JVM 등이 있음

• System Call 실행

  • 보통 각 System Call에는 번호가 매겨져 있음
  • System Call Interface는 index table로 구성
  • 해당 값에 맞는 번호를 전달하여 system call : 시스템 상태와 정해진 값을 return

• parameter passing

  • System Call 시 상세 동작 수행
    • ex. file open 시 어떤 파일을 열 것인가?
  • 레지스터를 통한 전달 (Table) : 가장 단순한 방법
    • CPU 레지스터 크기의 한계 존재
  • 메모리 Stack, Queue 사용 : 특정 규약에 따른 parameter passing
  • System Call 시 주소와 Call number를 전달
    • 주소는 parameter가 저장된 주소를 가리킴
    • call number는 해당 system call을 호출

• system call의 종류

  • 프로세스 생성/삭제
  • 종료, 취소
  • 불러오기, 실행
  • 프로세스 권한 설정
  • 대기, signal event
  • 메모리 할당 및 해제
  • 메모리 오류 시 dump
  • 버그 / 명령 실행 시 디버깅
  • 공유 자원 접근 시 제한
  • 파일 관리
    • 생성, 삭제, 열고 닫기, 읽기, 쓰기, 권한 조정
  • 디바이스 관리
    • 요청, 해제, 읽기, 쓰기, 권한 조정

System Services

• 운영체제의 기능
  • 파일 관리 - 생성, 삭제, 복사, 이름 바꾸기 등
  • 상태 정보
    • 시간, 디스크 용량, 사용자 수
    • 로깅, 디버깅 등
    • 몇몇 시스템은 레지스트리(설정 정보 저장) 실행
  • 프로그래밍 지원 - 컴파일러, 어셈블러, 디버거 등
  • 프로그램 로드 및 실행- 로더, 링커 등
  • 통신
  • 백그라운드 서비스
    • 서비스, 서브시스템, 데몬(daemon)으로 유명
    • 디스크 점검, 프로세스 스케줄링, 에러 로그 등
    • 부팅 시 동작하나 커널이 아닌 유저 레벨의 프로그램

Linkers and Loaders

• 작성된 소스 파일은 컴파일되어 Object 파일로 할당(.o)

• 링커(Linker)는 object 파일을 실행 가능한 파일로 생성

  • 소스 코드(.c, .py), 연관된 라이브러리 등을 연결(Link)
  • 최근 시스템의 경우 실행 파일에 라이브러리를 링크하지 않음
    • DLL(Dynamically Linked Library)
      • 과거에는 모든 프로그램에 라이브러리가 링크되어 메모리 효율이 낮음
      • DLL을 메모리에 로드하여 복수 프로그램이 같은 라이브러리에 접근 가능
      • 이때 라이브러리를 호출할 때만 DLL이 로드됨

• 로더는 생성된 실행 파일을 메모리에 이동

  • 이 때 pointer 등 할당되는 데이터의 주소 결정

• 소스 프로그램 >> 컴파일러 >> 오브젝트 파일 >> 링커 (+다른 오브젝트 파일) >> 실행 파일 >> 로더 (+DLL) >> 메모리 할당

Why Applications are Operating System Specific

• 컴파일된 프로그램은 특정 OS에서만 동작
• 각 운영체제별로 System Call을 사용하는 방식이 다름
• 다중 OS를 지원하는 경우
  • 인터프리터 : 파이썬, 루비 등
  • Virtual Machine 내 프로그램 : 자바 등
• OS specific한 원인 - Application Binary Interface (ABI)
  • 운영체제 별로 API 구조는 동일
  • 함수 실행, 데이터 배치 등의 세부적 구조가 다르기 때문에 OS별로 동작이 다르게 나타남

OS Design and Structure

• OS design
  • 설계는 목적과 상세 사항의 정의로 시작
    • 사용하는 하드웨어, 시스템 종류 (모바일 등 특정 목적)에 영향
  • 사용자 / 시스템 관점을 볼 필요가 있음
    • 사용자 관점 : 사용 편의성, 이용 난이도, 속도 등
    • 시스템 관점 : 설계 및 구현, 관리 용이성, 오류 신뢰성
  • 설계의 분리
    • 정책 : 어떠한 작업을 할 것인가
    • 동작 : 어떻게 할 것인가
    • 수정이 적은 부분과 많은 부분을 분리
  • OS의 구현
    • 최하단은 assembly (하드웨어 컨트롤)
    • 주요 내용은 C로
    • 시스템 프로그램은 C/Cpp, 스크립트는 최근 쉘이나 파이썬이 이용되기도 함
• OS Structure
  • Unix (Monolithic Kernel)
    

    

    • 커널 내에 모든 기능 포함(I/O handling, filesystem, CPU schedule 등)
    • 빠르지만 복잡함
  • Linux (Monolithic + Modular)
    

    

    • 각 시스템 기능을 각각의 메모리 공간으로 할당
  • Layerd approach
    

    

    • 운영체제를 기능에 따라 층으로 분리
    • 낮을수록 HW에, 높을수록 유저층에 가까움
    • 자신과 자기보다 하위 층으로만 접근 가능
    • 디버깅이 용이(하위 Layer부터 순차적으로 검증)
    • User Program이 시스템을 이용할 때 Layer를 거쳐야 하는 만큼 Call 회수가 많아지는 단점 존재
  • Microkernel
    

    

    • Window, Linux 등의 커널 구조와 반대
    • Mach가 대표적인 예
    • 커널에는 최소한의 기능만 부여하고, 대부분을 유저 기능으로 할당
    • 각 기능 간의 통신은 message passing으로 구현
      • file system, application, driver 등의 user mode로 구현된 기능들의 message passing(MPI)는 kernel을 통해 전달
    • 구현, 디버깅, 관리가 용이
    • 속도가 느림 (User-kernel 간 교환의 overhead)

Lagrange Interpolation

Weierstrass Approximation Theorem

• Algebric Polynomial
  • 임의의 f(x)에 대한 근사식
  • $P_n(x)=a_nx^n+a_{n-1}x^{n-1}+...+a_0$
    

    

  • 함수 f가 [a, b]에서 연속할 경우, $|f(x)-P(x)|<\epsilon$인 P가 존재
  • 오차 $\epsilon$이 작아질수록 차수 n은 증가

Taylor Polynomial

• 함수 f가 x=a에서 (n+1)번 미분 가능할 경우
  • $f(x)=f(0)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+...+\frac{f^n(a)}{n!}(x-a)^n+\frac{f^{n+1}(\psi_x)}{(n+1)!}(x-a)^{n+1}$
  • n+1차항 : Taylor 급수의 error
  • $f(x)=P(x)=f(0)+f'(a)(x-a)+\frac{f''(a)}{2}(x-a)^2+...+\frac{f^n(a)}{n!}(x-a)^n$으로 근사할 수 있다
  • $\psi_x$ : x ~ a 사이의 임의 값
• ex. x=0에서의 $f(x)=e^x$
  • f는 미분해도 모두 동일한 함수
  • x=0 대입시 f=1
  • $\therefore e^x\simeq1+x+\frac{x^2}{2!}+...+\frac{x^n}{n!}$
  • error : $\frac{e^{\psi_x}}{(n+1)!}x^{n+1}$
• Taylor Polynomal의 수렴 반경
  • ex. 1/x의 taylor polynomal : 전개할수록 오차가 커짐
  • 1/x를 x=1에서 전개 시 x는 0 ~ 2를 벗어날 수 없음(대칭성)
  • 수렴 범위를 벗어날 경우 taylor polynomal은 발산
• Weierstrass theorem : P가 taylor 급수 ≠ P(x)가 수렴한다

Lagrange Polynomial

• Polynomal Interpolation(1차 식으로 근사)
  • 점 [x0, y0], [x1, y1]의 경우 $P_1(x)=\frac{y_1-y_0}{x_1-x_0}(x-x_0)+y_0$
• Lagrange Polynomial : Polynomial Interpolation을 구조화
  • $L_0(x)=\frac{x-x_1}{x_0-x_1},\ L_1(x)=\frac{x-x)0}{x_1-x_0}$로 정의
  • $P_1(x)=f(x_0)L_0(x)+f(x_1)L_1(x)$
• 2차 Lagrange Pilynomial : 점 [x0, y0], [x1, y1], [x2, y2]
  • $L_0(x)=\frac{(x-x_1)(x-x_2)}{(x_0-x_1)(x_0-x_2)},\ L_1(x)=\frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)},\ L_2(x)=\frac{(x-x_0)(x-x_1)}{(x_2-x_0)(x_2-x_1)}$
  • $P_2(x)=f(x_0)L_0(x)+f(x_1)L_1(x)+f(x_2)L_2(x)$
• 자기 자신을 제외한 나머지 점으로 규칙성을 갖는 식 수립 가능
  • n+1개 점 > n차 Lagrange Polynomial
  • general case : n차 다항식의 k번째 점의 lagrange basis $L_{n,k}(x)$
    $=\Pi\frac{x-x_n}{x_k-x_n}=\frac{(x-x_0)...(x-x_{k-1})(x-x_{k+1})...(x-x_n)}{(x_k-x_0)...(x_k-x_{k-1})(x_k-x_{k+1})...(x_k-x_n)}$
    

    

InterPolating Error bound

• Lagrange Polynomial로 구한 근사식
  • $f(x)=P(x)+\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
    • $\zeta(x)$는 a~b 사이의 임의의 점
  • $P(x)=f(x_0)L_{n,0}(x)+...+f(x_n)L_{n,n}(x)=\sum^{n}_{k=0}f(x_k)L_{n,k}(x)$
  • Error : $\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
• 증명 과정
  • $x\not ={x_k}$라고 할 때, $g(t)$함수를 다음과 같이 정의
    • $g(t)=f(t)-P(t) - [f(x)-P(x)]\frac{(t-x_0)(t-x_1)...(t-x_n)}{(x-x_0)(x-x_1)...(x-x_n)}=f(t)-P(t) - [f(x)-P(x)]\Pi^n_{i=0}\frac{(t-x_i)}{(x-x_i)}$
  • P는 f의 interpolation이므로 모든 x값에 대해
    $g(x_n)=f(x_n)-P(x_n)=0$ ($Pi$항은 분자 식에 의해 0)
  • Rolle's Theorem : n개 점에서 함수가 0이면, n-1차 미분의 값이 0인 점이 존재
    • g(t)는 $x, x_0, x_1, ..., x_n$의 구간으로 n+2개의 함수가 0인 점이 존재하므로, n+1차 미분이 0인 점 $\zeta$가 존재
    • $f^{n+1}(\zeta)-P^{n+1}(\zeta)-[f(x)-P(x)]\frac{d^{n+1}}{dt^{n+1}}[\Pi^n_{i=0}\frac{t-x_i}{x-x_i}]_{t=\zeta}$
    • P는 최대 n차식이므로 $P^{n+1}=0$
  • $g^{n+1}(\zeta)=0= f^{n+1}(\zeta)-0-[f(x)-P(x)](n+1)!\Pi^n_{i=0}\frac{1}{x-x_i}$
    • $(t-x_i)$는 n+1차항이므로 n+1번 미분하면 (n+1)!
  • 위 식을 f(x)에 대해 정리하면
    $f(x)=P(x)+\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$
  • 즉 원래 식과 근사식의 차 $f(x)-P(x)=\frac{f^{n+1}\zeta(x)}{(n+1)!}(x-x_0)(x-x_1)...(x-x_n)$가 Error값이 됨
    • 최대 오차는 $max|\frac{f^{n+1}(\zeta(x))}{(n+1)!}|\cdot max|(x-x_0)(x-x_1)...(x-x_n)|$