CC-17 : Simulate round robin CPU time allocator using a CircularSingleLinkedList.
Description:
Write and test code for round robin CPU time allocator simulator:
Round robin CPU timeslot allocator (Circular Single Link List) has a set of nodes that represent processes that need CPU time “10->6->3->9->4”. Data value of each nodes represents how many more seconds of CPU time is required by the process.
1 second CPU time should be allocated to each process, in a round robin manner, until the processes required CPU time becomes 0.
Each time CPU is allocated, required node’s required CPU time should be reduced by 1 second and data value of node should be updated with this new required time.
Test cases and expected outputs:
| Input Parameters |
Expected outputs |
| Add these nodes one by one to CPU Time Allocator and check its contents after each add operation:
4->5->7->4->5
|
Nodes with CPU time required:4->3->7->4->5 (last node points to first node)
Nodes with CPU time required:3->3->7->4->5 (last node points to first node)
Nodes with CPU time required:3->2->7->4->5 (last node points to first node)
Nodes with CPU time required:3->2->6->4->5 (last node points to first node)
Nodes with CPU time required:3->2->6->3->5 (last node points to first node)
Nodes with CPU time required:3->2->6->3->4 (last node points to first node)
Nodes with CPU time required:2->2->6->3->4 (last node points to first node)
Nodes with CPU time required:2->1->6->3->4 (last node points to first node)
Nodes with CPU time required:2->1->5->3->4 (last node points to first node)
Nodes with CPU time required:2->1->5->2->4 (last node points to first node)
Nodes with CPU time required:2->1->5->2->3 (last node points to first node)
Nodes with CPU time required:1->1->5->2->3 (last node points to first node)
Nodes with CPU time required:1->5->2->3 (last node points to first node)
Nodes with CPU time required:1->4->2->3 (last node points to first node)
Nodes with CPU time required:1->4->1->3 (last node points to first node)
Nodes with CPU time required:1->4->1->2 (last node points to first node)
Nodes with CPU time required:4->1->2 (last node points to first node)
Nodes with CPU time required:3->1->2 (last node points to first node)
Nodes with CPU time required:3->2 (last node points to first node)
Nodes with CPU time required:3->1 (last node points to first node)
Nodes with CPU time required:2->1 (last node points to first node)
Nodes with CPU time required:2 (last node points to first node)
Nodes with CPU time required:1 (last node points to first node)
Circular Linked list empty
|
Pseudocode:
| Initialize a CircularSingleLinkedList with list of processes shown above.
|
| Use loops to iterate through the nodes list using next links.
|
| Once node is reached, reduce its data value by -1 (i.e require cpu time is reduced).
|
| Once data value reaches 0, remove node from Circular Single Linked List.
|
| Once all nodes are removed from CircularSingleLinked List, exit the program.
|
Code:
public class CircularSingleLinkedListCPUAllocator {
CircularSingleLinkedList circularSingleLinkedList=this.new CircularSingleLinkedList();
public void circularSingleLinkedListCpuAllocator() throws Exception{
SingleLinkedListNode currentNode=circularSingleLinkedList.getFirstNode();
while (circularSingleLinkedList.getFirstNode()!=null) {
SingleLinkedListNode nextNode=currentNode.getNextNode();
currentNode.setNodeData(currentNode.getNodeData()-1);
if (currentNode.getNodeData()<=0) {
circularSingleLinkedList.remove(0);
}
currentNode=nextNode;
circularSingleLinkedList.printSingleLinkList("Nodes with CPU time required:");
}
}
}
Click here to download and run code and test cases !
Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it.
Be sure to try your own test cases to enhance your understanding !
You can also tweak the code to optimize or add enhancements and custom features.
Note: For easier code execution and easier reference, the class below contains code for CircularLinkedList and SingleLinkedListNode as internal classes. Ideally both these classes should be separate public classes.
public class CircularSingleLinkedListCPUAllocator {
CircularSingleLinkedList circularSingleLinkedList=this.new CircularSingleLinkedList();
public void circularSingleLinkedListCpuAllocator() throws Exception{
SingleLinkedListNode currentNode=circularSingleLinkedList.getFirstNode();
while (circularSingleLinkedList.getFirstNode()!=null) {
SingleLinkedListNode nextNode=currentNode.getNextNode();
currentNode.setNodeData(currentNode.getNodeData()-1);
if (currentNode.getNodeData()<=0) {
circularSingleLinkedList.remove(0);
}
currentNode=nextNode;
circularSingleLinkedList.printSingleLinkList("Nodes with CPU time required:");
}
}
public static void main(String[] args) {
try {
CircularSingleLinkedListCPUAllocator circularSingleLinkedListCPUAllocator = new
CircularSingleLinkedListCPUAllocator();
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.addLast(4);
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.addLast(3);
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.addLast(7);
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.addLast(4);
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.addLast(5);
circularSingleLinkedListCPUAllocator.circularSingleLinkedList.
printSingleLinkList("Nodes with CPU time required:");
circularSingleLinkedListCPUAllocator.circularSingleLinkedListCpuAllocator();
} catch (Exception e) {
e.printStackTrace();
}
}
class CircularSingleLinkedList {
private SingleLinkedListNode firstNode=null;
public SingleLinkedListNode getFirstNode() {
return firstNode;
}
public void setFirstNode(SingleLinkedListNode firstNode) {
this.firstNode = firstNode;
}
public boolean addLast(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(firstNode);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);
node.setNextNode(firstNode);
return true;
}
}
public boolean addFirst(int data){
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
if (firstNode==null) {
firstNode=node;
node.setNextNode(firstNode);
return true;
}
else {
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {currentNode=currentNode.getNextNode();}
currentNode.setNextNode(node);;
node.setNextNode(firstNode);
firstNode=node;
return true;
}
}
public boolean add(int data, int pos){
int size=getSize();
if ((pos<0) || (pos > size)) { return false;}
if (pos==0) {
addFirst(data);
return true;
}
if (pos==size) {
addLast(data);
return true;
}
if (firstNode==null) {return false;}
SingleLinkedListNode node=new SingleLinkedListNode();
node.setNodeData(data);
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
do {
if ((idx==pos)){
node.setNextNode(prevNode.getNextNode());
prevNode.setNextNode(node);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
} while (currentNode !=firstNode);
return false;
}
public int getSize() {
if (firstNode == null) { return 0; }
SingleLinkedListNode currentNode=firstNode;
int idx=0;
do {
currentNode=currentNode.getNextNode();
idx++;
}while (currentNode !=firstNode) ;
return idx;
}
public boolean removeFirst() {
if (firstNode == null) { return false; }
if (firstNode.getNextNode()==firstNode) {
firstNode=null;
return true;
}
SingleLinkedListNode currentNode=firstNode;
while (currentNode.getNextNode()!=firstNode) {
currentNode=currentNode.getNextNode(); }
currentNode.setNextNode(firstNode.getNextNode());
firstNode=firstNode.getNextNode();
return true;
}
public boolean removeLast() {
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
do {
if (currentNode.getNextNode()==firstNode) {
if (prevNode==null) {
firstNode=null;
return true;
}
prevNode.setNextNode(firstNode);
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
} while (currentNode !=firstNode);
return false;
}
public boolean remove(int data){
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
do {
if (currentNode.getNodeData() == data) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==firstNode) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
} while (currentNode !=firstNode);
return false;
}
public boolean removeAtPos(int pos){
if (firstNode == null) { return false; }
SingleLinkedListNode currentNode=firstNode;
SingleLinkedListNode prevNode=null;
int idx=0;
do {
if (idx==pos) {
if (prevNode==null) {
removeFirst();
return true;
}
if (currentNode.getNextNode()==firstNode) {
removeLast();
return true;
}
prevNode.setNextNode(currentNode.getNextNode());
return true;
}
prevNode=currentNode;
currentNode=currentNode.getNextNode();
idx++;
} while (currentNode !=firstNode);
return false;
}
public int get(int idx) {
if (firstNode == null) { return Integer.MIN_VALUE; }
SingleLinkedListNode currentNode=firstNode;
int currIdx=0;
do {
if (currIdx==idx) {return currentNode.getNodeData();}
currentNode=currentNode.getNextNode();
currIdx++;
}while (currentNode !=firstNode);
return Integer.MIN_VALUE;
}
public void traverse() {
SingleLinkedListNode currentNode=firstNode;
do{
System.out.println(currentNode.getNodeData());
currentNode=currentNode.getNextNode();
}while (currentNode !=firstNode);
}
public void printSingleLinkList() throws Exception {
// Case 1: The Circular Linked list is empty !!
if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
// Case 2: Print CircularLinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("****************************************");
System.out.print("CircularSingleLinkedList nodes: ");
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != firstNode) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != firstNode);
System.out.print("<last node points to first node>");
System.out.println();
System.out.println("****************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
public void printSingleLinkList(String labelText) throws Exception {
// Case 1: The Circular Linked list is empty !!
if (firstNode == null) { System.out.println("Circular Linked list empty"); return; }
// Case 2: Print CircularLinkedList node by node
SingleLinkedListNode currentNode=firstNode;
System.out.println();
System.out.println("****************************************");
System.out.print(labelText);
do {
System.out.print(currentNode.getNodeData());
if (currentNode.getNextNode() != firstNode) System.out.print(" -> ");
currentNode=currentNode.getNextNode();
} while( currentNode != firstNode);
System.out.print("<last node points to first node>");
System.out.println();
System.out.println("****************************************");
System.out.println();
Thread.sleep(2000);
;
return;
}
}
class SingleLinkedListNode {
private SingleLinkedListNode nextNode=null;
private int nodeData=0;
public SingleLinkedListNode getNextNode() {
return nextNode;
}
public void setNextNode(SingleLinkedListNode nextNode) {
this.nextNode = nextNode;
}
public int getNodeData() {
return nodeData;
}
public void setNodeData(int nodeData) {
this.nodeData = nodeData;
}
}
}