I'm trying to do some simulation of CPU memory allocation in Java. I've got a NEW queue, a READY queue, and then a block of memory, represented by an array of size 256. I'm meant to load in a series of processes into NEW, see if there is space for them in memory, and if there is, load them into the READY queue, "allocate" memory for them in the array, and then run processes as their turn comes up in the READY queue, deallocating as necessary. Very basic.
Problem is, my code is acting strange, and I'm not sure why. It seems to be skipping the allocation of every other process, so it "loads" 102, but skips 102, loads half of 103, skips 104, and so on. I cannot parse why.
The code is not fully functional, and isn't able to parse through running all jobs being put on the READY queue yet, because I saw this happening with the array and have been stuck on it. Any idea what's happening?
Here's code, input, and the output so far.
Weird output skipping every other process
101 NEW 5 4 0 50
102 NEW 3 3 1 30
103 NEW 4 5 2 100
104 NEW 2 2 3 60
105 NEW 1 6 4 40
106 NEW 3 3 5 70
107 NEW 2 4 6 20
108 NEW 4 5 7 90
109 NEW 5 3 8 50
110 NEW 1 2 9 60
// Create a FIFO CPU Scheduling simulation, Incorporating memory allocation and Deallocation
import java.io.File;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
class Process {
//Class for the processes in the queue
int pid, priority, burst, arrival, size, baseRegister, readyTime;
String processStatus;
//Need to add functionality that differentiates time in vs time started
// Tracks wait time, end time, turnaround, and response time
//Constructor, the only type we'll need
public Process(int pid, String processStatus, int priority, int burst, int arrival, int size) {
this.pid = pid;
this.processStatus = processStatus;
this.priority = priority;
this.burst= burst;
this.arrival = arrival;
this.size = size;
this.baseRegister = -1;
}
//Overwrite print to string method for the sake of printing the queue
public String toString() {
return this.pid + " " + this.processStatus + " " + this.burst + " " + this.arrival + " " + this.baseRegister;
}
//Getters
public int getPid() { return this.pid; }
public int getBurst(){ return this.burst; }
public int getArrival(){ return this.arrival; }
public int getSize() { return this.size; }
public int getBaseRegister() { return this.baseRegister; }
//Setters
public void setBaseRegister(int baseRegister) { this.baseRegister = baseRegister; }
public void setProcessStatus(String s) { this.processStatus = s; }
public void setReadyTime(int n) { this.readyTime = n; }
}
//Add functionality to print out memory array
//Add functionality of memory array
public class Main {
//Method to print memory array
public static void printMemory(String[] arr){
if(arr.length!=256){
System.out.println("Array is not a memory block");
return;
}
for(int i=0; i<256; i+=16){
for(int j=0; j<16; j++){
System.out.print(arr[j+i] + " ");
}
System.out.println("");
}
}
//Method to scan memory for a space that fits
public static int spaceInMem(String[] arr, int n){
for(int i = 0; i<arr.length; i++){
if(arr[i].equals("---")){
for(int x = 1; x<n; x++){
if(!arr[i+x].equals("---")){
i=i+x;
break;
}
if(x==n-1 && arr[i+x].equals("---")){
return i;
}
}
}
}
return -1;
}
public static void addToMem(String[] arr, int pid, int size, int index){
for(int i=index; i<size; i++){
arr[i] = "" + pid;
}
}
public static void removeFromMem(String[] arr, int baseRegister, int size){
for(int i = baseRegister; i<size; i++){
arr[i] = "---";
}
}
public static void main(String[] args) throws Exception {
//variables to declare
int pid, prio, burst, arrival, time, startTime, completeTime,
numProcesses, size, totalWT, totalTT, totalRT, remainingTime;
String status;
Process p, runningProcess;
boolean processIsRunning = false;
String[] memory = new String[256];
Arrays.fill(memory, "---");
//Import from File
File file = new File("data");
Scanner fscan = new Scanner(new FileReader(file));
Queue<Process> NEWQueue = new LinkedList<>();
Queue<Process> READYQueue = new LinkedList<>();
while(fscan.hasNext()){
pid = fscan.nextInt();
status=fscan.next();
prio= fscan.nextInt();
burst = fscan.nextInt();
arrival = fscan.nextInt();
size = fscan.nextInt();
NEWQueue.offer(new Process(pid, status, prio, burst, arrival, size));
}
fscan.close();
numProcesses = NEWQueue.size();
//System.out.println("PID BURST ARRIVAL COMPLETION TURNAROUND WAITING RESPONSE");
time = 0;
// for(int i=0; i<256; i++){
// memory[i] = ""+ (i+1);
// }
// printMemory(memory);
remainingTime = -1;
runningProcess = new Process(0, "FALSE PROCESS",0,0,0,0);
while(!NEWQueue.isEmpty()){
System.out.println("Time: " + time);
if(NEWQueue.peek().getArrival() == time){
int index = spaceInMem(memory,NEWQueue.peek().getSize());
if(index != -1){
p = NEWQueue.remove();
p.setBaseRegister(index);
READYQueue.offer(p);
p.setProcessStatus("READY");
p.setReadyTime(time);
System.out.println("Process " + p.getPid() + " added to READY QUEUE at time " + time);
addToMem(memory, p.getPid(), p.getSize(), p.getBaseRegister());
printMemory(memory);
}
}
if(!processIsRunning){
if(!READYQueue.isEmpty()){
runningProcess = READYQueue.remove();
runningProcess.setProcessStatus("RUNNING");
remainingTime = runningProcess.getBurst() -1;
System.out.println("Process " + runningProcess.getPid() + " has begun running at time = " + time);
processIsRunning = true;
}
} else{
remainingTime--;
if(remainingTime==0){
System.out.println("Process " + runningProcess.getPid() + " has finished running at time = " + time);
runningProcess.setProcessStatus("TERMINATED");
removeFromMem(memory, runningProcess.getBaseRegister(), runningProcess.getSize());
printMemory(memory);
processIsRunning = false;
}
}
time++;
// totalWT += startTime - p.getArrival();
// totalTT += completeTime - p.getArrival();
// totalRT += startTime - p.getArrival();
//System.out.printf("%-7d%-6d%-8d%-11d%-11d%-8d%-8d%n", p.getPid(),p.getBurst(),p.getArrival(),completeTime, completeTime - p.getArrival(),startTime - p.getArrival(),startTime - p.getArrival());
}
// System.out.println("Average Turnaround Time: " + totalTT/numProcesses);
// System.out.println("Average Waiting Time: " + totalWT/numProcesses);
// System.out.println("Average Response Time: " + totalRT/numProcesses);
}
}
2 Answers 2
When you add (or remove) a process from memory, your loop stops at size instead of index + size.
The first process works fine (because it starts at index 0)
The next process (102) allocates nothing (start at index 50, end in 30).
The next one (103) allocates only part of its memory, which looks like every other process is being skipped (
index = 50,size = 100, the loop runs fromi = 50..99. that allocates 50 cells, not 100)
Same bug exists in both addToMem and removeFromMem loops.
tldr;
Always loop from the base address through the size of the process:
for (int i = index; i < index + size; i++)
instead of
for (int i=index; i<size; i++)
Comments
The bug is in your addToMem and removeFromMem methods. Look at the loop bounds.
public static void addToMem(String[] arr, int pid, int size, int index){
for(int i=index; i<size; i++){ // BUG: should be i < index + size
arr[i] = "" + pid;
}
}
When process 102 (size 30) tries to allocate starting at index 50: our loop: for(int i=50; i<30; i++) → never executes because 50 is already greater than 30.
When process 103 (size 100) allocates starting at index 50: Your loop: for(int i=50; i<100; i++) → only fills 50 slots instead of 100.
yo can fix it like:
public static void addToMem(String[] arr, int pid, int size, int index){
for(int i = index; i < index + size; i++){
arr[i] = "" + pid;
}
}
public static void removeFromMem(String[] arr, int baseRegister, int size){
for(int i = baseRegister; i < baseRegister + size; i++){
arr[i] = "---";
}
}
The patten for(i = start; i < start + length; i++) is the standard way to iterate over a range of a given length starting at an offset.