CPU Scheduling

[JoisFe]

cpu scheduling

• RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.
• 싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?
• 동시성과 병렬성의 차이에 대해 설명해 주세요.
• 타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?
• FIFO 스케쥴러는 정말 쓸모가 없는 친구일까요? 어떤 시나리오에 사용하면 좋을까요?
• 우리는 스케줄링 알고리즘을 "프로세스" 스케줄링 알고리즘이라고 부릅니다. 스레드는 다른 방식으로 스케줄링을 하나요?
• 유저 스레드와 커널 스레드의 스케쥴링 알고리즘은 똑같을까요?

[JoisFe]

CPU Scheduling

• 어떤 프로그램에 CPU 소유권을 줄 것인지 결정하는 알고리즘

Q) RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

• RR(Round Robin) 이란 선점형 알고리즘 스케줄링 방법 중 하나로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안
  에 끝나지 않으면 다시 ready queue (준비 큐) 의 뒤로 가는 알고리즘입니다.

라운드 로빈 스케줄링 같은 선점형 방식에는 프로세스가 CPU를 일정 시간 동안 사용한 후 다른 프로세스에 주어야 하기 때문에 앞의 긴 작업을 무작정 기다리는 콘베이 효과가 줄어듭니다.

타임 슬라이스 크기와 문맥 교환

라운드 로빈 방식의 타임 슬라이스 값의 크기에 따라 평균 대기 시간이 달라진다

그러면 평균 대기 시간이 최대한 짧게 타임 슬라이스를 만드는 것이 효율 적일까요???

타임 슬라이스가 큰 경우

단점

• 타임 슬라이스가 너무 크면 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것 처럼 보입니다
  (FCFS랑 다를게 없어는 것이지요)

==> 타임 슬라이스가 무한인게 FCFS 와 같습니다.

ex)

타임 슬라이스가 1000밀리초 (1초)인 시스템에서 비디오 플레이어와 워드 프로세서가 동시에 실행된다고 가정해보겠습니다.

그럼 비디오 플에이어 1초, 워드 프로세서 1초 씩 각각 두 프로그램이 1초 간격으로 실행됩니다.

그럼 비디오도 끊겨 보이고 워드 프로세서의 반응 속도도 매우 느려 보일 것입니다.

타임 슬라이스가 작은 경우

장점

• 타임 슬라이스를 매우 작은 값으로 설정하면 사용자는 어떤 프로그램이 동시에 실행되는 것 처럼 느낄 것 입니다.

단점

• 그러나 타임 슬라이스를 너무 작게 설정하면 시스템의 전반적인 성능이 떨어집니다.
• why ? 문맥 교환이 너무 자주 일어나서 문맥 교환에 걸리는 시간이 실제 작업 시간보다 상대적으로 커지며 문맥 교환에 많은 시간을 낭비하여 실제 작업을 못하게 됩니다.

- 참고 : https://g-batman.tistory.com/43

결론적으로 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요함 (유닉스는 타임 슬라이스가 100 밀리초 정도 100 ~ 200 밀리초 사이에서 조정)

싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

• 싱글스레드에서는 한번에 하나의 프로세스만 실행될 수 있기에 하나의 프로세스가 너무 독점적으로 CPU를 점유하면 다른 모든 프로세스가 실행 기회를 잃을 수 있습니다.

==> Round Robin

• 프로세스가 싱글 스레드에서 주기적으로 실행되어야하고, 선점형 스케줄링이 필요한 경우 적합하다고 생각합니다.
• 일정한 time slice 마다 프로세스를 교체하므로 상시 동작하는 프로세스가 독점적으로 실행되지 않도록 하기에 적합하다고 생각합니다.
• 다만, context swiching 이 자주일어날 수 있어 오버헤드가 증가할 수 있습니다.

Q) 동시성과 병렬성의 차이에 대해 설명해 주세요.

동시성 (Concurrency)

• CPU core가 1개가 있는 경우 여러 process 번갈아 가면서 처리 하는 것
• 매우 짧은 시간 내에 번갈아 가면서 작업을 하기에 사용자 입장에서는 동시에 여러 프로세스가 처리되는 것으로 보임
• ==> `시분할 시스템 (Time Sharing System) 이라고 불림

병렬성 (Parallelism)

• CPU core 2개 이상 일때 각 core 들이 각자의 process를 병렬적으로 처리하면서 실제로 여러 process가 동시에 처리되는 것

Q) 타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

Multilevel Queue Scheduling (다단계 큐 스케줄링)

• 우선순위에 따라 준비 큐를 여러개 사용하는 방식입니다.
• process는 OS로 부터 부여받은 우선순위에 따라 해당 priority queue에 삽입합니다.
• RR 방식으로 운영되는 queue는 우선순위에 따라 다단계로 나뉘어 있어 process가 queue에 삽입되는 것만으로 우선순위가 결정됩니다.
• 우선순위는 고정형 우선순위를 사용하며 상단의 queue에 있는 모든 �process의 작업이 끝나야 다음 priority queue의 작업이 시작됩니다.

==> Multilevel Queue Scheduling은 우선순위에 따라 다양한 스케줄링이 가능한 선점형 방식 입니다.

• 우선순위가 높은 프로세스가 우선순위가 낮은 프로세스보다 먼저 작동할 수 있을뿐더러 우선순위에 따라 타임 슬라이스를 조절하여 작업 효율을 높일 수 있다고 합니다.

단점

• 우선순위가 높은 상위 큐 process 작업이 끝나기 전에는 하위 큐 process의 작업을 할 수 없습니다.

==> 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기가 됩니다. 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링 입니다.

Multilevel Feedback Queue (다단계 피드백 큐 스케줄링)

• 우선순위가 낮은 프로세스에 불리한 Multilevel Queue Scheduling의 문제점을 보완한 방식입니다.

• Multilevel Feedback Queue은 Multilevel Queue Scheduling과 기본적인 형태가 같아 우선순위를 가진 여러 개의 큐를 사용 합니다.!

• 하지만 Multilevel Queue Scheduling의 경우 각 단계의 큐에 라운드 로빈 방식을 사용하고 우선순위에는 변화가 없는 데 반해 Multilevel Feedback Queue의 경우 CPU를 사용하고 난 프로세스의 우선순위가 낮아집니다.!

• CPU를 사용하고 난 프로세스는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어갑니다.

• 다단계 피드백 큐 스케줄링은 프로세스가 CPU를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮추어, 다단계 쿠에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화하게 됩니다.

  • (물론 프로세스의 우선순위가 낮아진다고 할지라도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않습니다.)

• 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것이 특징입니다.

  • 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커집니다.

• Multilevel Feedback Queue은 우선순위가 낮은 프로세스의 실행 기회를 확대하려고 하지만 그렇다고 해도 우선순위가 낮은 프로세스가 우선순위가 높은 프로세스보다 CPU를 얻을 확률이 여전히 낮습니다.

  • 따라서 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮은 큐의 타임 슬라이스를 크게 설정 해야합니다.
  • 결국 Multilevel Feedback Queue에서 마지막 큐에 있는(우선 순위가 가장 낮은) 프로세스는 무한대의 타임 슬라이스를 얻게 됩니다.

==> Multilevel Feedback Queue에서 마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작 합니다.

다단계 피드백 큐 스케줄링은 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식으로 변동 우선순위 알고리즘의 전형적인 예라고 합니다.

(이전에 이야기한 유닉스 운영체제에서 타임슬라이스를 고정하지 않고 10~200 밀리초 사이에 조정할 수 있도록 한 이유가 바로 다단계 피드백 큐 스케줄링을 사용하기 때문)

�프로세스 우선순위가 시스템의 효율성이 아니라 중요도를 기준으로 결정해야 합니다. (단순히 효율성만을 위한다면 그냥 일반적인 프로세스가 커널 프로세스보다 먼저 CPU 점유..)
따라서 우선순위에 따라 스케줄링이 되어야 합니다.
이를 Multilevel Queue 를 이용하여 우선순위에 따라 다양한 스케줄링이 가능한 방식을 사용할 수 있지만 우선순위가 낮은 하위 큐 프로세스 작업에 대해 starvation 현상이 발생할 수 있는 문제가 있습니다. 따라서 Multilevel Feedback Queue 는 다른 스케줄링과 달리 �프로세스의 중요도에 따른 우선순위에 따른 스케줄링 작업을 진행하면서도, 우선순위가 낮은 프로세스의 starvation 현상 까지 해결할 수 있는 효율적인 스케줄링 방식 입니다.

Q) FIFO 스케쥴러는 정말 쓸모가 없는 친구일까요? 어떤 시나리오에 사용하면 좋을까요?

---> 스케줄러에서는 FCFS를 말하는 것 같습니다.

FCFS(First Come First Served) Scheduling

• 준비 큐에 도착한 순서대로 CPU를 할당받는 비선점형 방식 입니다.

• 초기의 일괄 작업 시스템에서 사용되었다고 합니다.
• 프로세스가 큐에 도착한 순서대로 실행 됩니다.
• 비 선점형 방식이기 때문에 한번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있습니다.
• 큐가 하나라 모든 프로세스는 우선순위가 동일 합니다.

장점

• 단순하고 공평합니다.

단점

1. Convoy Effect(콘보이 효과) : 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려야 하므로 시스템의 효율성이 떨어집니다.
2. 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아져 작업 효율 떨어집니다.

(시분할 시스템에서는 입출력을 요청한 프로세스를 대기 상태로 보내어 처리할 수 있지만 일괄 작업 시스템에서는 프로세스의 상태 변화가 없기 때문에 작업 효율이 떨어진다고 합니다.)

==>

1. FCFS 경우 작업이 정해진 순서대로 처리되어야 하는 경우 (선행 작업이 처리된 이후 후행 작업이 처리되어야 하는 경우)

• 프로세스 작업의 효율이 중요한게 아니라 순서를 확실히 지켜야하는 경우
• ex) batch 성 작업 => read, process, write 순서대로

2. 모든 프로세스 처리되는 시간이 매우 짧은경우

• FCFS 단점 (Convoy Effect) 가 일어나지 않을 경우
• ex) 매우 짧은 동일 작업 반복

Q) 우리는 스케줄링 알고리즘을 "프로세스" 스케줄링 알고리즘이라고 부릅니다. 스레드는 다른 방식으로 스케줄링을 하나요?

Q) 유저 스레드와 커널 스레드의 스케쥴링 알고리즘은 똑같을까요?

1. User Level Thread : thread library에 의해 스케줄링 됨
2. Kernel Level Thread: 커널에 의해 스케줄링 됨

JVM 에서의 thread와 OS kerne thread

• 자바 스레드는 JVM에서 User Thread를 생성할 때 시스템 콜을 통해서 커널에서 생성된 커널 스레드와 1:1로 매핑이 되어 최종적으로 커널에서 관리된다.

• 이떄 User Thread가 User Level Thread 의 예시라고 합니다.

• Java Thread 참고사항

참고

• 쉽게 배우는 운영체제 ㅣ IT Cookbook 한빛 교재 시리즈 238 조성호 (지은이) | 한빛아카데미(교재)

[JoisFe]

Preemptive scheduling (선점형 스케줄링)

• 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 OS가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식 (ex 인터럽트 처리)

• 단점 :

�Context Switching 같은 부가적인 작업으로 인해 낭비가 생깁니다.

• 장점 :

하나의 프로세스가 CPU를 독점할 수 없기 때문에 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합
(대부분 저수준 스케줄러는 선점형 스케줄링 방식)

Non preemptive scheduling (비선점형 스케줄링)

어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

• 단점

CPU 사용 시간이 긴 프로세스 때문에 CPU 사용 시간이 짧은 여러 프로세스가 오랫동안 기다리게 되어 전체 시스템의 처리율이 떨어집니다.

• 장점
  작업량이 적고 문맥 교환에 의한 낭비도 적습니다.
  (과거에 일괄 작업 시스템에서 사용되는 방식)

[jay200333]

1. 자신이 알고 있는 CPU 스케줄링을 선점형, 비선점형으로 나누어 특징을 설명해주세요.

cpu scheduling

RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

✅ 답변
Time Slice가 너무 큰 경우 : 선입 선처리 스케줄링과 동일해지며 결국, 호위 효과가 발생함, 응답 시간 증가
Time Slice가 너무 작은 경우 : 문맥 교환 횟수가 증가하여 오버헤드가 발생할 수 있음, 효율성 저하

---

싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

✅ 답변

RR 스케줄링 → 상시 프로세스의 경우 우선순위가 높고 연속적인 실행이 보장되어야 하기에 주기적으로 CPU를 할당받아야하고 그렇다고 CPU를 독점하면 안되기 때문

---

동시성과 병렬성의 차이에 대해 설명해 주세요.

✅ 답변

동시성 : 하나의 CPU에서 작업을 번갈아가며 진행하여 눈에는 동시에 진행되는 것처럼 보임, 문맥 교환을 통해 작업 간 전환
병렬성 : 여러 개의 CPU코어를 사용하여 작업을 동시에 진행 → 성능 향상, 동기화 필요

---

타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

✅ 답변

선입 선처리 스케줄링과 RR 스케줄링에서 발생하는 호위 효과를 해결할 수 있고, 우선순위 스케줄링에서 발생할 수 있는 기아 현상을 에이징 기법을 이용하여 해결할 수 있다.

---

FIFO 스케쥴러는 정말 쓸모가 없는 친구일까요? 어떤 시나리오에 사용하면 좋을까요?

✅ 답변

CPU이용 시간이 짧은 프로세스들이 많은 경우, 프로세스 처리 순서가 중요한 경우, 오버헤드를 최소화해야 하는 경우

---

우리는 스케줄링 알고리즘을 "프로세스" 스케줄링 알고리즘이라고 부릅니다. 스레드는 다른 방식으로 스케줄링을 하나요?

✅ 답변

커널 수준 스레드 : 커널이 직접 스레드를 관리하고 스케줄링

→ 스레드가 독립적으로 CPU를 할당받음 → 다중 CPU 활용 가능

장점

• 프로세스의 스레드들을 프로세서에 한 번에 디스패치 할 수 있기에 멀티프로세서 환경에서 매우 빠르게 동작한다.
• 커널이 직접 스레드를 제공해 주기 때문에 안정성과 다양한 기능이 제공된다.

단점

• 스케줄링과 동기화를 위해 커널을 호출하는데 무겁고 오래 걸린다.
• 문맥 교환이 빈번히 발생하여 성능 저하가 발생 → 오버헤드 증가

유저 수준 스레드 : 사용자 영역에서 스레드를 관리하고 스케줄링

• 프로세스 내의 Thread 관련 Library가 Thread를 관리한다.
• 유저 수준 스레드의 존재를 커널에서는 알지 못한다.
• 하나의 Thread라도 동작을 멈출 경우, 그 프로세스 전체가 Block 된다.
• 멀티 프로세서를 전혀 이용할 수 없다.
  ex. new Thread() 같이 프로세스 내에서 Thread를 생성하는 것

장점

• 스케줄링이나 동기화를 위해 커널을 호출하지 않기에 인터럽트 발생시 오버헤드가 적다.

• 문맥 교환 시 커널 개입 없음 → 빠른 전환 가능

  단점

  • 시스템 전반에 걸친 스케줄링 우선순위를 지원하지 않는다.
  • I/O 작업 등에 의해 하나라도 Block된다면 전체 스레드가 Block된다.

  하이브리드 모델 : 커널 스레드와 사용자 스레드를 혼합하여 효율적

→ 블로킹 문제 해결 및 다중 CPU 활용 가능

[jay200333]

각 CPU 스케줄링의 단점

FCFS 스케줄링[선입 선처리 스케줄링](First Come First Served Scheduling)

→ 프로세스 대기 시간이 매우 길어질 수 있음(호위 효과)

→ 비선점형 : CPU를 독점으로 사용할 수 있음

→ 응답 시간 증가 : 짧은 작업도 대기 시간이 길어질 수 있음

---

SJF 스케줄링[최단 작업 우선 스케줄링](Shortest Job First Scheduling)

→ 우선순위가 높은 프로세스인데 늦게 처리될 수 있음

→ 우선순위 역전 : 짧은 작업 위주로 처리되어 긴 작업이 계속 대기할 수 있음(기아 현상)

→ 프로세스 실행 시간 예측 어려움

→ 비선점형 : CPU를 독점으로 사용할 수 있음

---

RR 스케줄링(round robin scheduling)

→ 타임 슬라이스가 클 경우 : FCFS 스케줄링과 다를게 없고 호위 효과가 생길 수 있음

→ 타임 슬라이스가 작은 경우 : 문맥 교환이 자주 발생하여 오버헤드가 발생할 수 있음

→ 프로세스 성격에 따른 비효율성 : 짧은 작업이 긴 작업과 동일한 타임 슬라이스를 사용해 비효율적

---

SRT 스케줄링[최소 잔여 시간 우선 스케줄링](Shortest Remaining Time) : SJF + RR

→ 기아 현상이 발생할 수 있음

→ 문맥 교환 오버헤드 발생할 수 있음

→ 예상 실행시간 예측하기 어려움

---

우선순위 스케줄링(priority scheduling)

→ 우선순위가 낮은 프로세스인 경우 기아 현상이 나타날 수 있음

---

다단계 큐 스케줄링(multilevel queue scheduling)

→ 프로세스들이 큐 사이를 이동할 수 없으므로 기아 현상이 발생할 수 있음

→ 유연성 부족 : 큐와 스케줄링 정책이 고정적이라 동적 환경에서 비효율적

---

다단계 피드백 큐 스케줄링(multilevel feedback queue scheduling)

→ 프로세스가 큐를 자주 이동하면서 문맥 교환 오버헤드가 발생할 수 있음

→ 설정이 복잡함

[dy102]

• RR을 사용할 때, Time Slice에 따른 trade-off를 설명해 주세요.

  라운드 로빈(Round Robin) 스케줄링은 프로세스들이 동일한 time slice(타임 슬라이스) 동안 CPU를 할당받는 방식의 스케줄링 알고리즘이다. 타임 슬라이스 크기 선택은 시스템의 성능과 사용자 경험에 큰 영향을 미치며, 이에 따른 장단점이 존재한다.

  타임 슬라이스 크기가 작을 때

  장점

  • 빠른 응답 시간
    • 프로세스들이 자주 CPU를 할당받으므로 대기 시간이 짧아져 인터랙티브(ex.GUI 응용 프로그램) 시스템에서 반응 속도가 좋아진다.
  • 공평성 증가
    • 모든 프로세스가 짧은 주기로 CPU를 할당받아 특정 프로세스가 과도하게 CPU를 점유하는 상황을 방지할 수 있다.

  단점

  • 오버헤드 증가
    • 컨텍스트 스위칭(context switching)이 자주 발생하므로 CPU가 실제 작업보다 상태 저장/복원 작업에 더 많은 시간을 소비하게 된다.
  • 처리율 감소
    • 컨텍스트 스위칭 오버헤드로 인해 CPU 사용 효율이 떨어져 시스템이 처리할 수 있는 작업량이 줄어든다.
  • 비효율적인 CPU 사용
    • 짧은 타임 슬라이스 동안 프로세스가 CPU를 충분히 활용하지 못하고 작업이 미완료 상태로 남을 가능성이 높다.

  타임 슬라이스 크기가 클 때

  장점

  • 컨텍스트 스위칭 오버헤드 감소
    • 프로세스가 더 오래 CPU를 점유하므로 상태 저장/복원 작업이 줄어들어 오버헤드가 감소한다.
  • 처리율 증가
    • CPU 사용 효율이 향상되어 시스템이 처리할 수 있는 작업량이 늘어난다.
  • CPU 집중 작업에 유리
    • CPU 사용량이 많은 작업(CPU-bound 프로세스)이 더 긴 시간 동안 실행되므로 성능이 향상된다.

  단점

  • 응답시간 증가
    • 다른 프로세스들이 CPU를 기다리는 시간이 길어져 인터랙티브 시스템에서 사용자 경험이 저하될 수 있다.
  • 공평성 감소
    • 특정 프로세스가 CPU를 오래 점유하게 되어, 짧은 작업이나 I/O 중심 작업은 상대적으로 불리해진다.
  • I/O 병목 가능성
    • CPU보다 I/O를 많이 사용하는 프로세스가 오래 대기하게 되어, 시스템 전체의 병목을 유발할 수 있다.

  타임 슬라이스 설정 기준

  • 프로세스 유형
    • I/O bound process 는 짧은 타임 슬라이스에서 더 효과적이다.
    • CPU-bound process는 긴 타임 슬라이스에서 더 효과적이다.
  • 컨텍스트 스위칭 오버헤드
    • 타임 슬라이스가 컨텍스트 스위칭 오버헤드보다 너무 작으면, 대부분의 CPU 자원이 오버헤드 처리에 사용된다.
  • 응답성과 처리율의 균형
    • 사용자 응답 시간을 유지하면서도 시스템 처리율을 높이기 위해 적절한 중간값을 찾아야 한다.

• 싱글 스레드 CPU 에서 상시로 돌아가야 하는 프로세스가 있다면, 어떤 스케쥴링 알고리즘을 사용하는 것이 좋을까요? 또 왜 그럴까요?

  우선순위 기반 스케줄링(priority-based scheduling)

  • 각 프로세스에 우선순위를 부여하여 CPU를 할당한다.
  • 우선순위가 높은 프로세스가 먼저 실행된다.
  • 우선순위가 동일한 프로세스 간에는 라운드 로빈이나 FCFS를 이용하여 순서를 정할 수 있다.

  적합성

  • 상시로 돌아가야 하는 프로세스에 높은 우선순위를 부여하면, 다른 프로세스보다 항상 먼저 실행됨
  • CPU는 특정 프로세스를 지속적으로 실행 상태로 유지할 수 있음
  • 단일 CPU에서는 동시 실행이 불가능하므로, 중요한 작업을 우선 처리하는 것이 효율적임
  • 우선순위가 낮은 작업은 대기 상태로 유지되더라도 중요한 작업의 실행에 영향을 주지 않음
  • 상시 실행 프로세스가 중요한 시스템 작업(ex. 네트워크 요청 처리, 센서 데이터 읽기)을 담당한다면, 이 프로세스가 지연되지 않도록 우선적으로 CPU를 할당할 수 있음.

  다른 고려사항

  1. 상시 프로세스와 일반 프로세스 간 균형 유지

  • 높은 우선순위를 가진 프로세스가 CPU를 독점하면, 우선순위가 낮은 프로세스가 기아 상태(starvation)에 빠질 수 있다.
  • 이를 방지하기 위해, 우선순위 상승(priority aging) 기법을 적용하여 일정 시간이 지나면 낮은 우선순위 프로세스의 우선순위를 점진적으로 높여준다.

  2. 선점형 vs 비선점형 스케줄링

  • 선점형 우선순위 스케줄링:
    • 높은 우선순위 프로세스가 도착하면 현재 실행 중인 낮은 우선순위 프로세스를 중단하고 CPU를 할당한다.
    • 상시 프로세스가 높은 우선순위를 가진 경우, 선점형 방식이 적합하다.
  • 비선점형 우선순위 스케줄링:
    • 현재 실행 중인 프로세스가 종료될 때까지 CPU를 유지한다.
    • 상시 프로세스가 주기적으로 실행되거나 비차단 작업이라면 비선점형 방식도 고려할 수 있다.

  예시

  상시 프로세스의 우선순위가 높은 경우

  • 예: 실시간 데이터 로깅 프로그램
    • 상시 실행 프로세스(데이터 로깅)는 우선순위 1.
    • 기타 작업(예: 사용자 입력 처리, 백그라운드 계산)은 우선순위 2 이상.

  적용

  • 스케줄러는 항상 상시 프로세스를 먼저 실행하고, 나머지 프로세스는 남은 CPU 시간을 공유합니다.

• 동시성과 병렬성의 차이에 대해 설명해 주세요.

  동시성

  동시성은 하나의 CPU에서 여러 작업이 번갈아가며 실행되는 것을 의미한다. 작업이 실제로 동시에 수행되지는 않지만, 빠르게 전환(Context Switching)되면서 동시에 실행되는 것처럼 보인다.

  • 단일 CPU에서 실행.

  • 작업 간에 시간 분할(Time Slicing)로 CPU를 교대로 사용.

  • 실행 순서를 관리하는 스케줄러가 중요.

  • 예시

    • 웹 서버에서 여러 클라이언트 요청을 처리할 때, CPU는 각 요청을 빠르게 전환하며 처리.
    • 하나의 작업이 I/O 대기 상태에 들어가면 다른 작업을 수행.

  병렬성

  • 정의: 병렬성은 다중 CPU나 다중 코어 환경에서 여러 작업이 동시에 실행되는 것을 의미합니다. 각 작업이 물리적으로 동시에 처리됩니다.
  • 특징:
    • 다중 CPU나 코어 필요.
    • CPU나 코어 간에 작업을 분배하여 성능 향상.
    • 작업 간에 상호 독립성이 중요한 역할.
  • 예시:
    • 대규모 데이터 처리 작업에서 여러 코어가 데이터를 동시에 계산.
    • 그래픽 처리에서 GPU가 픽셀을 병렬로 렌더링.

• 타 스케쥴러와 비교하여, Multi-level Feedback Queue는 어떤 문제점들을 해결한다고 볼 수 있을까요?

  1. 멀티 레벨 피드백 큐(Multilevel Feedback Queue)의 특징

  • 작업의 우선순위에 따라 여러 개의 큐를 유지.
  • 각 큐는 다른 스케줄링 알고리즘(예: FCFS, 라운드 로빈)을 사용할 수 있음.
  • 작업이 실행되지 않고 대기 시간이 길어질수록 낮은 우선순위에서 높은 우선순위 큐로 이동 가능 (우선순위 상승).
  • 작업이 너무 많은 CPU 시간을 소비하면 더 낮은 우선순위 큐로 이동 가능 (우선순위 하락).

  ---

  2. 타 스케줄러와 비교하여 해결할 수 있는 문제

  1. Short Job Bias 해결
     • 타 스케줄러(예: SJF, Shortest Job First)는 짧은 작업에 유리하여 긴 작업이 기아 상태에 빠질 수 있음.
     • 멀티 레벨 피드백 큐는 긴 작업도 시간이 지남에 따라 우선순위가 상승하여 결국 실행 가능.
  2. 우선순위 역전 문제 해결
     • 우선순위 기반 스케줄링에서는 낮은 우선순위 작업이 높은 우선순위 작업에 밀려 영구히 실행되지 않을 수 있음.
     • 멀티 레벨 피드백 큐는 일정 시간이 지나면 낮은 우선순위 작업의 우선순위를 상승시켜 이 문제를 완화.
  3. 응답 시간 개선
     • 짧은 작업(예: I/O Bound)은 높은 우선순위 큐에서 빠르게 처리되어 응답 시간이 단축됨.
     • 긴 작업(예: CPU Bound)은 낮은 우선순위 큐로 내려가므로 시스템의 전체적인 응답성을 유지.
  4. Fairness(공정성) 제공
     • 모든 작업이 정해진 규칙에 따라 적절한 CPU 시간을 배정받아 공정성이 향상됨.
     • 특히 라운드 로빈 방식을 사용하는 큐는 시간 분할을 통해 공평하게 CPU를 분배.

  ---

  3. 타 스케줄러와 비교

  스케줄러 유형	문제점	멀티 레벨 피드백 큐에서 해결 방법
  FCFS	짧은 작업이 긴 작업 뒤에서 대기.	우선순위 높은 큐에서 짧은 작업 먼저 처리.
  SJF	긴 작업이 기아 상태에 빠질 수 있음.	우선순위 상승으로 긴 작업도 처리 가능.
  우선순위 기반 스케줄링	우선순위 역전 문제.	우선순위 상승으로 해결 가능.
  라운드 로빈	모든 작업에 동일한 시간 할당.	작업 특성에 따라 다른 큐로 분리하여 최적화.

• 유저 스레드와 커널 스레드의 스케쥴링 알고리즘은 똑같을까요?

  사용자 수준 스레드와 커널 수준 스레드 스케줄링

  1. 유저 스레드(User-Level Threads):

  • 설명:

    • 사용자 레벨에서 관리되는 스레드.
    • 운영체제가 스레드의 존재를 알지 못하며, 프로세스 단위로만 스케줄링
    • 스레드 스케줄링은 라이브러리에서 처리.

  • 장점:

    • 스레드 관리가 빠르고, 컨텍스트 스위칭 비용이 적음.
    • 운영체제의 개입 없이 애플리케이션이 스케줄링을 직접 제어 가능.

  • 단점:

    • 하나의 유저 스레드가 블록되면 해당 프로세스의 모든 유저 스레드가 중단될 수 있음.
      1. 스레드 A가 블로킹 작업 실행
         • 사용자 스레드 A가 파일 읽기 작업과 같은 블로킹 시스템 호출을 수행
         • 커널은 해당 시스템 호출이 완료될 때까지 프로세스를 대기 상태로 전환
      2. 스레드 B, C가 실행 중단
         • 사용자 스레드 B, C는 여전히 실행 가능한 상태이지만, 커널은 이를 알지 못하고 해당 프로세스 전체를 대기 상태로 간주
         • 이로 인해 스레드 B, C도 실행될 기회를 잃음
      3. 프로세스 대기 큐로 이동
         • 해당 프로세스는 실행 가능한 상태가 아니므로, 커널의 스케줄링 큐에서 대기 큐로 이동됨
         • 블로킹 작업이 완료되면 다시 스케줄링 큐로 이동하여 실행을 재개

    스케줄링

    유저 스레드는 운영체제가 아닌 사용자 레벨의 스레드 라이브러리에서 스케줄링이 이루어진다. 따라서 일반적으로 간단한 스케줄링 알고리즘이 사용된다.

    • FIFO (First In, First Out)
      • 가장 먼저 생성된 스레드를 실행 후 종료하고, 다음 스레드를 실행.
      • 단순하고 구현이 쉬움.
    • Round Robin
      • 각 스레드가 고정된 시간 동안 실행한 뒤 다른 스레드로 전환.
      • 모든 스레드에게 공평한 CPU 사용 기회를 제공.
    • Priority-Based Scheduling
      • 스레드마다 우선순위를 설정하여, 높은 우선순위의 스레드가 먼저 실행.
      • 우선순위가 낮은 스레드가 기아(starvation)에 빠질 가능성 있음.
    • Yielding (Voluntary Scheduling)
      • 실행 중인 스레드가 스스로 실행을 양보(yield())하여 다른 스레드가 실행되도록 함.
      • 협력적 멀티태스킹 방식.
    • Work Stealing (분산형 스케줄링)
      • 작업을 다 완료한 스레드가 다른 스레드의 작업 큐에서 작업을 가져오는 방식.
      • 작업 분산을 통해 효율성을 높임.

  ---

  2. 커널 스레드(Kernel-Level Threads):

  • 설명:
    • 운영체제가 직접 관리하는 스레드.
    • 커널이 각 스레드에 대해 별도의 스케줄링을 수행.
  • 장점:
    • 스레드 간 독립적 실행 보장.
    • 하나의 스레드가 블록되어도 다른 스레드에 영향을 주지 않음.
  • 단점:
    • 컨텍스트 스위칭 비용이 높음.
    • 커널 개입으로 인해 오버헤드 증가.

  스케줄링

  커널 스레드는 운영체제 커널에서 스케줄링된다. 커널 스레드는 프로세스처럼 선점형 스케줄링 알고리즘을 사용하며, OS에서 제공하는 복잡한 알고리즘을 활용한다.

  • Round Robin
    • 프로세스와 동일하게 고정된 타임 슬라이스 동안 스레드를 실행하고 다음 스레드로 전환.
    • CPU를 공평하게 분배.
  • Priority Scheduling
    • 스레드마다 우선순위를 부여하고, 높은 우선순위의 스레드가 실행.
    • 우선순위가 낮은 스레드의 실행 지연 가능성 있음.
  • Multi-Level Feedback Queue (MLFQ)
    • 여러 큐로 스레드를 분류하고, 각 큐에 다른 스케줄링 정책 적용.
    • 작업의 종류나 실행 시간을 기준으로 스레드 실행 순서를 조정.
  • Completely Fair Scheduler (CFS)
    • Linux의 기본 스케줄링 알고리즘으로, 스레드에게 공정한 CPU 사용 시간을 보장.
    • 가중치와 실행 시간을 기반으로 스레드를 스케줄링.
  • Deadline Scheduling
    • 실시간 시스템에서 사용되며, 각 스레드가 특정 기한 내에 실행 완료되도록 보장.