- First-Come, First-Served (FCFS):
Description: In FCFS, the processes are executed in the order they arrive in the ready queue. The first process that arrives is the first to be executed.
Advantages: Simple and easy to implement.
Disadvantages: Can lead to the "convoy effect," where shorter processes get stuck waiting behind longer ones, causing inefficiency.
Implementation :
- Round Robin (RR):
Description: In Round Robin, each process is assigned a fixed time slice or quantum. The CPU cycles through the processes, executing each for the time quantum, then moves to the next process in the queue.
Advantages: Fairly distributes CPU time among all processes, reducing the chance of starvation.
Disadvantages: Performance heavily depends on the length of the time quantum. If it's too short, the overhead of context switching can be high; if too long, it behaves more like FCFS.
Implmentation :
- Priority Scheduling (Non-preemptive):
Description: In Priority Scheduling, each process is assigned a priority, and the CPU is allocated to the process with the highest priority. In the non-preemptive version, the CPU will not be taken away from a running process even if a higher-priority process arrives.
Advantages: Important tasks get executed first.
Disadvantages: Can lead to starvation, where low-priority processes may never get executed if higher-priority processes keep arriving.
Implementation :
- Shortest Job First (SJF):
Description: In SJF, the process with the shortest burst time (execution time) is selected next. This minimizes the average waiting time in the queue.
Advantages: Efficient in terms of reducing average waiting time.
Disadvantages: Difficult to implement since it requires precise knowledge of the burst time of processes. Also, can lead to starvation of longer processes.
Implementation :
Page replacement algorithms are used in operating systems to decide which memory pages to replace when a new page is required in the page frame.
- FIFO (First-In, First-Out) Replaces the oldest page in the memory.
Advantages:
Simple and easy to implement. Requires minimal tracking. Disadvantages:
May lead to poor performance (Belady's Anomaly).
Ignores usage patterns of pages.
Implementation:
- LRU (Least Recently Used) Replaces the page that has not been used for the longest time.
Advantages:
Approximates optimal performance in many scenarios. Adapts well to practical workloads. Disadvantages:
Implementation overhead due to tracking usage history.
Performance may degrade with frequent context switches.
Implementation:
- MRU (Most Recently Used) Replaces the page that was most recently used.
Advantages:
Useful in specific workloads where recently used data becomes irrelevant. Simpler to implement than LRU. Disadvantages:
Poor performance for general workloads.
Rarely matches real-world access patterns.
Implementation:
- OPTIMAL (Optimal Page Replacement) Replaces the page that will not be used for the longest time in the future.
Advantages:
Provides the best theoretical performance. Serves as a benchmark for other algorithms. Disadvantages:
Requires future knowledge, which is impractical.
Used primarily for analysis and comparison.
Implementation:
Fit algorithms determine how memory blocks are allocated to processes based on their size requirements.
- First Fit Allocates the first available block that is large enough.
Advantages:
Simple and fast. Reduces search time for allocation. Disadvantages:
Causes external fragmentation. Does not consider optimal utilization of space. \
- Next Fit Starts searching from the last allocated block and wraps around.
Advantages:
Similar speed to First Fit with improved locality. Prevents clustering near the start of memory. Disadvantages:
Suffers from fragmentation issues like First Fit. \
- Best Fit Allocates the smallest block that is large enough.
Advantages:
Reduces leftover space, minimizing fragmentation. Optimizes memory usage. Disadvantages:
Slower due to the need for scanning the entire list. May create small unusable gaps. \
- Worst Fit Allocates the largest available block.
Advantages:
Avoids small leftover gaps. Provides large contiguous space for future allocations. Disadvantages:
Wastes memory by allocating unnecessarily large blocks.
May lead to more fragmentation.
Fit Algorithm Implementation ( -1 indicates that the particular process has not been allocated any memory ) :
