[정처기 필기] 프로세스 스케쥴링, 기억 장치 관리 전략, 가상 기억 장치, 세그먼테이션, 워킹 셋, 스레싱

프로세스 스케쥴링

• 프로세스의 생성 및 실행에 필요한 시스템의자원을 해당 프로세르에 할당하는 작업이다.
• 다중 프로그래밍 운영체제에서 자원의 성능을 향상시키고 효율적인 프로세서의 관리를 위해 작업 순서를 결정하는 것이다.

 

프로세스 스케쥴링의 목적

• 모든 작업들에 대한 공평성 유지
• 단위 시간당 처리량 최대화
• 응답 시간 및 반환 시간 최소화
• 운영체제의 오버헤드 최소화

 

프로세스 스케쥴링 기법 - 비선점(Non-Preemptive) 스케쥴링

• 한 프로세스가 일단 CPU를 할당받으면 다른 프로세스가 CPU를 강제로 빼앗을 수 없고, 사용이 끝 날 때 까지 기다리는 방식이다.
• 모든 프로세스들에 대한 요구를 공정히 처리하여 응답 시간의 예측이 용이하다
• CPU의 사용 시간이 짧은 프로세스들이 사용 시간이 긴 프로세스들로 인하여 오래 기다리는 경우가 발생할 수 있다.

 

FIFO(First In First Out)

• 준비 상태 큐에 도착한 순서대로 CPU를 할당하는 기법
• FCFS(First Come Fisrt Service)라고도 한다.
• 문제 예제) FIFO스케쥴링에서 다음과 같은 3개의 작업에 대하여작업 도착 시간 실행시간은 아래와 같다.
  모든 작업들의 평균 대기 시간 및 평균 반환 시간은?
  
  

  작업	도착시간	실행시간
  P1	0	13
  P2	3	35
  P3	8	10

  • 실행순서 : P1 → P2 → P3
  • 대기 시간 : P1(0), P2(10), P3(40)
  • 평균 대기 시간 : (0+10+40)/3 = 16.66
  • 반환 시간 : P1(13), P2(45), P3(50)
  • 평균 반환 시간 : (13+45+50)/3 = 36
•  

SJF(Shortest Job First)

• 준비 상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 스케쥴링 기법이다.
• 평균 대기 시간을 최소화한다.
• 문제 예제) SJF스케쥴링에서 다음과 같이 4개의 작업이 준비 상태 큐에 있을 때작업 실행시간은 아래와 같을 때 
  모든 작업들의 평균 대기 시간 및 평균 반환 시간은?

  작업	실행시간
  P1	6
  P2	3
  P3	8
  P4	7

  • 실행 순서 : P2 → P1 → P4 → P3
  • 대기 시간 : P2(0), P1(3), P4(9), P3(16)
  • 평균 대기 시간 : (0+3+9+16)/4 = 7
  • 반환 시간 : P2(3), P1(9), P4(16), P3(24)
  • 평균 반환 시간 : (3+19+16+24)/4 = 13

HRN(Highest Reponseratio Next)

• 어떤 작업이 서비스받을 시간과 그 작업이 서비스를 기다린 시간으로 결정되는 우선순위에 따라 CPU를 할당하는 기법이다
• 우선순위 계산식 = (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간
• 문제예제) HRN 방식으로 스케쥴링 할 경우, 입력된 작업이 다음과 같을 때 처리되는 작업 순서는

  작업	대기시간	서비스(실행) 시간
  P1	5	20
  P2	40	20
  P3	15	45
  P4	20	20

  답 ⬇︎ 

 

기억 장치 관리 전략 - 배치전략

보조 기억 장치에 보관 중인 프로그램이나 데이터를 주기억 장치 내의 어디로 가져올 것인지 결정하는 전략이다.

• 최초 적합(Fisrt-Fit)
• 적재 가능한 공간 중에서 첫 번째 분할 영역에 배치
• 최적 적합(Best-Fit)
• 적재 가능한 공간 중에서 가장 작은 공백이 남는 부분에 배치
• 최악 적합(Worst-Fit)
• 적재 가능한 공간 중에서 가장 큰 공백이 남는 부분에 배치

 

기억장치 관리 전략 - 기억 장치 교체 전략

주기억 장치의 모든 페이지 프레임이 사용 중일 때 어떤 페이지 프레임을 교체할 것인지 결정하는 전략

 

OPT(OPTimal Replacement)

• 이후에 가장 오랫동안 사용되지 않을 페이지를 먼저 교체하는 기법
• 실현 가능성이 희박하다.

 

FIFO(Fisrt In First Out)

• 가장 먼저 적재된 페이지를 먼저 교체하는 기법이다.
• 구현이 간단하다.

 

LRU(Last Frequently Used)

• 각 페이지마다 계수기나 스택을 두어 현시점에서 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

 

LFU(Laeast Frequently Used)

• 참조된 횟수가 가장 적은 페이지를 먼저 교체하는 기법이다.

 

NUR(Not Used Recently)

• 각 페이지당 두 개의 하드웨어 비트를 두어서 가장 최근에 사용하지 않은 페이지를 교체하는 기법이다.

 

SCR(Second Chance Replacement)

• FIFO의 단점을 보완하는 기법으로, 가장 오랫동안 주기억 장이체 상주했던 페이지 중에서 자주 참조되는 페이지의 교체를 예방한다.

 

가상 기억 장치(Virtual Memory)

• 주기억 장치의 부족한 용량을 해결하기 위해 보조 기억 장치를 주기억 장치처럼 사용하는 기법
• 가상 기억 장치의 일반적인 구현 방법에는 프로그램 고정된 크기의 일정한 블록으로 나누는 페이징 기법과 가변적인 크기의 블록으로 나누는 세그멘테이션 기법이 있다.

 

페이징(Paging) 기법

• 가상 기억 장치에 보관된 프로그램과 주기억 장치의 영역을 동일한 크기로 나눈 것이 페이지이다.
• 나눠진 프로그램을 동일하게 나눠진 주기억 장치의 영역에 적재시켜 실행하는 기법이다.
• 가상 기억 장치에서 주기억 장치로 주소를 조정(매핑)하기 위해 페이지의 위치 정보를 가진 페이지 맵테이블이 필요하다.
• 페이지의 크기가 클수록
  → 단편화가 증가하고
  → 전체 입출력 시간이 감소한다.
  → 디스크 접근 횟수가 감소하며
  → 페이지 맵 테이블의 크기가 작아지고

 

세그먼테이션(Segmentation) 기법

• 가상 기억 장치에 보관된 프로그램을 다양한 크기로 나눈 후, 나눠진 프로그램을 주기억 장치에 적재시켜 실행하는 기법이다.
• 세그먼트(Segment) :
  큰 프로그램을 보다 작은 프로그램으로 분할해서 하나의 논리적 단위로 묶어서 주기억 장치에 읽어 들일 수 있는 최소 단위이다.

 

워킹 셋(Working Set)

운영체제의 가상 기억 장치 관리에서 프로세스가 일정시간 동안 자주 참조하는 페이지들의 집합이다.

 

스레싱(Thrashing)

하나의 프로세스가 작업 수행 과정에 수행하는 기억 장치 접근에서 지나치게 페이지 부재가 발생하여 프로세스 수행에 소요되는 시간보다 페이지 이동에 소요되는 시간이 더 커지는 현상이다.