skyjump's blog

Divide-and-Conquer
(1) 피봇을 정하고 (2)피봇보다 작은 수 큰 수를 나누고 나눠진 집합에 대해 다시 (1),(2)번을 반복하면 정렬이 되는 그러한 정렬방식이다.

Partition
피봇을 정하고 피봇보다 작은 수 큰 수를 나누는 과정이다.
time은 Θ(n) 이다. 리스트 한번만 읽으면 되니까.

Balanced partitioning
파티션이 반반씩 나눠질때, T(n) <= 2T(n/2) +  Θ(n) = O(nlgn)
퀵소트에서 피봇이 잘 뽑이면 이러한 결과가 나온다.

Unbalanced partitioning
피벗이 가장 작은 수나 가장 큰 수가 뽑혔을때
원소가 n개 있으면 파티션이 하나, n-1개로 나눠져서
최악의 경우가 된다. 파티션을 많이 해야 한다.
최악의 경우가 insertion sort랑 비슷하다.
T(n) = T(n-1) +  Θ(n) 이므로 계산하면 Θ(n^2)가 된다.

worst cast 분석
unbalanced partitioning이 최악의 경우임을 보증하는가?
증명 여기 사이트 formal worst case analysis 참고

Average-case analysis
Zij = {zi, zi+1 ... zj} 인 array를 퀵소트한다고 하자.

X를 임의의 quicksort 실행에서 전체 비교횟수인 확률변수로 보면
quicksort의 평균수행시간은 O(n+E[X]). (n은 스캐닝 + etc)

각각 파티션마다의 비교횟수를 생각하지말고 전체적으로 비교횟수를 보자.
그러면 array에서 임의의 2개 원소는 많아야 한번 비교한다. 2개중 하나가 피봇일 때 한번 비교 하는 것이다. 그리고 피봇은 다음번 단계 이후부터는 비교대상에서 제외된다. 그래서 임의의 두개 원소는 기껏해야 한번 비교가 된다.
 
그럼 이 식들이 이해가 되었음.

계산과정은 생략하고 
계산하면 O(nlgn)이 나온다. 평균수행시간이 된다.

Randomized quicksort
피벗을 랜덤으로 뽑는다.
average-case를 보장하도록 한다.
input의 형태에 관계없이 항상 uniform하게 quicksort를 할 수 있다. 

디자인원리는 코드를 좀 더 유지보수하기 쉽고 유연하고 확장하기 쉽게 만들어준다.
이전에 배웠던 디자인원리
캡슐화, 구현에 의존하기 보다 인터페이스에 의존하도록 코딩, 각 클래스는 변경요인이 하나여야 한다, 클래스는 행동과 기능에 관한 것이다.

Open-Closed principle, OCP 
클래스는 확장에는 열려있고, 수정에는 닫혀있어야 한다.

OCP의 예

 
CRT와 LCD는 Monitor를 상속한다. Monitor 클래스는 수정에는 닫혀 있다. display 메소드는 변경되지 않는다.
하지만 서브클래스들이 오버라이드를 통해 display의 행동을 변경할 수 있기 때문에 확장에는 열려있다.

OCP는 단순히 상속에 대한 내용은 아니고 유연성에 대한 내용이다. 또 다른 예 : private 가 있는 클래스.
OCP는 잘 동작하여 고객을 만족시키고 있는 코드를 건드리지 않고도 부모 클래스의 행동을 추가 확장할 수 있다.
OCP는 캡슐화와 추상화의 조합. 변하지 않는 클래스의 기능을 찾아 부모 클래스에 추상화하여 변경하지 못하게 한다. 새롭거나 다른 기능이 필요할 때, 부모 클래스를 확장하여 변경을 해결한다.

DRY (Don't Repeat Yourself)
공통되는 부분을 추출하여 추상화하고 한 곳에 두어 중복 코드를 피하기.
하나의 요구 사항은 한 곳에 두어야 한다는 원리.(시스템의 정보와 기능이 한 곳에 있어야 한다)
코딩할 때 뿐만아니라 요구사항 수집때부터 요구사항이나 유스케이스가 겹치지 않도록 해야 한다.

 SRP (Single Responsibility Principle)
 한가지 일만 잘하게 하자. (클래스 변경의 요인이 한가지여야 한다.)
응집도와 같은 의미
SRP인지 테스트 하는 방법.
(클래스이름)가 자신을 (클래스의 각 메소드)한다.
이게 말이 되면 SRP.

리스코프 치환 원리(LSP)
상속에 대한 내용. 부모클래스가 사용되는 곳은 아무 문제없이 자식 클래스도 사용될 수 있어야 한다.

위임(Delegation)
특정 일의 책임을 다른 클래스나 메소드에 맡길 때
다른 클래스의 기능을 사용해야 하지만 그 기능을 변경하고 싶지 않을때 사용.
예) 악기 인벤토리 클래스에서 사용자가 악기를 검색할 때, 검색기능을 악기스펙 클래스에게 맡기는 것.

구성(Composition)
비슷한 여러 종류의 기능을 참조하는 경우.
예 ) 병사가 여러 무기를 사용하고 싶을 때 무기 인터페이스를 참조해서 실행중에 특정무기 클래스로 바꿀 수 있도록 할 때.
구성되어 있는 객체들은 그것들을 참조하는 객체에 속한 거라 그 객체가 없어지면 구성 객체들도 없어지는 특징이 있다.
하지만 안 사라지게 하고 싶을땐? 즉, 클래스 외부에서도 존재하도록 하고 싶을 때는 어떻게 할까? 집합(Aggregation)을 사용한다.

집합(Aggregation)
한 클래스가 다른 클래스의 부분으로 사용되지만 다른 클래스의 외부에서도 여전히 존재하는 경우.

리스코프 치환 원리(LSP)는 언제 상속을 사용할 것인가에 대한 원리. LSP가 성립하지 않는 다면, 즉 부모클래스가 사용된 곳에 자식클래스가 대체되어 사용될 수 없으면, 집합이나 구성, 위임등 다른 객체지향 방법을 찾아봐야 한다.
 

merge sort와 같이 running time이 O(nlgn)이다.
insertion sort와 같이 sorts in place이다.

Heaps
complete binary tree이다. 높이가 k일 때 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k부터는 왼쪽부터 오른쪽으로 노드가 채워지는 tree.

참고) full binary tree : 각 레벨에 노드가 꽉 차있는 트리

힙의 종류

Threads란?
CPU 이용의 기본 단위. 스케쥴링의 가장 작은 단위
lightweight process라고 부른다.
코드섹션, 데이터섹션, open files나 signal같은 운영체제 자원을 같은프로세스에 속한 쓰레드들끼리 공유한다.
쓰레드끼리 공유 안하는 것은 Thread Id, stack, register, pc 이다.

참고> 코드영역, 데이터영역, 스택영역, 힙영역
코드영역 : 실행할 프로그램 소스코드
데이터영역 : 전역변수, static 변수
스택영역 : 지역변수, 매개변수, 리턴값
힙영역 : malloc같이 사용자가 할당한 메모리가 여기 저장됨.
참고 사이트 : http://blog.naver.com/PostView.nhn?blogId=ace7min&logNo=18253266

장점
1. 쓰레드 중에 하나가 blocking될 경우 다른 쓰레드가 돌아가기 때문에 프로그램이 계속 돌아간다.
2. 메모리와 자원을 공유한다.
3. 같은 프로세스 내에서 쓰레드 전환이 일어날 경우 프로세스 생성을 하지 않고 context switch overhead 작다.

User threads와 Kernel Threads

큰 조각을 작은 조각으로 나누었고 아키텍쳐는 이러한 조각들이 어떻게 연결되는지 그리고 어떤 조각들이 더 중요한지를 알게 해준다. 즉, 무엇부터 시작해야 될지 알려준다.
아키텍쳐 (architecture)
아키텍쳐는 디자인 구조이고 프로그램의 가장 중요한 부분들과 그들 사이의 관계를 명확히 보여준다.
중요한 구성요소들의 관계를 파악하기 위해서는 구성 요소를 알아야 한다.
그래서 그 구성요소부터 파악한다. 가장 중요한 기능에 초점을 맞춘다.

중요한 기능을 정하는 기준.
1. 시스템의 본질이 되는 부분인지. 가장 기본적인 요소.
2. 그 기능이 무슨 의미인지 모를 때.
3. 그 기능을 도대체 어떻게 해결해야될지 감이 안올 때.

중요한 기능을 발견하고 나서 어떤 기능을 먼저 만들지는 위험요소(양이 많아 시간이 오래 걸린다던가, 고객이 시스템을 맘에 들어 하지 않는다던가, 해결못할 가능성이 있다던가 등등 )를 줄이는 방향으로 진행하기만 하면 순서는 상관없다.

시나리오는 중요한 요구사항을 포함한 유스케이스의 특정 경로.
시나리오는 중요한 기능에 초점을 맞춤으로써 위험요소를 줄이는 데 도움이 된다.
시나리오는 빠르게 문제를 해결할 때, 보편적인 요구 사항을 찾는 데 도움이 된다.
유스케이스는 모든 경로를 다루고 있어서 시간이 오래걸리고 형식적일 수도 있다. 처음부터 너무 세세한 내용에 집착하지 말것.
유스케이스를 사용하든 유스케이스 다이어그램을 사용하든 시나리오를 사용하든 사용목적은 고객의 만족이다.
위험을 줄이려면 한번에 하나의 특징에 집중하고, 위험을 줄이는데 도움이 되지 않는 특징들에 너무 연연해하지 말기.

기능이 무슨 의미 인지 모를 때 먼저 고객들에게 물어본다.
고객들의 이야기를 바탕으로 공통점을 찾고 그 특징을 어떻게 구현할 것인가를 정한다.
좋은 디자인은 위험을 줄여 준다. 이 기능이 무엇인지 파악했고 프로젝트 진행 중에 별다른 변경없이 다른 클래스들과 연결될 수 있다.
공통점분석할 때 차이점이 더 많다면 시스템내에서 그 기능을 처리하지 않는 것이 좋은 방법이 될 수 있다. 

Thread 클래스 상속.
run()함수에서 쓰레드 동작 수행
start()함수로 쓰레드 실행

2가지 방식으로 run함수 제공할 수 있다.
첫번째는 쓰레드 클래스를 상속해서 run함수를 오버라이드.
두번째는 Runnable 인터페이스를 구현.

쓰레드 상태

출처 : http://www.cs.nccu.edu.tw/~linw/javadoc/tutorial/java/threads/states.html

API 보니까 stop, suspend, resume은 위험하다고 쓰지 말라고 하네. 한 15년 된 자료인듯ㅋ

Runnable에서 not runnable로 갈 때는 sleep함수가 호출 되었을 때, 또는 condition variable(공유하구 있는 변수인듯)을 기다릴때, 또는 I/O 처리할때

Dead일 때는 할일 다하고 죽었을 때랑. stop에 의해 죽었을 때. API 문서 보니까 stop 대신에 thread 레퍼런스에 null을 넣으라고 하네.

IsAlive() method : 쓰레드가 살아있는지 확인하는 함수. Runnable일때랑 Not runnable일 때 참.

Thread 우선순위
우선순위가 가장 높은 쓰레드가 선택되어 실행되고 중간에 우선순위가 더 높은 쓰레드가 나오면 교체된다.(preemptive) 쓰레드가 종료되거나 yield()함수로 다른 쓰레드에게 CPU를 넘겨주거나, 무슨 이유로 Not runnalbe이 될 때 낮은 우선순위 쓰레드가 실행 될 수 있다. 쓰레드 2개 이상이 우선순위가 같으면 시스템이 time-sliced일 경우 round-robin 방식으로 수행된다. 즉, 뺑뺑이 돌리면서 실행 된다. time-sliced가 아니면 cpu가 쓰레드 교체 안하고 계속 처리하겠지.

Daemon thread.
다른 스레드에게 서비스를 제공하는 스레드. 그래서 프로세스에 daemon thread 혼자만 남았을 때 존재의 이유가 없어지므로 프로세스가 종료된다.

Thread group
쓰레드를 묶어서 한번에 처리.
처음에 쓰레드 생성할 때 그룹을 지정.

큰 문제는 여러 개의 기능별 조각들로 나누고 각 조각들을 개별적으로 해결.

이제까지 배운것들.
1. 좋은 요구 사항을 얻는 가장 좋은 방법은 시스템이 해야 할 일을 이해하는 것.
2. 변하는 것을 캡슐화해서 프로그램을 더 유연하고 변경하기 쉽게 만든다.
3. 구현보다는 인터페이스에 맞춰서 코딩하면 소프트웨어의 확장이 더 쉬워진다.
4. 좋은 소프트웨어는 변경과 확장이 쉽고 고객이 원하는일을 한다.
5. 분석은 시스템이 실제로 잘 돌아가도록 만드는 데 도움이 된다.

시스템 파악하기
고객과의 대화를 통해 시스템을 파악한다.
좋은 방법 중 하나는 공통점과 차이점을 알아내는 것인데
이는 시스템이 어떤 시스템과 비슷하고, 안비슷한지 얘기하는 것이다.
그리고 나서 대화 정보를 가지고 시스템의 특징을 찾아낸다.
특징을 가지고 요구사항을 알아낸다. 특징과 요구사항은 비슷하다고 보면 된다.
세부내용은 늦출 수 있을 때까지 최대한 늦추기. 세부내용에 신경쓰다가 큰 것을 놓칠 수 있기 때문에
먼저 큰 그림을 봐야 한다.
유스케이스는 큰 그림을 보는 데 도움이 되지 않는다.
그래서 유스케이스 다이어그램을 이용한다.

Use-case 다이어그램
시스템 전체에 대한 큰 그림
특징 리스트 내용이 유스케이스 다이어그램에 빠짐없이 들어가도록 하기.

Actor - 시스템과 상호작용하는 외부객체
Box는 시스템의 경계
각 타원은 유스케이스

도메인 분석
시스템에 대해 알아낸 정보를 고객이 잘 이해할 수 있도록 나타내는 프로세스
특징리스트를 고객이 이해하는 언어로 작성한다.

이제 큰 그림을 그렸으니 작은 기능들로 쪼갠다.
도메인 분석을 하면 만들 필요가 없는 시스템기능을 알 수 있다.

작은 기능들로 나누면 디자인 패턴을 시스템에 적용할 수 있다. 
모델-뷰-컨트롤러
모델 - 시스템에서 실제 일어나는일을 모델링
컨트롤러 - 모델을 관리
뷰 - 모델을 나타내는 것

 

combinational circuit
input, logic gates, output으로 구성되어 있다.

analysis
회로도 분석해서 logic function, truth table 구하기

디자인
combinational circuit 만드는 절차.
1. 입력갯수, 출력갯수 몇개인지 정확히 파악한다.
2. truth table을 만든다.
3.boolean functions를 간략화한다. (카르노맵 이용)
4.그린다.

Half adder
비트2개 더하기. 입력 2개, 출력 2개. 출력은 합(S)과 자리올림값(C).
S = x'y + xy'
C = xy

Full adder
비트3개 더하기. 입력 3개. 출력 2개(S,C).
입력 2개는 더하는 수, 나머지 하나는 이전 자리수에서 발생한 carry로 본다.
Half adder 2개와 OR gate 하나로 만들 수 있다.

Binary adder
Full adder로 n-bit 끼리 더하기를 할 수 있다.
각 자리의 Carry값들이 동시에 나오지 않고 낮은 자리부터 전파되어서 연속으로 나온다.
Carry Lookahead Generator : 케리들이 같이 나오게 하는 방법.

Binary subtractor
A-B면 B의 각 bit에 보수를 해서 더해주고 처음 carry 값 C0에 1을 넣어준다.

overflow
binary adder, subtractor에서 overflow가 발생할 수 있다. 4bit adder subtractor가 있을 때 더하는 수가 unsigned면 C4 가 1이면 overflow. signed면 C3나 C4중 둘 중하나가 1이면 overflow다. signed일때 C3가 1이 될 경우는 큰 양수 2개(A+B)를 더했을 때 sign bit 전의 bit 합(A3+B3)이 2가 넘어 자리 올림이 발생한다. 이 때 C3가 1이 되어 sign bit로 가고 sign bit가 1이 되어 버린다. 그리고 C4가 1이 되는 경우는 큰 음수 2개를 더했을 때 sign bit값이 더해져서 sign bit가 0이 되어 버린다.

BCD Adder
binary sum과 BCD Sum을 관찰해보면 10부터 BCD값이 binary 값에 6을 더한 값으로 표시된다. 이를 회로로 나타내기 위해 10이상을 나타내는 규칙을 찾아 6을 더하는 회로를 만들면 된다.

Binary multiplier
보통 손으로 곱하기 하는 것과 똑같은 방식. K bit 곱하기 J bit는 J*K개의 AND gate와 J-1개의 K-bit adder로 그릴 수 있다. 결과는 J+K bit이다.

Magnitude comparator
A, B의 크기 비교.
A, B가 같으면 각 비트가 모두 같은 것이다. 따라서 xi = (AiBi + Ai'Bi') 구해서 모두 AND 게이트에 연결시키면 된다.
A >B이면 가장 큰 자리부터 A가 1이고 B가 0 인지 비교하면 된다. 4자리면 A3B3' + x3A2B2' + x3x2A1B1' + x3x2x1A0B0' (xi의 의미는 '같고'이다.)
A<B도 A>B이랑 비슷한 방식으로 하면 된다.

Decoders
n bit의 입력을 통해서 2^n 개의 결과 중 하나만 1이 나오도록 하는 회로. 여러개 입력하고 출력은 하나만 1이 나온다.
n-to-2^n line decoder라고 적는다.

decorder로 boolean function 표현할 수 있다.
boolean function은 sum of minterms로 표시할 수 있다. minterm들은 decorder의 출력으로 표현할 수 있다. 그리고 logical sum역할을 하는 외부 OR gate가 있으면 minterms의 합을 표현할 수 있다.

Encoders
디코더의 반대. 입력 2^n개, 출력 n개.
입력 2^n개 중에 하나가 1이 된다. 
OR gates로 출력 n을 표현할 수 있다.

priority encoder
2개 이상의 input이 동시에 1일 때 가장 높은 우선순위의 input이 우선권을 가지는 encoder.

Multiplexers
input 중에 하나를 선택하고 그 값이 output에 연결되는 것.
입력라인, OR gate 없애면 decoder랑 똑같다.
따라서 multiplexer로도 boolean function 만들 수 있다.
효과적으로 boolean function을 표현할 수 있는 방법: n variable boolean function을 n-1 selection input을 가지는 멀티플렉서로 표현 할 수 있다.

 

순환문제

문제푸는 방법
1. substitution method
결론을 가정하고 수학적귀납법을 써서 가정이 참임을 보이는 것.
2. Recursion-tree method
3. Master method

 

process
실행중인 프로그램.
포함하는 것 :
프로그램 코드, 현재상태(PC, 레지스터값), 스택(함수 파라미터, return address, 지역변수), 데이터섹션(전역변수) 
 
프로세스 상태
new(프로세스가 생성되었을 때), running(실행중일 때), waiting(I/O 처리같은 어떤 이벤트가 끝나기를 기다리는 것) ready(실행되기를 기다림. new에서나 waiting 상태에서 ready로 가겠죠.), terminated(프로그램 실행이 끝남)

PCB(Process Control Block)
OS에서 프로세스들을 관리하기 위해 사용하는 자료구조
구성요소
프로세스 상태, Program Counter, CPU registers, CPU 스케쥴링 정보(우선순위, 스케쥴링 큐를 가리키는 포인터 등), 메모리 관리 정보(value of base and limit registers, page table, segment table), 할당된 I/O 장치 리스트, 연 파일 리스트 등.
PCB는 프로세스간 스위칭 할 때 주로 사용한다.

Process Scheduling Queues
OS가 프로세스들을 관리하기 위해 사용하는 큐

종류
Job queue : running중인 모든 프로세스
Ready queue : 상태가 ready인 프로세스 리스트, 큐 헤더가 첫번째, 마지막 PCB 포인터다.
Device queues :  상태가 waiting인 프로세스들. 장치마다 그 장치 사용을 기다리는 큐가 있네.

Context Switch
CPU가 다른 프로세스를 처리하려고 할 때 발생. 기존 프로세스 PCB를 메모리에 저장하고 새로운 프로세스 PCB에서 값을 불러올 때 그 시간 동안 아무일도 못하는 상황. overhead라고 한다.
그래서 이 overhead가 OS성능에 영향을 미친다. 하드웨어 성능 좋으면 빨라지겠고 자주 일어날수록 느려지겠지.

프로세스 생성
부모 프로세스가 자식 프로세스들을 생성한다.
자식 프로세스는 OS로부터 자원을 얻을 수 있고, 또한 부모 자원을 공유할 수 있다.
자식 프로세스가 실행될 때 어떤 부모는 자식이 제 할 일 다하고 끝나기를 기다리고 어떤 부모는 자식이랑 동시에 일을 한다.
자식 프로세스는 부모의 주소공간의 복사값을 가지고 그 공간에 프로그램을 불러온다. 리눅스에서 fork함수가 자식프로세스를 생성하는 거고, exec 함수가 호출되면 자식프로그램이 실행되는 거다. 따라서 exec함수가 실행되기 전까지는 부모프로세스의 복사값을 가지고 있겠지.

Swapper and Init processes
Process 0 (swapper)
Process 1 (init) : 초기화 프로그램이다. 부팅될 때 생성되는 첫번째 user process. 모든 user process의 1대조상. 자식있는 부모가 종료되면 자식은 미아가 되는데 init이 관리 해줌. 
process 2 (pagedaemon) : free memory pool 유지.

프로세스 종료 2가지 경우
정상적인 종료 : 자기 할일 다 했을 때, OS에게 끝내달라고 요청하고 OS는 프로세스에 할당된 자원을 해제한다.
비정상적인 종료 : 다른 프로세스를 죽일 수 있다. SIGKILL 같은 걸로.

프로세스간 협력
실행중인 프로세스들끼리 서로 영향을 끼칠 수 있다.
같이 함으로써 자원을 공유할 수 있고, 계산을 나눠서 해서 빨라질 수 있는 등의 장점이 있다.
프로세스간 어떤식으로 커뮤니케이션을 할 것이고 공유데이터를 어떻게 처리할 것인지에 대한 문제를 생각해볼 수 있다.
예로 Producer-Consumer problem이 있다. producer는 정보를 생산하며 consumer는 정보를 소비한다. 이 두 프로세스는buffer를 통해 커뮤니케이션을 하고 자원을 공유한다. producer나 consumer가 정보를 너무 빨리 생산하거나 소비하면 정보가 꽉 차거나 텅 비게 되는 경우도 발생할 것이다. 서로 이 경우를 알아차리고 기다리게 될 것이다.

Direct/Indirect communication.
커뮤니케이션 방법.
Direct
프로세스들이 서로 이름을 지정해서 메시지를 주고 받는 방식. 채팅처럼 양방향이 될 수도 있고 무전처럼 단방향이 될 수도 있다.
Indirect
메일박스를 통해 메시지를 주고 받는다. 여러 프로세스가 같은 메일박스를 공유하면 서로 메시지를 주고 받을 수 있다. direct는 두 프로세스가 메시지를 주고 받는 반면, 얘는 많은 프로세스와 통신할 수 있다.

Synchronization
메시지가 전달되는 방식은 blocking 또는 nonblocking 이다.
blocking은 synchronization, non-blocking은 asynchronous

Buffering
큐 사이즈가 0이면 Sender는 receiver가 일을 처리할 때까지 기다려야 한다.
큐 사이즈가 메시지를 몇개 받을 수 있으면 sender는 만약 큐가 다 찼을 경우에 기다린다.
큐 사이즈가 무한이면 sender는 기다릴 필요가 없다.