운영체제 (2) - 스케줄링과 메모리

1. 스케줄링

멀티 프로세스 환경에서는 여러 프로세스가 모두 실행되어야 하지만 CPU 자원은 한정적이다.

스케줄링을 통해 모든 프로세스를 공평하게 실행해서 한정된 자원을 효율적으로 사용하는 것이 목적이다.

 

- 스케줄링의 단계 

장기 스케줄링 : 준비 큐에 어떤 프로세스를 넣을지 결정해서 메모리에 올라가는 프로세스의 수를 조절. 잡 스케줄링 또는 승인 스케줄링

중기 스케줄링 : 메모리에 로드된 프로세스의 수를 동적으로 조절. 많이 로드되면 스왑아웃과 스왑인을 통해 조절

단기 스케줄링 : 어떤 프로세스를 실행할지 결정. CPU 스케줄링

 

 

2. 스케줄링 알고리즘

단기 스케줄러가 어떤 프로세스를 실행할지 결정하는 데 사용한다.

 

- 비선점형 스케줄링 : 실행 중인 프로세스가 종료될 때까지 다른 프로세스를 실행할 수 없다.

   FCFS(First Come First Served) : 먼저 들어온 프로세스를 먼저 실행
   SJF(Shortest Job First) : 실행 시간이 짧은 프로세스가 우선 순위

   HRR(Highest Response Ratio First) : 가장 높은 응답 비율을 우선 순위

   * 기아 상태(starvation) : 우선순위가 높은 프로세스만 실행되면서 낮은 프로세스는 계속 실행되지 못하는 상태

 

- 선점형 스케줄링 : 실행 중인 프로세스를 중단하고 다른 프로세스를 실행할 수 있다.

   RR (Round Robin) : 우선순위없이 일정 시간(타임 퀀텀, 타임 슬라이스)동안 프로세스를 실행. 콘텍스트 스위칭때문에 오버헤드가 크지만 응답속도 빠름

   SRTF(Shortest Remaining Time First) : 대기 시간이 가장 짧게 남은 프로세스를 우선 실행. 기아 상태가 되기 쉬움

   멀티 레벨 : 준비 큐를 응답 속도가 중요한 것과 성능이 중요한 것으로 나눔

 

 

3. 논리 메모리와 물리 메모리

CPU가 프로세스를 처리할 때 보는 주소값과 실제 메모리 주소값은 다르다.

CPU가 보는 메모리 영역/주소 값을 논리 메모리 영역/논리 주소 또는 가상 메모리 영역/가상 주소라고 한다.

실제로 사용되는 메모리 영역/주소 값은 물리 메모리 영역/물리 주소라고 한다.

 

- 메모리 관리 장치(MMU) : 논리 주소를 물리 주소로 바꾸는 데 사용되는 장치. CPU 에 위치하고 메모리 접근 전에 거친다.

 

 

4. 연속 메모리 할당

멀티 프로세스 환경에서 여러 프로세스를 메모리에 연속적으로 로드

 

- 고정 분할 방식 : 메모리를 분할해서 프로세스 할당. 단편화 문제 발생 가능

* 단편화

외부 단편화 : 분할된 크기보다 더 큰 프로세스 할당 불가능. 메모리 압축을 통해 해결

내부 단편화 : 분할된 크기보다 작은 프로세스가 할당되면서 메모리 공간이 남는 경우

 

- 가변 분할 방식 : 프로세스 크기에 따라 메모리 공간 분할

최초 적합(first-fit): 프로세스 크기만큼 비어있는 메모리 공간에 차례대로 할당

최적 적합(best-fit): 프로세스 크기 이상의 메모리 공간 중에 가장 작은 곳에 할당. 메모리 크기 모두 확인해야 한다.

최악 적합(worst-fit): 프로세스 크기 이상의 메모리 공간 중에 가장 큰 곳에 할당. 메모리 크기 모두 확인해야 한다.

 

 

5. 비연속 메모리 할당

- 페이징 : 논리와 물리 메모리 영역을 일정 크기의 페이지와 프레임으로 나눈다. 페이지 테이블을 통해 페이지와 프레임 매핑

- 세그먼테이션 : 세그먼트로 분할해 할당. 세그먼트 테이블에 맵핑되고 세그먼트 시작 주소와 길이가 들어있다.

 

 

6. 가상 메모리

프로그램을 실행하면 디스크에 저장된 데이터를 메모리로 로드하는데, 메모리 공간이 한정되어 있다.

많은 프로그램을 실행하기 위한 방법이다.

프로세스의 일부만 메모리에 로드하고 나머지는 디스크에 둔다.

 

 

7. 요구 페이징(demand paging)

프로세스에서 필요한 페이지만 메모리에 로드하는 방법.
필요한 페이지가 물리 메모리에 있는지 테이블을 통해 확인하고, 테이블 폴드가 발생하면 스왑 인을 통해 디스크에서 가져온다. 
만약 빈프레임이 없으면 기존 로드된 페이지를 스왑 아웃하고 로드한다.

 

8. 스레싱(thrashing)

동시에 일정 수 이상의 프로그램을 실행했을 때 CPU 이용률이 떨어지는 상황

가상 메모리를 통해서 다중 프로그래밍을 하면 CPU 이용률이 올라가지만, 일정 수 이상이 되면 페이지 폴트가 자주 발생한다.

스왑 인, 아웃도 빈번히 발생하면서 CPU 이용률이 떨어진다.

 

워킹 셋(working set)으로 예방 : 지역성을 기반으로 자주 사용하는 페이지를 저장해두는 것

 

 

8. 캐시 메모리

CPU와 메인 메모리 간에 데이터 접근 속도를 줄이기 위해 사용한다.

자주 사용하는 데이터를 캐시 메모리에 저장하는 것

 

시간 지역성(time locality) : 최근에 참조할 내용을 다시 참조할 가능성이 높다.

공간 지역성(space locality) : 참조한 주소 근처의 내용을 참조할 가능성이 높다.