Feature #2: Resume Process

Implementing the "Resume Process" feature for our "Operating System" project.

Description

Our second task is building a feature to identify which process should be resumed into memory from its preempted state. Initially, one or more contiguous memory blocks are allocated to each running process. The allocation is done in ascending order of process ID. This means that the lower-numbered process IDs get memory blocks near address 0, and higher-numbered process IDs get allocated at higher addressed portions of memory. Some processes are preempted(interrupted) and currently don’t have any memory allocated to them. The OS wants to schedule one of the preempted processes. The OS uses a strategy that the resumes preempted processes in a round-robin fashion, starting with the one that has the lowest process ID. We are currently in the nth round of process resumption. Our task is to find the nth process to resume from an array of process IDs that are currently in memory.

We’ll be provided with an array of process IDs and a number n. We’ll have to find the nth missing process id starting from the beginning of the array.

Solution

Since we are searching for a number in a sorted array, the binary search algorithm would be most applicable to use here. Let’s assume we have an array of process IDs [5, 7, 9, 10, 13] and we want to find and resume the 3rd process that was preempted. In other words, we need to find the 3rd missing number from the sorted array.

Following the binary search algorithm, we’ll keep dividing the array from the middle to search for the required missing number in the first and second halves. The first division of our array [5,7,9,10,13] gives us [5,7,9] as our first half and [9,10,13] as our second. If there are no missing numbers in a subarray, the size of the subarray should be one plus the difference between the last and first numbers. For our first subarray [5, 7, 9], the actual size is 3. However, we expected there to be 95+19 - 5 + 1 ...