[CS] 운영체제 기초 지식 정리 (2/3)

스케줄링

• CPU 자원은 한정적 → 스케줄링을 통해 모든 프로세스를 공평하게 실행해 한정된 자원을 효율적으로 활용하는 것이 OS의 주요 목적.

스케줄링의 목적

• 멀티 프로세스 환경에서 모든 프로세스를 공평하게 실행하는 것
• 5가지 목적
  • 공평성 - 모든 프로세스가 공평하게 실행되어야 함. 특정 프로세스가 실행되지 않는 경우가 없도록 스케줄링해야 함.
  • 효율성 - 자원을 효율적으로 사용해 자원이 사용되지 않는 시간이 없도록 스케줄링 해야 함.
  • 안정성 - 우선순위를 고려해 높은 우선순위의 프로세스를 먼저 처리하도록 스케줄링 해야 함.
  • 반응 시간 보장 - 프로세스가 오랜 시간 응답이 없으면 사용자는 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록 스케줄링해야 함.
  • 무한 연기 방지 - 특정 프로세스에 대한 처리가 무한히 연기되지 않도록 스케줄링해야 함.

스케줄링의 단계

• 장기 스케줄링
  • 준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수를 조절.
  • 잡 스케줄링 또는 승인 스케줄링이라고도 함.
  • 현대 운영체제에서는 시분할 시스템을 사용하기 때문에 대부분 사용하지 않음.
• 중기 스케줄링
  • 메모리에 로드된 프로세스 수를 동적으로 조절.
  • 메모리에 프로세스가 많이 로드되면 스왑 아웃해서 일부 프로세스를 통째로 저장.
  • 스왑 아웃된 프로세스는 중단 상태가 됨. 중단 상태는 준비상태에서 스왑 아웃된 중단된 준비 상태와 대기 상태에서 스왑 아웃된 중단된 대기 상태로 구분.
    • 스왑 아웃 : 프로세스가 실행되려면 메모리에 로드되어야 함. 그런데 메모리 공간보다 많은 프로세스가 로드되는 경우가 있을 수 있음. 이럴 때 중기 스케줄러가 이벤트 발생을 기다리고 있는 프로세스를 통째로 저장 공간으로 옮겨 저장하는 것.
    • 스왑 인 : 스왑 아웃한 프로세스에서 이벤트 요청이 오면 해당 프로세스를 통째로 다시 메모리에 로드하는 것.
    • 스와핑 : 스왑 아웃과 스왑 인처럼 프로세스를 통째로 메모리 영역과 저장 공간으로 옮기는 것. 스와핑하면 메모리 공간보다 많은 프로세스를 실행 가능.
• 단기 스케줄링
  • 준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할지 스케줄링 알고리즘으로 결정. 즉, 어떤 프로세스를 디스패치할지 결정하는데 이를 CPU 스케줄링 이라고도 함.

스케줄링 알고리즘

• CPU 스케줄러가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는 데 사용.
• 스케줄링 알고리즘 평가 기준
  • CPU 사용률 - CPU를 놀리지 않고 사용하는지 판단
  • 처리량 - 단위 시간 당 실행한 프로세스 수
  • 응답 시간 - 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간
  • 반환 시간 - 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간
  • 대기 시간 - 프로세스가 대기 큐에서 대기하는 시간의 총합
• 스케줄링 알고리즘은 비선점형과 선점형으로 나뉨
• 비선점형 스케줄링 - 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없음.
  • FCFS 스케줄링 : 준비 큐에 먼저 들어온 프로세스가 우선순위를 갖는 알고리즘. 준비 큐에 먼저 들어온 프로세스를 먼저 실행
  • SJF 스케줄링 : 실행 시간이 짧은 프로세스가 우선순위를 갖는 알고리즘. SJN 스케줄링이라고도 함. 준비 큐에 있는 프로세스 중 CPU를 점유하는 실행 시간이 가장 짧은 프로세스부터 실행. 평균 대기 시간이 가장 짧지만, 실행시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 밀려 기아 상태가 될 수 있음.
  • HRRN 스케줄링
• 선점형 스케줄링 - 스케줄러가 실행 중인 프로세스를 중단시키고 다른 프로세스를 실행할 수 있음.
  • RR 스케줄링 - 모든 프로세스를 순서대로 일정 시간 동안 실행하며, 일정 시간(타임 슬라이스)을 초과하면 다른 프로세스를 실행. Context Switching이 빈번하게 일어나서 오버헤드가 큼. 모든 프로세스가 반복 수행되어 응답 속도가 빠름.
    • 타임 슬라이스는 일반적으로 10~100밀리초
  • STRF 스케줄링 : 준비 큐에서 대기 시간이 가장 짧게 남은 프로세스를 우선 수행하는 알고리즘. 한 프로세스가 실행 중일 때 실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 CPU를 차지하게 됨. 평균 대기 시간이 짧음. 수행 시간이 긴 프로세스는 기아 상태가 되기 쉬움.
  • 멀티 레벨 스케줄링 : 준비 큐를 목적에 따라 여러 개로 분리해 사용하는 알고리즘. 분리한 큐는 각각 우선순위가 있고 각자 다른 스케줄링 알고리즘을 적용 가능.
    • foreground queue와 background queue로 나뉨.
    • foregroud queue는 응답 속도가 중요한 프로세스가 들어감.
    • backgroud queue는 응답 속도보다 성능을 중요시하는 프로세스가 들어감.

---

메모리 관리 전략

• 다수의 프로세스를 실행하려면 한정된 메모리 공간에 많은 프로세스를 로드할 수 있어야 함.

논리 메모리와 물리 메모리

• CPU가 프로세스를 처리할 때 보는 주소 값과 실제 메모리의 주소 값은 다름.
• 논리 메모리 영역 or 가상 메모리 영역 : 프로세스가 보는 메모리 영역
• 물리 메모리 영역 : 실제로 사용되는 메모리 영역
• 논리 주소 or 가상 주소 : CPU 프로세스를 실행하며 보는 주소 값.
• 물리 주소 : 실제 메모리에서 사용되는 주소
• CPU가 프로세스를 실행할 때 사용하는 주소 값과 실제 주소 값이 다르므로 논리 주소를 물리 주소로 변화해 줘야 하는데, 이러한 동작을 하는 하드웨어 장치를 메모리 관리 장치(MMU) 라고 함.
  • MMU는 CPU에 위치하며, CPU에서 메모리에 접근하기 전에 MMU를 거쳐 논리 주소에 해당하는 물리 주소를 얻음.
  • MMU는 보호해야 하는 메모리 영역에 대한 접근을 제한해 메모리를 보호하는 역할을 함.

연속 메모리 할당

• 멀티 프로세스 환경에서 여러 프로세스를 메모리에 연속적으로 로드하는 방법
• 고정 분할 방식
  • 메모리 여역을 분할한 뒤 각 영역에 프로세스를 할당하는 방식.
  • 분할된 영역의 크기는 서로 다를 수 있으며, 분할된 크기는 고정됨.
  • 메모리에 올릴 수 잇는 프로세스 수와 각 프로세스 크기가 제한됨. → 단편화 문제 발생 가능.
  • 외부 단편화 - 프로세스를 할당한 공간이 없어 할당하지 못하는 경우
    • 메모리 집약으로 해결 가능. 프로세스가 사용 중인 메모리 공간을 재배치해서 흩어져 있는 가용 메모리 공간을 하나로 합침.
  • 내부 단편화 - 고정 분할한 크기보다 작은 프로세스가 할당되어 메모리 공간이 남는 경우
• 가변 분할 방식
  • 할당할 프로세스의 크기에 따라 메모리 공간 분할하는 방식
  • 메모리 할당 알고리즘을 이용해 가용 메모리 공간에서 프로세스가 로드될 수 있는 메모리 공간을 찾음.
  • 최초 적합 - 가용 메모리 공간에서 프로세스 크기만큼 비어 있는 메모리 공간을 찾아 차례대로 프로세스를 로드하는 방식.
  • 최적 적합 - 할당하려는 프로세스 크기 이상인 가용 메모리 공간 중에서 가장 작은 공간에 프로세스를 할당하는 방식. 가용 메모리 공간을 모두 탐색해야 함.
  • 최악 적합 - 할당하려는 프로세스 크기보다 큰 가용 메모리 공간 중에서 가장 큰 공간에 프로세스를 할당하는 방식

비연속 메모리 할당

• 프로세스의 메모리 영역을 나눠서 메모리 공간에 저장하는 방법.
• 페이징
  • 프로세스의 논리 메모리 영역과 물리 메모리 영역을 각각 일정한 크기의 페이지와 프레임으로 나눔.
  • 프로세스의 논리 메모리 영역과 물리 메모리 영역을 각각 일정한 크기의 페이지와 프레임으로 나눔. 페이지와 프레임 크기는 동일.
  • 페이지와 프레임에는 각각 번호를 할당해 프로세스의 페이지와 메모리의 프레임을 매핑. 페이지 테이블 사용.
    • 페이지 테이블 - 프로세스의 페이지 정보와 페이지에 매핑하는 프레임의 주소 값을 저장. 각 프로세스의 PCB에 저장됨.
  • 페이징 기법을 사용하면 페이지를 물리 메모리에 연속으로 할당할 필요가 없어서 외부 단편화 문제 해결 가능.
  • 프로세스 크기가 페이지 수로 나누어 떨어지는지는 보장 못 함. → 프로세스의 마지막 페이지가 페이지 크기보다 작을 수 잇으므로 내부 단편화 밠애 가능. 페이지 테이블을 저장하기 위한 메모리 공간이 추가로 필요.
  • 계층적 페이징 : 페이지 테이블을 다시 페이지로 나눠 페이지 테이블 자체를 페이징하는 방식. 멀티 레벨 페이징 이라고도 함.
  • 해시 페이지 테이블 : 해시 테이블의 각 항목에 저장된 연결 리스트에 페이지 번호를 해싱한 뒤에 첫 번째 요소와 가상 페이지 번호를 비교하는 방식.
  • 역 페이지 테이블 : 프레임을 이용해 페이지를 찾는 방식. 페이지로 프레임을 찾는 기존 방식과 반대.
• 세그멘테이션
  • 프로세스의 메모리 영역을 논리적 단위인 세그먼트로 분할해 메모리를 할당.
  • 논리적 단위는 파일 내 함수 단위나 프로세스의 스택, 힙과 같은 영역을 의미하기도 함.
  • 세그멘테이션 테이블을 사용해 세그먼트의 논리 주소를 물리 주소로 매핑.
  • 세그먼트 테이블은 세그먼트 번호를 인덱스로 사용하며, 세그먼트별 시작 주소인 base와 세그먼트 길이인 limit를 저장.
  • 프로세스의 메모리 영역을 논리적 단위로 나눠 저장하므로 단위별로 데이터를 보호하기 쉬움.
  • 세그먼트의 크기가 균등하지 않아서 프로세스의 할당/해제를 반복하는 과정에서 외부 단편화 문제 발생 가능.
  • 메모리에 로드된 스택 세그먼트 영역에서 오버플로가 발생하면 다른 프로세스와 메모리 영역이 겹칠 수 있음. → 다른 프로세스의 세그먼트나 스택 오버플로가 발생한 세그먼트를 디스크로 스왑 아웃해야 함.