CPU Scheduling 알고리즘
프로세스 상태
스레드 상태
FIFO, FCFS
SJF
SRTF
RR
Semaphore와 Mutex, Spin lock , 모니터,
https://www.youtube.com/watch?v=NL9JQh5bbZ8
유튜브 시청기록
문맥교환,
장기스케줄
PCB
다단계 큐 스케줄링(Multilevel Queue Scheduling)
- 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 프로세스를 여러 개의 큐에 분류하여 관리하는 방식이다.
- 운영체제가 프로세스의 특성(ex : 프로세스의 우선순위, 작업 유형)에 따라 프로세스를 분류하여 각각 다른 스케줄링 알고리즘을 적용할 수 있도록 설계되었다.
- 예를 들어, 작업을 전면작업과 후면작업으로 분류한다면 두 유형의 요청 반응시간은 서로 다르므로 서로 다르게스케줄링 해야한다. -> 전면작업은 후면작업에 비해 우선순위가 높을 때가 많다.
특징
- 다단계 큐 스케줄링은 준비 상태 큐를 종류별(특정기준 ex> 우선순위, 프로세스 유형)로 여러 단계로 분할한다. 각 큐는 자신만의 고유한 스케줄링이나 알고리즘(ex > 라운드 로빈, 우선순위 스케줄링 등)을 가진다.
- 예를 들어 전면작업과 후면작업을 분할된 큐에 지정하면 전면 작업 큐는 라운드 로빈 스케줄링으로 작업하고, 후면 작업 큐는 선입선처리 스케줄링으로 관리할 수 있다.
- 이렇게 각 큐는 독립적으로 스케줄링 되며, 큐 간에 프로세스 이동은 일반적으로 제한된다. 이는 각 큐가 마치 별도의 스케줄러를 가진 것처럼 작동하게 한다.
- 큐 사이에도 스케줄링을 해야하는데 각 큐에는 고정된 우선순위가 할당되어있으며 이는 고정된 선점 우선순위 스케줄링이다. ex) 전면 작업 큐는 후면 작업 큐보다 절대적인 우선순위를 가질 수 있다.
- 우선순위가 같은 큐 내에서는 해당 큐의 스케줄링 알고리즘에 따라 프로세스에 CPU가 할당된다.
- 프로세스가 한 번 특정 큐에 할당되면, 그 프로세스의 우선순위나 요구사항이 변하더라도 다른 큐로 이동하기 어렵다.
- 우선순위가 높은 큐가 모두 비어있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없다.
- 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스보다 오랜시간 동안 CPU를 할당 받지 못할 수 있다.
- 선점 우선순위 스케줄링이므로 높은 우선순위 프로세스가 준비 큐에 들어오면 낮은 우선순위 큐는 CPU를 반납해야한다.
- 큐 사이에 시간을 나눠 사용할 수 있다. 각 큐는 프로세서 시간의 일정량을 받아서 큐에 있는 프로세스들을 스케줄링할 수 있다. ex) 전면 작업 큐는 자신의 프로세스 사이에서 라운드 로빈 스케줄링을 하는데 프로세서의 시간 80%를 할당하고, 후면 작업 큐는 선입선처리 방법으로 프로세스를 스케줄링하는데 프로세서의 시간을 20%할당할 수 있다.
장점
응답이 빠르다 -> 중요한 큐에 대해서는 응답이 빠른거 같음 .. 낮은 우선순위는 응답이 느리다.
단점
- 여러 준비 큐와 스케줄링 알고리즘 때문에 추가 오버 헤드가 발생한다.
- 우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아상태가 발생할 수 있다.
다단계 피드백 큐 스케줄링 (Multi-Level Feedback Queue Scheduler : MLFQS)
- 프로세스의 큐간에 이동이 허용된다.
- Feedback을 통해 우선순위가 조정된다. -> 우선순위가 동적이다.
- 현재까지의 프로세서 사용 정보(패턴) 활용
- 프로세스에 대한 사전정보 없이 SPN, SRTN, HRRN(HRN)기법의 효과를 볼 수 있다.
단점
설계와 구현이 매우 복잡하다, 스케줄링 overhead가 크다.
gpt , 책 2개 , 블로그 , 유튜브 내용 정리
뮤텍스와 이진 세마포어의 차이점
1. 뮤텍스는 소유권을 가지며 잠금을 한 스레드만이 해제할 수있지만, 이진 세마포어는 잠금과 해제를 다른 스레드가 할 수 있다.
2. 뮤텍스는 주로 상호배제 목적으로 사용되며, 이진 세마포어는 상호배제와 더불어 다른 스레드간의 동기화 문제를 해결한다.
3. 이진 세마포어는 다른 스레드에게 시그널을 통해 신호를 보내는 용도로 사용할 수있다.
4. 이진 세마포어는 상호배제 목적으로 사용된다.
5. 이진 세마포어에서 소유권이 없다는 문제는 다른 스레드가 잠금을 해제 할 수있다는 문제 였는데
가능성만 존재하고 상호배제를 안전하게 구현하기 위해서는 한스레드가 잠금과 해제를 동시에 하는 것이 좋다
6. 이진 세마포어 에서 소유권이 없다는 문제는 상호배제의 목적이 아니라 동기화에 초점을 맞춘것이다.
뮤텍스와 이진세마포어,,, 궁금했던점들
test and set
스핀락
오벌헤드가 적을 때
멀티스레딩일 때
멀티코어 스핀락 오버헤드 언제발생하는지 궁금헀다,
이진세마포어 생산자 소비자 문제
출처 > 그림으로 배우는 구조와 원리 운영체제 3판
