프로세스 스케줄링 알고리즘

Q. 프로세스 스케줄링 알고리즘에는 어떤 것들이 있나요?

비선점형 알고리즘, 선점형 알고리즘, 다단계 큐 알고리즘, 다단계 피드백 스케줄링이 있습니다.

비선점형 알고리즘과 선점형 알고리즘의 차이점으로는 선점형 알고리즘은 실행 중인 프로세스를 강제로 중단하고 다른 프로세스를 실행할 수 있지만, 비선점형 알고리즘은 프로세스가 작업을 완료할 때까지 CPU를 점유할 수 있습니다.

 

프로세스 스케줄링 알고리즘

1. 비선점형 스케줄링(Non-preemptive Scheduling) : 한번 CPU를 점유한 프로세스는 작업이 끝날 때까지 CPU를 사용
   1. FCFS(Fisrt-Come, First-Served) : 도착한 순서대로 실행(선입선출 방식)
      1. 단점 : 긴 작업이 먼저 오면 짧은 작업 시간이 대기 시간에 영향을 받기 때문에 평균 대기시간이 길어지는 문제가 발생
   2. SJF(Shortest Job First) : 실행시간이 짧은 순서대로 실행
2. 선점형 스케줄링(Preemptive Scheduling) : 실행중인 프로세스를 강제로 중단하고 다른 프로세스 실행 가능
   1. SRTF(Shortest Remaining Time First) : 남은 실행시간이 가장 짧은 프로세스부터 실행
   2. RR(Round Robin) : 모든 프로세스가 동일한 시간 단위를 할당받아 실행
   3. Priority Scheduling : 우선순위가 높은 순으로 실행
3. 다단계 큐 스케줄링 : 우선순위 별 큐로 분리 → 각 큐에 별도의 스케줄링 알고리즘 적용
4. 다단계 피드백 스케줄링 : 프로세스가 특정 조건에 따라 다른 큐로 이동 가능 

---

 

 *꼬리질문 *

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

• Time Slice란 프로세스가 CPU를 점유하는 시간 단위입니다. Time Slice 설정은 시스템 성능에 큰 영향을 미칩니다.
• trade-off란 시간 할당이 너무 짧거나 너무 길 때 발생하는 문제들 간의 균형을 의미합니다.

1. Time Slice가 너무 짧을 때
   1. 빠른 응답 시간과 공정성을 제공하지만, 잦은 문맥 전환으로 인해 오버헤드가 증가하여 시스템 성능이 저하될 수 있습니다.
2. Time Slice가 너무 길 때
   1. 문맥 전환 오버헤드가 감소하고 CPU 효율성이 향상되지만, 응답 시간이 길어지고 짧은 작업들의 대기 시간이 증가합니다.

따라서 RR은 단순하고 공정한 스케줄링 알고리즘이지만, Time Slice 길이에 따른 trade-off가 존재합니다. 시스템 요구사항에 맞는 적절한 Time Slice 설정이 필요합니다.

 

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

• 비선점형 스케줄링이 적합합니다. 그 이유는 CPU를 점유한 프로세스가 끝날 때까지 실행되므로, 상시 프로세스를 가장 먼저 실행하도록 배치하면 중단 없이 지속적으로 실행할 수 있기 때문입니다. 비선점형 스케줄링 중에서도 상시 실행이 필요한 프로세스를 다룰 때는 FCFS를 선호합니다.
• 왜 FCFS를 선호하는가?
• FCFS는 스케줄링 방식이 단순하고 오버헤드가 적습니다. 또한 다른 작업에 의해 중단되지 않고 지속적으로 CPU를 사용할 수 있습니다.
• SJF는 왜 덜 선호되는가?
  • SJF는 작업 시간을 기준으로 스케줄링하므로 프로세스의 실행 시간을 사전에 알아야 합니다. 하지만 상시 실행 프로세스는 작업 시간을 예측할 수 없어 SJF를 적용하기 어렵습니다.

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

• 동시성
  • 여러 작업이 논리적으로 동시에 진행되는 것을 의미합니다.
  • 실제로 작업들이 짧은 시간동안 빠르게 전환 되면서 실행됩니다.
  • 하나의 CPU가 작업을 번갈아 가며 실행하여 멀티태스킹으로 구현합니다
  • 예시 : 사용자가 웹 브라우저에서 신문을 읽는 동안 백그라운드에서 이미지 파일이 다운로드가 이루어 지고 있는 상황.
• 병렬성
  • 여러 작업이 물리적으로 동시에 진행되는 것을 의미합니다.
  • 실제로 여러 CPU 또는 코어에서 각 작업이 동시에 실행 됩니다.
  • 다중 코어 프로세서가 필요하기 때문에 하드웨어에 의존적인 특징을 지니고 있습니다.
  • 예시 : 대규모 온라인 쇼핑몰에서의 검색 요청 처리
    • 사용자가 특정 상품을 검색하면, 여러 서버나 프로세서가 상품 데이터베이스를 분할하여 서로 다른 범위를 동시에 검색합니다.
    • 각 프로세서가 맡은 부분을 처리한 결과를 병합해 최종 검색 결과를 반환합니다.
  • (쉽게 이해 가능한 비유)
    • 동시성:
      • 물리적으로 한 번에 하나씩만 작업하지만, 여러 작업이 동시에 진행되는 것처럼 보임.
    • 요리사가 하나의 스토브에서 국을 끓이고, 간을 맞추며, 동시에 불 조절을 빠르게 전환하며 작업.
    • 병렬성:
      • 각 작업이 물리적으로 독립된 자원에서 동시에 처리됨.
    • 여러 명의 요리사가 각자 스토브에서 동시에 요리.
  결론적으로 동시성은 다중 작업의 논리적 동시성을 구현하고, 병렬성은 다중 작업의 물리적 동시성을 구현합니다.

 

---

참고한 사이트[질문지]

✔️Tech-Interview