I'm implementing a Round Robin scheduling algorithm in Python with context switching, I/O handling, and a time quantum. I have the following code:
jobs = [
{"name": "J1", "arrival": 0, "burst": [1, 5, 2], "type": ["CPU", "IO", "CPU"], "completion_time": None},
{"name": "J2", "arrival": 1, "burst": [1, 2], "type": ["CPU", "CPU"], "completion_time": None},
{"name": "J3", "arrival": 2, "burst": [2, 1], "type": ["IO", "CPU"], "completion_time": None},
]
# Variables for simulation
current_time = 0
ready_queue = [] # Jobs ready for CPU execution
io_queue = [] # Jobs in I/O phase with (job, start_time)
completed_jobs = 0
context_switch = 1 # Time for context switch
quantum = 1 # Time quantum for Round Robin
first = False
# Event log for debugging
event_log = []
arrived_jobs = set() # Track jobs that have already had their arrival logged
def log_event(time, event):
"""Log events for debugging."""
event_log.append(f"Time {time}: {event}")
def update_ready_queue():
"""Update ready queue based on job arrival."""
for job in jobs:
# Check if the job arrived
if job["arrival"] <= current_time and job["name"] not in arrived_jobs:
arrived_jobs.add(job["name"]) # Mark job as having arrived
log_event(current_time, f"{job['name']} arrived")
# If job is starting with CPU burst, add to ready queue
if job["type"][0] == "CPU":
ready_queue.append(job)
log_event(current_time, f"{job['name']} added to ready queue")
# If job is starting with I/O burst, add to I/O queue
if job["type"][0] == "IO":
io_queue.append((job, current_time))
log_event(current_time, f"{job['name']} moved to I/O queue")
def process_io():
"""Process jobs in the I/O queue."""
global completed_jobs
for job, start_time in list(io_queue):
elapsed_time = current_time - start_time
io_burst_time = job["burst"][0]
if elapsed_time >= io_burst_time: # I/O burst completed
io_queue.remove((job, start_time))
job["burst"].pop(0)
job["type"].pop(0)
if job["burst"]:
if job["type"][0] == "CPU":
ready_queue.append(job)
log_event(current_time, f"{job['name']} completed I/O and added to ready queue")
else:
job["completion_time"] = current_time
completed_jobs += 1
log_event(current_time, f"{job['name']} completed")
previous_job = None
while completed_jobs < len(jobs):
# Process I/O jobs
update_ready_queue()
process_io()
if ready_queue:
# Select the next job from the ready queue
current_job = ready_queue.pop(0)
# Handle context switch if necessary
if first and previous_job != current_job:
current_time += context_switch
log_event(current_time, "Context switch")
# Execute the CPU burst for a quantum (time slice)
burst_time_left = current_job["burst"][0]
time_to_execute = min(burst_time_left, quantum) # Execute only up to the quantum time
current_job["burst"][0] -= time_to_execute
current_time += time_to_execute
log_event(current_time, f"{current_job['name']} executed for {time_to_execute} time units")
# If CPU burst completed, move to next burst or I/O
if current_job["burst"][0] == 0: # CPU burst completed
current_job["burst"].pop(0)
current_job["type"].pop(0)
if current_job["burst"]:
# Check if the next burst is I/O
if current_job["type"][0] == "IO":
io_queue.append((current_job, current_time))
log_event(current_time, f"{current_job['name']} moved to I/O")
else:
current_job["completion_time"] = current_time
completed_jobs += 1
log_event(current_time, f"{current_job['name']} completed")
# If the job is not completed and still has CPU burst left, add it back to the ready queue
if current_job["burst"]:
if current_job["type"][0] == "CPU":
ready_queue.append(current_job)
log_event(current_time, f"{current_job['name']} added back to ready queue")
previous_job = current_job
first = True # Set first to True after J1 starts execution
else:
# If no jobs are ready, increment time (CPU idle)
log_event(current_time, "CPU idle")
current_time += 1
# Output
print("\n".join(event_log))
completion_times = {job["name"]: job["completion_time"] for job in jobs}
print("Completion Times:", completion_times)
The code simulates the execution of three jobs (J1, J2, J3) with varying CPU and I/O bursts. However, I'm encountering an unexpected behavior:
Problem:
Job J3, which has an arrival time of 2, appears to arrive at time 3 in the output. I'm expecting the event log to show "Time 2: J3 arrived" but it's showing "Time 3: J3 arrived".
Expected Output
Time 0: J1 added to ready queue
Time 1: J1 executed for 1 time unit
Time 1: J1 moved to I/O
Time 1: J2 added to ready queue
Time 2: Context switch
Time 2: J3 arrived
Time 2: J3 moved to I/O queue
Time 3: J2 executed for 1 time unit
Time 4: Context switch
Time 5: J2 executed for 1 time unit
Time 5: J2 completed
Time 6: J1 completed I/O and added to ready queue
Time 7: J1 executed for 1 time unit
Time 8: J1 executed for 1 time unit
Time 9: J1 completed
Time 10: CPU idle
Time 11: CPU idle
Time 13: J3 completed I/O and added to ready queue
Time 14: Context switch
Time 15: J3 executed for 1 time unit
Time 15: J3 completed
Completion Times: {'J1': 9, 'J2': 5, 'J3': 15}
Actual Output
Time 0: J1 arrived
Time 0: J1 added to ready queue
Time 1: J1 executed for 1 time units
Time 1: J1 moved to I/O
Time 1: J2 arrived
Time 1: J2 added to ready queue
Time 2: Context switch
Time 3: J2 executed for 1 time units
Time 3: J2 added back to ready queue
Time 3: J3 arrived
Time 3: J3 moved to I/O queue
Time 4: J2 executed for 1 time units
Time 4: J2 added back to ready queue
Time 5: J2 executed for 1 time units
Time 5: J2 completed
Time 5: J3 completed I/O and added to ready queue
Time 6: Context switch
Time 7: J3 executed for 1 time units
Time 7: J3 completed
Time 7: J1 completed I/O and added to ready queue
Time 8: Context switch
Time 9: J1 executed for 1 time units
Time 9: J1 added back to ready queue
Time 10: J1 executed for 1 time units
Time 10: J1 completed
Completion Times: {'J1': 10, 'J2': 5, 'J3': 7}
I'm hoping to find the correct implementation of the Round Robin algorithm with the given job parameters and identify the issue causing the incorrect arrival time for Job 3.