'2011/06'에 해당되는 글 27건

  1. 2011.06.30 Heapsort 1
  2. 2011.06.30 Multithreaded Programming
  3. 2011.06.30 7장 아키텍쳐 (architecture)
  4. 2011.06.30 Thread
  5. 2011.06.29 6장 큰문제 해결하기
  6. 2011.06.28 4장 Combinational Logic
  7. 2011.06.28 4 Recursion
  8. 2011.06.28 Process Concept
  9. 2011.06.28 5장 좋은디자인 = 유연한 소프트웨어
  10. 2011.06.26 Inverse Matrices
공부/알고리즘2011. 6. 30. 18:58


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

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

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

힙의 종류
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)

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011.07.03
7장 Quicksort  (0) 2011.07.03
4 Recursion  (0) 2011.06.28
3장 Growth of Funtions  (0) 2011.06.24
2장 insertion sort, merge sort, binary search, selection sort, bubble sort  (1) 2011.06.23


Posted by skyjumps
공부/운영체제2011. 6. 30. 16:27


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
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 시그널을 해당 프로세스에게 보낸다. 

'공부 > 운영체제' 카테고리의 다른 글

6장 Synchronization  (0) 2011.07.04
Process scheduling  (0) 2011.07.03
Process Concept  (0) 2011.06.28
2장 System Structures  (0) 2011.06.25
1장 Introduction  (0) 2011.06.24


Posted by skyjumps
공부/객체지향2011. 6. 30. 12:05


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

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

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

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

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

'공부 > 객체지향' 카테고리의 다른 글

9장 반복하기, 테스팅하기  (0) 2011.07.03
8장 디자인 원리들  (0) 2011.07.02
6장 큰문제 해결하기  (0) 2011.06.29
5장 좋은디자인 = 유연한 소프트웨어  (0) 2011.06.28
4장 분석  (0) 2011.06.26


Posted by skyjumps
공부/JAVA2011. 6. 30. 02:48


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
쓰레드를 묶어서 한번에 처리.
처음에 쓰레드 생성할 때 그룹을 지정.
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


Posted by skyjumps
공부/객체지향2011. 6. 29. 11:46


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

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

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

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


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

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

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

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

 

'공부 > 객체지향' 카테고리의 다른 글

8장 디자인 원리들  (0) 2011.07.02
7장 아키텍쳐 (architecture)  (0) 2011.06.30
5장 좋은디자인 = 유연한 소프트웨어  (0) 2011.06.28
4장 분석  (0) 2011.06.26
3 요구사항 변경  (0) 2011.06.25


Posted by skyjumps
공부/논리설계2011. 6. 28. 23:54


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을 가지는 멀티플렉서로 표현 할 수 있다.

 

'공부 > 논리설계' 카테고리의 다른 글

3장 Gate-Level Minimization  (0) 2011.06.26
2장 Boolean Algebra and Logic gate  (0) 2011.06.24
1장 Binary Systems  (0) 2011.06.22


Posted by skyjumps
공부/알고리즘2011. 6. 28. 21:59


순환문제

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

 

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011.07.03
7장 Quicksort  (0) 2011.07.03
Heapsort  (1) 2011.06.30
3장 Growth of Funtions  (0) 2011.06.24
2장 insertion sort, merge sort, binary search, selection sort, bubble sort  (1) 2011.06.23


Posted by skyjumps
공부/운영체제2011. 6. 28. 21:26


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는 기다릴 필요가 없다.

 

'공부 > 운영체제' 카테고리의 다른 글

6장 Synchronization  (0) 2011.07.04
Process scheduling  (0) 2011.07.03
Multithreaded Programming  (0) 2011.06.30
2장 System Structures  (0) 2011.06.25
1장 Introduction  (0) 2011.06.24


Posted by skyjumps
공부/객체지향2011. 6. 28. 13:14


추상클래스
실제 구현 클래스를 위한 저장장소
추상클래스는 기능을 정의하고 서브클래스는 기능을 구현한다.

클래스의 공통적인 요소를 묶기 위해 추상클래스를 사용할 수 있다.

UML
1. Aggregation(집합) - 연관(Association)의 특별한 형태, 어떤 것이 다른 것으로 구성되어 있음을 의미.
출처 : byteonic.com

2. association(연관)
출처 : mscs.mu.edu

3. generalization(일반화)
출처 : jot.fm


객체지향의 원리

1. 인터페이스
클래스 FootballPlayer, BaseballPlayer가 인터페이스 Athlete를 상속할 때 이들 클래스와 상호작용하는 코드를 만들때 FootballPlayer, BaseballPlayer와 직접 상호작용하는 것 보다는 Athlete 인터페이스와 상호작용하는 것이 좋다. 항상 구현이 아니라 인터페이스에 따라 코딩하도록 해야 한다.
이게 왜 중요하냐면 프로그램이 유연해지기 때문이다. 인터페이스와 상호작용하는 코드를 만들면 새로운 클래스 예를 들면BasketballPlayer와도 잘 동작하게 될 것이다.

2. 캡슐화
클래스를 불필요한 변경으로부터 보호한다.
변경하는 것을 캡슐화 한다. 즉, 변화의 가능성이 낮다고 생각하는 부분과 많다고 생각하는 부분을 따로 때어낸다.

3. 변경
소프트웨어는 변하기 때문에 좋은 소프트웨어는 쉽게 변경될 수 있어야 한다. 변경에 잘 견딜 수 있는 프로그램을 만들 수 있는 방법 중 하나는 각 클래스가 변경의 이유를 하나만 갖도록 하는 것이다. 즉, 각 클래스가 하나의 일만을 하도록 해야 한다.

디자인의 오류 발견하기
디자인은 반복적으로 진행되며, 남의 디자인뿐만아니라 자신의 디자인도 기꺼이 변경해야 한다.
자존심은 좋은 디자인에 방해된다.

변하는 것을 볼 때마다, 캡슐화할 방법을 찾아야 함.
객체들 사이에 변하는 속성들이 있을 때, map 같은 콜렉션을 사용하서 속성들을 동적으로 저장하기. 그래서 새로운 속성들이 추가되어도 메소드를 추가하거나 코드를 변경할 필요가 없다.

보통 행동이 변할 때 서브클래스를 사용한다.

대부분의 좋은디자인은 나쁜디자인의 분석을 통해 나온다.
실수하는 것과 변경하는 것을 두려워하지 말기.

응집도
 

응집도는 하나의 클래스를 이루는 원소들 사이에 연결의 정도.
응집도가 높은 클래스는 특정한 일에 집중하고 그 외의 일은 하려고 하지 않는다.
모든 클래스는 하나의 일을 위해 존재해야 한다.
응집도가 높을 수록 클래스끼리는 더 느슨해 진다. 즉 변경이 쉬워진다.
변경뿐만 아니라 재사용도 쉽다. 객체들이 서로 의존하지 않기 때문에. 

'공부 > 객체지향' 카테고리의 다른 글

7장 아키텍쳐 (architecture)  (0) 2011.06.30
6장 큰문제 해결하기  (0) 2011.06.29
4장 분석  (0) 2011.06.26
3 요구사항 변경  (0) 2011.06.25
2장 요구사항 수집 (유스케이스)  (0) 2011.06.24


Posted by skyjumps
공부/선형대수2011. 6. 26. 23:16


Block multiplication
묶어서 곱하는 경우. 묶은 걸 요소하나로 보면 요소 하나 일때 곱셈이랑 같다. 자세한건 위키 참고.

출처 : 위키피디아 

Block matrix multiplication

A block partitioned matrix product can be formed involving operations only on the submatrices. Given an (m \times p) matrix \mathbf{A} with q row partitions and s column partitions


\mathbf{A} = \begin{bmatrix}
\mathbf{A}_{11} & \mathbf{A}_{12} & \cdots &\mathbf{A}_{1s}\\
\mathbf{A}_{21} & \mathbf{A}_{22} & \cdots &\mathbf{A}_{2s}\\
\vdots          & \vdots          & \ddots &\vdots \\
\mathbf{A}_{q1} & \mathbf{A}_{q2} & \cdots &\mathbf{A}_{qs}\end{bmatrix}

and a (p\times n) matrix \mathbf{B} with s row partitions and r column partitions


\mathbf{B} = \begin{bmatrix}
\mathbf{B}_{11} & \mathbf{B}_{12} & \cdots &\mathbf{B}_{1r}\\
\mathbf{B}_{21} & \mathbf{B}_{22} & \cdots &\mathbf{B}_{2r}\\
\vdots          & \vdots          & \ddots &\vdots \\
\mathbf{B}_{s1} & \mathbf{B}_{s2} & \cdots &\mathbf{B}_{sr}\end{bmatrix},

the matrix product


\mathbf{C}=\mathbf{A}\mathbf{B}

can be formed blockwise, yielding \mathbf{C} as an (m\times n) matrix with q row partitions and r column partitions. The matrices in your matrix \mathbf{C} are calculated by multiplying while you multiply:


\mathbf{C}_{\alpha \beta} = \sum^s_{\gamma=1}\mathbf{A}_{\alpha \gamma}\mathbf{B}_{\gamma \beta}.

 
Inverse = non singular
No Inverse = singular

즉, 역행렬을 가지면 정상이고 못가지면 이상한거란다. 무슨 기준이지?ㅋㅋ
아무튼 역행렬을 못가지는 행렬이 있다.
어떨때 못가질까? 첫번째는 고딩때 배웠던 determinant를 이용하는 것. 2x2일 때 ad-bc = 0 이면 역행렬이 없다.
두번째는 A 가 (a11, a12, a21, a22)가 (1,3,2,6)이라고 하자. determinant로는 0이 나오므로 역행렬을 못가진다. 진짜 그럴까?
얘가 역행렬을 가진다고 치자. 그러면 Ax = I 인 x가 있을 것이다. 자, column 벡터를 생각해보자. (1,3)이랑 (2,6) 벡터로 (1,0)이나 (0,1)을 표현할 수 있나? 없다. 따라서 A는 역행렬이 없다. column 벡터를 보면 역행렬을 왜 가질 수 없는지 알 수 있다.
마지막 세번째는 Ax = 0 에서 0이 아닌 vector x가 있으면 A는 역행렬을 못가진다. 이유는 뭘까? A의 역행렬을 가진다고 쳐보자. 그럼 Ax = 0 에서 양변에 A^-1 해주면 x = 0이다. 0이 아닌 벡터 x가 있다고 했는데 0이 나와버렸으니 모순이다.

The Gauss-Jordan Method
역행렬을 구하는 방법이다.
가우스 조단 방법을 모른다고 하고 2x2 역행렬을 구한다고 하면
AA^-1 = I 여기서 A^-1을 (a,b,c,d)로 놓고 A에서 A^-1의 각 컬럼을 곱하면 
식이 두개가 나온다. 하나는 결과가 (1,0) ,나머지는 (0,1)인 행렬식 두개. 두 식으로부터 역행렬을 구할 수 있다.
여기서 가우스 조단 방법은 두 식을 한번에 계산해버리는 거다.
일반화하면 가우스 조단 방법은 nxn 역행렬을 구할 때 n개 식을 한번에 하는 것임.
가우스 조단 방법을 적용하면 [A I] 가 [I A^-1]로 변하고 따라서 A^-1를 구할 수 있다. 즉, A를 I로 만들어주면 I는 A^-1가 된다. 그런데 왜 I가 A의 역행렬이 될까?
E[A I] -> [I ??]
A에 E를 곱하여 I가 되었다. 따라서 E는 A의 역행렬이다. '??'는 E에 I를 곱한 값이고 E x I = E다. 따라서 '??'는 A의 역행렬.
여기서 앞에서 배웠던 블럭 곱하기가 사용된 걸 체크! [A I]는 A와 I로 파티션이 나누어져 있다.

'공부 > 선형대수' 카테고리의 다른 글

Elimination with Matrices  (1) 2011.06.24
1장 Matrices and Gaussian Elimination (1)  (0) 2011.06.22


Posted by skyjumps