skyjump's blog

Background

Dynamic programming은 문제를 subproblems로 쪼개서 문제를 푸는 방식이다.

subproblem들이 독립적이면 divide-and-conquer 방식으로 풀 수 있고
독립적이지 않으면 dynamic programming을 한다.
독립적이지 않은 것의 의미는 sub problems가 subsub problems를 공유하는 것이다.
dynamic programming 알고리즘은 같은문제를 또 풀지 않기 위해서 subproblem을 한번만 풀고, 그 결과를 table에 저장한다. 그리고 나중에 필요할 때, 테이블을 참조해서 값을 가져온다.

 Dynamic programming은 최적화 문제(optimization problems)를 푸는데 이용된다.
솔루션은 여러개이지만 그중에 최적화 된 값(최소값 or 최대값)을 가진 솔루션은 하나다. Dynamic programming으로 그 솔루션을 찾는다.

문제 푸는 4가지 단계 
1. optimal substructure를 구한다.
2. recursive solution을 구한다. 
3. optimal solution의 값을 bottom-up 방식으로 계산한다.
4. 계산된 정보로 optimal solution을 구한다.

optimal solution의 sub solution도 optimal solution이다.

overlapping subproblems
순환적인 알고리즘이 같은 문제를 계속 반복하여 방문할 때.

참고 

cs.kangwon.ac.kr/~ysmoon/courses/2011_1/alg/06.pdf

blocked 프로세스가 서로 필요로 하는 자원을 가지고 있을 때.

System Model
시스템은 자원(씨피유 사이클, 메모리 공간, I/O 디바이스 등)들로 이루어져 있다. 
각각의 자원은 여러개의 인스턴스가 있다.
프로세스가 한 자원 type의 인스턴스를 요구하면 그 타입의 어떤 인스턴스라도 그 요청을 수행할 수 있다.
자원을 사용하고 나서는 반드시 반환해야 한다.

Deadlock Characterization
네가지 조건이 동시에 발생했을 때 Deadlock이 발생할 수 있다.
1. Mutual exclusion(리소스가 여러 프로세스에 의해 공유될 수 없다.)
2. Hold and wait (하나 이상의 리소스를 가지고 있는 채로 다른 자원을 획득하기를 기다리는 것)
3. No preemption (중간에 리소스를 뺏기지 않는 것. 작업을 마치고 내놓는 것)
4. 기다리는 프로세스들이 사이클을 이룰 때. p0는 p1이 가지고 있는 리소스를 원하고, p1은 p2, p2는 p0.

일반적으로 사이클이 없으면 데드락이 없다. 사이클이 있으면 데드락 가능성이 있다. 하지만 있어도 반드시는 아니다. 하나의 자원 type에 여러개 인스턴스가 있는 경우 데드락이 생기지 않을 수도 있다.

Methods for Handling Deadlocks
시스템이 데드락 상태에 빠지는 것을 허용하지 않도록 하는 것.
시스템이 데드락 상태에 빠지는 것을 허용하나, 그것을 감지하고 회복하는 것.
데드락 상태에 빠지면 그 문제를 무시하고 데드락이 발생하지 않은 것처럼 행동하는 것.

Deadlock Prevention

1. Direct-address tables
키가 n개 있으면 테이블의 크기도 n개
키를 테이블에서 찾는 것, element를 삽입하는 것, 삭제하는 것 모두 running time O(1)
전체 키에서 실제 사용되는 키가 적을 경우 공간 소비가 심하다.
O(1)를 유지시키면서 공간을 줄일 수 있는 방법이 없을까?

2. Hash tables
Hashing
키를 해쉬함수에 넣어서 나온 값으로 hash table에 들어갈 위치를 정하는 것.
Collision
두 키의 Hashing 결과 같은 위치를 가질 때
테이블의 크기가 키크기보다 작기 때문에 collision을 피할 수 없다. collision을 최소화하도록 한다.
어떻게? Hashing function을 잘 만들기.

Collision이 발생하였을 때 해결하는 방법

소프트웨어 개발

1. 특징리스트

2. 유스케이스 다이어그램

3. 문제점 분해하기
코드에 관한 것으로 어떻게 기능을 분해할지에 대한 것.
4. 요구사항
고객이 소프트웨어를 어떻게 사용할지에 대한 것.
5. 도메인 분석

6. 사전 설계

7. 구현

8. 4~7 반복

9. 완성

시스템에서 특징은 시스템이 해야 하는 것이며, 시스템이 어떻게 사용되어야 하는지 보여 주는 유스케이스에 항상 반영되지는 않는다. 간접적으로 사용된다.

문제점을 분해하고 유스케이스를 요구사항으로 바꿀 때, '문제 이해하기' 단계가 들어갈 수 있다.

 

http://www.eclipse.org/forums/index.php/m/525050/

상대경로로 했더니 java.io.filenotfoundexception가 나고 절대경로로 하면 괜찮아서 이유를 검색해보니 루트디렉토리가 내가 생각한게 아니었다.

이클립스가 자바클래스를 돌릴 때 현재 경로는 프로젝트의 루트 리렉토리이다. 프로젝트 소스트리의 루트디렉토리가 아니다.
즉 class폴더가 현재경로가 아니라 프로젝트 폴더가 현재경로이다.
나는 class 폴더에 파일을 넣어서 계속 읽을수 없다는 예외가 발생한 것이었다. 

파일시스템의 경로로 읽는 것보다 getResourceAsStream을 써서 클래스패스로부터 파일을 읽으라고 한다. 

Lower bounds for sorting
worst case에서 nlgn보다 빠른 comparison sort(원소의 순서를 정할 때 비교만 사용하는 정렬)가 없다.
참고) heap sort랑 merge sort가 worst case에서 O(nlgn)

The decision-tree model

출처 : http://serverbob.3x.ro/IA/DDU0048.html


모든 원소가 구별되는 값(distinct)이라면
input의 모든 원소를 ai <= aj 로 표현할 수 있다.

comparison sort를 decision trees로 볼 수 있다.
내부 노드 (i,j)는 ai<=aj 임을 의미한다.
각각의 잎노드는 input 원소의 순열(permutation)이다.
 
decision tree의 루트부터 leaf까지의 path는 sorting algorithm의 수행하고 같다.
가장 긴 path의 길이는 worst case를 의미한다.
즉, worst case는 트리의 높이와 같다.

모든 comparison sort algorithm은 worst case일 때 Ω(nlgn) 만큼 비교한다.
n! <= 2^h      (n!은 총 잎의 갯수, h는 트리의 높이)
h>= lg(n!)  
h = Ω(nlgn)   ( 왜냐하면 lg(n!) = Θ(nlgn) )

Counting sort
n개의 입력원소가 정수이고 범위가 0부터 k(k<=n)일 때라고 가정한다.
"입력원소 x는 x보다 작은 원소의 수가 i-1개 라면 정렬후에는 i에 위치해야 한다." 라는 원리
집합 A의 원소의 범위가 0~k일 때, 집합 A의 원소의 값이 집합 C의 i와 같으면 Ci값에 1을 추가한다. 집합 C는 A의 원소의 범위가 0~k이므로 k+1크기의 배열이면 된다. C는 A원소의 횟수를 저장한 집합이 된다. C'는 C의 누적합이다. (C'[i] = C[0] + ... + C[i]) 
이 C'를 이용해서 A를 정렬을 할 수 있다. C'i의 값이 a라고 하면 이는 i보다 작거나 같은 값이 집합 A에 a개 있다는 소리다. 그래서 i가 들어갈 자리는 a가 될수 있다.
Stable(입력값이 같은 값이 있을 때 그 순서를 결과값에도 유지 시키는 것)하게 하기 위해서 A의 맨 끝에 있는 원소부터 C'를 이용해서 위치를 찾는다.
수행시간
Θ(n+k)
Θ(k) : C를 0으로 초기화
Θ(n) : A를 스캔하면서 C에 카운터를 증가.
Θ(k) : C를 스캔해서 C' 구하기
Θ(n) : C'과 A를 이용해서 정렬된 집합 B를 구하기. B[C'[A[j]] <- A[j]
k가 O(n)이면 수행시간은 Θ(n)!

Radix sort
n 자리수 숫자들이 있을 때 각 자리수끼리 정렬.
1) 최대유효숫자 -> 최소유효숫자
최대유효숫자부터 정렬. 이전 그룹을 유지하면서 정렬을 해줘야 바르게 정렬이 된다. 
2) 최소유효숫자 -> 최대유효숫자
최소유효숫자부터 정렬.

정렬할 때 stable한 sort 알고리즘을 쓴다.

각 자리수의 범위가 k일 때 d 자리인 n개의 수를 radix sort한 수행시간은?
k가 안크면 counting sort 사용하면 된다.
Θ(d(n+k))           (n+k을 d번한거)
d가 상수고, k = O(n)일 때 radix sort는 linear한 소트이다.

b-bit인 수 n개를, r<=b일 때, r개씩 자르고 radix-sort로 정렬했을 때 수행시간은?
Θ((b/r)(n+2^r)) time.
b/r은 d이고 2^r은 k.
예를 들면
32bit를 8bit씩 4개로 나눠서 4자리씩 radix sort.
r=8, b=32, k는 8bit로 0부터 2^8-1까지, 0부터 255까지 표현할 수 있으니 256개 필요하고, b/r=4, n+2^r = n+256.

Θ((b/r)(n+2^r))을 최소화하는 r
1. b < floor(lgn) 일 때
r<=b 이므로 (n+2^r)은 Θ(n)
그래서 r=b일때, (b/b)(n+2^b) = Θ(n) 

2. b >= floor(lg n) 일 때
r=floor(lg n)을 선택는 것이 최적이다. (b/lgn)(n+2^(lgn) = (b/lgn)(2n) = Θ(bn/lg n)
r이 floor(lg n)보다 커지면 2^r은 기하급수적으로 증가하고
r이 floor(lg n)보다 작아지면 b/r은 커지고 n+2^r 은 Θ(n)이 된다.

따라서 1,2 종합해보면 r=lg n씩 자를 때가 최적이다.

Radix sort가 퀵소트보다 좋을까?
Radix sort는 Θ(n)이고 퀵소트는 Θ(nlgn) 이니 radix sort가 더 좋을 것 같다.
퀵소트보다 각단계(pass)의 횟수가 작을 수가 있지만 Θ(n)에 감춰진 상수값이 클 수가 있다. 즉, Radix sort의 각각의 pass에서 오래 걸릴 수 있다. 그리고 퀵소트는 하드웨어 캐쉬를 더 효과적으로 사용해서 더 빨리 처리된다. 그리고 Radix는 sort in place가 아니다. 정렬하면서 중간값을 저장할 공간이 더 필요하다. 이런점에서 메모리가 좋다면, in-place 알고리즘인 퀵소트가 빠르다.
퀵소트와 캐쉬 locality를 설명한 글 참고
http://soyoja.tistory.com/248#comment1449755



 

반복작업을 통해 소프트웨어를 만든다.
큰 그림에서부터 거기서 나눠진 조각들에 대해 반복적으로 작업한다.

특징주도개발(Feature driven development)
고객이 원하는 기능의 한 조각을 선택하고 그것이 완성될 때까지 작업하는 것

유스케이스 주도 개발(Use case driven development)
하나의 완전한 경로를 시작에서 끝까지 코드로 구현.

두가지 방법 모두 고객이 원하는 것을 개발하는 데 초점을 맞추고 있다.

특징 주도 개발
하나의 특징을 결정했다면, 다시 그 특징에대한 분석을 한다.
반복적인 분석. 트리처럼 깊히 분석할수록 세부적인 기능들이 나오는 것을 상상.

고객을 만족시키기 위해 테스트 시나리오를 만든다.
모든 가능한 사용 방법으로 테스트한다.
잘못된 사용 방법에 대해서도 테스트 한다. 이는 초기에 오류를 잡도록 해줄 것이다.

테스트 주도 개발
테스트를 먼저 작성하고 이 테스트를 통과할 수 있도록 소프트웨어를 개발한다.

실제 대부분의 소프트웨어 분석 설계는 다양한 접근 방식을 혼용하여 사용한다. 예) 유스케이스 주도 개발로 시작하여 다음 작업은 유스케이스에서 작은 특징 하나를 선택(특징 주도 개발)해서 개발. 이 특징을 어떻게 구현할지 확인하기 위해 테스트 주도 개발 사용.

각 테스트는 기능의 한 부분에 초점을 맞춘다.

설계방식을 결정할 때( 예) 공통점과 캡슐화 중에서 하나 선택해야 할 때.) 어느 방법이든 항상 트레이드오프(trade off)가 있다. 장점이 있지만 단점도 있는.

반복해서 작업할 때마다 기존의 설계방식을 재평가하고 더 나은 방향으로 변경하는 것을 두려워하지 마라.

약정에 의한 프로그래밍(contract), 방어적 프로그래밍(defensive)
약정에 의한 프로그래밍을 할 때, 문제 상황을 어떻게 다룰 지 합의하기 위해 고객의 코드와 같이 작업하는 것.
방어적 프로그래밍을 한다면, 고객이 어떠한 일이 발생되기를 원하건 간에, 고객이 안전한 응답을 얻도록 확인할 것.
 

CPU Scheduler
상태가 ready인 프로세스큐에서 하나 선택.
스케쥴링 결정은 프로세스가 (1) running에서 waiting으로 바뀔때, (2) running에서 ready로 바뀔 때, (3) waiting에서 ready로 바뀔때, (4) 종료될 때 nonpreemptive(자발적으로 cpu를 내놓는것)하게 발생한다. 다른 경우는 preemptive(cpu를 빼기는 것)이다.

preemptive 스케줄링의 문제점
공유데이터 일관성이 깨질 가능성 (한 프로세스가 data를 업데이트하는 중에 다른 프로세스한테 cpu 뺏기고 그 프로세스가 그 data를 읽으려고 할 때)
커널데이터의 일관성이 깨질 가능성
예) 커널이 I/O queue를 바꾸고 있었다. 다른 프로세스에게 cpu를 뺏겼다.
시스템콜을 호출할때 그것이 완료되기까지 다른 프로세스가 돌아가지 않도록 하거나, I/O block을 하는 방법이 있다.

Dispatcher
스케줄러가 프로세스를 결정하고 cpu에게 넘겨주는 작업
context switching.
user mode로 바꿈. 스케줄러는 커널에서 작동하므로.
user program에서 다시 시작할 곳의 위치로 jumping

어떻게 하는 것이 좋은 스케줄링인지 결정하는 기준
좋은 스케줄링일 수록 CPU가 노는 일 없게 한다.
Throughout - 임의 시간동안 처리가능한 프로세스갯수. 최대화
Turnaround time - 프로세스의 제출부터 종료까지 경과되는 시간. 최소화
waiting time - 프로세스가 레디큐에 머물러 있는 시간. 최소화
response time - 프로세스가 만들어졌을때부터 실행하기까지 걸리는 시간. 최소화.

First-Come, First-Served(FCFS) Scheduling
선착순방식.
프로세스 도착 순서에 따라 성능이 좌우.
CPU burst(설명, 간단하게 요구하는 시피유 시간)가 큰 프로세스가 들어오면 average waiting time이 커짐.

Shortest-Job-First (SJF) Scheduling
CPU burst가 가장 작은 프로세스를 실행하도록 스케줄링
2가지 방식이 있다.
nonpreemptive - process에게 한번 cpu가 주어지면 cpu burst가 완료될때까지 cpu를 뺏기지 않는다.
preemptive - 새로운 프로세스가 현재 실행중인 프로세스의 남아있는 burst time보다 작은 burst time를 가지고 있다면 cpu를 빼았는다.

Priority scheduling
우선순위에 따라 CPU를 주는 것.
Preemptive, nonpreemptive가 있다.
SJF도 우선순위 스케줄링 방식(cpu burst time이 작을수록 우선순위가 높은것)이니 위에 것이 이해가 될 듯.
문제점
Starvation - 낮은 우선순위는 영원히 실행 안될 가능성이 있다.
해결책 - aging. 프로세스의 우선순위를 시간이 지나면 올려준다. 나이먹는 것처럼.

Round Robin (RR)
각 프로세스가 작은 단위의 CPU time을 얻는다.
한 프로세스가 cpu 사용시간이 지나면 그 프로세스는 preempted 되고 레디큐의 끝에 추가된다.
보통 average turnaround time은 SJF보다 길지만, response time은 짧다. interaction이 중요한 프로그램에게는 이 방식이 좋을수도.

Multilevel queue
레디큐는 여러개의 큐로 나눠진다.
예) foreground용, background용
각각의 큐는 스케줄링 알고리즘을 가지고 있다.
예) foreground(RR), background(FCFS)
큐들 사이에도 스케쥴링이 있다.
예) fixed priority scheduling(foreground queue의 우선순위가 background queue의 우선순위보다 높아서 높은 우선순위의 프로세스가 무조건 cpu를 뺏어올 수 있도록), Time slice(각각의 큐마다 CPU time을 할당한다. foreground에는 80%, background에는 20% 이런식으로) 

Multilevel Feedback Queue
프로세스가 큐들 사이를 이동 할 수 있는 것.
한 프로세스가 CPU를 너무 많이 잡아먹었다싶으면 낮은 우선순위 큐로 내려보내는 것.

리눅스에서의 스케줄링 정책