[CHAPTER - 03] 운영체제 - 2

4. CPU 스케줄링

• CPU 스케줄링 : 운영체제(OS)에서 여러 프로세스가 CPU를 사용하려고 할 때, 어떤 프로세스에 CPU를 할당할지 결정하는 메커니즘. 이는 효율적인 시스템 자원 활용과 공정성, 성능 최적화를 목표로 한다.
  - 운영체제는 프로세스의 우선순위를 판단하여 PCB에 명시하고 높은 우선순위를 가진 프로세스에 CPU의 자원을 더 빨리, 많이 할당한다.
• CPU 활용률 : 전체 CPU의 가동 시간 중 작업을 처리하는 시간의 비율
• CPU 버스트, 입출력 버스트 : 프로세스는 CPU와 입출력 장치를 모두 사용하며 실행과 대기를 번갈아가며 실행된다. 이 때 프로세스가 CPU를 이용하는 작업을 CPU 버스트, 입출력 장치를 기다리는 작업을 입출력 버스트 라고함.
• 스케줄링 큐 : CPU의 할당을 기다리거나 메모리에 적재되고 싶은 프로세스, 대기 상태로 특정 입출력 장치를 이용하고 싶은 프로세스들을 스케줄링 큐로 관리 (각 프로세스의 PCB를 큐에 담는다.)
  - 준비 큐 : CPU 할당을 기다리는 프로세스의 PCB가 삽입되는 곳
  - 대기 큐 : 대기 상태에 접어든 프로세스의 PCB가 삽입되는 곳

 

스케줄링 큐의 흐름

1. 입출력 작업을 수행하는 경우, 프로세스의 PCB는 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 기다림.
2. 새로운 프로세스의 PCB, 혹은 대기 상태에서 인터럽트를 받고 다시 준비 상태가 된 프로세스의 PCB는 준비 큐의 마지막에 삽입되어 CPU 할당을 기다림
3. 운영체제는 큐에 삽입된 프로세스를 순서대로 실행하되, 우선순위를 고려하여 실행함
4. 실행되던 프로세스가 타이머 인터럽트를 받으면 준비 큐로 이동하고, 입출력 작업을 수행해야 한다면 대기 큐로 이동

• 선점형 스케줄링 : 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링
• 비선점형 스케줄링 : 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식

 

CPU 스케줄링 알고리즘

1. 선입 선처리 스케줄링 (FCFS) : 준비 큐에 삽입된 순서대로 먼저 CPU를 요청한 프로세스부터 CPU를 할당
   • 먼저 삽입된 프로세스가 오래 실행되면, 나중에 삽입된 프로세스의 실행이 지연되어 성능 저하가 일어나는 단점 존재
2. 최단 작업 우선 스케줄링 (SJF) : 준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간이 가장 짧은 프로세스부터 실행하는 방식. 동일하면 선입 선처리 적용
   • 기본적으로는 비선점형 스케줄링 이지만, 선점형으로 구현이 가능함. (이 경우 최소 잔여 시간 우선 스케줄링으로 분류)
3. 라운드 로빈 스케줄링 (RR) : Time Quantum 또는 Time Slice라고 하는 작은 단위의 시간을 정의하여 각 프로세스에 이 시간을 할당함. 주어진 시간 간격만큼 수행한 후 프로세서를 양도. 순환+FIFO 큐로 설계
   
   
4. 최소 잔여 시간 우선 스케줄링 (SRT) : 정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택 (처음 들어온 프로세스가 있더라도 짧은 실행시간을 가진 프로세스가 선점)
   
   
5. 우선순위 스케줄링 (Priority) : 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행
   • 우선 순위가 낮은 프로세스가 무기한 연기되어 실행되지 못할 수 있는데, 이를 기아 상태라고 한다. 
   • 기아 상태를 방지하기 위해 오래 대기한 프로세스의 우선순위를 점차 높이는 에이징(aging) 방식이 있다.
6. 다단계 큐 스케줄링 (MLQ) : 우선순위 별로 여러 개의 준비 큐를 사용하는 방식. 우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리하고, 큐가 비어 있게 되면 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리.
   

 

7. 다단계 피드백 큐 스케줄링 (MFQ) : 다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있다. 오래 CPU를 사용해야 하는 프로세스들은 우선순위 큐에서 점점 내려감과 동시에 오래 실행되지 못한 프로세스들은 에이징 기법으로 우선순위를 높여준다.

 

 

5. 가상 메모리

• 물리 주소 : 실제 데이터나 프로그램이 저장되는 공간을 말한다. (메인 메모리의 사용 가능한 주소)
• 논리 주소 : 프로세스 마다 부여되는 0번지 부터 시작하는 주소 체계 (프로그램에서 사용하는 자료구조, 목적코드가 저장된 공간 등)
• CPU가 실제 정보가 저장되어 있는 하드웨어 상의 메모리와 상호작용하기 위해 논리 주소 → 물리 주소 변환이 필요하다. 이 때 그 사이에서 CPU가 이해하는 논리 주소를 메모리가 이해하는 물리 주소로 변환하는 것이 메모리 관리 장치(MMU)이다.
  
  
• 스왑 영역 : 오랫동안 사용되지 않은 프로세스들을 임시로 쫓아 내는 곳 (보조기억장치의 일부 영역)
• 스와핑 : 메모리에 적재되었지만 실행되고 있지 않은 프로세스를 쫓아내고 그 자리에 새로운 프로세스를 적재하여 실행하는 메모리 관리 방식
  - 메모리 → 스왑 영역 : 스왑 아웃
  - 스왑 영역 → 메모리 : 스왑 인
  - 스왑 아웃 되었던 프로세스가 다시 스왑 인이 될 때는 아웃 되기 전의 물리 주소와는 다른 주소에 적재될 수 있다.
  
  
• 연속 메모리 할당 : 프로세스가 연속적인 메모리 주소를 할당받아 배치되는 방식.
• 외부 단편화 : 프로세스들이 메모리에 연속적으로 할당되는 방식은 메모리 사이에 빈 공간을 만들게 되고 빈 공간보다 큰 프로세스를 적재하지 못해 공간 낭비, 즉 메모리가 낭비되는 현상이 발생
  - 이러한 문제를 해결하는 기술이 가상 메모리로, 실행하고자 하는 프로그램의 일부만 메모리에 적재하여 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 만드는 것. (메모리가 실제 크기보다 더 크게 보이게 하는 기술)
  
  
• 페이징 : 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 나누고, 물리 주소 공간을 페이지와 동일한 크기의 프레임이라는 일정한 단위로 나눈 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
  - 프로세스를 구성하는 페이지는 물리 메모리 내에 불연속적으로 배치될 수 있음.
  - 페이지라는 일정한 크기로 잘린 프로세스들을 메모리에 프레임 형태로 불연속적으로 할당하기 때문에 빈 공간이 생기지 않아 외부 단편화가 발생하지 않는다.
  
  
• 세그멘테이션 : 프로세스를 일정한 크기의 페이지 단위가 아닌 가변적인 크기의 세그먼트 단위로 분할한다. 한 세그먼트는 코드영역일 수도 있고 데이터 영역일 수도 있다. 세그먼트는 가변적인 크기를 가지기 때문에 외부 단편화가 발생할 수 있음.

페이징 & 세그멘테이션 ⇒ 페이지나 세그먼트 자체가 프로세스의 일부를 뜻하기 때문에 전체 프로세스가 메모리에 적재되지 않아도 된다는 점을 시사한다. CPU 입장에서 바라본 논리 메모리의 크기가 실제 메모리보다 클 수 있다는 것.

물리 메모리는 식당의 테이블 수라고 생각할 수 있음.

→ 논리 메모리는 예약 가능한 손님 수.

→ 손님이 모두 한 번에 올 필요가 없고, 순차적으로 테이블을 비우고 새 손님을 받을 수 있다면 예약 가능한 손님 수(논리 메모리)가 테이블 수(물리 메모리)보다 클 수 있음.

 

 

• 페이지 테이블 : 페이지는 물리 메모리 내에 불연속적으로 배치될 수 있다고 했는데, CPU가 다음으로 실행할 페이지의 위치를 찾기 어려울 때 프로세스의 페이지와, 실제로 적재된 프레임을 짝지어주는 정보를 담은 테이블
  - CPU는 페이지 테이블의 페이지 번호를 보고 적재된 프레임을 찾아갈 수 있음. (= 메모리에 접근할 수 있음)
  
  
• 테이블 엔트리 : 페이지 테이블을 구성하고 있는 각각의 행들로 대표적으로 페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트 등이 있다.
• 페이지 폴트 : CPU가 메모리에 적재되지 않은 페이지, 즉 유효 비트가 0인 페이지에 접근할 때 발생하는 예외.
  - 페이지 폴트가 발생하면 보조기억장치 속 페이지를 메모리에 적재한 뒤에 CPU가 다시 접근해야 한다.
  
  페이지 폴트 처리 과정
  1. 현재 실행 중인 작업 상태를 백업
  2. 원하는 페이지를 메모리로 가져와 유효 비트를 1로 변경 (페이지 테이블 갱신)
  3. 메모리에 적재된 페이지 실행
     
     
• 내부 단편화 : 페이징 방식이 야기할 수 있는 문제로 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것이 아님. 프로세스의 메모리와 데이터 크기가 페이지보다 작을 때 발생 (메모리 낭비)
• 페이지 테이블 베이스 레지스터 (PTBR) : 특정 프로세스의 페이지 테이블이 적재된 메모리 상의 위치를 가리키는 특별한 레지스터, PTBR은 프로세스마다 가지는 정보로 PCB에 저장됨.
  
  
• 요구 페이징
  1. CPU가 특정페이지에 접근하는 명령어를 실행한다. (5번 페이지, 변위 2라는 논리주소 <5, 2> 에 접근)
  2. 해당 페이지가 현재 메모리에 있을 경우, (유효 비트가 1) CPU는 페이지가 적재된 프레임에 접근함. 프레임 번호는 페이지 테이블에 존재하고, 프레임의 물리 주소가 시작하는 번지 수에 변위를 더한 주소에 접근하게 됨
  3. 페이지 폴트가 발생하면 처리 루틴을 통해 페이지를 메모리로 적재하고, 유효 비트를 1로 설정 (페이지 테이블 갱신)
  4. 반복

 

페이지 교체 알고리즘

1. FIFO 페이지 교체 알고리즘 : 메모리에 가정 먼저 적재된 페이지부터 스왑 아웃
2. 최적 페이지 교체 알고리즘 : 사용 빈도가 가장 낮은 페이지를 교체 (앞으로 가장 적게 사용할 페이지를 스왑 아웃, 그러나 미리 예측이 어려워 실제 구현은 어려운 알고리즘)
3. LRU 페이지 교체 알고리즘 : 가장 적게 ‘사용한’ 페이지를 교체하는 알고리즘. 보편적으로 사용됨

 

 

6. 파일 시스템

• 파일 시스템 : 보조기억장치의 정보를 파일 및 디렉토리의 형태로 저장하고 관리하는 운영체제 내부 프로그램
• 파일 디스크립터 : 운영체제에서 파일이나 I/O 리소스(소켓, 파이프 등)를 식별하고 관리하기 위해 사용하는 정수 값
  1. 프로세스가 open() 시스템 콜을 통해 파일을 열면 커널은 해당 파일의 디스크립터를 반환
  2. 파일 디스크립터는 해당 파일의 메타데이터(위치, 권한 등)를 커널 내부 테이블에 저장
  3. 파일 작업을 할 때 보통 파일 디스크립터가 사용됨.
  4. 작업이 끝난 파일 디스크립터는 close() 호출로 닫아야 함. (리소스 누수를 방지)
• 블록 : 운영체제는 파일과 디렉토리를 블록이라는 단위로 읽고 씀.
• 색인 할당 : 파일을 이루는 모든 블록의 주소를 색인 블록이라는 특별한 블록에 모아 관리