In this post, we implement the First Come First Serve (FCFS) CPU scheduling algorithm in C++. FCFS is the simplest scheduling strategy — the process that arrives first in the ready queue gets the CPU first. It is non-preemptive: once a process starts, it runs to completion without interruption.
What is FCFS Scheduling?
FCFS works exactly like a real-world queue: the first person in line is served first. The CPU picks the first process from the ready queue, runs it completely, then picks the next. No reordering happens — processes execute strictly in arrival order.
The key metrics computed are:
Waiting Time (WT) — Time a process spends waiting before the CPU is allocated to it. Formula: WT[i] = WT[i-1] + BurstTime[i-1] - (ArrivalTime[i] - ArrivalTime[i-1])
Turnaround Time (TT) — Total time from arrival to completion. Formula: TT[i] = WT[i] + BurstTime[i]
A well-known drawback is the Convoy Effect — a long process can block many short ones behind it, inflating average waiting time.
In this post, we implement the Best Fit Memory Allocation Algorithm in C++. Unlike First Fit which takes the first block large enough for a job, Best Fit searches through all free blocks and selects the one whose size is closest to the job’s size — the tightest possible fit. The goal is to minimize wasted space inside allocated blocks (internal fragmentation) and preserve large blocks for future large jobs.
What is Best Fit Memory Allocation?
Best Fit works by sorting memory blocks in ascending order of size before allocation. By scanning the sorted list and taking the first block that fits, we automatically pick the smallest block that still accommodates the job. This is the defining characteristic of Best Fit: among all free blocks that are large enough, it selects the one with the smallest size, leaving the rest of the available space in larger blocks undisturbed for future use.
Sort all memory blocks in ascending order of size.
For each job, scan the sorted blocks and allocate the first free block whose size ≥ job size. Because blocks are sorted by ascending size, the first fitting block is automatically the smallest one that fits — i.e., the best fit.
After all allocations are done, re-sort blocks by their original block number so the output table is readable.
Compared to First Fit, Best Fit produces less internal fragmentation per allocation because it picks the tightest available block. However, it tends to leave behind many tiny leftover fragments that are too small to be reused — a form of external fragmentation. It is also slower than First Fit because it must consider all blocks before allocating.
The Midpoint Circle Algorithm (MPC) is an efficient way to draw a circle using raster graphics. It is an improved version of Bresenham’s circle drawing algorithm and avoids using floating-point calculations, making it faster for computer graphics. This blog post explains a C++ program that implements the Midpoint Circle Algorithm using the graphics.h library.
Ellipses are fundamental shapes in computer graphics, widely used in various applications such as image processing, animation, and CAD systems. In this blog post, we’ll explore how to draw an ellipse using the Midpoint Ellipse Algorithm in C++ with graphics.h.
Introduction to Midpoint Ellipse Algorithm
The Midpoint Ellipse Algorithm is an efficient way to generate an ellipse using only integer operations. It is based on the midpoint method, which determines the next pixel position by evaluating a decision parameter.
This algorithm divides the ellipse into two regions:
Region 1: The slope of the curve is less than 1.
Region 2: The slope of the curve is greater than 1.
Each region is processed separately to ensure a smooth curve.
C++ Code Implementation
Below is the C++ program that implements the Midpoint Ellipse Algorithm. It uses the graphics.h library, which is part of the Turbo C++ environment.
The Flood Fill Algorithm fills a connected region on a raster display by replacing all pixels that share the same original colour as the seed pixel with a new fill colour. Unlike the Boundary Fill Algorithm — which stops at a specific boundary colour — Flood Fill continues spreading in all directions as long as the pixel matches the original seed colour. It is the underlying technique used by the “Paint Bucket” tool in image editors.
The Digital Differential Analyzer (DDA) algorithm is one of the simplest line-drawing algorithms in computer graphics. It is an incremental method that determines intermediate points between two given endpoints of a line. In this blog post, we will explore the DDA algorithm, understand its working, and implement it using C++.
What is the DDA Algorithm?
The DDA (Digital Differential Analyzer) algorithm is a rasterization algorithm used to draw lines on a pixel-based display. It works by calculating the intermediate points that form a straight line between two given points and plotting them sequentially. The algorithm uses floating-point arithmetic to incrementally determine the next pixel position.
Steps of the DDA Algorithm:
Calculate the change in x (dx) and y (dy) between the starting and ending points.
Determine the number of steps required for the line. This is the greater value between dx and dy.
Compute the increment values dx/steps and dy/steps to determine how much x and y should increase per step.
Start from the initial point and iteratively plot the next points by adding the increment values.
Stop when the endpoint is reached.
C++ Implementation of DDA Algorithm
Here is a simple C++ program to implement the DDA line drawing algorithm using the graphics.h library:
The Cohen-Sutherland Line Clipping Algorithm is one of the most widely used algorithms in computer graphics for clipping line segments against a rectangular viewport. It works by assigning a 4-bit region code to each endpoint of a line to quickly determine whether the line is fully inside the window, fully outside, or needs to be clipped. The algorithm avoids expensive intersection calculations whenever possible, making it very efficient for real-time rendering pipelines.
