Overview This project implements a CPU scheduling simulator with three distinct algorithms:
1.First Come First Serve (FCFS) 2.Round Robin (RR) 3.Preemptive Priority Scheduling with Aging
The purpose of this simulator is to mimic the behavior of a CPU scheduler by selecting tasks to run from a ready queue based on the scheduling algorithm. The simulation prints the task execution sequence, resembling a Gantt chart, along with performance metrics such as average waiting time, average response time, and CPU usage.
Features Input: The task information is read from an input file, where each line specifies:
pid: Process ID (1 to 10) priority: Priority of the process (higher value indicates higher priority) arrival_time: Time at which the process arrives (milliseconds) burst_time: CPU time requested by the process (milliseconds)
Output: The simulation produces a timeline of task execution, as well as the following metrics:
Average waiting time Average response time Average turnaround time CPU usage (percentage)
Algorithms Implemented
First Come First Serve (FCFS): Tasks are processed in the order they arrive. Each task is executed in the sequence of its arrival, and there is no preemption. The average waiting time, turnaround time, and response time are calculated based on this first-come-first-served mechanism.
Round Robin (RR): Tasks are processed in a cyclic order with a configurable time quantum. Each task gets a fixed time slice (time_quantum). If a task doesn’t complete in its allocated time, it is moved to the back of the ready queue, and another task is scheduled. The scheduler continues switching between tasks until all tasks are completed, taking into account context switches between tasks.
Preemptive Priority Scheduling with Aging: Processes with the highest priority are scheduled first. Aging is implemented to prevent process starvation. The priority of a process increases over time based on its waiting time and the aging factor alpha. The formula used for the priority adjustment is:
priority_order = base_priority + (alpha * waiting_time)
How to Run The program accepts input via command-line arguments as follows:
For Preemptive Priority Scheduling: ./scheduler [input_filename] [output_filename] [time_quantum_for_RR] [alpha_for_priority]
For Round Robin and FCFS: ./scheduler [input_filename] [output_filename] [time_quantum_for_RR]
input_filename: File with process data (format: pid priority arrival_time burst_time) output_filename: File to save the output. time_quantum_for_RR: Time quantum for Round Robin scheduling. alpha_for_priority: Aging factor for the priority scheduling.
Example command for Preemptive Priority Scheduling:
./scheduler input.dat output.txt 5 0.2
Example Input
1 50 10 50 2 50 0 40 3 30 20 50 5 10 7 35
Example Output
<time 0> ---- system is idle ---- <time 1> ---- system is idle ---- <time 2> [new arrival] process 1 <time 2> process 1 is running ... <time 50> all processes finish
Average CPU usage : 92.00 % Average waiting time : 15.2 Average response time : 12.1 Average turnaround time: 21.0
Performance Metrics FCFS: Measures time efficiency in processing tasks in a first-come-first-served manner. RR: Optimizes fairness through time-slicing, minimizing process starvation. Preemptive Priority Scheduling with Aging: Adjusts task priorities dynamically to balance response time and throughput, preventing starvation through aging.
개요 이 프로젝트는 세 가지 알고리즘을 구현한 CPU 스케줄링 시뮬레이터입니다
선입선출(FCFS) 라운드 로빈(RR) 에이징이 적용된 선점형 우선순위 스케줄링
CPU 스케줄러의 동작을 모방하여 준비 큐에서 작업을 선택하고 실행 순서를 출력합니다. 또한 평균 대기 시간, 평균 응답 시간, CPU 사용률 등의 성능 지표를 제공합니다.
주요 기능 입력: 작업 정보는 다음 형식의 파일로부터 읽어옵니다:
pid: 프로세스 ID (1~10) priority: 프로세스 우선순위 (값이 클수록 우선순위가 높음) arrival_time: 프로세스 도착 시간 (밀리초) burst_time: 프로세스가 요청한 CPU 시간 (밀리초)
출력: 실행된 작업의 타임라인과 함께 다음 성능 지표를 출력합니다:
평균 대기 시간 평균 응답 시간 평균 반환 시간 CPU 사용률 (퍼센트)
구현된 알고리즘
선입선출(FCFS): 도착 순서대로 작업을 처리합니다. 각 작업은 도착 순서에 따라 실행되며, 선점이 발생하지 않습니다. 이 방식에서 평균 대기 시간, 반환 시간, 응답 시간이 계산됩니다.
라운드 로빈(RR): 주어진 시간 할당량(time_quantum)을 사용하여 작업이 주기적으로 처리됩니다. 각 작업은 고정된 시간 할당을 받으며, 할당된 시간이 지나면 큐의 뒤로 이동하고 다음 작업이 스케줄링됩니다. 모든 작업이 완료될 때까지 작업을 교체하며, 작업 간 문맥 전환도 고려됩니다.
에이징이 적용된 선점형 우선순위 스케줄링: 우선순위가 높은 작업을 먼저 처리합니다. 에이징을 통해 작업이 오랫동안 대기하는 것을 방지하며, 우선순위는 대기 시간과 alpha 계수를 바탕으로 조정됩니다.
우선순위 계산 식: priority_order = base_priority + (alpha * waiting_time)
실행 방법 프로그램은 명령줄 인수를 통해 입력을 받습니다:
선점형 우선순위 스케줄링의 경우: ./scheduler [입력 파일명] [출력 파일명] [RR의 시간 할당량] [우선순위 알고리즘의 알파 값]
라운드 로빈 및 선입선출의 경우: ./scheduler [입력 파일명] [출력 파일명] [RR의 시간 할당량]
입력 파일명: 작업 데이터를 포함하는 파일 (형식: pid priority arrival_time burst_time) 출력 파일명: 출력이 저장될 파일. RR의 시간 할당량: 라운드 로빈 스케줄링의 시간 할당량. 우선순위 알고리즘의 알파 값: 우선순위 스케줄링의 에이징 계수.
명령 예시 (우선순위 스케줄링): ./scheduler input.dat output.txt 5 0.2
입력 예시 1 50 10 50 2 50 0 40 3 30 20 50 5 10 7 35
출력 예시
스케줄링 : 에이징이 적용된 선점형 우선순위 스케줄링
========================================== <time 0> ---- 시스템 대기 ---- <time 1> ---- 시스템 대기 ---- <time 2> [새 도착] 프로세스 1 <time 2> 프로세스 1 실행 중 ... <time 50> 모든 프로세스 완료
평균 CPU 사용률 : 92.00 % 평균 대기 시간 : 15.2 평균 응답 시간 : 12.1 평균 반환 시간: 21.0
성능 지표 FCFS: 선입선출 방식으로 작업 처리 효율성을 측정합니다. RR: 시간 분할을 통해 공평성을 최적화하고, 프로세스 기아 상태를 최소화합니다. 우선순위 스케줄링: 우선순위를 동적으로 조정하여 응답 시간과 처리량 간의 균형을 맞추며, 에이징을 통해 기아 상태를 방지합니다.