4. CPU 스케줄링
1) 우선순위
- 프로세스별 우선순위를 판단해 PCB에 명시
- 우선순위가 높을수록 CPU의 자원을 더 빨리, 더 많이 할당함
- CPU 활용률을 고려해 우선순위를 할당
- 일반적으로 입출력 집중 프로세스가 CPU 집중 프로세스보다 우선순위가 높음
- 입출력 집중 프로세스
- 비디오 재생, 디스크 백업 작업을 담당하는 프로세스
- 입출력을 위한 대기 상태에 더 많이 머묾
- CPU 집중 프로세스
- 복잡한 수학 연산, 그래픽 처리를 담당하는 프로세스
- 실행 상태에 더 많이 머묾
2) 스케줄링 큐
- 동시다발적으로 자원을 요구하는 여러 프로세스를 효율적으로 관리하기 위해 사용
- 선입선출 구조를 따르지만 우선순위가 높은 프로세스가 있다면 그것 먼저 실행함
(1)준비 큐
- CPU를 이용하고자 하는 준비 상태의 프로세스의 PCB가 삽입됨
- 실행되는 프로세스가 타이머 입터럽트를 받을 경우 준비 큐로 이동
(2) 대기 큐
- 대기 상태에 있는 프로세스의 PCB가 삽입됨
- 실행 도중 입출력 작업을 수행하는 등 대기 상태로 전환될 경우 대기 큐로 이동
- 같은 입출력장치를 요구한 프로세스끼리 같은 대기 큐에서 대기함
3) 선점형 스케줄링과 비선점형 스케줄링
(1) 선점형 스케줄링
- 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링
ex. 타이머 인터럽트 기반 스케줄링 - 한 프로세스의 독점을 막고 여러 프로세스에 골고루 CPU 자원 배분 가능
- 문맥 교환 과정에서 오버헤드 발생 가능성이 있음
(2) 비선점형 스케줄링
- 어떤 프로세스가 CPU를 사용하고 있을 때 해당 프로세스가 종료되거나 대기 상태가 될 때까지 다른 프로세스가 끼어들 수 없는 스케줄링
- 문맥 교환 횟수가 적어 상대적으로 오버헤드 발생 가능성이 낮음
- 당장 사용해야 하는 프로세스더라도 계속 대기해야 하는 상황 발생
4) CPU 스케줄링 알고리즘
(1) 선입 선처리 스케줄링
- 준비 큐에 삽입된 순서대로 CPU를 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
- 먼저 삽입된 프로세스의 실행 시간이 오래 걸려 나중에 삽입된 프로세스의 실행이 지연되는 호위 효과가 발생할 수 있음
(2) 최단 작업 우선 스케줄링
- 준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식
- 기본적으로 비선점형 스케줄링 알고리즘으로 분류되나 선점형으로도 구현 가능
(3) 라운드 로빈 스케줄링
- 선입 선처리 스케줄링 + 타임 슬라이스
- 준비 큐에 삽입된 순서대로 CPU를 요청한 프로세스에게 할당하되 프로세스가 CPU를 사용하도록 정해진 시간인 타임 슬라이스만큼만 CPU를 이용하는 스케줄링 방식
- 선점형 스케줄링 알고리즘
- 프로세스가 정해진 시간을 모두 사용하고도 완료되지 않을 경우 문맥 교환이 발생해 다시 큐의 맨 뒤에 삽입됨
(4) 최소 잔여 시간 우선 스케줄링
- 최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
- 정해진 타임 슬라이스만큼 프로세스가 CPU를 이용하되 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택하는 스케줄링 방식
(5) 우선순위 스케줄링
- 프로세스에 우선순위를 부여하고 가장 높은 우선순위대로 실행하는 스케줄링 방식
- 우선순위가 낮은 프로세스는 계속 실행이 연기되는 아사 현상이 발생할 수 있음
- 아사 현상을 방지하고자 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 에이징 기법을 사용함
(6) 다단계 큐 스케줄링
- 우선순위 스케줄링의 발전된 형태
- 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식
- 프로세스들이 큐 사이를 이동할 수 없기에 아사 현상이 발생할 수 있음
(7) 다단계 피드백 큐 스케줄링
- 다단계 큐 스케줄링의 아사 현상을 보완한 스케줄링 방식
- 프로세스들이 큐 사이를 이동할 수 있다는 차이가 있음
5) 리눅스 CPU 스케줄링
(1) 스케줄링 정책
- 새로운 프로세스를 언제 어떻게 선택하여 실행할지를 결정하기 위한 규칙의 집합
- 상황에 따라 다양한 스케줄링 알고리즘을 사용하며 크게 5가지가 있음
- 실시간성이 강조된 프로세스에 적용
- SCHED_FIFO, SCHED_RR, SCHED_RT
- 일반적인 프로세스에 적용
- SCHED_NORMAL: 완전히 공평한 CPU 시간 배분을 지향하는 CFS CPU 스케줄러에 의해 스케줄링이 이루어짐
- 리눅스에서는 프로세스의 가중치를 고려한 가상의 실행 시간인 가상 실행 시간 정보를 유지하는데 CFS는 이를 활용해 가장 작은 프로세스부터 스케줄링함
5. 가상 메모리
- 실행하고자 하는 프로그램의 일부만 메모리에 적재해 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 하는 메모리 관리 기법
1) 물리 주소와 논리 주소
(1) 물리 주소
- 메모리의 하드웨어 상 실제 주소
(2) 논리 주소
- 프로세스마다 부여되는 0번지부터 시작하는 주소 체계
- CPU와 프로세스가 사용하는 주소 체계
- 중복되는 논리 주소의 번지 수가 존재할 수 있음
(3) 메모리 관리 장치 = MMU
- CPU와 메모리 사이에 존재하는 하드웨어
- 메모리가 이해하는 물리 주소와 CPU가 이해하는 논리 주소간 변환하는 역할을 함
2) 스와핑과 연속 메모리 할당
(1) 스와핑
- 현재 실행되고 있지 않은 프로세스를 보조기억장치의 일부 영역인 스왑 영역으로 쫓아내고 해당 빈 공간에 다른 프로세스를 적재하여 실행하는 메모리 관리 방식
- 스왑 아웃되었던 프로세스가 스왑 인될 때는 이전과 다른 물리 주소에 적재될 수 있음
- 스왑 아웃: 현재 실행되지 않은 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
- 스왑 인: 스왑 영역에 있는 프로세스가 다시 메모리로 옮겨오는 것
(2) 연속 메모리 할당
- 프로세스에 연속적인 메모리 공간을 할당하는 방식
- 프로세스 간 빈 공간이 생겼을 때 해당 공간보다 큰 프로세스를 적재하기 어려운 외부 단편화 문제가 발생할 수 있음
3) 페이징
-
프로세스 논리 주소 공간을 페이지라는 일정한 단위로 나누고 물리 주소 공간을 페이지와 동일한 크기의 프레임이라는 일정한 단위로 나눈 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
-
페이지 하나의 크기보다 작은 크기로 발생하게 되는 메모리 낭비인 내부 단편화 문제가 발생할 수 있음
(1) 페이지 아웃과 페이지 인
- 페이지 단위로 스왑 아웃, 스왑 인을 하는 것을 말함
- 페이지는 물리 메모리 내 불연속적으로 배치될 수 있으므로 다음으로 실행될 페이지의 위치를 찾기 어려움
(2) 페이지 테이블
- 프로세스의 페이지와 실제로 적재된 프레임을 짝지어주는 정보
- 불연속적으로 배치된 페이지가 어떤 프레임에 적재되어 있는지 확인 가능
- 프로세스마다 각자의 페이지 테이블 정보를 가지고 있음
(3) 페이지 엔트리
- 페이지 테이블을 구성하고 있는 각각의 행
- 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트를 정보로 가짐
- 유효 비트
- 해당 페이지에 접근 가능한지 알려주는 정보
- 페이지가 메모리에 적재되어 있다면 1, 아니라면 0이 됨
- 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트 예외 발생
- 페이지 폴트 발생 시 해당 페이지를 메모리로 가져와 유효 비트를 1로 바꿔주는 페이지 폴트 처리 루틴이 실행됨
- 보호 비트
- 페이지 보호 기능을 위해 존재하는 비트
- 참조 비트
- CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타내는 비트
- 수정 비트 = 더티 비트
- 해당 페이지에 데이터를 쓴 적이 있는지의 여부를 알려주는 비트
(4) 페이지 테이블 베이스 레지스터(PTBR)
- 특정 프로세스의 페이지 테이블이 적재된 메모리 상의 위치를 가리키는 레지스터
- 프로세스마다 가지고 있는 정보로 각 PCB에 기록됨
- 다른 프로세스로의 문맥 교환 발생 시 변경됨
(5) TLB
- 페이지 테이블의 캐시 메모리를 사용해 메모리 접근 시간을 줄이는 방식
- 참조 지역성의 원리에 근거해 자주 사용할 법한 페이지를 예상해 페이지 테이블의 일부 내용을 저장함
(6) 계층적 페이징
- 페이지 테이블을 페이징하는 방식
- 페이지 테이블을 계층적으로 구성해 CPU에 가장 가까운 페이지 테이블만 메모리에 유지함으로써 메모리 용량을 줄일 수 있음
(7) 페이징 주소 체계
- 페이지 번호: 몇 번째 페이지 번호에 접근할지를 나타내는 정보
- 변위: 접근하려는 주소가 페이지 시작 번지로부터 얼마나 떨어져 있는지를 나타내는 정보
4) 페이지 교체 알고리즘
- 요구 페이징을 통해 페이지를 메모리에 적재하는 과정에서 메모리가 가득차 스왑 아웃해야 할 때 보조기억장치로 내보낼 페이지를 선택하는 방법
(1) 요구 페이징
- 메모리에 필요한 페이지만을 적재하는 기법
- CPU가 특정 페이지에 접근하는 명령어를 실행하면 해당 페이지가 메모리에 있는지에 따라 페이지 폴트 처리 루틴을 실행하거나 페이지에 적재된 프레임에 접근함
- 순수 요구 페이징
- 메모리에 적재하지 않은 채 프로세스를 실행함
- 초기엔 페이지 폴트가 발생하나 페이지가 메모리에 적재되며 발생 빈도가 떨어짐
(2) FIFO 페이지 교체 알고리즘
- 메모리에 가장 먼저 적재된 페이지부터 스왑 아웃하는 페이지 교체 알고리즘
- 초기에 적재되어 참조되고 있는 페이지를 스왑 아웃해 페이지 폴트가 발생할 수 있음
(3) 최적 페이지 교체 알고리즘
- 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
- 앞으로 가장 적게 사용할 페이지를 스왑 아웃해 가장 낮은 페이지 폴트율을 보장하는 알고리즘
- 미래를 예측하기 어려우므로 실제 구현하기 어려운 알고리즘
(4) LRU 페이지 교체 알고리즘
- 가장 적게 사용한 페이지를 교체하는 알고리즘
- 보편적으로 사용되는 페이지 교체 알고리즘의 원형
6. 파일 시스템
- 보조기억장치의 정보를 파일 및 디렉터리(폴더) 형태로 저장하고 관리할 수 있도록 하는 운영체제 내부 프로그램
1) 파일과 디렉터리
(1) 파일
- 파일의 이름, 파일을 실행하기 위한 정보, 파일과 관련한 부가 정보인 속성 또는 메타데이터로 구성됨
- 운영체제에 의해 파일을 다루는 모든 작업이 이루어지므로 시스템 콜을 이용해야 함
- 시스템 콜을 통해 파일을 할당받고 사용 중인 파일을 구분하기 위해 파일 디스크립터 사용
- 프로세스가 새로 파일을 열거나 생성할 때 운영체제가 해당 파일에 대한 파일 디스크립터를 프로세스에 할당
- 파일 디스크립터
- 저수준에서 파일을 식별하는 정보
- 0 이상의 정수 형태를 띄고 있음
- 저수준의 파일 식별 및 입출력에 자주 사용
(2) 디렉터리
- 여러 파일들을 관리하기 위해 사용
- 계층적 구조를 띄는 트리 구조 디렉터리로 관리됨
- 디렉터리에 속한 요소의 관련 정보가 포함된 파일로 간주됨
- 슬래시(/)를 디렉터리를 구분하는 구분자로 사용
- 경로: 디렉터리 정보를 활용해 파일 위치를 특정하는 정보
- 디렉터리 엔트리: 테이블 형태로 표현된 정보의 행 하나
2) 파일 할당
(1) 블록
- 파일과 디렉터리를 읽고 쓰는 단위
- 하나 이상의 블록을 할당받아 하나의 파일이 보조기억장치에 저장됨
- 블록 하나 = 4096byte
(2) 연결 할당
- 각 블록의 일부에 다음 블록의 주소를 저장하여 각각의 블록이 다른 블록 가리키는 형태로 할당하는 방식
- 디렉터리 엔트리에 파일 이름, 파일을 이루는 첫 번째 블록 주소, 파일을 이루는 블록 단위 길이 명시
- 디렉터리 엔트리로 어떤 파일이 어디에 저장되어 있는지를 파악함
(3) 색인 할당
- 색인 블록에 파일을 이루는 모든 블록의 주소를 모아 관리하는 방식
- 디렉터리 엔트리에 파일 이름, 색인 블록 주소 명시
- 색인 블록만 알면 접근하려는 파일 데이터에 접근 가능
3) 파일 시스템
(1) 포매팅
- 파일 시스템을 설정하여 어떤 방식으로 파일을 저장하고 관리할 것인지 결정하고 새로운 데이터를 쓸 준비를 하는 작업
- 보조기억장치를 포매팅할 때 어떤 파일 시스템을 사용할지 결정할 수 있음
(2) 아이노드 기반 파일 시스템
- 색인 블록인 아이노드를 기반으로 파일을 할당하는 방식
- 파일마다 각각의 아이노드를 가지며 이 아이노드에는 각각의 번호가 부여됨
- 아이노드에는 파일 이름을 제외한 거의 모든 정보가 담겨 있음
- 파티션 내 특정 영역에 아이노드가 모여 있음
- 데이터 영역에 공간이 남아 있더라도 아이노드 영역이 가득 차 더이상 아이노드를 할당할 수 없다면 새로운 파일 생성 불가능
(3) 마운트
- 어떤 저장장치의 파일 시스템에서 다른 저장장치의 파일 시스템으로 접근할 수 있도록 파일 시스템을 편입시키는 작업
