재민

이진트리의 표현으로는, 배열과 연결리스트를 들 수 있다. 1) 배열 우선 1차원 배열에 노드를 저장한다. 자신의 번호를 가진 인덱스 위치에 저장해둔다. 이 때 인덱스 0번은 사용하지 않고 비워두고, 인덱스 1번부터 루트 노드를 저장한다. n개의 노드를 가진 트리는 부모와 자식 노드의 인덱스 관계임을 볼 수 있다. 따라서 parent(i) : [i/2] if i != 1이 되고, leftChild(i) : 2i if 2i

스와핑(Swapping)이란 실행을 계속할 수 없는 프로세스를 메모리에서 일시적으로 예비 저장장치로 내보내고, 실행을 계속할 수 있는 프로세스를 예비 저장장치에서 메모리로 불러오기 하여 실행을 재개할 수 있게 하는 것을 의미한다. 예비 저장장치로는 모든 프로세스의 메모리의 복제본을 저장할 수 있을 정도의 저장 용량을 가진 빠른 디스크를 사용한다. 이 때 빠른 접근을 위해 저장된 메모리 이미지에 대해 직접 접근이 가능해야 한다. 스와핑이 존재하지 않는다면, 물리적 메모리의 크기보다 모든 프로세스의 물리적 주소 공간의 합이 반드시 작아야만 한다. 그러나 스와핑을 통해 이러한 경우가 아니더라도 모든 프로세스가 동시에 실행될 수 있게 할 수 있다. 스와핑 동작은 다음과 같은 프로세스로 진행된다. 1. CPU s..

다단계 큐(multilevel Queue) 스케줄링 에서는 Ready queue가 여러 개의 큐로 분활되어 각 큐는 자신의 스케줄링 알고리즘을 사용한다. 이 때 각 큐는 자신의 스케줄링 알고리즘을 이용하여 스케줄링을 진행한다. (ex: foreground용 큐는 RR, background용 큐는 FCFS 사용) 스케줄링은 큐 들 사이에서도 존재해야 한다. 고정 우선순위 스케줄링은 foreground 작업을 모드 처리한 후에 background 작업을 수행한다. 그러나 기아 상태의 가능성이 존재한다. Time slice는 각 큐마다 CPU 사용량과 비율을 정해서 할당한다. EX) fore, background 에 8:2 할당 다단계 피드백 큐 스케줄링은 process 생성시에 하나의 queue에 영구할당이..

I/O장치에 I/O 주소지정을 할 때, 각 I/O 장치 당 두 개씩 주소를 할당한다.(데이터 레지스터의 주소 & 상태/제어 레지스터의 주소) I/O주소 지정방법은 기억장치-사상 방법과 분리형 I/O 방법으로 이루어진다. 1) 기억장치-사상 I/O 기억장치 주소 영역의 일부분을 I/O 제어기 내의 레지스터들의 주소로 할당하는 방식이다. 프로그래밍에서 기억장치 관련 명령어들을 I/O 장치 제어에도 사용가능하다(EX. LOAD 명령어와 STORE 명령어 등) 그리고 기억장치 읽기/쓰기 신호를 I/O 읽기/쓰기 신호로 사용한다. 2) 분리형 I/O(isolated - I/O) I/O 장치 주소공간을 기억장치 주소 공관과는 별도로 할당하는 방식이다. I/O 제어를 위해서 별도의 I/O 명령어를 사용하며, 별도의 ..

스택을 이용하여, 중위표기식을 후위표기식으로 변경하기 위한 절차는 다음과 같다. 스택 및 연산자 우선순위 함수 정의: 스택을 위한 구조체 및 스택 관련 함수들을 정의한다. (createStack, isEmpty, peek, push, pop) 연산자의 우선순위를 반환하는 함수인 getPrecedence를 정의한다. 중위 표기식을 후위 표기식으로 변환하는 함수 정의 (infixToPostfix): 입력된 중위 표기식을 문자열로 받아오고, 후위 표기식을 저장할 문자열(postfix)을 초기화한다. 반복문을 통해 중위 표기식을 한 글자씩 읽으면서 처리한다. 피연산자일 경우, 그대로 후위 표기식에 추가한다. 여는 괄호일 경우, 스택에 push한다. 닫는 괄호일 경우, 여는 괄호를 만날 때까지 스택에서 연산자를 ..

교착상태(deadlock)란 프로세스 집합에 있는 모든 프로세스가 한 자원을 점유하고, 같은 집합의 다른 프로세스가 점유한 자원의 획득을 기다리는 상태를 의미한다. EX) DVD와 프린터에서 P1은 DVD를 점유, 프린터 요청/ P2는 프린터를 점유, DVD를 요청하는 경우 교착상태 발생 교착상태의 발생 필요조건은 4가지로 볼 수 있다. 이 4가지 조건이 '동시에' 성립할 때에 교착상태는 발생한다. 1) 상호배제 : 한 번에 한 프로세스만 사용할 수 있는 자원이 적어도 하나 존재 2) 점유하며 대기: 프로세스가 최소 하나의 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 대기 3) 순환대기 : {P0,P1,... PN)에서 각각 자기 앞 자원 대기중인 경우 4) 비선점: 자원이 강제로 방출될 수 없..

세마포(Semaphore)는 Mutex Lock보다 더 정교하고 강력한 프로세스 동기화 도구이다. (* 동기화: 시스템을 동시에 작동시키기 위하여 여러 사건들을 조화시키는 것) 세마포 S는 특별한 표준 동기화 연산을 통해서만 접근 할 수 있는 정수 변수로서, 세마포 값은 대개 사용 가능한 특정 자원의 수를 의미한다. 이 때 Semaphore 연산은 초기화 연산(semaphore S의 값을 초기화 하는 연산)과 두개의 원자적 연산(P operation & V operation)으로 나눈다. Semaphore는 1)상호배제, 2) 유한 개수의 자원 접근, 3) 프로세스 동기화를 위한 것이 목적이다. 이를 위해 사용되는 각각의 방법을 알아보자면, 1) 상호배제 구현 > 이진 세마포 (Mutex lock과 유사..

시스템 버스의 기본 동작은 다음과 같은 절차를 통해 이루어진다. - 쓰기 동작 순서 1) 버스 마스터가 버스 사용권을 획득 2) 버스를 통해 주소와 데이터 및 쓰기 신호 전송 - 읽기 동작 순서 1) 버스 마스터가 버스 사용권 획득 2) 주소와 읽기 신호를 보내고, 데이터가 전송되어 올 때까지 대기 버스 동작의 타이밍에 따라 버스는 동기식과 비동기식으로 나뉜다. 동기식 버스는 시스템 버스에서 모든 버스 동작들이 공통의 버스 클럭을 기준으로 발생하는 데에 반해, 비동기식 버스는 버스 동작들의 발생 시간이 관련된 다른 버스 동작의 발생 여부에 따라 결정된다.

운영체제 상에서 임계구역(Critical section:CS)이란 프로세스가 공유 자원을 변경할 수 있는 코드 부분을 의미한다. )이 때 공유자원은 공유 변수, 테이블, 파일 등을 뜻함).이러한 임계구역 상에서 경쟁조건이 발생하지 않도록 서로 협력하기 위한 방법으로서, 프로세스 동기화와 조정이 사용된다. 임계구역 문제를 해결하기 위한 해결방안으로써, 3가지 필요조건이 존재한다. 1) 상호배제 프로세스가 본인의 임계구역 상에서 실행중이라면, 다른 프로세스들은 자신의 임계구역 내에서 진행될 수 없다. 2) 진행 임계구역 상에서 진행되는 프로세스가 없고, 자신의 임계구역으로 진입하려는 프로세스가 있다면, 나머지 구역에서 실행하지 않는 프로세스들만이 cs에 진입하는 프로세스 결정에 참여한다. 그리고 CS 밖에서..

Linked list를 통한 다항식의 표현과정은 크게 두가지이다. 1) 다항식의 모든 항을 배열에 저장함으로써 구현하는 방법 다항식의 각종 연산이 간단해진다는 장점이 있다. 해당 항의 값을 추출하여 연산하면 되기 때문이다. 그러나 대부분의 항의 계수가 0이면 공간 낭비가 심해진다는 단점을 갖고 있다. 이를 극복하기 위한 방법으로 다음 방법을 쓴다. 2) 다항식의 계수가 0이 아닌 항만을 배열에 저장하는 방법 하나의 배열로 여러 개의 다항식을 나타낼 수 있는 방법이다. 메모리 공간 측면에서는 효율적이지만, 다항식의 연산이 복잡해진다.