정보처리기사 필기 2006년 5월 A형 운영체제

<가상 기억장치>

• 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로, 용량이 작은 주기억장치를 마치 큰 용량을 가진 것처럼 사용하는 것으로, 현재 사용되는 운영체제에서 흔히 사용되는 기법이다.
• 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용한다.
• 가상 기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸는 주소변환 작업(주소 매핑)이 필요하다.
• 블록 단위로 나누어 사용하므로 연속 할당 방식에서 발생할 수 있는 단편화를 해결할 수 있다.
• 기억장치의 이용률과 다중 프로그래밍의 효율을 높일 수 있다.
• 운영체제의 설계가 복잡해지고 주소 변환을 위한 테이블을 사용하므로 기억장소를 낭비할 수 있다.
• 가상 기억장치 구현 기법
 - 페이징 (Paging)기법
 - 세그먼테이션 (Segmentation)기법

<교착 상태(Deadlock)>

• 정의

상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상

• 필요 충분 조건

- 상호 배제(Mutual Exclusion) : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 함

- 점유와 대기(Hold & Wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함

- 비선점(Non-preemptive) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼았을 수 없어야 함

- 환형 대기(Circular Wait) : 공유 자원과 공유 자원을 사용하기 위해 대기하는 프로세스들이 원형으로 구성되어 있어 자신에게 할당된 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구해야 함

<UNIX의 주요 명령어>

명령어	의미
fork	새로운 프로세스 생성(하위 프로세스 호출, 프로세스 복제)
exec	새로운 프로세스 수행
&	백그라운드 처리를 위해 명령의 끝에 입력
wait	fork후 exec에 의해 실행되는 프로세스의 상위 프로세스가 하위 프로세스 종료 등의 event를 기다림
exit	프로세스 수행 종료
cat	내용을 화면에 표시(DOS 명령 중 ‘TYPE’과 유사)
chmod	파일의 사용 허가 지정
mount	파일 시스템을 마운팅(새로운 파일 시스템을 기존 파일 시스템의 서브 디렉터리에 연결하는 것) 함
mkls	파일 시스템 생성
chdir	현재 사용할 디렉터리 위치 변경
fsck	파일 시스템을 검사 및 보수하여 무결성을 검사 함
rmdir	디렉터리 삭제
ls	현재 디렉터리 내의 파일 목록 확인
getpid	자신의 프로세스 아이디를 얻음
getppid	부모 프로세스의 아이디를 얻음
cp	파일 복사
mv	파일 이동 및 이름 변경
rm	파일 삭제
finger	사용자 정보를 표시함

<인터럽트의 종류 및 발생 원인>

• 외부 인터럽트

- 전원 이상 인터럽트(Power Fail Interrupt) 

: 정전이 되거나 전원 이상이 있는 경우

• 기계 착오 인터럽트(Machine Check Interrupt) 

: CPU의 기능적인 오류 동작이 발생한 경우

• 외부 신호 인터럽트(External Interrupt)

1. 타이머에 의해 규정된 시간(Time Slice)을 알리는 경우

2. 키보드로 인터럽트 키를 누른 경우

3. 외부장치로부터 인터럽트 요청이 있는 경우

• 입·출력 인터럽트(Input-Output Interrupt)

1. 입·출력 Data의 오류나 이상 현상이 발생한 경우

2. 입·출력장치가 데이터의 전송을 요구하거나 전송이 끝났음을 알릴 경우

<국부성(Locality, 구역성)>

• 프로세스가 실행되는 동안 주기억장치를 참조할 때 일부 페이지만 집중적으로 참조하는 성질이 있다는 이론이다.

• 스래싱을 방지하기 위한 워킹 셋 이론의 기반이 된다.

• 프로세스가 집중적으로 사용하는 페이지를 알아내는 방법 중 하나로, 가상 기억장치 관리의 이론적인 근거가 된다.

• Locality 종류

- 시간 구역성 (Temporal Locality)

 1. 프로세스가 실행되면서 하나의 페이지를 일정 시간 동안 집중적으로 액세스하는 현상

 2. 시간 구역성이 이루어지는 기억장소 : Loop(반복, 순환), 스택(Stack), 부프로그램(Sub Routine), Counting(1씩 증감), Totaling(집계)에 사용되는 변수(기억장소)

- 공간 구역성 (Spatial Locality)

 1. 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상

 2. 공간 구역성이 이루어지는 기억장소 : 배열 순회(Array Traversal), 순차적 코드의 실행,       프로그래머들이 관련된 변수(데이터를 저장할 기억장소)들을 서로 근처에 선언하여 할당되는 기억장소, 같은 영역에 있는 변수를 참조할 때 사용

<선점 스케줄링의 종류>

선점 우선순위	준비상태 큐의 프로세스들 중에서 우선순위가 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법
SRT (Shortest Remaining Time)	비선점 기법인 SJF 알고리즘을 선점 형태로 변경한 기법으로, 현재 실행중인 프로세스의 남은 시간과 준비상태 큐에 새로 도착한 프로세스의 실행 시간을 비교하여 가장 짧은 실행 시간을 요구하는 프로세스에게 CPU를 할당하는 기법
RR (Round Robin)	• 시분할 시스템(Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점 형태로 변형한 기법 • FCFS(FIFO) 기법과 같이 준비상태 큐에 먼저 들어온 프로세스가 먼저 CPU를 할당받지만 각 프로세스는 할당된 시간(T i m e S l i c e, Quantum) 동안만 실행한 후 실행이 완료되지 않으면 다음 프로세스에게 CPU를 넘겨주고 준비상태 큐의 가장 뒤로 배치됨 • 할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생됨
다단계 큐(Multi level Queue)	프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 준비상태 큐를 사용하는 기법
다단계 피드백 큐(Multi level Feedback Queue)	특정 그룹의 준비상태 큐에 들어간 프로세스가 다른 준비상태 큐로 이동할 수 없는 다단계 큐 기법을 준비상태 큐 사이를 이동할 수 있도록 개선한 기법

<스래싱(Thrashing)>

• 프로세스의 처리 시간보다 페이지 교체 시간이 더 많아지는 현상이다.

• 다중 프로그래밍 시스템이나 가상 기억장치를 사용하는 시스템에서 하나의 프로세스 수행 과정중 자주 페이지 부재가 발생함으로 인해 나타나는 현상으로 전체 시스템의 성능이 저하된다.

• 다중 프로그래밍의 정도가 높아짐에 따라 CPU의 이용률은 어느 특정 시점까지는 높아지지만 다중 프로그래밍의 정도가 더욱 커지면 스래싱이 나타나고, CPU의 이용률은 급격히 감소된다.

• CPU 이용률을 높이고, 스래싱 현상을 방지하려면 다중 프로그래밍의 정도를 적정 수준으로 유지, 부족한 자원 증설, 일부 프로세스 중단, 페이지 부재 빈도 (Page Fault Frequency) 조절, Working Set 유지, 적정 프레임 수 제공 등의 방법을 수행한다.

<직접 파일(Direct File), 직접 접근방식>

• 파일을 구성하는 레코드를 임의의 물리적 저장공간에 기록하는 것이다.

• 레코드에 특정 기준으로 키가 할당되며, 해싱 함수 (Hashing Function)를 이용하여 이 키에 대한 보조기억장치의 물리적 상대 레코드 주소를 계산한 후 해당하는 주소에 레코드를 저장한다.

• 레코드는 해싱 함수에 의해 계산된 물리적 주소를 통해 직접 접근이 가능하다.

• 임의 접근이 가능한 자기 디스크나 자기 드럼을 사용한다.

• 장점 : 파일의 각 레코드에 직접 접근하거나 기록할 수 있음, 접근 시간이 빠르고, 레코드의 삽입, 삭제, 갱신이 용이함

• 단점 : 레코드의 주소 변환 과정이 필요하며, 이 과정으로 인해 시간이 소요됨, 기억공간의 효율이 저하됨, 기억장치의 물리적 구조에 대한 지식이 필요함

<FIFO 페이지 부재수 구하기>

• 예시

FIFO 교체 알고리즘을 사용하고 페이지 참조의 순서가 다음과 같다고 가정한다면 할당된 프레임의 수가 4개일 때 몇 번의 페이지 부재가 발생하는가? (단, 초기 프레임은 모두 비어 있다고 가정한다.)

0  1  2  3  0  1  4  0  1  2  3  4

• 해결
[ ][ ][ ][ ]
[0][ ][ ][ ] - 부재
[0][1][ ][ ] - 부재
[0][1][2][ ] - 부재
[0][1][2][3] - 부재
[0][1][2][3] - hit (0 1 2 3 다음에 0인데 프레임안에 이미 있기때문에 hit입니다.)
[0][1][2][3] - hit (마찬가지로 1도 프레임 안에 있으므로 hit)
[4][1][2][3] - 부재 (4를 입력해야하는데 프레임 안에 없으므로. 부재. 0이 제일 먼저 들어왔었으므로 0을제거하고 4입력)
[4][0][2][3] - 부재 (0을 입력해야하는데 프레임 안에 없으므로. 부재. [4][1][2][3]중에 제일 먼저 있었던놈인 1을 제거하고 0입력)
[4][0][1][3] - 부재 (1을 입력해야하는데 프레임 안에 없으므로. 부재. [4][0][2][3]중에 제일 먼저있던놈인 2제거후 1입력)
[4][0][1][2] - 부재 (2를 입력해야하는데 프레임 안에 없으므로. 부재. 알아서 하실거라고 봐요)
[3][0][1][2] - 부재 (3을 입력해야하는데 프레임 안에 없으므로. 부재.)
[3][4][1][2] - 부재

• 결론

10 page faults.

• etc. Belady’s Anomaly

<디스크 스케줄링>

• 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법이다.

• 디스크 스케줄링의 목적 : 처리량 최대화, 평균 응답 시간의 최소화, 응답 시간 편차의 최소화

<비선점 스케줄링의 종류>

FCFS (First-Come First-Service)	• 준비상태 큐에 도착한 순서에 따라 차례로 CPU를 할당하는 기법 • 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을, 중요한 작업이 중요하지 않은 작업을 기다리게 됨
SJF (Shortest Job First)	• 실행 시간이 가장 짧은 프로세스에 먼저 CPU를 할당하는 기법 • 가장 적은 평균 대기 시간을 제공하는 최적 알고리즘
HRN(Hightest Responseratio Next)	• 실행 시간이 긴 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로, 대기 시간과 서비스(실행)시간을 이용하는 기법 • 우선순위 계산 공식 = (대기 시간 + 서비스 시간) / 서비스 시간 • 우선 순위 계산 결과값이 높은 것부터 우선 순위가 부여되는데, 대기 시간이 긴 프로세스일 경우 계산 결과값이 높게 나옴
기한부 (Deadline)	• 프로세스에게 일정한 시간을 주어 그 시간 안에 프로세스를 완료하도록 하는 기법 • 시스템은 프로세스에게 할당할 정확한 시간을 추정해야 하며, 이를 위해서 사용자는 시스템이 요구한 프로세스에 대한 정확한 정보를 제공해 야 함
우선순위 (Priority)	준비상태 큐에서 기다리는 각 프로세스마다 우선순위를 부여하여 그 중 가장 높은 프로세스에게 먼저 CPU를 할당하는 기법