CPU 스케줄링 / CPU스케줄링 방법 / 외부단편화 , 내부단편화 / 외부단편화 해결방법 / First Fit, Best Fit, Worst Fit / 페이지교체 알고리즘 / 운영체제에서 기아상태란 / 운영체제에서 에이징/ 세그먼테이션

cs 메모장

CPU 스케줄링 / CPU스케줄링 방법 / 외부단편화 , 내부단편화 / 외부단편화 해결방법 / First Fit, Best Fit, Worst Fit / 페이지교체 알고리즘 / 운영체제에서 기아상태란 / 운영체제에서 에이징/ 세그먼테이션

nakgopsae 2024. 7. 15. 09:36

CPU 스케줄링

CPU 스케줄링은 운영 체제가 CPU 자원을 여러 프로세스에 효율적으로 배분하기 위해 사용하는 방법입니다
운영체제의 CPU 스케줄러는 Ready Queue 에 있는 프로세스들을 스케줄링 정책에 따라 Queue에 정렬하고 앞에 있는 프로세스부터 cpu에  할당 합니다
이를 통해 CPU 사용률을 최대화하고, 응답 시간, 처리량, 대기 시간을 최적화합니다

연관개념

프로세스 상태

생성: 사용자에 의해 프로세스가 생성된 상태
준비: cpu를 할당 받을수 있는 상태
실행: cpu할당받아 동작(점유) 중인 상태
대기: 프로세스 실행 중 입출력 처리등으로 cpu를 양도하고 처리 완료 까지 기다리는 상태
종료: 프로세스가 cpu를 할당 받아 주어진 시간내에 완전히 수행을 종료한 상태

디스패쳐 / Dispatcher

디스패처는 CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 주는 모듈이다.
디스패쳐(Dispatcher)는 운영 체제의 중요한 구성 요소로, 스케줄러가 선택한 프로세스를 실제로 CPU에 할당하는 역할을 합니다.

문맥 전환(Context Switching)
사용자 모드에서 커널 모드로 전환
프로그램 카운터 설정
타이머 설정
등의 역할을 합니다

스케줄링이 일어나는 경우 4가지

1. 실행상태의 프로세스가 대기상태로 전환 되었을 경우 : 현재 실행 중인 프로세스가 더 이상 CPU를 사용하지 않기 때문에, 운영 체제는 준비 상태에서 다음에 실행할 프로세스를 선택해야 합니다.

2. 실행 상태의 프로세스가 준비상태로 전환 되었을 경우: 현재 실행 중인 프로세스는 준비 상태로 돌아가고, 스케줄러는 다른 준비 상태의 프로세스를 선택하여 실행해야 합니다

3. 대기 상태의 프로세스가 준비 상태로 전환 되었을 경우 : 이때 새롭게 준비 상태가 된 프로세스가 있을 경우, 스케줄러는 우선순위를 고려하여 이 프로세스를 즉시 실행할지 여부를 결정해야 합니다.

4. 실행상태의 프로세스가 종료되었을 경우 : 현재 실행 중인 프로세스가 종료되면, CPU가 비게 되므로 스케줄러는 준비 상태에서 다음에 실행할 프로세스를 선택해야 합니다.

CPU스케줄링 방법

선점형과 비선점형 방식이 있는데 

선점형:하나의 프로세스가 cpu를 차지하고 있을때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단 시키고 cpu를 점유하는 스케줄링 방식
우선순위가 높은 프로세스를 빠르게 처리할 수 있다
우선순위가 높은 프로세스들이 계속 들어 오는 경우 오버헤드 발생

종류 : 

라운드 로빈(Round Robin) : 프로세스는 같은 크기의 CPU 시간을 할당 (균등한 CPU 점유 시간)하고 할당된 시간 내에 처리 완료를 못한다면, 준비 큐 리스트의 가장 뒤로 보내지고 CPU는 대기 중인 다음 프로세스로 넘어간다

SRTF(Shorttest Remaining Time First): 가장 짧은 소요시간이 걸리는 프로세스를 먼저수행하고 남은 처리시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점된다

+ 다단계 큐 다단계 피드백 큐(MLFQ, Multi-Level Feedback Queue)



비선점형: 하나의 프로세스가 cpu를 할당 받으면 작업 종료 후 cpu 반환시 까지 다른 프로세스가 cpu를 점유 할 수 없는 스케줄링 방식
모든 프로세스에 대한 요구를 공정하게 처리 
짧은 작업을 수행하는 프로세스가 긴 작업 종료시 까지 대기

종류:

FCFS(First Come First Served): 프로세스가 대기 큐에 도착한 순서에 따라 cpu를 할당 Queue와 동일 FIFO 알고리즘

SJF(Short Job First): FCFS를 보완하기 위해 만들어짐 / 프로세스가 도착하는 시점에 따라 그당시 가장 짧은 소요 시간을 갖는 프로세스가 종료시까지 CPU점유 / CPU 요구시간이 긴 작업과 짧은 작업간의 불평등이 심해 기아현상 발생가능성이 존재한다


HRN(Higtest Response-ratio Next): 실행이 긴 SJF를 보완하기 위한 기법 / 대기시간과 실행시간을 이용한다 우선순위 계산 결과값이 높은 것부터 우선순위를 부여하며 대기시간이 긴 프로세스일 경우 계산 결과값이 높게 나온다

+ 선순위(Priority) , 기한부(Deadline)

외부단편화 , 내부단편화

단편화 : 주기억장치에 프로그램을 할당하고 반납하는 과정에서 발생하는, 사용되지 않는 작은 조각 공간을 단편화라고 합니다

외부 단편화 : 메모리 할당과 해제가 반복되면서 빈공간이 작은 조각들로 나뉘어져 사용할 수 없는 상태를 말합니다 충분한 전체 메모리가 있음에도 남은 공간이 연속적이지 않아  큰메모리 블록을 할당할 수 없는 문제가 발생합니다 

내부단편화: 메모리 할당 시 요청된 크기보다 큰 메모리 블록을 할당하게 되어 사용되지 않고 남는 공간이 생기는 현상을 말합니다. 메모리 낭비가 발생합니다

외부단편화 해결방법 / 압축

압축이란 주기억장치내에 분산되어있는 단편화된 공간을 통합하여 하나의 커다란 빈 공간을 만드는 작업을 의미합니다
흩어진 공간을 연속된 공간으로 만들어 기존에 할당할 수 없는 프로세스를 할당할 수 있습니다

First Fit, Best Fit, Worst Fit

fit은 프로세스를 남아있는 메모리에 적합시키는것입니다 

최초적합: 가장 최초로 발견되는 메모리 공간에 할당한다 탐색 시간이 짧고 빠르게 동작하지만, 외부 단편화를 일으킬 수 있습니다

최적적합: 모든 빈공간을 계산해서 프로세스를 할당했을 때 가장 남는 공간이 적은 곳에 할당한다 작은 빈 공간이 많이 생겨 외부 단편화를 증가시킬 수 있습니다

최악적합: 가장 큰 공간에 할당한다 남는 공간을 가장 크게 남겨야 다른 프로세스가 그 곳에 할당될 확률이 크다 최적과 반대의 사고 /큰 빈 공간이 줄어들어 큰 블록을 할당할 때 유리할 수 있지만, 내부 단편화가 발생할 수 있습니다

페이지교체 알고리즘

스왑영역:  스왑 영역은 물리적 메모리가 가득 찼을 때 메모리에서 제거된 페이지들을 임시로 저장하는 디스크 공간입니다.
스왑 영역을 통해 시스템은 실제 물리적 메모리보다 더 큰 가상 메모리 공간을 사용할 수 있습니다. 페이지 교체가 발생할 때,
선택된 페이지는 스왑 영역으로 보내지고, 필요한 페이지가 메모리로 불러와집니다.

간단한 알고리즘:

무작위: 대상 페이지를 선정하여 스왑영역으로 보낸다

FIFO(First in First out): 선입 선출 / 처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다

이론적알고리즘: 

최적(OPT/Optimal Page Replacement): 미래의 접근패턴을 보고 대상페이지를 선정하여 스왑영역으로 보낸다

최적 근접 알고리즘

LRU(Least Recently Used): 시간적으로 멀리 떨어진 페이지를 스왑영역으로 보낸다

LFU(Least Frequently Used): 사용빈도가 적은 페이지를 스왑영역으로 보낸다

NUR(Not Used Recently): 최근에 사용한 적이 없는 페이지를 스왑영역으로 보낸다

FIFO변형/2차 기회 알고리즘( Second Chance (Clock)): FIFO알고리즘을 변형하여 성능을 높인다

운영체제에서 기아상태란

운영체제의 기아상태란 

기아상태는 특정 프로세스가 자원을 오랫동안 할당받지 못해 무한정 대기하는 상황을 말합니다. 이는 주로 우선순위 스케줄링에서 우선순위가 낮은 프로세스가 높은 프로세스들에 의해 계속 밀려나면서 발생합니다.

교착상태와 차이점 

교착상태는 프로세스가 자원을 얻지못해 다음 처리를 하지 못하는 상태이고 기아상태는 프로세스가 원하는 자원을 계속 할당 받지 못하는 상태입니다 

교착 : 여러프로세스가 동일한 자원 점유를 원할때 // 찐따 
기아 : 여러프로세스가 자원을 점유하기위해 경쟁할때 특정 프로세스는 자원 할당이 안된다// 왕따

운영체제에서 에이징

에이징이란 기아상태를 방지하기 위해 우선순위가 낮은 프로세스의 우선순위를 시간이 지남에 따라 점진적으로 높여주는 기법입니다 
오래동안 기아상태였던 프로세스는 추후 자원을 할당 받을수 있게 됩니다

세그먼테이션

프로세스를 논리적인 단위인 세그먼트로 나누어 메모리를 할당하는 기법입니다  각 세그먼트는 프로세스의 다른 부분을 나타내며, 각 세그먼트는 크기가 다를 수 있습니다

장점: 내부단편화 분제가 해소되고 보호와 공유 기능을 수행할 수 있다 프로그램의 중요한 부분과 중요하지 않은 부분을 분리하여 저장할 수있고 같은 코드 영역은 한번에 저장할 수있다 

단점: 외부단편화가 생길수 있다

페이징과 다른점
페이징은 내부 단편화가 생길수 있습니다



페이징: 내부 단편화 O, 외부 단편화 X
세그먼테이션: 내부 단편화 X, 외부 단편화 O