Brute force Study

Hard Disk InternalsMoving head disk mechanism아래 내용은 참고 트랙(track): 디스크 표면에서의 원형 경로스핀들(spindle): 디스크를 회전시키는 중심축섹터(sector): 트랙을 나눈 작은 저장 단위실린더(cylinder): 동일한 위치의 모든 트랙표면(surface): 플래터의 저장 공간플래터(platter): 회전하는 디스크헤드(head): 데이터를 읽고 쓰는 장치회전(rotation): 디스크의 회전 운동Disk I/O service time디스크 I/O 서비스 시간: 탐색 시간 + 회전 지연 + 데이터 전송 시간탐색 시간(Seek time): 디스크 헤드를 원하는 트랙으로 이동하는 시간(위 아래 수직이동)탐색 시간 ≈ 탐색 거리회전 지연(Rotation..

Virtual Memory ConceptsRestricted physical memory size물리적 메모리 크기의 제한물리적 메모리 공간보다 큰 프로그램은 실행될 수 없음.General program execution pattern일반적인 프로그램 실행 패턴프로그램의 일부만 실행되고 전체 프로그램은 실행되지 않음.오류 코드 및 예외 코드100x100 배열 중 10x10 요소만 사용됨.프로그램의 특정 옵션 및 기능이 드물게 사용됨.전체 프로그램이 필요할 때조차도 모든 부분이 동시에 필요하지 않을 수 있음.Virtual memory가상 메모리메모리에 완전히 들어가지 않은 프로세스의 실행을 허용.프로그램의 일부만 메모리에 있어도 실행 가능.논리적 메모리 주소 공간과 물리적 메모리 주소 공간의 분리.논리적 ..

Multistep Processing of a User Program source program(test.c)가 compiler나 assembler에 의해 object module(test.o) 파일로 컴파일 됨(컴파일 시간)linker가 다른 object module과 linking 해줌loader가 모듈과 system library를 load함 (2, 3 과정을 load time이라고 함)loader에 의해 메모리에 올라온 프로세스가(실행시간에) dynamically loaded system library에서 불러온다.(Windows의 경우 프로세스에서 DLL 파일을 실행시킨 후 프로세스로 복귀함) Address binding프로그램 명령어와 데이터를 물리 메모리 주소에 연결하는 과정명령어나 데이터에..

What is Deadlock?세마포어 사용 예제두 개의 세마포어 S와 Q가 있고, 초기값은 1입니다.  Deadlock : 한 집합의 차단된 프로세스들이 각자 하나의 자원을 잡고 있으며, 동시에 다른 프로세스가 가지고 있는 자원을 얻기 위해 기다리고 있는 상태. Deadlock Characterization(데드락 특성)시스템 모델링 (System modeling)프로세스: P1, P2, ..., Pn.자원 유형(resource types): R1, R2, ..., RmCPU 사이클, 메모리 공간, I/O 장치, 파일 등.각 자원 유형 Ri는 Wi 인스턴스를 가짐.각 프로세스는 다음과 같이 자원을 이용합니다:요청 (request)사용 (use)해제 (release)Deadlock은 네 가지 조건이 동시..

Classical Problems of SynchoronizationBounded-Buffer ProblemReaders and Writers ProblemDining-Philosophers ProblemBounded-Buffer Problem원형 버퍼 문제한줄 요약 : 생산자와 소비자가 고정 크기의 버퍼를 안전하게 공유하며 오버플로우나 언더플로우를 방지하는 고전적인 동기화 문제버퍼의 개수가 N개 있다고 가정합니다.새 항목이 도착했습니다.비어 있는 버퍼가 있습니까? 채우십시오. 꽉 찬 버퍼를 만듭니다.그렇다면, 그러나...공유 변수(Shared variabe)를 지금 접근할 수 있습니까?소비자꽉 찬 버퍼가 존재합니까? 가져가십시오. 비어 있는 버퍼를 만듭니다.그렇다면, 그러나...공유 변수를 지금 접근할..

Race Condition: 공유 데이터에 대한 동시 접근은 data inconsistency(불일치)를 초래할 수 있다.Race condition여러 프로세스가 공유 데이터를 동시에 접근 및 조작할 때 발생하는 상황.race condition을 방지하기 위해서는, concurrent processes는 반드시 동기화되어야 한다.단일 프로세서 환경에서도 CPU scheduler에 의해 race condition이 발생할 수 있습니다.Critical Section ProblemCritical section(임계 구역)공유 데이터에 접근하는 코드 세그먼트.공유 데이터로 접근되는 코드 세그먼트를 말하는 듯Critical section problem한 프로세스가 critical section에서 실행 중일때, ..

CPU bursts and I/O bursts의 교대 시퀀스 Histogram of CPU burst timesCPU Scheduler실행 준비된 프로세스 중 하나를 선택한다CPU scheduling 결정은 다음과 같은 경우에 이루어진다(1) 프로세스가 실행 상태(running)에서 대기 상태(wating)로 전환될 때 (예: I/O 요청)(2) 프로세스가 실행 상태(running)에서 준비 상태(ready)로 전환될 때 (예: time slice expiration)(3) 프로세스가 대기 상태(wating)에서 준비 상태(ready)로 전환될 때 (예: I/O 완료)(4) 프로세스가 종료될 때(terminate)(1)과 (4) 상황에서의 스케줄링은 비선점형(non-preemptive, 수행 중간에 중단..

스레드란 무엇인가?웹 서버를 예시로 들어 설명할게요!웹 서버(Web server)웹 페이지를 제공하는 컴퓨터 프로그램웹 서버는 한 번에 많은 클라이언트를 서비스해야 합니다.웹 서버가 입출력(I/O) 작업을 수행하면?블록될 것입니다.다른 클라이언트의 요청을 처리할 수 없습니다.동시 서비스(concurrent service)를 위해 많은 서버 프로세스가 필요합니다.메모리 공간 낭비.프로세스를 생성하는 동안 delay 발생.스레드(Thread)가 필요합니다.Code, data, and resources를 공유할 수 있습니다.Register values and stacks은 공유할 수 없습니다. ThreadCPU utilization의 기본 단위각 프로세스는 여러 스레드를 포함할 수 있습니다.모든 프로세스의 스..

다양한 트리 구조(균형 트리, N-항 트리)균형 트리(Balanced Tree)만약 BST에 다음과 같은 순서로 삽입한다고 생각해보자bst tree;tree.insert(10);tree.insert(9);tree.insert(11);tree.insert(8);tree.insert(7);tree.insert(6);tree.insert(5);tree.insert(4); 다음과 같은 구조를 갖는다전체 트리가 왼쪽으로 편향되어 있다이 경우 검색을 한다면 비교 횟수가 원소 개수와 거의 같아진다만약 다음과 같은 순서로 삽입하여 구성된 트리에서 검색을 한다면bst tree;tree.insert(7);tree.insert(5);tree.insert(9);tree.insert(4);tree.insert(6);tree.i..

다양한 트리 구조(BST)평범한 이진 트리의 효용성은 그리 높지 않음BST, Balanced Tree 등에 대해 알아보자이진 검색 트리(BST, Binary Search Tree)널리 사용되는 형태의 이진 트리다음과 같은 속성이 있다.부모 노드의 값 >= 왼쪽 자식 노드의 값부모 노드의 값 즉, (왼쪽 노드 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있다.부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다.완전 이진 트리(complete binary tree)이진트리에서 마지막 레벨을 제외한 모든 노드에 두개의 자식 노드가 있는 트리를 말함이 때 트리의 높이는 log_2(N)이 됨BST에서 원소 검색BST의 속성 때문에 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다..