[정보처리기사 실기 이론정리12] 메모리 관리(단편화) & 가상기억장치(페이지 교체 알고리즘) & 프로세스(스케줄링 알고리즘)

1. 기억장치 관리 전략

• 반입(Fetch) 전략 : 보조기억장치에 보관 중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인지를 결정하는 전략

요구 반입 (Demand Fetch)	실행 중인 프로그램이 특정 데이터를 필요로 할 때 해당 데이터를 주기억장치로 적재
예상 반입(Anticipatory)	실행 중인 프로그램이 미래에 참조할 것으로 예상되는 데이터를 미리 주기억장치로 적재

• 배치(Placement) 전략 : 새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에 위치시킬 것인지를 결정하는 전략

최초 적합(First Fit)	사용 가능한 첫 번째 분할 영역에 프로그램이나 데이터를 배치
최적 적합(Best Fit)	단편화를 최소화하는 분할 영역에 배치
최악 적합(Worst Fit)	단편화를 최대화하는 분할 영역에 배치

• 교체(Replacement) 전략 : 이미 사용 중인 주기억장치 영역 중에서 새로운 프로그램이나 데이터를 위해 어떤 영역을 교체할 지 결정하는 전략 ex) FIFO, OPT, LRU, LFU 등

2. 단일 분할 할당 기법 :

• 경계 레지스터를 사용해 운영체제 영역과 사용자 영역을 구분
• 주기억장치보다 큰 프로그램을 실행하기 위해 오버레이 기법과 스와핑 기법을 사용

오버레이(Overlay)	- 보조기억장치에 저장된 프로그램을 여러 개의 조각으로 분할 - 필요한 조각만을 순서대로 주기억장치에 적재하여 프로그램을 실행 - 주기억장치의 공간이 부족할 경우, 필요하지 않은 조각이 위치한 장소에 새로운 프로그램 조각을 중첩하여 적재
스와핑(Swapping)	- 하나의 프로그램 전체를 주기억장치에 할당하여 사용하다가, 필요에 따라 다른 프로그램과 교체 - 가상기억장치의 페이징 기법으로 발전

3. 다중 분할 할당 기법 :

• 주기억장치를 여러 영역으로 나누어 프로그램을 할당
• 고정 분할과 가변 분할 기법이 있다.

4. 단편화 : 주기억장치에 프로그램 할당과 반납 과정에서 발생하는 빈 공간

내부 단편화	주기억장치 공간이 프로그램보다 커서 프로그램의 사용 공간을 할당 후 사용되지 않고 남아있는 공간
외부 단편화	주기억장치 공간보다 프로그램이 커서 할당되지 못한 남아있는 공간

예제 ex)

• 영역 1 : 분할크기 20K, 작업크기 10K => 내부단편화 10K
• 영역 2 : 분할크기 50K, 작업크기 70K => 외부단편화 50K

5. 단편화 해결 방법

• 통합 기법(Coalescing) : 인접한 두 개의 빈 분할 공간을 하나로 통합하여 메모리의 효율성을 높이는 작업
• 압축 기법(Compaction) : 주기억장치 내에 분산된 여러 단편화된 공간들을 하나의 큰 빈 공간으로 만드는 작업, 가비지 컬렉션 작업
• 재배치 기법(Relocation) : 압축과정에서 프로그램 주소를 새롭게 지정해주는 기법

 

6. 가상기억장치 : 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 기법

7. 페이징 기법: 가상기억장치를 모두 같은 크기의 블록(페이지)로 편성하여 운용하는 기법

• 외부 단편화는 발생하지 않으나 내부 단편화는 발생

페이지 크기	기억장소 효율	단편화	입출력 시간	맵 테이블
클수록	감소	증가	감소	감소
작을수록	증가	감소	증가	증가

8. 세그먼테이션 기법 : 가상 메모리를 크기가 다른 논리적 단위인 세그먼트로 분할하고 메모리를 할당하는 기법

• 내부 단편화는발생하지 않으나 외부 단편화는 발생

9. 페이지 부재 : 프로세스 실행 중 필요한 페이지가 주기억장치에 없는 상황

10. 지역성 : 프로세스가 실행되는 동안 주기억장치에서 일부 페이지만 집중적으로 참조하는 성질

시간 구역성(Temporal Locality)	- 하나의 페이지가 짧은 시간 동안 집중적으로 참조 - 반복, 스택, Sub Routine  emd
공간 구역성(Spatial Locality)	- 프로세스 실행 시 특정 위치의 페이지들이 집중적으로 참조 - 배열순회, 순차적 코드 실행 등

11. 워킹 셋(Working Set) : 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합

12. 스래싱(Thrashing) : 프로세스 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상

13. 페이지 교체 알고리즘

• FIFO(First In First Out) : 가장 먼저 메모리에 적재된 페이지를 먼저 교체하는 기법
• OPT(OPTimal relpacement, 최적 교체) : 미래에 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법
• LRU(Least Recently Used) : 가장 오랫동안 사용되지 않은 페이지를 교체하는 기법
• LFU(Least Frequently Used) : 사용 빈도가 가장 적은 페이지를 교체하는 기법
• NUR(Not Used Recently) : 각 페이지마다 참조 비트와 변형 비트를 사용하여 최근 사용 여부를 확인
• SCR(Second Chance Replacement) :  FIFO 단점을 보완한 기법, 가장 오래된 페이지 중에서도 자주 사용되는 페이지의 교체를 방지

14. 프로세스 : 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램, 실행 가능한 프로세스 제어 블록을 가진 프로그램

프로세스 영역	설명
코드 영역	- 실행할 프로그램의 코드가 저장되는 영역 - 함수, 제어문, 상수 등이 지정
데이터 영역	- 전역 변수와 정적 변수(Static)가 할당되는 부분 - 프로그램 종료 시 메모리에서 소멸
스택 영역	- 프로그램이 자동으로 사용하는 임시 메모리 영역 - 지역 변수와 함수의 매개변수가 저장 - 함수 호출이 완료되면 해당 정보는 사라진다.
힙 영역	- 프로그래머가 할당하고 해제하는 메모리 공간 - 동적 할당

15. 스레드 : 프로세스 내에서 실행되는 흐름의 단위

• 하나의 프로세스는 최소 하나 이상의 스레드를 가지며, 스레드는 경량 프로세스라고도 불린다.
• 스레드들은 부모 프로세스의 자원과 메모리를 공유하므로, 자원 공유가 용이하다.
• 동기화 문제와 교착상태(Deadlock)를 주의해야 한다.

16. 프로세스 상태 전이

17. PCB(Process Control Block, 프로세스 제어 블록)

• PCB는 운영체제가 프로세스의 정보를 저장하는 공간
• 각 프로세스가 생성될 때마다 고유한 PCB가 생성되며, 프로세스 종료 시 해당 PCB는 제거된다.

18. 문맥교환(Context Switching)

• 하나의 프로세스가 CPU 사용을 마치고 다른 프로세스가 CPU를 사용하도록 전환하는 과정
• 문맥교환이 일어나는 시점 : 멀티태스킹, 인터럽트 처리, 사용자 및 커널 모드 전환

19. 스케줄링 : 메모리에 올라온 프로세스들 중 어느 프로세스를 먼저 처리할지 순서를 정하는 것

• 프로세서 차원 : CPU 사용률, 처리량(Throughput)
• 프로세스 차원 : 
  응답시간(Response Time) : 대기 상태에서 CPU를 최초로 얻기까지 걸리는 시간
  대기시간(Waiting Time) :  CPU를 할당받기 전 대기하는 시간
  반환시간(Turn-around Time) : 프로세스 생성부터 종료 후 자원 반환까지 걸리는 시간

20. 스케줄링 기법

• 선점형 스케줄링(Preemptive) : 운영체제가 실행 중인 프로세스로부터 CPU를 강제로 빼앗을 수 있는 방식
• 비선점형 스케줄링(Non-Preemptive) : 프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식
• 기아현상(Starvation) :  시스템에 부하가 많아서 우선순위가 낮은 프로세스가 무한정 기다리는 현상
• 에이징 기법(Aging) : 기아현상을 해결하기 위한 기법, 오랫동안 기다린 프로세스에게 우선순위를 높여주는 기법

21. 선점형 스케줄링

• Round Robin :  시간단위를 정하여 프로세스에 순서대로 CPU를 할당하는 방식
• SRT(Shortest Remaining Time) : 남아있는 실행시간이 가장 짧은 프로세스에 CPU를 먼저 할당
• 다단계 큐(MLQ, Multi-Level Queue) : 프로세스를 특정 그룹으로 분류하고, 각 그룹에 따라 다른 준비 상태 큐를 사용하는 기법
• 다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue) : 프로세스가 생성되면 가장 높은 우선순위의 준비 큐에 등록되며, FCFS 순서로 CPU를 할당받아 실행. 단계가 내려갈수록 시간할당량이 증가하며, 가장 하위 큐는 round robin 방식으로 운영

22. 비선점형 스케줄링

• FCFS(First Come First Serve) : 먼저 도착한 프로세스를 먼저 처리하는 스케줄링 기법
• SJF(Shortest Job First) : 실행 시간이 가장 짧은 프로세스에게 CPU를 할당하는 기법, 기아현상이 발생할 수 있음
• HRN(Highest Response ratio Next) : 우선순위를 계산, 우선순위 = (대기시간 + 실행시간) / 실행시간