KTU S4 OS Lab - PCCSL407 - Algorithms Reference

1. CPU Scheduling - FCFS

1. Input the number of processes n.
2. Input each process's: Process ID, Arrival Time, Burst Time.
3. Sort processes in ascending order of arrival time.
4. For each process:
- If CPU is idle, start at arrival time
- Compute Completion Time
- Compute Turnaround Time
- Compute Waiting Time
5. Compute average waiting time.
6. Display the scheduling table.

2. CPU Scheduling - SJF

1. Input number of processes n.
2. For each process, input: Process ID, Arrival Time, Burst Time.
3. At each step:
- Select the process which has arrived and has smallest burst time.
- Execute it to completion (non-preemptive).
4. For each process: Compute CT, TAT, WT.
5. Compute Average Waiting Time.
6. Display results.

3. CPU Scheduling - SRTF

1. Input n processes with arrival time and burst time.
2. Create structure array storing each process's information.
3. At each time unit:
- Select process with smallest remaining time that has arrived.
- Decrement remaining time.
- If remaining time = 0, mark completion.
4. After all processes finish:
- Compute Turnaround Time
- Compute Waiting Time
5. Compute Average Waiting Time.

4. CPU Scheduling - Priority Scheduling

1. Input number of processes n.
2. For each process, input: Arrival Time (AT), Burst Time (BT), Priority.
3. Set all processes as not completed.
4. At current time, select the process that:
- Has arrived (AT <= time)
- Has highest priority (largest priority number)
- Is not completed
5. Execute it non-preemptively until completion.
6. Calculate: CT = completion time, TAT = CT - AT, WT = TAT - BT.
7. Repeat until all processes are completed.
8. Compute Average Waiting Time.

5. CPU Scheduling - Round Robin (RR)

1. Input number of processes n.
2. For each process: Process ID, Arrival Time (AT), Burst Time (BT).
3. Input Time Quantum (TQ).
4. Maintain a ready queue.
5. At each time:
- Add all processes that have arrived.
- Dequeue the process at the front.
- Execute for min(BT, TQ) time.
- If remaining BT > 0, enqueue it again.
- Else mark the process as completed and compute CT.
6. Compute TAT, WT and Average WT.
 7. Print the results.

6. Disk Scheduling - FCFS

1. Read number of disk requests n.
2. Read the request queue.
3. Read the initial head position.
4. Set total head movement = 0.
5. For each request in order:
- Calculate distance = |current head - request|.
- Add distance to total movement.
- Move head to that request.
6. Display total head movement.

7. Disk Scheduling - SSTF

1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Mark all requests as unvisited.
5. From current head:
- Find request with minimum absolute distance.
- Move head to that request.
- Add movement to total.
- Mark request visited.
6. Repeat until all requests are serviced.

8. Disk Scheduling - SCAN

1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Read disk size.
5. Read direction (LEFT or RIGHT).
6. Sort request queue.
7. If direction = RIGHT:
- Service all requests greater than head (ascending).
- Move to disk end.
- Reverse and service remaining smaller requests.
8. If direction = LEFT:
- Service smaller requests first (descending).
- Move to 0.
- Reverse and service larger requests.
9. Compute total movement.

9. Disk Scheduling - C-SCAN

1. Read number of disk requests.
2. Read request queue.
3. Read initial head position.
4. Read disk size.
5. Sort requests.
6. Move head in one direction only (RIGHT assumed):
- Service all requests greater than head.
7. Move head to disk end.
8. Jump to track 0.
9. Continue servicing remaining smaller requests.
10. Calculate total head movement.

10. Disk Scheduling - LOOK

1. Read disk requests.
2. Read initial head position.
3. Sort the request queue.
4. Choose direction (LEFT or RIGHT).
 5. If RIGHT:
- Service all requests greater than head in ascending order.
- Reverse direction.
- Service remaining smaller requests in descending order.
6. If LEFT:
- Service smaller requests first.
- Reverse and service larger ones.
7. Sum total head movement.

11. Page Replacement - FIFO

1. Initialize all frames to -1.
2. Maintain a pointer (next) to track the oldest page.
3. For each page reference:
- If page is found → Hit.
- Else → Fault: Replace frame at next, move next circularly.
4. Count total page faults.

12. Page Replacement - LRU

1. Initialize frames as empty (-1).
2. For each page reference:
- If page is present → Hit, update its time.
- Else:
- If empty frame exists → place page.
- Else → replace page with minimum last-used time.
3. Display frame table after each reference.
4. Count page faults.

13. Page Replacement - Optimal

1. Initialize all frames as empty (-1).
2. For each page reference:
- If page exists in frames → Hit.
- Else:
- If empty frame exists → place page.
- Else: for each page in frame, find next future use.
- Replace page with farthest future use (or never used again).
3. Display frame table after each reference.
4. Count page faults.

14. Banker's Algorithm

1. Input number of processes n and resource types m.
2. Input Allocation matrix, Maximum matrix, and Available vector.
3. Calculate Need matrix: Need[i][j] = Max[i][j] - Allocation[i][j].
4. Print the Need matrix and Available resources.
5. Initialize Work = Available; Finish[i] = false for all i.
6. Find a process i such that:
- Finish[i] == false
- Need[i] <= Work (for all resource types)
7. If such process found:
- Work = Work + Allocation[i]
- Finish[i] = true
- Add i to safe sequence
8. Repeat step 6-7 until no such process exists.
9. If all processes finish → System is in SAFE state, print safe sequence.
10. Else → System is in UNSAFE state.