Hey there :) :) :)

I'm doing a "simulation" project for the first-come, first-served (FCFS) CPU scheduling algorithm.
To give u an idea of what this is:
CPU Scheduling is all about having a Scheduler determine which process should be allocated to the CPU next. It has many various algorithms such as priority sched, shortest-job-first, etc. But for this project, I'm doing the FCFS.

Yes! It's supposed to be the Easiest sched algorithm to implement. :P
Of course, since this is a "Simulation", I'm gonna have to make representations (models and not the real thing in the system) of the CPU, the processes and the scheduler.

All I have to do is store all processes in a FIFO queue. But the problem is that my teacher insists on incorporating a "Math Equation" to the program since it's supposed to be a "Simulation".
So I've found out about the "Little's Formula"
which is quite popular for Queueing Problems.

Now, the program specifics:
Processes will be generated randomly.
Each process will have a CPU-burst and an IO-burst which are both randomized.
Everytime a process becomes Ready, it will be added to the Queue.
The Scheduler then will allocate the CPU to the process if it is already that process's turn (if it's in front of the queue).
Once the process is allocated to the CPU, it will then be Executed based on its CPU-burst value. After that, the process will be thrown to another queue in case it has a randomized IO-burst. After the IO-burst it will be thrown back to the Ready Queue and wait for its turn to the CPU again.
This will keep looping until a certain number of processes has been allocated to the CPU and then the Loop will stop.
The AVERAGE WAITING TIME for the processes while they are in the Ready Queue is to be determined.

Here's what I've got so far and please tell me if i'm on the right track... :)

The code below basically creates 3 Threads (i used threads to represent processes)
and allocates them to the CPU but their CPU-bursts are fixed for now and they dont have IO bursts yet.

here's the Sched class

import java.util.*;

public class Sched extends Thread {
private Queue q;
private int burst;
private Thread current;
	public Sched() {
		this.setPriority(6);
		System.out.println("Set to priority 6: " + this.getName());
		burst = 1000;
		q = new LinkedList();
	}

	public Sched(int b) {
		burst = b;
		q = new LinkedList();
	}

	public void addThread(Thread t){
		q.offer(t); //add process/ thread to the Q
		System.out.println("Thread added: " + t.getName());
	}

	public void executeThread(){
		try{
			System.out.println("Executing: " + current.getName());
			Thread.sleep(burst);
			}
			catch(InterruptedException ex){};
	}

	public void run(){
		while(true){
			//
			current = (Thread)q.poll(); //remove the process/ thread from the Q
			if(current!=null){
				System.out.println("Current thread to execute: " + current.getName());
				executeThread();
			}
			else{
				if(q.isEmpty()){
				System.out.println("Queue is already empty...");
					break;
				}

			}
		}
	}
}

and here's the main

public class CPUSched {

    public static void main(String[] args) {

		Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
		Sched CPUScheduler = new Sched();
		CPUScheduler.start();

		Thread t1 = new Thread("Thread 1");
		t1.start();
		CPUScheduler.addThread(t1);
		Thread t2 = new Thread("Thread 2");
		t2.start();
		CPUScheduler.addThread(t2);
		Thread t3 = new Thread("Thread 3");
		t3.start();
		CPUScheduler.addThread(t3);
    }
}

I can easily add the Program Specifics above which is to keep on generating the processes with randomized cpu and io burst values.
but the problem is on incorporating the Little's formula to calculate for the Average Waiting time.
the formula is as easy as:
n = X * w
where n is the average size of the queue
X is the average ARRIVAL RATE of the processes into the queue (in processes per sec)
w is the AVERAGE WAITING TIME

here's the specific help that i need: :D :D :D
i have to keep on generating the processes not only with random burst values but also at Random Times, meaning each process should also have random arrival time.
Is there any way to track the Time when the whole program starts in Java?
and how do i incorporate it into this project....
thanks much <3 <3

oh and before i forget,
i also cant figure out how to display a Line Graph in java...
The time should be running on the X-axis and the average waiting time should be plotted on the Y-axis... and it should keep running while the program is scheduling and executing the processes... are there any packages in Java i can use for this???

For the time, you could use a Timestamp object created at the beginning and each point you want to check. Check out the any related Timestamp class (could be Date, Time, or something... can't remember).

In graph, you need a bit of computation. I usually implement from scratch from 2D graphic to draw it, but you may use other class if you want.

By the way, you actually try to complicate yourself by implementing it this way. It would be much simpler to not use Thread but your own class (may be called Process) instead. Though, it is your way and I would not change your mind.

Edited 5 Years Ago by Taywin: n/a

:) hey thanks
yes i was thinking of expanding those threads into my own class called Process which extends the Thread class...
coz i want the Process objects to generate their own random values for their burst times... but i havent had the time to code it all yet so i just used the Thread for now... :D

i'm really worried about the Time Graph though...
it's kinda like the one in downloading torrents where u have the Download speed at the y-axis and the time at the x-axis
or in the task manager where u have the network utilization % at the y-axis and the x is the running time....

ooh wait or should I use Runnable instead? :D

i gotta finish this in 12 hrs :P
deadline is on saturday but i have many things to do
so, i just found out about JavaFX and this is perhaps what i need:
http://blogs.sun.com/rakeshmenonp/entry/javafx_linechart#%22
im still fast-learning JavaFX though... it comes with Netbeans, so great! :)
in case u know something faster and easier to implement, let me know
pls and thank uuu

Well, simulation does not need to be real. You may not need Thread or Runnable at all. The reason is that you CPU scheduling simulation could be running in linear. Thread or runnable is useful when you want to do tasks that can be run in parallel. Also, it will be a lot easier to keep track on all values while running in linear fashion. That's why I said you are complicated yourself.

However, you want to take advantage of the project to learn JavaFX, it could be fine as long as you can get your work done. I would not stop you either.

hey thanks so much
i just realized that the process can be just a simple class... thanks! :D

i'm trying to connect the CPU scheduling topic to Process Synchronization topic
wherein multiple processes try to access a common resource which in this case is the CPU.

any idea how this can be multi-threaded?
I may assume that the system can be a multiprocessor system (not uniprocessor) so that i can have each CPU object to run as a separate thread(?)
or should it be the other way around... it's the process objects will i should run in separate threads and i will try to synchronize them so that they can have the CPU objects to 'execute' them.
so im heading to process synchronization now :) and i just have to put a flag variable in the CPU objects which should prevent another process from accessing it while it's currently allocated to one process.
is this enough synchronization scheme? :o

If you want to change it to use synchronization, your assignment would be more difficult to monitor for CPU Scheduling. The synchronization I normally use is to control and solve 'critical section' problem. The 'critical section' is a portion of shared resources which should be small. In other words, multiple processes can share a CPU, but only one may access the critical section at a time. If you want to learn this type of synchronization, you should try 'Concurrent Programming' or some sort of that. It is fun but not everyone can see the picture though.

If you want to use thread to do the CPU scheduling, you can get rid of the 'arriving time' for each Process but rather monitor when a process arrives in your CPU class. However, the rest of your process variables (length of completion, cpu-burst, etc.) would still remain. That's why using thread makes this assignment more complicated. ;)

This article has been dead for over six months. Start a new discussion instead.