Jinny - CS10

REAMDME.md

🖥 CS10 - 프로세스 스케줄링

🔍 미션 설명

운영체제에서 프로세스를 실행해서 종료될 때까지 작업을 시뮬레이션하는 프로그램을 구현한다.
스케줄링 방식은 다음 3개 중 1개를 골라서 구현하고, 여유가 된다면 다른 방식도 구현해 본다.

• 기한부 스케줄링 (deadline scheduling)
• 고정 우선순위 스케줄링 (static priority scheduling)
• 라운드 로빈 스케줄링 (Round Robin scheduling)

학습 키워드

#스케줄링 #프로세스 #PCB #운영체제 #우선순위

실행 결과 예시

프로세스A(3초) , 프로세스B(5초), 프로세스C(7초) 를 생성한 경우 출력 예시

A(ready), 0 / 3sec
B(ready), 0 / 5sec
C(ready), 0 / 7sec
.
A(running), 1 / 3sec , waiting 0 sec
B(waiting), 0 / 5sec , waiting 1 sec
C(waiting), 0 / 7sec , waiting 1 sec
.
A(waiting), 1 / 3sec , waiting 1 sec
B(running), 1 / 5sec , waiting 1 sec
C(waiting), 0 / 7sec , waiting 2 sec
.
A(waiting), 1 / 3sec , waiting 2 sec
B(waiting), 1 / 5sec , waiting 2 sec
C(running), 1 / 7sec , waiting 2 sec
.
A(running), 2 / 3sec , waiting 2 sec
B(waiting), 1 / 5sec , waiting 3 sec
C(waiting), 1 / 7sec , waiting 3 sec
.
A(waiting), 2 / 3sec , waiting 3 sec
B(running), 2 / 5sec , waiting 3 sec
C(waiting), 1 / 7sec , waiting 4 sec
.
A(waiting), 2 / 3sec , waiting 4 sec
B(waiting), 2 / 5sec , waiting 4 sec
C(running), 2 / 7sec , waiting 4 sec
.
A(running), 3 / 3sec , waiting 4 sec
B(waiting), 2 / 5sec , waiting 5 sec
C(waiting), 2 / 7sec , waiting 5 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(running), 3 / 5sec , waiting 5 sec
C(waiting), 2 / 7sec , waiting 6 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(waiting), 3 / 5sec , waiting 6 sec
C(running), 3 / 7sec , waiting 6 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(running), 4 / 5sec , waiting 6 sec
C(waiting), 3 / 7sec , waiting 7 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(waiting), 4 / 5sec , waiting 7 sec
C(running), 4 / 7sec , waiting 7 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(running), 5 / 5sec , waiting 7 sec
C(waiting), 4 / 7sec , waiting 8 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(terminated), 5 / 5sec , waiting 7 sec
C(running), 5 / 7sec , waiting 8 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(terminated), 5 / 5sec , waiting 7 sec
C(running), 6 / 7sec , waiting 8 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(terminated), 5 / 5sec , waiting 7 sec
C(running), 7 / 7sec , waiting 8 sec
.
A(terminated), 3 / 3sec , waiting 4 sec
B(terminated), 5 / 5sec , waiting 7 sec
C(terminated), 7 / 7sec , waiting 8 sec

라운드로빈 방식 스케줄링이 종료되었습니다.
평균 대기시간 = (4 + 7 + 8) / 3 = 6.3sec
평균 반환시간 = (7 + 12 + 15) / 3 = 11.3sec

---

다른 스케줄링 방식 표시

✅ 기능 요구사항

프로세스 기능

• 프로세스 종료를 A부터 F까지 6개 정하고, 프로세스 마다 최대 동작 시간을 겹치지 않도록 생성하는 기능
• 프로세스의 상태를 나타내는 기능
  • 준비(ready), 실행(running), 대기(waiting), 종료(terminated)

운영체제 기능

• 한 번에 프로세스 하나씩, 1초동안 실행하는 기능
  • 프로세스는 준비 또는 대기 상태에서만 실행 상태로 변경 가능
• 1초 이후 같은 프로세스가 아닌 다른 프로세스를 실행하는 기능
  • 단, 프로세스가 1개만 남은 경우 반복해서 같은 프로세스를 실행 가능
• 누적 동작 시간이 최대 동작 시간만큼 실행한 프로세스를 종료 상태로 변경하는 기능
• 누적 동작 시간이 최대 동작 시간보다 작으면, 대기 상태로 바꿨다가 준비 상태로 변경하는 기능

프로그램 기능

• 프로그램 시작 후, 랜덤으로 프로세스 3개를 생성하고 대기 큐에 추가하는 기능

출력 기능

• 1초마다 전체 프로세스 상태, 대기 시간, 누적 실행 시간을 출력하는 기능

---

📝 개념 공부

본문은 CPU 스케줄링에 대해 주로 다루고자 하여
프로세스와 스레드의 기본 개념은 가볍게 훑고 갈 예정이다.

🧑🏼‍🍳 1. 프로세스와 스레드

📌 1.1 프로세스

• 프로그램이 실행되어서 돌아가고 있는 상태를 프로세스라고 한다.

📌 1.2 스레드

• 프로세스 내에서 프로그램을 실행하는 최소 작업 단위이다.

💡 1.3 예시

조금 더 이해하기 쉽게 예시를 들어보겠다.

하나의 브라우저도 프로그램이다. (== 브라우저가 프로그램이기 때문에 브라우저가 실행되어서 돌아가고 있는 상태가 프로세스인 것)

브라우저에서 파일 다운로드를 받으며 웹 서핑이 가능해야 하고
유튜브 영상의 데이터를 받아옴과 동시에 시청이 가능해야 한다.

이렇듯 한개의 프로세스 안에서도 여러 갈래의 작업들로 나뉜다.
이러한 갈래를 스레드라고 한다.

💡 1.4 비유

그리고 비유도 하나 들어보겠다.

식당에서 메뉴 하나를 만드는 것을 프로세스라고 하자.
이 식당은 파스타도 만들고, 피자도 만들고, 햄버거도 만든다.
"파스타 만들기" "피자 만들기" "햄버거 만들기"가 각각의 프로세스가 된다.

그리고 피자와 햄버거 주문이 들어오면
주방에는 각각 "피자를 만드는 섹션(조리공간)" "햄버거를 만드는 섹션(조리공간)"이 생긴다.
이 과정이 CPU의 할당이다.

주문이 들어오면 햄버거를 만들어야 한다.
패티를 굽는 "스레드"를 진행하는 동안 빵에 소스를 뿌리는 "스레드"도 진행되어야 한다.

🔖 1.5 중요

여기서 주의해야 할 점은
프로세스는 주방(CPU)이라는 자원을 나눠서 쓰지만 스레드는 자원(조리공간)을 공유한다는 점이다.

이로 인해 발생할 수 있는 문제점있다.
프로세스 안에서 공유되는 변수에 스레드 두개가 동시에 접근하게 되면 에러가 발생할 수 있다는 것이다.

시간 문제(동시성)로 발생하는 문제는 디버깅해서 오류와 원인을 찾아내는 것이 힘들다.
이로 인해 주목을 받게된 패러다임이 있는데 바로 이전에 언급했던 함수형 프로그래밍이다.

자세한 내용은 여기를 참고하시라.

• [프로그래밍] 함수형 프로그래밍(Functional Programming)

🕛 2. CPU 스케줄링(프로세스 스케줄링)

📌 2.1 스케줄링

• 프로세스 작업을 수행하는데 필요한 CPU 공간을 할당받기 위한 작업

프로세스가 실행되려면 CPU의 공간을 할당받아야 한다.
최고의 효율와 성능을 내기 위해 언제 어떤 자원을 프로세스에 얼마나 할당하는지 관리하는 것을 CPU 스케줄링이라고 한다.

FIFO이니 라운드로빈이니 다단계 큐니 다양한 스케줄링 알고리즘을 알아보기에 앞서
이 스케줄링을 "왜" 하는 것인지 이해하는 것이 중요하다.

🔖 2.2 스케줄링의 목적

CPU 스케줄링의 목적은 모든 프로세스가 적당히, 공평하게, 효율적으로 자원을 할당받는 것이다.
하지만 안정성과 효율성을 높이기 위해 때로는 공정성을 일부 희생해야 한다.
(컴퓨터의 모든 일은 trade-off가 있기 마련이니...)
그리고 다양한 상황에서 최적의 선택은 상이하기 마련이다.

그래서 다양한 상황에서 어떠한 목적을 더 고려해야 할지에 따라 다양한 알고리즘이 생긴 것이다.
알고리즘은 바로 뒤에서 설명할 예정이며, 우선 목적에 대해 알아보자.

1. 공정성
   • 모든 프로세스가 자원을 공평하게 할당받아야 한다.
2. 처리량 증가(Throught put)
   • 단위 시간당 처리량을 최대화한다.
3. CPU 이용률 증가(CPU Utilization)
   • 프로세스가 메로리를 사용하거나 I/O 명령에 의해 잠시 쉬는 상태(운휴 상태)를 줄이고 CPU가 프로세스를 실행한 상태로 유지해야 한다.
4. 반환 시간 단축(Turnaround Time)
   • 프로세스가 생성된 후 종료까지 사용하던 자원을 반환하는 데 걸리는 시간을 최소화 해야한다.
5. 대기 시간 단축(Waiting Time)
   • 프로세스가 준비 상태 큐에서 대기하는 시간을 최소화 한다.
6. 반응 시간 단축(ResponseTime)
   • 대기 큐에서 처음으로 CPU를 할당받기까지의 시간을 최소화한다.

일반적으로 CPU 이용률과 처리율 극대화하는 것이 좋고, 시간 관련 지표는 줄이는 것이 좋다.

⌨️ 2.3 스케줄링 알고리즘

운영체제에 따라 사용하는 스케줄링 알고리즘이 다르며, 종류도 다양하다.
본문에서는 다음과 같은 스케줄링 알고리즘에 대해 다룰 예정이다.

기한부 스케줄링, 우선순위 스케줄링, 라운드 로빈 스케줄링

기한부 스케줄링(Deadline Scheduling)

• 프로세스가 주어진 제한 시간(deadline) 안에 완료되도록 하는 알고리즘이다.
• 프로세스가 일정한 시간 안에 완료되지 못하면 진행 중인 프로세스는 제거되거나 처음부터 다시 진행된다.

우선순위 스케줄링(Priority Scheduling)

• 선점 방식, 비선점 방식 모두 있다.
• 프로세스가 갖고 있는 우선 순위에 따라 CPU에 프로세스를 할당한다.

라운드 로빈 스케줄링(Round Robin Scheduling)

• 비선점 방식의 알고리즘이다.
• 각각의 프로세스에 동일한 CPU 할당 시간을 부여해서 해당 시간 동안만 CPU를 이용하게 한다.
• 할당 시간 내에 처리를 완료하지 못하면 다음 프로세스로 넘어간다.

---

• 참고:
  • 프로세스는 뭐고 스레드는 뭔가요?
  • [운영체제] CPU 스케줄링 알고리즘 정리 및 요약 | FCFS, SJF, Round Robin