본문 바로가기

IT 이론236

소켓의 다양한 옵션 소켓은 그냥 정해진 함수 3~4개만 쓰면 사용 할 수 있는 편한 것이라고들 인식하지만, 사실 더 깊게 들어가면 정말 다양한 옵션들이 있다. 일반적으로 간단한 데이터 송수신 정도의 프로그래밍에서는 아무것도 건들일 필요 없이 그대로 쓰면 되지만 점점 고급 프로그래밍을 하게 되면 그 특성에 맞기 옵션들을 조작 해 줘야 한다. (조작 안해도 사용 할 수 있지만 조작 해 주면 더 좋은 성능이 나고, 프로그래밍하기도 편해진다.) 소켓의 옵션은 아.주. 많지만 일단 자주 사용되는 몇 가지만 뽑아 보자면 아래와 같다. Protocol Level Option Name 설명 Get Set SOL_SOCKET SO_SNDBUF SO_RCVBUF SO_REUSEADDR SO_KEEPALIVE SO_BROADCAST SO_OO.. 2013. 6. 15.

File System Implement 하드디스크는 page array이다. 메모리와 연관지어서 생각하면 된다. 프로세스를 메모리상에 allocation 하는것과 파일을 디스크에 allocation 하는것은 같은 원리이다. Memory에서는 contiguous allocation 방식이 있었고 non-contiguous인 paging방식이 있다. 하드디스크도 똑같다. 하드디스크엔 추가적으로 한개 더 있다. fopen함수를 쓰면 파일 포인터를 return한다. 이 포인터는 OS에서 정의하는 파일 table의 인덱스정보이다. 파일을 read할땐 실제로는 두개의 자료구조가 열린다. per-process open-file table, system-wide open file table. 일단 system-wide open file table이 한개 열.. 2013. 6. 12.

가상 메모리(Virtual Memory) 이론 및 페이지교체 알고리즘 Virtual Memory 주기억장치의 부족한 physical memory를 보조기억장치를 이용해서 가상으로 늘려 준다. Demand Paging 어떤 것을 하드에 두고 어떤 것을 실제 메모리에 올릴 것인가를 판단하는 기준이다. 여러가지가 있지만 일반적으로 사용되는것이 demand paging이므로 이에 대해서만 설명한다. demand paging은 말 그대로, 어떤 알고리즘에 따라서 미리 올려 두는 것이 아니라 실제 사용되려고 할때(demand 되었을때) 메모리에 올리는 방식을 말한다. 어떻게 보면 무척이나 당연한 이야기이다. 이 방식은 아래와 같은 장점이 있다. Less I/O needed Less memory needed Faster response More users Virtual memory는 .. 2013. 6. 12.

Banker's Algorithm cf. Detection Algorithm Deadlock Avoidance는 거의 뱅커스 알고리즘이 다라고 보면 된다. 이름에서도 알 수 있듯이, 리소스 할당을 돈을 빌려주고 갚은 은행의 업무에 비유하여 고안된 알고리즘이다. 간단하게 예를 들어, 은행에 돈이 1000만원 있다. 그리고 3명의 고객이 은행에서 돈을 빌린다. 은행은 고객이 원하는 돈을 다 빌려 주면 바로 반환 받을 수 있다. 하지만 돈을 다 빌려주기 전까지는 강제로 반환받지 못한다. - 고객1이 총 600만원을 빌리고자 한다. - 고객2이 총 800만원을 빌리고자 한다. - 고객3이 총 400만원을 빌리고자 한다. 지금 현재 상태는 safe하다. 1-2-3, 1-3-2, 2-3-1 등등 모든 경우가 다 가능하다. 한꺼번에 필요한 돈을 다 빌려주고 다시 받은 후 다음 고객에게 빌려주.. 2013. 6. 11.

Briefly compare the two heap-construction algorithms Make heap : bottom up, O(n), off-line algorithm, heapsort에 유용 Heap insert : top-down, O(nlogn), on-line algorithm, priority queue에 유용 Make heap은 shift_down을 사용하고 Heap insert(construct heap)은 insert_hep을 사용한다. shift_down은 구성된 ECBT에서 하위 서브트리부터 순서를 재조정하여 Heap을 구성하는 함수이고, insert_heap은 ECBT를 구성 해 가며 노드를 하나씩 추가해 나가는 것이다. sorting을 목적으로 할 경우 Make heap은 주어진 키값으로 ECBT를 구성 해 놓은 후 순서를 맞추기 때문에 새로운 값이 갑자기 추가되.. 2013. 6. 6.

Branch and bound, BFS 0/1 Knapsack Knapsack 알고리즘이란, 무게(크기)가 한정된 가방이 있고, 넣을 수 있는 물건의 무게(크기)와 가격이 정해져 있을 때 어떤 물건을 버리고 어떤 물건을 넣어야 최대한의 이익을 얻을 수 있는가를 구하는 알고리즘이다. Branch and Bound에 대해서는 TSP에서 설명 했으므로 바로 문제를 풀어보자. 목적에 따라 bound를 구하는 방법만 다를 뿐 다 같은 맥락이다. 1. W = 11 i pi wi pi/wi 1 20 2 10 2 21 3 7 3 12 2 6 4 35 7 5 input 값는 이런 식으로 주어진다. pi는 물건 i에 대한 profit, wi는 weight, pi/wi는 단위무게당 profit이다. 이 input은 pi/wi이 큰 순서대로 sorting되어 들어오며, sorting되지.. 2013. 6. 6.

Deadlock의 발생 조건과 해결법 데드락이 무엇인가? 두개 이상의 프로세스가 서로의 작업이 끝나기만을 기다리고 있어 둘다 영원히 끝나지 않는 상황을 가리킨다. (A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set) 예를 들어서 semaphores A and B, initialized to 1 Process1 Deadlock Process2 wait(A); wait(B); wait(B); wait(A); 데드락은 어떨 때 일어나나? 아래 4가지 조건이 모두 만족하면 데드락이 발생할 가능성이 있다. 하나라도 만족하지 않으면 절대 발생하지 않는다. Mutual exclusion : .. 2013. 5. 30.

Branch and bound 기법을 이용한 TSP Branch(가지)와 Bound(범위) 기법이란 "최적의 경우"를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다' 라는 범위(Bound)를 정 해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다. 이 알고리즘으로 풀 수 있는 문제는 대표적으로 Knapsack과 TSP가 있는데, 인터넷에 있는 예제들은 대부분 Knapsack에 관한 예제이므로, 여기선 TSP를 풀어 보도록 하자. 0 5 2 4 1 6 0 5 4 3 2 3 0 4 5 2 3 4 0 1 4 2 1 3 0 위와 같은 input이 있다. 그래프는 그리지 않겠다. 이번 알고리즘은 확실히 Matrix로 보는게 더 편하다. 매트릭스를 어떻게 보는지 모르는 분들을 위해 간단하게 설명 드리자면 (1, 1),.. 2013. 5. 28.

[C언어 소스] Backtracking을 이용한 N-Queen 문제 해결법 일단 N-Queen문제가 뭘까? 이 문제의 목적은 잘 모르겠으나 알고리즘을 공부하다 보면 자주 보이는 문제이다. 이 문제를 푸는 방법도 참 여러가지다. 일단 이 문제는 이름대로 장기판에 여왕말을 놓는 문제인데, 이 여왕말이 다 적이다. 어떤 여왕말이든 다른 여왕말을 먹을 수 있다는 것이다. 하지만 그걸 못 먹도록 하는게 이 문제의 핵심이다. 즉, 모든 여왕말이 다른 여왕말이 바로 공격할 수 있는 거리에 있는 것이다. 그 말인 즉슨 어떤 여왕말이 다른 여왕말을 먹으면 그 여왕말은 또 다른 말에게 먹히기 때문에 아무도 움직일 수 없는 상태인 것이다. 예를 들어 4x4의 체스 판에서는 Q Q Q Q 이런 구도라면 어떤 여왕말도 쉽사리 움직 일 수 없다. 그리고 5x5라면 Q Q Q Q Q 이런식의 결과가 나올.. 2013. 5. 26.

Internet transport protocols : TCP and UDP TCP connection-oriented: setup required between client and server processes reliable transport between sending and receiving process flow control: sender won’t overwhelm receiver congestion control: throttle sender when network overloaded does not provide: timing, minimum throughput guarantees, security UDP unreliable data transfer between sending and receiving process does not provide: connecti.. 2013. 4. 17.

인터넷 계층 계층화를 하는 이유 - 크고 복작한 시스템의 잘 정의된 특정 부분을 논의 할 수 있도록 해 준다. (explicit structure allows identification, relationship of complex system’s pieces) - 시스템의 다른 요소들에 영향을 주지 않고 서비스 구현을 변화시킬 수 있도록 해준다. (change of implementation of layer’s service transparent to rest of system) 인터넷 프로토콜 스택 application - transport - network - link - physical 프로토콜 데이터 유닛 message - segment - datagram - frame 인터넷 프로토콜 스택을 하나씩 지나면서.. 2013. 4. 17.

Delay in packet-switched networks dnodal = dproc+ dqueue + trans + dprop 패킷 스위칭에서 한 패킷이 한 노드(호스트 혹은 라우터)에서 다른 노드까지 가는 경로 중 생기는 지연을 "노드 지연(nodal delay)"이라고 한다. 대표적인 delay는 4개가 있다. 1. 처리 지연(processing delay) 패킷의 헤더를 조사하고 그 패킷을 어디로 보낼 것인가 파악 하는데 걸리는 시간. 비트 수준에서의 오류 조사 시간도 포함한다. 2. 큐잉 지연(queuing delay) 링크로 전송되기 전에 큐에서 차례가 올 때 까지 기다리는 시간. queuing delay를 정도를 측정하기 위한 척도로 트래픽 강도(traffic intensity) 가 중요하게 사용된다. 트래픽 강도를 계산하는 공식은 아래와 같다. L.. 2013. 4. 17.

Chainging Coin System 관련 Suppose you are in the wonder land in which the coin changing system is not governed by the greedy strategy. There are only 4 coins cl = 1, c2 = 3, c3 = 7, and c4 = 11 in the country. (a) Construct N[0..21] and P[0..21] for changing 21 wons. (b) Write a recursive program "void print_coins (int x)" to print optimal coins for x wons. You must assume that array P[0..21] is global to this program. (.. 2013. 4. 15.

Operating System A computer system can be divided into four components Hardware, Operating System, Application Program, Users(People, machine, other computer) 기본적인 3가지 Process Management Memnory Management Storage Management 정의 OS is resource allocator OS is control program No universally accepted definition 특징 1. I/O devices and the CPU can execute concurrently. I/O CPU는 같이 실행 될 수 있다. 2. Each device controller .. 2013. 4. 12.

여러가지 관계해석식 표현법과 예제 *관계 대수와의 비교 관계 대수식은 절차적(procedural)인 반면에 관계 해석식은 비절차적이다. 그러나 두 언어의 표현력(expresive power)은 동등하다. 튜플 관계 해석식 셀렉트 연산 : { t | EMPLOYEE(t) and t.SALARY>5000 } 프로젝트 연산 : { t.FNAME, t.LNAME | EMPLOYEE(t) } 셀렉트 + 프로젝트 : { t.FNAME, t.LNAME | EMPLOYEE(t) and t.SALARY > 50000 } Ex1) Research 부서에서 일하는 모든 사원들의 이름과 주소를 검색하라 { e.FNAME, e.LNAME, e.ADDRESS | EMPLOYEE(e) and (∃d) (DEPARTMENT(d) and d.DNAME = ‘Resea.. 2013. 1. 12.

여러가지 관계대수식 표현법과 예제 SELECT 연산 (σ로 표기) σc(R) - 릴레이션 R에서 선택조건 c를 만족하는 튜플들을 선택한다. - 조건 c는 R의 애트리뷰트들에 대한 boolean expression이다. σ DNO=4 (EMPLOYEE) σ SALARY>30000 (EMPLOYEE) σ (DNO=4 AND SALARY>25000) OR DNO=5 (EMPLOYEE) σ (DNO=4 AND SALARY>25000) OR (DNO=5 AND SALARY>30000) (EMPLOYEE) PROJECT 연산 (Π로 표기) Πc(R) - 릴레이션 R에서 애트리뷰트 리스트 L에 명시된 애트리뷰트들만 선택한다. - 결과 릴레이션 L은 수학적 집합이다. => 중복된 튜플들을 제거한다. Π FNAME,LNAME,SALARY (EMPLOYE.. 2013. 1. 12.

[데이터베이스] Super Key, Candidate Key, Primary Key 1. Super Key : 어떤 릴레이션의 어떠한 튜블들도 같은 값을 가지지 않는 Atrribute, 또는 Atrribute 조합 2. Key : 슈퍼키를 수정하는 Attribute 중 하나라도 빠지면 Super Key가 될 수 없는 Super Key (최소 슈퍼키) 3. Candidate key : 모든 Key는 Candidate Key가 될 수 있다. 4. Primary key : Candidate key중 선택된 한개의 기본 키 ex) Car Relation CAR {지역, 번호, 모델 명, 제작 년도, 고유번호} 는 두개의 키를 가진다 {지역, 번호} 와 {고유번호} 이들은 슈퍼키인 동시에 키이고, Primary Key가 될 수 있는 Candidate Key이다. {모델명, 고유번호} 또한 슈퍼키.. 2013. 1. 12.

[데이터베이스] Null값이 의미하는 두 가지 1. Not applicable (해당사항 없음) : 외국인의 한국 주민등록 번호, 내 여자친구의 신상 정보, 고졸자의 학사학위 정보 등 존재하지 않음이 확실한 애트리뷰트 값. 2. Unknown (모름) : Value exists but is missing, It is unown whether the attribute value exist 2-1. 존재하지만 누락 된 경우 : 사람의 키, 몸무게 등 존재하지 않을 수가 없는 것. 2-2. 존재 하는지조차 모름 : 휴대폰 번호, 차번호 등 2013. 1. 12.

이전 1 ··· 9 10 11 12 13 14 다음

티스토리툴바