skyjump's blog

max-heaps 과 min-heaps가 있다.

max-heap
부모 노드 값이 항상 같거나 크다. A[Parent(i)] >= A[i]
루트 노드는 최대값이다.
subtree의 루트노드는 그 subtree의 최대값이다.

min-heap
부모노드값이 항상 작거나 같다.
루트노드는 최소값이다.

힙은 배열에 저장할 수 있다.
배열 A[1]에 루트노드가 저장되고 A[2]부터 레벨순으로 왼쪽에서 오른쪽으로 차례대로 배열에 저장된다.
배열에서 노드의 부모값과 자식값을 알 수 있는 방법
Parent(i) = floor(i/2)
left(i) = 2i
right(i) = 2i+1

heap의 높이
각 레벨의 노드 갯수 ; 1, 2, 4, 8 ..... 2^(n-1)
k레벨일 때까지 등비수열 합을 해주면 총 노드 갯수 n = 2^k -1
k = lg(n+1) 따라서 높이 h = θ(lgn)

Maintaining the heap property

Max-Heapify
노드의 왼쪽 오른쪽 서브트리가 max heap인데 정작 노드는 자식노드보다 작을 때 부모는 자식보다 크다는 max heap 속성을 어기므로 만족할때까지 밑으로 내린다. 내려가는 횟수는 아무리 많아도 트리의 높이보다 작다. O(h) = O(lg n)
 
Building a heap
자식을 가진 맨 아래 오른쪽에 있는 노드부터 시작해서 Max-heapify 해준다. (밑에서부터 힙이 이루어지도록 한다.) 다음 max-heapify 해줄 노드 방향은 오른쪽 -> 왼쪽, 아래 -> 위다.
위에서부터 밑으로 내려가는 방식은 힙이라는 것을 보증하지 못하기 때문에 힙이 안만들어 질 수도 있다.

Running time
Upper bound는 Max-HEAPIFY가 O(lg n)이므로 노드 O(n)개에 대해 수행하면 O(nlg n) 이 된다.
Thighter bound를 살펴보면 트리의 아래쪽에 있는 노드는 lg n보다 적은 시간이 들고 이러한 아래에 있는 노드들이 많으므로 tighter bound는 Upper bound 보다 작다. 계산하면 O(n)이 된다. linear time으로 기존의 배열을 힙으로 만들 수 있다.

max힙에서 n번 최대값을 뽑는 비용은? (Heap sort)
O(nlgn)
루트가 최대값이므로 그 값을 뽑고 루트 자리에 가장 낮은 노드를 넣어서 max heapify 한다. 그래서 n-1번 동안 O(lgn) 이므로 O(nlgn)

Priority queue
우선순위 개념을 큐에 도입한 자료 구조. 데이터가 우선순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 힙으로 구현할 수 있다.
최대값을 읽는 것은 O(1)이고 읽고 지우는 것은 지우고 나서 Max heapify가 사용되므로 O(lg n)
노드의 키값을 증가시킬때, 바꾼 값이 힙을 깨뜨릴 가능성이 있다. 힙을 유지하기 위해 위로 올라가면서 자기자리를 찾는다. 기껏 올라가봤자 트리 높이 보다 작다. O(lg n)
노드를 삽입할 때는 힙의 맨 마지막에 넣고 힙을 유지하기 위해 노드를 위로 올리면서 자기자리를 찾는다. 이것도 O(lg n)

1) User threads
user-level의 thread library에 의해 관리된다.
커널로부터 지원이 없다.
장점
쓰레드간 전환할 때 커널 스케쥴러를 호출할 필요가 없기 때문에 빠르다. 커널 스케쥴러를 호출함은 유저모드에서 커널모드로 들어가는 것을 의미한다. 이는 레지스터 교환 등 많은 작업이 일어나게 되므로 느려진다.
단점
한 쓰레드가 system call등을 호출해서 커널로 진입할 때 그 프로세스의 다른 쓰레드도 모두 정지된다. 커널이 쓰레드의 존재를 알지 못하기 때문이다. 

2) Kernel threads

커널에서 사용하는 쓰레드.
장점
쓰레드 단위로 스케쥴링이 되므로 멀티프로세서를 활용할 수 있다.
단점
kernel level에서 동작하기 때문에, user level 쓰레드보다 느리다.

Multithreading Models

1) M-to-one
커널쓰레드 하나에 많은 유저쓰레드
쓰레드 하나가 blocking 당하면 나머지 쓰레드도 blocking.
한번에 한 유저쓰레드만 커널쓰레드에 접근 가능하다.

2) One-to-one
커널쓰레드 하나에 유저쓰레드 하나.
멀티프로세서에 병렬적으로 처리가 가능하다.
커널쓰레드를 만드는데 드는 오버헤드는 프로그램의 성능에 안좋은 영향을 줄 수 있다.

3) Many-to-Many
많은 커널쓰레드에 많은 유저쓰레드가 매핑됨.

참고사이트 : http://kldp.org/node/295/  유명한 곳인 듯

 
1. Thread Issue

한 쓰레드에서 fork 호출 할때, 새로운 프로세스는 부모의 모든 쓰레드를 복사할 것인가, 그 쓰레드 하나만 복사할 것인가?
exec()가 바로 호출되면 모든 쓰레드 복사가 필요없을 것이고 exec()가 바로 호출되지 않으면 필요할 것이다.

2. Thread Issue - signal

Unix 시스템에서 사용되고 프로세스에게 특정한 이벤트가 발생했다고 통보한다.
signal 처리
Default action
프로세스가 시그널처리 핸들러가 없을 경우 커널에 의해 처리
core dump(메모리, 레지스터 값을 알려주고) 종료되는 경우 (Abort), 그냥 종료되는 경우(exit), 무시하는 경우(ignore), 프로세스를 정지하는 경우(stop), 정지되었을 경우 재개하는 경우(continue)가 있다.

시그널 핸들러가 있는 경우
스그널을 받으면 핸들러에 따라 처리.
신호를 블락할 수 있다.
그러나 SIGKILL이나 SIGSTOP은 핸들러 처리나 블락 못하고 받아들어야 한다.

한 프로세스에 쓰레드가 여러개 있을 경우 시그널이 어디로 전달되어야 하나 ?
1. 시그널이 적용되는 스레드에게 전달(예 : 동기적 시그널)
2. 모든 스레드에게 전달 (예 : ctrl-c)
3. 프로세스의 특정 스레드에게 전달. 어떤 스레드는 block할 수 있고 어떤 스레드는 accept할 수 있다.
4. 모든 시그널을 받는 지정된 스레드에게 전달.

3. Threading issues - Thread Pool

프로세스 시작시에 쓰레드 미리 생성해서 pool에다가 보관하다가

프로세스가 요청하면 전달한다.
쓰레드가 종료되면 다시 pool로 복귀.
미리 생성해놔서 더 빠르다.
쓰레드 수 제한이 가능해진다. 많은 수의 쓰레드를 동시에 처리하지 못하는 시스템에게는 좋겠지.

4. Threading Issues - Stack overflow

User thread의 스택이 overflow가 날 경우 커널은 알지 못한다.
커널이 protection fault를 감지하고 SIGGEGV 시그널을 해당 프로세스에게 보낸다. 

public Thread(ThreadGroup group, Runnable target)

public Thread(ThreadGroup group, String name)

public Thread(ThreadGroup group, Runnable target, String name)
지정 안하면 default 그룹이 됨.
자기가 속한 그룹 찾기
theGroup = myThread.getThreadGroup();

The ThreadGroup Class

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

▶ 쓰레드그룹은 쓰레드를 많이 가질 수 있고, 또한 쓰레드그룹도 가질 수 있다. 
쓰레드그룹은 쓰레드를 관리할 수 있고, 그 그룹에 속한 객체가 자신의 쓰레드그룹의 정보를 알 수 있다. ex) activeCount(), enumerate()
▶ 쓰레드그룹은 그룹레벨에서 유효한 속성 값을 지정하거나 참조할 수 있다. 예를 들면 그룹 속성을 지정할 때 이미 그룹안에 있던 쓰레드들은 영향을 받지 않는다. 새로 들어오는 애들은 영향을 받지만. 예를 들면 setMaxPriority() 함수는 쓰레드나 쓰레드그룹에서 최대로 가질 수 있는 우선순위를 매기는 함수이다. 쓰레드그룹이 setMaxPriority(5)를 하면 그 안에 있는 개별 쓰레드나 개별 그룹이 가질 수 있는 최대 우선순위는 5이다. 하지만 기존에 있던 개별 쓰레드는 자기의 우선순위를 그대로 유지한다. 10이었으면 5로 안바뀌고 10이다. 하지만 새로 들어오는 쓰레드는 영향을 받는다. 그리고 하위 그룹쓰레드의 경우에는 미리 들어와 있던 새로 들어오던 상관없이 부모의 최대우선순위를 준수했다.
▶ 쓰레드그룹은 자기 그룹내에서는 접근제한이 없지만 다른 그룹끼리 정보를 참조 하거나 수정하는 것에는 접근제한이 있다. checkAccess 함수를 이용하여 접근할 수 있는지 없는지 알 수 있다.

Synchronizing Threads
쓰레드들이 데이터를 공유할 경우. 이 데이터들은 동기화 되어야 한다.
Producer/Consumer 문제
producer가 물건을 생산하고 consumer가 그 물건을 소비한다고 할 때, producer와 consumer는 번갈아가면서 물건을 생산 소비 하는 문제. 동기화가 안될 경우 producer나 consumer가 연달아 두 번이상 실행될 경우가 발생한다. 

Race conditions
비동기로 실행되는 쓰레드들이 한 자원에 동시에 접근해서 잘못된 결과를 내는 것.

Monitors
두 쓰레드가 한 자원을 공유할 경우 그 자원의 접근은 반드시 동기화를 해야 하며 이 자원을 condition variable이라 부른다. 자바 랭귀지는 monitors를 사용해서 쓰레드가 condition variable의 동기화 접근을 가능하게 한다.

notify(), wait()함수를 사용해서 producer, consumer가 번갈아 한번씩 물건에 접근하게 한다.

Critical sections
두 쓰레드가 동시에 같은 자원에 접근할 가능성이 있는 코드
자바랭귀지에서는 Critical sections에 synchronized 키워드를 써서 동시 접근을 막는다.
자바에서는 주로 method 에 synchronized를 붙인다. 일부분에도 붙일 수 있으나 객체지향적인 관점에서 프로그램을 유지보수하기가 어렵다고 한다.
쓰레드가 synchronized 함수에 접근할 때 그 쓰레드는 그 객체의 monitor를 얻어서 다른 쓰레드가 그 객체의 synchronized함수를 호출 하는 것을 막는다.
monitor의 획득과 반납은 Java runtime system에 의해 자동으로 이루어 진다.

notify() method
notify() 함수가 호출되면 객체의 모니터를 획득하기 위해 기다리고 있는 쓰레드들 중 하나를 선택하여 모니터를 준다. 모니터를 객체에 접근할 수 있는 허가증이라고 보자.
기다리는 쓰레드가 여러개 있을 때 어떤 객체에게 모니터를 줄것인가는 모른다. Java runtime system 마음이다.
notifyAll()은 기다리고 있는 쓰레드 모두에게 모니터를 얻을 자격을 주는 것이다. 경쟁해서 한놈이 모니터를 갖고 나머지는 다시 기다려야 한다.

wait() method
현재 쓰레드가 wait() method를 호출하면 다른 쓰레드가 notify를 할 때까지 기다린다.
wait()와 notify()을 같이 사용함으로써 자원을 공유하는 쓰레드문제를 처리할 수 있다.

Monitors and the notify() and wait() methods.
현재 쓰레드가 wait() 함수가 호출 될 때 다른 쓰레드가 synchronized 함수에 들어갈 수 있도록 monitor를 내놓는다. 그래서 notify 받으면 다시 모니터를 획득한다.


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