[컴퓨터과학 개론] 8강 - 운영체제(2)

✅ 1. 프로세서 관리(1)

[ 프로세스 : Process ]

• 운영체제에 의해 메모리에 적재되고 CPU 실행 대상이 된 프로그램을 프로세스라고 한다.
• 메모리에 올라가 있는 상태만으로도 OS 관점에서 이미 프로세스로 관리되고 있는 것이기 때문에 이것도 프로세스로 본다.
• CPU가 실제로 해당 메모리에 올라간 프로그램의 명령어를 가져와 실행시켜도 프로세스로 본다.
• 프로세스는 주기억장치에 적재되고 중앙처리장치를 할당받아 실행될 명령어로 변경되어 다양한 작업을 수행할 수 있는 능동적 프로세스가 된다.
• 정리하면 메모리에 올라간 상태와 CPU에서 메모리에 명령어를 가져와 실행 시키는 단계 또한 프로세스로 볼 수 있다는 의미

[ 프로세서 : Processor ]

• 처리하는 장치라는 뜻으로, 보통 명령어를 해석하고 실행하는 장치인 CPU를 의미한다.

(1) 개요

[ 프로세서 관리자 ]

• 중앙처리장치(CPU)를 프로세스에게 할당하는 관리자를 의미한다.
• 쉽게말해, 중앙처리장치(CPU)를 프로세스에게 할당하는 관리자
• 중앙처리장치 할당은 프로세서 관리자(운영체제)의 역할임
• 프로세서 관리자는 단일 CPU에 프로세스를 할당하는 방법과 시간을 결정함
• 정리하면 CPU에선 하나의 코어에서 하나의 프로세서만 동작이 가능하지만, 운영체제의 프로세서 관리자의 의해 CPU를 번갈아 가면서 프로세스에게 할당(스케줄링) 을 한다. 쉽게말해, 프로세서 관리자는 프로세스가 CPU에서 실행될 수 있는 기회(시간)를 나눠주는 역할을 한다.

(2) 프로세스 개념

[ 프로세스 상태 ]

• 프로세스는 실행 상태에 있는 능동적 프로그램이며, 프로그램은 보조기억장치에 저장된 상태의 수동적 객체이다.
• 프로세스는 주기억장치에 적재되고 중앙처리장치를 할당받아 실행될 명령어로 변경되어 다양한 작업을 수행할 수 있는 능동적 프로세스가 된다. ( 이것이 운영체제가 해주는 일이다. )
• 운영체제는 프로세스의 정보를 저장하는 프로세스 제어 블록(Process Control Block, PCB) 을 관리하며, 프로세스의 실행이 끝나면 프로세스 제어 블록을 삭제한다. 
• 프로세스가 시스템 내에 존재하는 동안, 그 프로세스는 생성(new), 준비(ready), 실행(running), 대기(waiting), 종료(finished) 와 같은 5개 상태 중 한 상태에 있게 된다. ( 운영체제가 해줌 )

(3) 중앙처리장치 스케줄링 기법

[ 프로세스 스케줄링 개요 ]

• 프로세스 스케줄링 알고리즘: 운영체제가 프로세스에게 중앙처리장치를 할당하는 방법 ( CPU 할당 방법 )
• 즉, 운영체제가 해당 알고리즘을 활용해서 프로세스에게 프로세서를 할당해주는 방법임.
• 프로세스 스케줄링 알고리즘은 선점 스케줄링 기법과 비선점 스케줄렁 기법으로 크게 구분이 된다.

[ 비선점 스케줄링 기법 ]

• 일단 프로세스에 중앙처리장치가 할당되어 프로세스의 실행이 시작되면, 프로세스가 종료될 때까지 중앙처리장치를 다른 프로세스에게 양보하지 않는 기법임. ( 하나의 프로세스가 끝날때 까지 중앙처리장치를 쭉 사용 양보하지 않음 )
• 비선점 스케줄링 기법은 짧은 작업이 긴 작업으로 인해 기다리게 되는 경우가 있지만 모든 프로세스 관리가 공평해짐.
• 비선점 스케줄링 기법은 우선순위에 관계없이 대기 중인 작업에는 변동이 없으므로 응답시간을 예측할 수 있는 장점이 있음.

[ 선점 스케줄링 기법 ]

• 중앙처리장치(CPU)를 점유하여 실행 중인 프로세스를 내보내고, 다른 프로세스에게 중앙처리장치에 할당하는 스케줄링 기법이다. ( 스케줄링 알고리즘의 의해 더 중요한 프로세스가 들어오면 해당 프로세스에게 양보를 하는 경우 )

[ FCFS (First-Come First-Served) 스케줄링 기법 - 비선점 스케줄링 ]

• 준비 큐에 도착한 순서대로 중앙처리장치를 할당 받도록 해 주는 기법이다. ( 큐 순서대로 처리 하나씩 )
• 하나의 프로세스가 중앙처리장치를 차지하면 그 프로세스의 수행이 완료된 후에 그 다음 프로세스에게 중앙처리장치를 할당함.
• 해당 FCFS 스케줄링에서는 대기 큐에 늦게 들어온 짧은 작업이 대기 큐에 일찍 들어온 긴 작업을 기다리게 되고, 중요한 프로세스가 덜 중요한 프로세스의 완료를 기다리는 단점이 있음.
• 참고로 비선점 방식 중 하나로 비선점 전체에 포함되는 하위 개념이다. ( 즉, 비선점의 한 종류임 )
• 쉽게말해, 비선점이랑 선점은 추상적 설계 원칙이고, 해당 추상화를 구현한 것으로 볼 수 있음.

[ 우선순위 스케줄링 - 선점 스케줄링 ]

• 우선순위가 높은 프로세스부터 먼저 처리하는 스케줄링 기법
• 우선순위는 여러 가지 요인에 의해 결정될 수 있음
• 기본적 우선순위: 각 프로세스가 요구하는 기억장치의 양, 주변장치의 수와 형태, 중앙처리장치 처리 요구 시간, 작업 처리를 시작한 시점부터 경과된 시간 등을 고려하여 중앙처리장치 관리자에 의해 결정이 됨.
• 외부적 우선순위: 사용자의 직위나 상거래의 규모 등을 이용하여 시스템 관리자가 결정함.

• 우선순위 스케줄링을 사용하는 경우 프로세스는 일반적으로 우선순위에 따라 배치하기 위해서 여러 개의 준비 큐에 들어감
• 우선순위 스케줄리에 의해 준비 리스트 큐 A 의 내부 작업들이 순차적으로 실행 된 후 B, C 로 넘어가는 구조이다.
• 해당 구조의 단점은 만약 list A, list B 작업이 끝나고 C를 실행하려고 할 때, list A 큐에 작업 D가 들어오게 되면 다시 우선순위에 따라 D가 실행이 되게 된다. 즉, C가 실행이 못되는 현상이 발생 할 수 있게 된다.

[ SJF (Shortest Job Fist) 스케줄링 ]

• 현재 준비 큐에 있는 프로세스들 중에서 수행시간이 가장 짧은것으로 예상되는 프로세스를 먼저 처리하는 스케줄링 기법
• 프로세스의 예상 수행 시간을 실행 입력 이전에 알아야 하므로 일괄처리 환경에서는 구현하기 쉽지만, 대화식 시스템에는 사용자와 컴퓨터간의 상호작용으로 인해 실행시간을 예측할 수 없기 때문에 사용되기 힘듦
• 대기하는 프로세스의 수를 최소화할 수 있으므로 빠른 응답시간을 제공할 수 있지만, 수행시간이 긴 프로세스는 CPU를 할당 받지 못한 채 계속 기다릴 수 있는 단점도 있음.
• 해당 스케줄링의 우선순위는 짧은 수행시간의 프로세스이다.

[ RR (Round Robin) 스케줄링 ]

• 프로세스가 도착한 순서대로 CPU가 할당되지만, CPU의 시간 할당량 또는 시간 간격에 의해 제한을 받는 스케줄링 방식
• 시간 할당량을 모든 프로세스에게 동일하게 주고, 그 시간 동안 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치되고 준비 중인 다음 프로세스에게 중앙처리장치를 할당함.
• 하나의 프로세스가 CPU를 독점하지 않고 공평하게 이용될 수 있도록 하는 장점도 있지만, 운선순위가 높은 작업을 빨리 처리하기 어려운 단점도 있음. ( 우선순위 높은 애를 먼저 큐의 앞으로 보내는 방법도 사용하기도 함 )

• 쉽게말해, 큐에 도착한 순서대로 CPU 할당을 해주고 정해진 시간 만큼만 프로세스에게 CPU를 할당해준다. 이후, 정해진 시간을 벗어나는 작업은 남은 시간을 가진채 큐의 맨 뒤로 다시 들어가게 되는 방식이다.

[ 결론 ]

• 운영체제의 프로세서 관리자 개념안에 프로세스 스케줄링 알고리즘을 통해 프로세스에게 CPU를 할당을 해줌.

---

✅ 2. 프로세서 관리(2)

(1) 교착 상태

[ 개요 ]

교착 상태의 예시

• 다중 프로그래밍 실행 환경에서는 여러 프로세스들이 제한된 컴퓨터 자원을 사용하려고 서로 경쟁할 수 있음
• 한 프로세스가 컴퓨터 자원을 요청했지만 바로 할당 받을 수 없다면, 그 프로세스는 자원을 얻기 위한 대기 상태로 들어감
• 그림의 예시를 보면 P1 - 프린터 할당, P2 프린터 요구, P1 자기테이프 요구, P2 자기테이프 할당 서로 필요한 것이 엇갈려 가지고 있는 상태를 교착 상태라 한다. ( 즉, 움직일 수 없는 상태 )
• 두 개의 다른 프로세스가 서로에게 할당된 컴퓨터 자원을 얻기 위해 대기하면서 자신에게 할당된 컴퓨터 자원을 포기하지 않는다면, 서로의 컴퓨터 자원을 무한대로 기다리는 상태가 됨.
• 쉽게말해, 2개 이상의 프로세스가 대기 중인 프로세스들 중의 하나에 의해서만 발생할 수 있는 사건을 무작정 기다리는 상태를 교착상태(deadlock) 라고 한다.

(2) 교착 상태의 필수 조건

• 교착상태는 다음의 네 가지 조건이 동시에 만족할 때에만 발생한다.

• 상호 배제 조건: 한 프로세스가 컴퓨터 자원을 사용 중이면 다른 프로세스는 그 컴퓨터 자원을 사용하지 못하고 해제될 때까지 반드시 기다려야 한다. ( 예: 프린터를 한 번에 두 프로세스가 동시에 사용할 수 없음. )
• 대기 조건: 프로세스가 적어도 하나 이상의 컴퓨터 자원을 할당 받아 점유하고 있으면서 다른 프로세스가 할당 받은 자원을 요청하고 그것이 해제되기를 기다려야 한다. ( 예: 프로세스 A가 프린터를 가지고 있으면서, 동시에 스캐너를 기다림. )
• 비선점 조건: 할당된 컴퓨터 자원이 그 프로세스의 작업 종류 후 자발적으로만 해제될 수 있고 타의에 의해서는 해제되지 않는다. ( 예: 프로세스가 프린터를 쓰는 도중 운영체제가 강제로 뺏을 수 없음. )
• 환형 대기 조건: 프로세스의 원형 사슬이 존재해서 이를 구성하는 각 프로세스가 사슬 내의 다음에 있는 프로세스가 요구하는 하나 이상의 자원을 가지고 있다. ( 예: 자원 요청이 원형 고리를 이루며 대기하는 상황 )

(3) 교착상태의 처리

[ 교착상태 방지(prevention) ]

• 교착상태는 교착상태 필수 조건을 만족할 경우에 발생이 됨.
• 네 가지 교착상태 발생 조건 중에서 어느 한 가지 조건이도 제거하면, 교착상태가 발생하지 않도록 할 수 있음
• 이와 같이 요구 상태를 제한함으로써 교착상태를 방지하게 되면 컴퓨터 자원의 이용률과 시스템 성능이 저하되는 부작용이 생기게 된다.

[ 교착상태 탐지(detection) ]

• 교착상태에 빠진 프로세스의 존재를 검사하여 교착상태를 찾아내는 기법을 의미한다.
• 교착상태 탐지 알고리즘을 수행하는 것은 시스템 성능에 상당한 부담이 되기 때문에, 교착상태 탐지 알고리즘은 적절하게 수행이 되어야 한다. ( 확실한 교착 상태를 탐지를 해줘야 한다는 의미임 )

[ 교착상태 복구(recovery) ]

• 교착상태를 제거하여 다른 프로세스가 컴퓨터 자원을 사용할 수 있도록 하는 방법이다.
• 교착상태 복구 방법 중 하나는 시스템 관리자에게 교착상태가 발생하였음을 알려주어 직접 수작업으로 처리하도록 하는 것임
• 환형 대기를 없애기 위해 몇 개의 프로세스들을 중지시키거나 교착상태에 있는 하나 이상의 프로세스들로부터 몇 개의 자원을 반납하게 하는 것이다. ( 몇 개의 프로세스들을 중지할지 여부를 판단하는 것이 굉장히 복잡함 )

[ 정리 ]

• CPU를 효율적으로 사용하기 위해서 여러 프로세스를 동시에 메모리에 올려놓고 번갈아 실행하는 것은 운영체제의 스케줄링 덕분에 가능하며, 해당 다중 프로그래밍에서 동시에 자원을 요구하면서 발생하는것이 교착상태로 볼 수 있다.

---

✅ 3. 장치 관리

(1) 장치 관리와 파일 관리

[ 개요 ]

• 운영체제는 장치 관리자와 파일 관리자의 역할도 수행함
• 장치 관리자는 시스템의 키보드, 마우스, 프린터, 네트워크 카드 등과 같은 모든 주변기기를 관리함.
• 파일 관리자는 시스템 내에 존재하는 파일의 저장과 접근 권한 등을 관리함.

(2) 보조기억장치

[ 개요 ]

• 대용량의 프로그램이나 데이터를 장기간 저장하기 위한 장치 매체는 보조기억장치이며 디스크 상의 파일에 직접 접근할 수 있는 직접 접근 매체인 하드 디스크와 플래시 메모리가 대표적인 보조기억장치임.
• 하드디스크와 같은 직접 접근장치: 자기 디스크의 특정 위치에 있는 데이터를 읽거나 쓸 경우 임의적인 접근이 가능하기 때문에 임의 접근 저장장치라고도 함.
• 이러한 보조기억장치를 관리 기법을 사용해 빠르게 접근을 하는것이 운영체제의 역할이다.

[ 디스크 팩의 구조 ]

• 일반적으로 디스크에 접근하는 데 걸리는 시간은 트랙 탐색 시간(seek time), 디스크 회전 지연 시간(latencty time), 데이터 전송 시간(transfer time)의 합으로 구성이 되어있음.
• 그 중 트랙 탐색 시간에 걸리는 시간이 가장 길어 보조기억장치를 관리하는 알고리즘 기법에는 대부분 트랙 탐색 시간을 줄이는데 초점이 맞춰져 있음.
• 트랙 탐색 시간: 헤드를 움직여 원하는 트랙으로 이동시키는 데 필요한 시간을 의미하며, 기계적인 동작으로 이루어지기 때문에 가장 시간이 많이 걸리는 요소임. ( 해당 트랙까지 디스크 암이 가는데 걸리는 시간을 의미 )
• 디스크 회전 지연 시간: 헤드가 원하는 트랙에 위치한 후에, 요구된 자료가 저장된 특정 섹터가 헤드 밑에 이를 때까지 디스크가 회전하는 데 필요한 시간을 의미함.
• 데이터 전송 시간: 쓰기 동작일 경우에는 주기억장치에서 데이터가 보조기억장치에 저장되는 시간이며, 읽기 동작일 경우에는 보조기억장치로부터 데이터를 읽어 주기억장치로 이동하는 데 필요한 시간임. ( 앞의 두 가지 보다 걸리는 시간은 짧음 )

(3) 디스크 스케줄링

[ 개요 ]

• 프로세스들의 보조기억장치 읽기 요청이나 쓰기 요청을 효율적으로 처리하기 위한 보조기억장치(디스크) 관리 기법임.
• 디스크 스케줄러는 대기하고 있는 요청들 간의 위치적 관계를 조사한 후에, 최소한의 기계적 동작에 의해 처리될 수 잇도록 요청들의 순서를 재배열을 한다. ( 트랙 탐색 시간에 가장 집중을 함. )
• 트랙 탐색 시간 최적화와 회원지연 시간 최적화의 두 가지 형태로 나눌 수 있음

[ FCFS(First-Come First Served) 스케줄링 기법 ]

• 먼저 도착한 디스크 접근 요청이 가장 먼저 서비스를 받도록 하는 기법을 의미함.
• 일단 디스크 접근 요청이 도착하면 실행 순서가 고정되어 더 높은 요청이 도착해도 실행 순서가 바뀌지 않음
• 부하가 적은 시스템의 경우에는 비교적 좋은 방법이지만, 부하가 커질수록 장치를 포화시키기가 쉽고 응답시간이 길어지는 단점이 있음.
• 즉, 처음 들어온 디스크 요청부터 순서대로 처리를 해주는 방식임

[ SSTF(Shortest Seek Time First) 스케줄링 기법 ]

• 현재 디스크 헤드의 위치에서 가장 짧은 트랙 탐색 거리(또는 탐색 시간)를 가진 디스크 접근 요청을 먼저 처리하는 기법
• FCFS에 비해 평균 응답시간도 짧지만, 가장 중요한 단점은 중간 범위의 트랙에 비해 가장 안쪽 또는 바깥쪽 트랙이 서비스를 받지 못하는 경우가 발생할 확률이 높음
• SSTF는 처리량이 주요 관심사인 일괄 처리 시스템에서는 유용하게 사용될 수 있지만, 응답 시간의 큰 편차로 발생하기 때문에 대화식 시스템에서는 사용되지 않는다.

[ SCAN 스케줄링 기법 ]

• SSTF 스케줄링 기법의 서비스에 대한 불공평성 문제를 극복하기 위해서 제안된 방법이다. (엘리베이터 알고리즘으로 불림)
• 한쪽 방향에서 가장 짧은 탐색 거리의 디스크 접근 요청이 먼저 서비스를 받도록 하는 기법이다.
• 해당 방향의 마지막 실린더를 만나거나 기다리는 요구가 더 이상 없을때에는 방향을 바꾸어 서비스를 계속한다.
• 쉽게말해, 디스크 헤드가 한쪽 끝에서 다른 쪽 끝으로 이동하면서, 지나가는 요청들을 순서대로 처리하는 방식임.
• 헤드가 지나간 후 헤드 바로 뒤에 도착하는 요구는 헤드가 진행 방향의 끝까지 갔다가 방향을 바꾸어 되돌아올 때까지 기다려야하는 문제가 있으며, 상대적으로 안쪽 트랙과 바깥쪽 트랙이 중앙트랙보다 서비스를 많이 받게 되는 불공평성 문제가 있음.

[ SLTF(Shortest Latency Time First) 스케줄링 기법 ]

• 트랙 탐색 시간을 최적화하기 위한 SSTF 스케줄링과 유사하게 디스크의 회전 지연 시간을 최적화하기 위한 기법임.
• 일단 디스크 헤드가 특정 실린더에 도착하면 그 실린더 내의 여러 트랙에 대하여 많은 요구가 있을 가능성이 높기 때문에 모든 요구를 검사한 후 가장 짧은 회전 지연을 갖는 요구들에게 우선적으로 서비스를 하는 기법이다.
• 가장 가까우면서, 해당 트랙에 대하여 많은 요구가 있을 경우 우선순위를 준다는 의미임.

[ 결론 ]

• 디스크 스케줄링은 운영체제(OS) 안에서, 여러 프로세스가 동시에 디스크 I/O 요청을 할 때, 그 요청들을 어떤 순서로 처리할지를 결정하는  역할을 하며, CPU 스케줄링이 CPU 자원 분배를 관리하듯, 디스크 스케줄링은 디스크라는 입출력 장치 자원을 효율적으로 배분하는 것이다.

---

✅ 4. 파일 관리

(1) 파일 관리 시스템

[ 개요 ]

• 파일(file) 이란 일반적으로 디스크 등의 보조기억장치에 저장되어 있는 서로 관련성 있는 데이터의 집합(레코드의 집합)을 의미한다.
• 파일에 의해서 사용되는 자원의 관리를 비롯하여 파일의 생성, 삭제, 수정, 접근 등을 제어하는 소프트웨어를 파일 관리 시스템(File Management System)이라고 한다.

[ 구성 요소 ]

• 파일 관리 시스템(운영체제)의 주요 구성 요소
• (1) 파일에 저장되어 있는 데이터에 대한 접근 방식
• (2) 파일의 저장, 참조, 공유 및 파일 보호 기법을 제공하는 파일 관리
• (3) 보조기억장치에 파일 저장을 위한 공간 할당과 관련된 보조기억장치 관리
• (4) 파일의 정보가 소실되지 않도록 보장하는 일에 관계된 파일 무결성 유지

 [ 역할 ]

• 구성 요소들을 통해 파일 관리 시스템은 물리적인 저장 요소, 정보자원, 그리고 파일들을 저장하고 분배하기 위한 정책들을 책임진다.
• 구체적으로 파일의 생성, 수정, 삭제, 공유, 백업과 복구, 보호, 사용자 편의 인터페이스 제공 등의 다양한 기능들을 수행한다.
• 파일 구조는 파일을 구성하는 레코드들의 보조기억장치 배치 기법으로 파일에서 레코드에 접근하는 방식과 밀접한 관계 가짐.
• 실제 내부적으로 사용자는 파일 시스템을 통해 "파일"이라는 단위로 접근 후 파일 시스템은 내부적으로 해당 파일을 디스크 블록(섹터)에 매핑 한 뒤 디스크 블록 요청이 들어가면, 디스크 I/O 단계에서 디스크 스케줄링 알고리즘이 어떤 순서로 접근할지 결정을 한다.
• 즉, 파일 관리 시스템은 논리적 계층(사용자 -> 파일, 디렉토리 관리)으로 볼 수 있고, 디스크 스케줄링은 물리적 계층으로 (디스크 헤드 이동, 섹터 접근 최적화)으로 볼 수 있다. 둘은 층위가 달라서, 파일 시스템이 논리적 요청을 만들고 디스크 스케줄링이 물리적으로 처리하는 흐름으로 볼 수 있음.
• 쉽게말해, 앞에서는 파일 관리 시스템이 인터페이스를 제공하고, 뒤에서는 디스크 스케줄링이 효율을 맞춰 돌고 있는 구조

[ 순차 파일 ]

• 레코드들의 저장이 연속적인 물리적 위치에 따라 저장되어 있는 파일 형태를 의미한다.
• 순차 파일은 일반적으로 키 값에 따라 일정한 순서를 유지하며 저장되며, 논리적으로 연속적으로 나타나는 레코드들은 물리적으로도 연속적인 위치에 저장이 된다.
• 한 레코드에 접근하기 위해서, 그 레코드의 앞에 있는 레코드들을 먼저 접근해야 한다. ( 순차 접근 )
• 물리적으로 순차적인 접근 특성을 가진 자기 테이프에 가장 많이 이용이 된다.

[ 직접 파일 ]

• 레코드가 저장되어 있는 저장장치의 물리적 주소에 의해 직접적으로 접근할 수 있는 구조의 파일 형태이다.
• 다른 레코드를 참조하지 않고 어떤 레코드에도 접근할 수 있음
• 특정 레코드를 식별하기 위한 레코드 키와 보조기억장치의 저장 주소의 관계 정보를 알고 있어야 함
• 파일을 구성할 때 레코드 키와 실제 저장 주소 사이의 관계를 찾아낼 수 있는 함수가 필요하며, 이를 통해 레코드 키를 변환하여 실제 저장된 보조기억장치의 주소를 얻어낸다.
• 직접 파일은 이와 같은 접근의 효율성을 위해 순차 파일과는 다르게 자기 디스크와 같은 직접 접근 저장장치에 저장한다.

[ 인덱스 순차 파일 - 현대 하드디스크는 대부분 이방식이라는데? ]

• 레코드 키 값에 따라 정렬된 레코드를 순차적으로 접근할 수 있는 순차파일의 특징을 가지고 있음.
• 주어진 키 값에 따라 직접 접근할 수 있는 직접 파일의 특징을 갖는 구조의 파일 형태이다.
• 순차 접근을 지원하는 순차 파일과 직접 접근을 지원하는 직접 파일을 결합한 형태로 볼 수 있다.

[ 결론 ]

• 정리하면, 순차 파일, 직접 파일, 인덱스 순차 파일 등은 파일 조직 방식(논리적 설계 개념)에 가깝다. 즉, 데이터를 보조기억장치에 어떻게 배치하고 접근할지를 정의하는 논리적 설계라고 보는게 맞는 것이다. 거기에 따라 데이터를 검색할 때 사용할 알고리즘이 따로 붙는 것이다.

(2) 디스크 공간 할당 방식

• 파일을 보조기억장치에 저장할 때 어떻게 디스크 공간을 할당 할것인가와 관련된 문제를 파일 관리 시스템의 한 요소를 차지하고 있는 중요한 부분이며, 공간의 효율성과 파일의 접근성 등이 공간 할당 방식에 따라 달라진다.

[ 연속 할당 (Contiguous Alloccation) 기법 ]

• 파일이 보조기억장치에 저장될 때 연속된 공간을 할당 받는 기법
• 파일의 시작 주소와 파일의 길이 정보를 관리하는 파일 디렉터리를 통해 파일에 접근을 함.
• 만약 보조기억장치에 파일 크기보다 큰 연속된 공간이 없을 경우에는 파일을 생성할 수 없음
• 논리적으로 연속된 레코드들이 물리적으로도 서로 인접하게 저장되므로 접근 시간이 줄어들고, 파일 디렉터리의 구현이 쉬움
• 파일이 제거되고 난 후의 빈 공간이 새로 저장되는 파일의 크기와 같지 않기 때문에 보조기억장치의 단편화 문제가 발생하고, 이를 해결하기 위한 보조기억장치 압축 작업이 필요함.
• 파일의 크기가 시간이 지남에 따라 파일크기가 변하기 때문에 정확한 크기로 공간을 할당할 수 없는 문제로 인해 낭비가 발생할 수 있음

[ 불연속 할당 (Noncontiguous Allocation) 기법 ]

• 파일을 작은 단위로 나누고, 보조기억장치의 불연속적인 공간을 나누어 할당 받는 기법
• 보조기억장치의 불연속적인 공간 단위에 따라 섹터 단위 할당과 블록 할당이 있다.

[ 섹터 단위 불연속 할당 기법 - 불연속 할당 기법 구현 방식 중 하나 ]

• 디스크 상에 있는 하나의 파일은 여러 개의 섹터 단위로 나누어 저장을 한다.
• 동일한 파일에 속하는 섹터들은 포인터를 통해서 연결된 하나의 리스트를 이루도록 저장하는 방식
• 파일 관련 정보를 저장하는 파일 디렉터리는 해당 파일의 시작 주소와 마지막 주소에 대한 포인터를 가짐
• 데이터 삽입과 같이 파일을 더 확장할 필요가 생기면 추가 섹터를 할당 받아 연결 리스트에 추가함.
• 파일이 축소되는 경우에는 불필요한 섹터를 되돌려주는 방식을 사용함
• 보조기억장치 공간에 대한 압축과 같은 작업이 필요 없음.
• 단점: 파일의 읽기 작업을 위해 분산된 섹터를 찾고 접근하기 위해 연속 할당 기법에 비해 긴 탐색 시간이 필요함.
• 이유는, 섹터가 여러군데에 나눠져 있기 때문임.
• 추가적으로 연결 리스트 관리 및 포인터에 사용되는 공간 등에 따른 추가 비용이 발생한다는 단점이 있음.

[ 블록 단위 불연속 할당 기법 - 불연속 할당 기법 구현 방식 중 하나 ]

• 보조기억장치의 보다 효율적인 이용과 실행 과정 중에 발생하는 추가 비용의 문제를 줄이기 위한 연속 할당과 불연속 할당 기법의 절충된 방법이다. 연속된 섹터 몇 개를 하나의 블록으로 삼는 것임. ( 움직이는 비용이 많이 줄어듦 )
• 개별적인 섹터를 할당하는 대신에 연속된 섹터로 구성된 블록을 이용한다.
• 추가적인 공간 할당이 요구되면 현재 파일이 저장되어 있는 블록에서 가장 가까운 거리에 있는 블록을 선택하여 할당함.
• 블록 단위 불연속 할당 기법에서는 매번 파일에 접근할 때마다 해당 블록을 결정하고, 다시 해당 섹터를 결정한다.