• Year 2026
Operating System

Some Math for Practice

Various Times and Terms of Process

Arrival Time: The time when a process enters the ready queue.

Completion Time: The time when a process finishes execution.

Burst Time (Execution Time): Total time a process uses CPU for execution.

Turnaround Time: Total time from arrival to completion.
Formula: Turnaround Time = Completion Time − Arrival Time

Waiting Time: Time a process waits in the ready queue (excluding execution time).
Formula: Waiting Time = Turnaround Time − Burst Time

Response Time: Time from arrival until the process gets CPU for the first time.
Formula: Response Time = First CPU Time − Arrival Time

Throughput: Number of processes completed per unit time.

Arrival Time: process যখন ready queue-তে আসে সেই সময়।

Completion Time: process যখন execution শেষ করে সেই সময়।

Burst Time: process CPU-তে যত সময় run করে

Turnaround Time: arrival থেকে completion পর্যন্ত মোট সময়।
Formula: Turnaround Time = Completion Time − Arrival Time

Waiting Time: ready queue-তে অপেক্ষার সময় (execution বাদে)।
Formula: Waiting Time = Turnaround Time − Burst Time

Response Time: process প্রথমবার CPU পাওয়ার সময় − arrival time।

Throughput: নির্দিষ্ট সময়ে কতগুলো process complete হয়েছে।

FCFS CPU Scheduling (Processes with Same Arrival Time):
Consider the following table of arrival time and burst time for three processes P1, P2 and P3
ProcessArrival TimeBurst Time
p105
p203
p308
Find avg Turnaround & Waiting Time

  • Turnaround Time (TAT) = CT – AT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
FCFS CPU Scheduling (Processes with different Arrival Time):
Consider the given table below and find Completion time (CT), Turn-around time (TAT), Waiting time (WT), Response time (RT), Average Turn-around time and Average Waiting time.
Process IDArrival TimeBurst Time
P122
P256
P304
P407
P574

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Suppose we have set of four processes whose arrival times and CPU burst times are as follows −
ProcessArrival TimeCPU Burst Time
P106
P2410
P344
P483
Let us draw the GANTT chart and find the average turnaround time and average waiting time using non-preemptive SJF algorithm.

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Using preemptive SJF (SRTN) scheduling on the following processes, draw GANTT chart and find the average turnaround time and average waiting time.
ProcessArrival TimeCPU Burst Time
P108
P2410
P343
P4104

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Suppose that we have a set of four processes that have arrived at the same time in the order P1, P2, P3 and P4. The burst time in milliseconds and their priorities of the processes is given by the following table −
ProcessArrival TimeCPU Burst TimePriority
P1062
P24101
P3442
P4831
Considering that a lower priority value means higher priority, perform non-preemptive priority scheduling on it. Draw the GANTT chart and find the average turnaround time and average waiting time.

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Consider the following set of processes whose arrival times, burst times and priorities are give in the following table −
ProcessArrival TimeCPU Burst TimePriority
P1083
P24102
P3433
P41041
Considering that a lower priority value means higher priority, perform preemptive priority scheduling on it. Draw the GANTT chart and find the average turnaround time and average waiting time.

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Consider the following set of processes whose arrival times, burst times are give in the following table −
ProcessArrival TimeBurst Time
P128
P207
P319
Time Quantum=4 . Draw the GANTT chart and find the average turnaround time and average waiting time.

  • Turnaround Time (TAT) = FinishT – ArrivalT
  • Waiting Time (WT) = TAT – BT
  • Start Time (ST) = max(AT, Previous CT)
  • Finish Time (FT) / Completion Time (CT) = ST + BT
  • Waiting Time (WT) = ST – AT
  • Turnaround Time (TAT) = FT – AT
Consider we have three memory blocks of sizes 6, 12, and 25 units, and three processes of sizes 12, 25, and 30 units respectively. Allocate memory to these processes using the First Fit Algorithm.
Process No.Process SizeBlock No.
1122
2253
330Not Allocated
Initial Blocks
[6]   [12]   [25]
Step-by-step Allocation (scan from left each time)
P1 (12):
[6] ❌ too small → [12] ✅ allocate
Blocks: [6]   [0]   [25]

P2 (25):
[6] ❌ → [0] ❌ → [25] ✅ allocate
Blocks: [6]   [0]   [0]

P3 (30):
[6] ❌ → [0] ❌ → [0] ❌ → Not allocated
Consider we have five memory blocks of sizes 6, 5, 50, 20, and 14 units, and five processes of sizes 4, 10, 15, 20, and 23 units respectively. Allocate memory to these processes using the Best Fit Algorithm.
Process No.Process SizeBlock No.
145
21014
31520
42050
523Not Allocated
Initial Memory Blocks
[6]   [5]   [50]   [20]   [14]
🔹 Allocation (Best Fit)
P1 (4)  → [5]   → leftover = 1
Blocks: [6]   [1]   [50]   [20]   [14]

P2 (10) → [14]  → leftover = 4
Blocks: [6]   [1]   [50]   [20]   [4]

P3 (15) → [20]  → leftover = 5
Blocks: [6]   [1]   [50]   [5]   [4]

P4 (20) → [50]  → leftover = 30
Blocks: [6]   [1]   [30]   [5]   [4]

P5 (23) → ❌ Not allocated (no suitable block)
Consider we have five memory blocks of sizes 6, 5, 50, 20, and 16 units, and five processes of sizes 4, 10, 15, 20, and 23 units respectively. Allocate memory to these processes using the Worst Fit Algorithm.
Process No.Process SizeBlock No.
1450
21020
31516
420Not Allocated
523Not Allocated
Initial Blocks
[6]   [5]   [50]   [20]   [16]
🔹 Step-by-step Allocation (pick LARGEST available block)
P1 (4):
Largest block = 50 → allocate
[6] [5] [46] [20] [16]

P2 (10):
Largest block = 46 → allocate
[6] [5] [36] [20] [16]

P3 (15):
Largest block = 36 → allocate
[6] [5] [21] [20] [16]

P4 (20):
Largest block = 21 → allocate
[6] [5] [1] [20] [16]

P5 (23):
No block ≥ 23 → Not allocated
Consider page reference string 1, 3, 0, 3, 5, 6, 3 with 3-page frames. Find the number of page faults using FIFO Page Replacement Algorithm.

  • Initially, all memory slots are empty. So when pages 1, 3, and 0 arrive, they are loaded into the empty slots. Therefore, 3 Page Faults occur.
  • When page 3 arrives again, it is already present in memory. Therefore, 0 Page Fault occurs.
  • Then page 5 arrives. Since it is not available in memory, it replaces the oldest page, which is page 1. Therefore, 1 Page Fault occurs.
  • Next, page 6 arrives. It is also not available in memory, so it replaces the oldest page, which is page 3. Therefore, 1 Page Fault occurs.
  • Finally, page 3 arrives again. Since it is not present in memory, it replaces page 0. Therefore, 1 Page Fault occurs.
  • শুরুতে সব memory slot খালি থাকে। তাই যখন page 1, 3 এবং 0 আসে, তখন সেগুলো empty slot-এ load করা হয়। ফলে 3টি Page Fault ঘটে।
  • যখন আবার page 3 আসে, তখন এটি আগে থেকেই memory-তে থাকে। তাই 0টি Page Fault ঘটে।
  • এরপর page 5 আসে। যেহেতু এটি memory-তে নেই, তাই এটি সবচেয়ে পুরোনো page অর্থাৎ page 1-কে replace করে। ফলে 1টি Page Fault ঘটে।
  • এরপর page 6 আসে। এটিও memory-তে নেই, তাই এটি সবচেয়ে পুরোনো page অর্থাৎ page 3-কে replace করে। ফলে 1টি Page Fault ঘটে।
  • সবশেষে page 3 আবার আসে। যেহেতু এটি memory-তে নেই, তাই এটি page 0-কে replace করে। ফলে 1টি Page Fault ঘটে।
Consider the page references 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frame. Find number of page fault using Optimal Page Replacement Algorithm.

  • Initially, all memory slots are empty. So when pages 7, 0, 1, and 2 arrive, they are loaded into the empty slots. Therefore, 4 Page Faults occur.
  • When page 0 arrives again, it is already present in memory. Therefore, 0 Page Fault occurs.
  • When page 3 arrives, it is not available in memory. According to the Optimal Page Replacement algorithm, page 7 is replaced because it will not be used for the longest duration in the future. Therefore, 1 Page Fault occurs.
  • When page 0 arrives again, it is already available in memory. Therefore, 0 Page Fault occurs.
  • When page 4 arrives, it replaces page 1 according to the optimal replacement rule. Therefore, 1 Page Fault occurs.
  • For the remaining page references, the required pages are already available in memory. Therefore, 0 Page Fault occurs.

Note:

Optimal Page Replacement gives the best possible result by producing the minimum number of page faults. However, it is not practically possible because the operating system cannot predict future page requests.

This algorithm is mainly used as a benchmark to compare the performance of other page replacement algorithms.

  • শুরুতে সব memory slot খালি থাকে। তাই যখন page 7, 0, 1 এবং 2 আসে, তখন সেগুলো empty slot-এ load করা হয়। ফলে 4টি Page Fault ঘটে।
  • যখন page 0 আবার আসে, তখন এটি আগে থেকেই memory-তে থাকে। তাই 0টি Page Fault ঘটে।
  • যখন page 3 আসে, তখন এটি memory-তে available থাকে না। Optimal Page Replacement algorithm অনুযায়ী page 7 replace করা হয়, কারণ ভবিষ্যতে এটি সবচেয়ে দীর্ঘ সময় ব্যবহার হবে না। ফলে 1টি Page Fault ঘটে।
  • যখন page 0 আবার আসে, তখন এটি আগে থেকেই memory-তে available থাকে। তাই 0টি Page Fault ঘটে।
  • যখন page 4 আসে, তখন optimal replacement rule অনুযায়ী এটি page 1-কে replace করে। ফলে 1টি Page Fault ঘটে।
  • পরবর্তী page reference-গুলোর জন্য প্রয়োজনীয় page আগে থেকেই memory-তে available থাকে। তাই 0টি Page Fault ঘটে।

Note:

Optimal Page Replacement সর্বনিম্ন page fault তৈরি করে সবচেয়ে ভালো result প্রদান করে। তবে বাস্তবে এটি implement করা সম্ভব নয়, কারণ operating system ভবিষ্যতের page request আগে থেকে জানতে পারে না।

এই algorithm মূলত অন্যান্য page replacement algorithm-এর performance তুলনা করার benchmark হিসেবে ব্যবহৃত হয়।

Consider the page reference string 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 3 with 4-page frames. Find number of page faults using LRU Page Replacement Algorithm.

  • Initially, all frames are empty. When pages 7, 0, 1, and 2 arrive, they are loaded into the empty frames. Therefore, 4 Page Faults occur.
  • When page 0 arrives again, it is already present in memory. Therefore, a Hit occurs and there is 0 Page Fault.
  • When page 3 arrives, it is not available in memory. According to the LRU algorithm, page 7 is replaced because it was the least recently used page. Therefore, 1 Page Fault occurs.
  • When page 0 arrives again, it is already available in memory. Therefore, a Hit occurs and there is 0 Page Fault.
  • When page 4 arrives, it is not available in memory. According to the LRU algorithm, page 1 is replaced because it was the least recently used page. Therefore, 1 Page Fault occurs.
  • For the remaining page references (2, 3, 0, 3, 2, 3), all pages are already available in memory. Therefore, only Hits occur and no additional page faults are generated.

Total Page Faults = 6

  • শুরুতে সব frame খালি থাকে। যখন page 7, 0, 1 এবং 2 আসে, তখন সেগুলো empty frame-এ load করা হয়। ফলে 4টি Page Fault ঘটে।
  • যখন page 0 আবার আসে, তখন এটি আগে থেকেই memory-তে থাকে। তাই একটি Hit ঘটে এবং 0টি Page Fault হয়।
  • যখন page 3 আসে, তখন এটি memory-তে available থাকে না। LRU algorithm অনুযায়ী page 7 replace করা হয়, কারণ এটি সবচেয়ে দীর্ঘ সময় ব্যবহার হয়নি। ফলে 1টি Page Fault ঘটে।
  • যখন page 0 আবার আসে, তখন এটি আগে থেকেই memory-তে available থাকে। তাই একটি Hit ঘটে এবং 0টি Page Fault হয়।
  • যখন page 4 আসে, তখন এটি memory-তে available থাকে না। LRU algorithm অনুযায়ী page 1 replace করা হয়, কারণ এটি সবচেয়ে কম recently used page ছিল। ফলে 1টি Page Fault ঘটে।
  • পরবর্তী page reference (2, 3, 0, 3, 2, 3)-গুলোর জন্য সব page আগে থেকেই memory-তে available থাকে। তাই শুধুমাত্র Hit ঘটে এবং নতুন কোনো page fault হয় না।

মোট Page Fault = 6

• Year 2026
Computer Security

Leave a Comment

WhatsApp Telegram Messenger