Lunatic Server Solutions Interview Question for Computer Scientists
- 0of 0 votes
AnswersAn older has a very old computer at his house. It is so old that there is no notion of virtual memory in the operating system. Instead it uses a simple memory allocation technique called the 'Best Fit Algorithm'. The BFA works like this:
- PriyaDarad May 26, 2012 in United States
Whenever a request comes in for some memory space, the OS looks for the smallest, continuous empty space, which can satisfy it, and allocates a portion of this region to the program making the request. If such space cannot be found, the program is terminated and all the memory used by the program is freed. Any program can get terminated due to two reasons:
The program exits
Enough memory is not available to start the program or keep it running
All memory requests that come in at the same time-instant are processed in ascending order of process-id. If while processing, a program is terminated for lack of memory, all memory held by it is freed before processing any other request and no further memory requests by the terminated program are considered. All termination is also done in order of process-id.
You have to write a program to simulate this algorithm and print out the number of processes that were terminated due to lack of memory.
Note:
1.No process will request for memory before its start-time or after its end-time.
2.All memory sizes are specified in KB.
3.The memory is linear in nature, i.e., addresses do not wrap around. It starts at zero and goes up to N-1 KB.
4.At a given time unit, all processes that have reached end-time will be terminated (and memory freed) before other memory requests are serviced.
5.The total free space available in memory might be enough to satisfy a request, however the OS will terminate the process if a continuous region of empty space is not found
Input specification:
First line has an integer N (0 < N <= 1000), size of the memory in KB.
Second line of input will have integer P (0 <= P <= 20), the total number of processes to be run on the system.
Next P lines will have data for each process in the following format:
<process-id> <start-time> <end-time> <initial-memory>
These input lines will be sorted in ascending order of the process-id.Process-id will be unique integers greater than zero.
Next line will have integer R (0<= R <= 20), which specifies the subsequent memory requests by any process.
Next R lines have the following format:
<process-id> <request-time> <memory-required>
Output specification:
An integer specifying the number of processes that were terminated due to lack of memory
Sample Input and Output:
Input:
100
4
1 3 7 20
2 0 4 30
3 0 3 70
4 0 10 25
2
3 2 30
2 2 10
Output:
2
Input:
10
2
1 0 8 4
2 0 3 2
3
1 1 2
2 1 2
1 4 4
Output:
1| Report Duplicate | Flag | PURGE
Lunatic Server Solutions Computer Scientist Java