Brute force Study

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의 속성 때문에 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다..

비선형 문제선형 자료 구조로 표현할 수 없는 대표적인 문제계층적 문제(hierachical problem)순환 종속성 문제(cyclic dependency)계층적 문제ex)회사 조직과 같은 조직 구성은 계층적으로 표현되지만, 선형 자료구조로 표현하기 어렵다선 이수 체계를 갖는 대학교 과정에 대한 종속 관계를 표현할 때에도 마찬가지다.트리를 이용하여 해결순환 종속성ex)SNS에서 사람들과의 친구관계 (그래프)도시와 도시를 잇는 도로망그래프를 이용하여 해결

Process Concept(프로세스 개념)운영 체제는 다양한 프로그램을 실행합니다.배치 시스템 - jobsTime-shared systems(시분할 시스템) - user programs 또는 tasks교재에서는 job과 process라는 용어를 번갈아가면서 사용할 거라고 하네요프로세스실행 중인 프로그램(a program in execution)프로세스는 다음을 포함합니다.프로그램 코드(code), 텍스트 섹션(text section)이라고도 함전역 변수 및 정적 변수를 포함하는 데이터 섹션(data section)임시 데이터를 포함하는 스택(stack)함수 매개변수, 반환 주소, 로컬 변수실행 중 동적으로 할당된 메모리를 포함하는 힙(heap)프로그램 카운터(program counter), 프로세서 레..

운영체제 서비스 (Operating System Services)운영체제는 사용자에게 다음과 같은 서비스를 제공사용자 인터페이스(User Interface)명령어 인터페이스 (CLI), 그래픽 사용자 인터페이스 (GUI)프로그램 실행(Program execution)프로그램을 메모리에 로드, 실행, 종료I/O 작업(I/O operation)키보드/마우스 입력, 모니터/프린터 출력파일 시스템 조작(File system manipulation)파일 또는 디렉토리 읽기/쓰기, 생성/삭제/검색 등통신(Communications)프로세스 간 정보 교환오류 검출(Error detection)하드웨어 (메모리 오류, power failure)I/O 장치 (네트워크 연결 실패, 프린터 용지 부족)사용자 프로그램 (산술..