help me plz RR cpu scheduling whith context switch time=1

RR cpu scheduling whith context switch time=1 and time quntum=5

Page 1 of 1

12 Replies - 7676 Views - Last Post: 19 April 2007 - 04:13 PM Rate Topic: -----

#1 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

help me plz RR cpu scheduling whith context switch time=1

Post icon  Posted 06 April 2007 - 01:40 PM

hi every one

help my plz

I wont the RR and fcfs cpu scheduling whith context switch time=1 and time quntum=5 no I/O
to show the Gantt chart and the average waiting time and average response time and average turn around time for both algorithms.
it is not problem to do the program with any kind of implemtion array,linked list....ect put NECESSARY in c or the c+
but help me plz the dead line is this monday

I have this code from this section but i can not do the changes to my constraints

this is the code
or plz tell me how the rr function in this code work ((tracing))

thank you



/* Scheduling Simulation*/

#include <stdio.h>
#include <stdlib.h>

/* Process Data Structure */
struct process {
	int pid;				/* Process ID */
	int burst;			  /* CPU Burst Time */
	int priority;		   /* Priority */
	int working;			/* Working time, for round-robin scheduling */
	int waiting;			/* Waiting time, for round-robin scheduling */
	struct process *next;
};

/* Function Prototype Declarations */
struct process *init_process (int pid, int burst, int priority);
void fcfs (struct process *proc);
void listprocs (struct process *proc);
void priority (struct process *proc);
void rr (struct process *proc, int quantum);
void sjf (struct process *proc);
 
/* Main Program Segment */
int main (void) {
	/* Initialize process list */
	struct process *plist, *ptmp;
	plist	   = init_process(1, 10, 3);
	plist->next = init_process(2,  1, 1); ptmp = plist->next;
	ptmp->next  = init_process(3,  2, 3); ptmp = ptmp->next;
	ptmp->next  = init_process(4,  1, 4); ptmp = ptmp->next;
	ptmp->next  = init_process(5,  5, 2);

	/* Perform simulations */
	listprocs(plist);
	fcfs(plist);
	sjf(plist);
	priority(plist);
	rr(plist, 1);

	/* Terminate cleanly */
	while (plist != NULL) {
		ptmp = plist;
		plist = plist->next;
		free(ptmp);
	};
	return(0);
};


/* Process list entry initialization routine */
struct process *init_process (int pid, int burst, int priority) {
	struct process *proc;
	proc = malloc(sizeof(struct process));
	if (proc == NULL) {
		printf("Fatal error: memory allocation failure.\nTerminating.\n");
		exit(1);
	};
	proc->pid = pid;
	proc->burst = burst;
	proc->priority = priority;
	proc->working = 0;
	proc->waiting = 0;
	proc->next = NULL;
	return(proc);
};


/* First-Come-First-Served scheduling simulation */
void fcfs (struct process *proc) {
	int time = 0, start, end;
	struct process *tmp = proc;

	printf("BEGIN:\tFirst-Come-First-Served scheduling simulation\n");

	while (tmp != NULL) {
		start = time;
		time += tmp->burst;
		end = time;
		printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
		tmp = tmp->next;
	};

	printf("END:\tFirst-Come-First-served scheduling simulation\n\n");
};


/* Process listing */
void listprocs (struct process *proc) {
	struct process *tmp = proc;

	printf("BEGIN:\tProcess Listing\n");

	while (tmp != NULL) {
		printf("PID: %d\t\tPriority: %d\tBurst: %d\n", tmp->pid, tmp->priority, tmp->burst);
		tmp = tmp->next;
	};

	printf("END:\tProcess Listing\n\n");
};


/* Priority scheduling simulation
 * Note: lower priority value gets a higher priority
 */
void priority (struct process *proc) {
	int time, start, end, highest;
	struct process *copy, *tmpsrc, *tmp, *beforehighest;

	printf("BEGIN:\tPriority scheduling simulation\n");

	/* Duplicate process list */
	tmpsrc = proc;
	copy = tmp = NULL;
	while (tmpsrc != NULL) {
		if (copy == NULL) {
			copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = copy;
		} else {
			tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = tmp->next;
		};
		tmpsrc = tmpsrc->next;
	};

	/* Main routine */
	time = 0;
	while (copy != NULL) {
		/* Find the next job */
		beforehighest = NULL;
		highest = copy->priority;
		tmp = copy->next;
		tmpsrc = copy;
		while (tmp != NULL) {
			if (tmp->priority < highest) {
				highest = tmp->priority;
				beforehighest = tmpsrc;
			};
			tmpsrc = tmp;
			tmp = tmp->next;
		};

		/* Process job and remove from copy of process list */
		if (beforehighest == NULL) {
			/* Handle first job is highest priority case */
			start = time;
			time += copy->burst;
			end = time;
			printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", copy->pid, time, start, end);
			tmpsrc = copy->next;
			free(copy);
			copy = tmpsrc;
		} else {
			/* Handle first job is not highest priority case */
			tmp = beforehighest->next;
			start = time;
			time += tmp->burst;
			end = time;
			printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
			beforehighest->next = tmp->next;
			free(tmp);
		};
	};

	printf("END:\tPriority scheduling simulation\n\n");
};


/* Round-Robin scheduling simulation */
void rr (struct process *proc, int quantum) {
	int jobsremain, passes;
	struct process *copy, *tmpsrc, *tmp, *slot;

	printf("BEGIN:\tRound-Robin scheduling simulation (Quantum: %d)\n", quantum);
	/* Duplicate process list */
	tmpsrc = proc;
	copy = tmp = NULL;
	while (tmpsrc != NULL) {
		if (copy == NULL) {
			copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = copy;
		} else {
			tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = tmp->next;
		};
		tmpsrc = tmpsrc->next;
	};

	/* Main routine */
	jobsremain = 1;
	slot = NULL;
	while (jobsremain) {
		jobsremain = 0;

		/* Pick next working slot */
		if (slot == NULL) {
			slot = copy;
			jobsremain = 1;
		} else {
			passes = 0;
			do {
				if (slot->next == NULL) {
					passes++;
					slot = copy;
				} else {
					slot = slot->next;
				};
			} while (passes <= 2 && slot->burst == slot->working);
			if (passes <= 2) {
				jobsremain = 1;
			};
		};

		/* Perform a cycle */
		tmp = copy;
		while (tmp != NULL) {
			if (tmp->burst > tmp->working) {
				if (tmp == slot) {
					tmp->working += quantum;
				} else {
					tmp->waiting += quantum;
				};
			};
			tmp = tmp->next;
		};
	};

	/* Display statistics and clean up copy */
	tmp = copy;
	while (tmp != NULL) {
		printf("Process: %d\tWorking: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, tmp->working, tmp->waiting, tmp->working + tmp->waiting);
		tmpsrc = tmp;
		tmp = tmp->next;
		free(tmpsrc);
	};

	printf("END:\tRR scheduling simulation\n\n");
};


/* Shortest Job First scheduling simulation */
void sjf (struct process *proc) {
	int time, start, end, shortest;
	struct process *copy, *tmpsrc, *tmp, *beforeshortest;

	printf("BEGIN:\tShortest Job First scheduling simulation\n");

	/* Duplicate process list */
	tmpsrc = proc;
	copy = tmp = NULL;
	while (tmpsrc != NULL) {
		if (copy == NULL) {
			copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = copy;
		} else {
			tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = tmp->next;
		};
		tmpsrc = tmpsrc->next;
	};

	/* Main routine */
	time = 0;
	while (copy != NULL) {
		/* Find the next job */
		beforeshortest = NULL;
		shortest = copy->burst;
		tmp = copy->next;
		tmpsrc = copy;
		while (tmp != NULL) {
			if (tmp->burst < shortest) {
				shortest = tmp->burst;
				beforeshortest = tmpsrc;
			};
			tmpsrc = tmp;
			tmp = tmp->next;
		};

		/* Process job and remove from copy of process list */
		if (beforeshortest == NULL) {
			/* Handle first job is shortest case */
			start = time;
			time += copy->burst;
			end = time;
			printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", copy->pid, time, start, end);
			tmpsrc = copy;
			copy = copy->next;
			free(tmpsrc);
		} else {
			/* Handle first job is not shortest case */
			tmp = beforeshortest->next;
			start = time;
			time += tmp->burst;
			end = time;
			printf("Process: %d\tEnd Time: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, time, start, end);
			beforeshortest->next = tmp->next;
			free(tmp);
		};
	};

	printf("END:\tShortest Job First scheduling simulation\n\n");
};

This post has been edited by reem9: 06 April 2007 - 02:20 PM


Is This A Good Question/Topic? 0
  • +

Replies To: help me plz RR cpu scheduling whith context switch time=1

#2 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 08 April 2007 - 12:08 PM

pllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllz help me
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 09 April 2007 - 04:34 AM

Well first read a bit about the algorithm.

This code works by selecting a job (slot) and then scrolling though the list and adding the quantum to the working time of the current selected job, or adding the quantum to the waiting time to all other processes.

I made a few comments here and there. Ireally I don't think that this is a very good version of the algorithm myself. I would re-write it.
void rr (struct process *proc, int quantum) {
	int jobsremain, //Flag var... there are still processes needing to execute?
		passes; //Number of times we scroll though process list looking for a process to work on...
	struct process *copy,  //Copy of the process list
				   *tmpsrc, // Temp pointer to inital list
				   *tmp,  //Temp node used to make a copy of the pricess list
				   *slot; //The current process that is working...

	//Scafold: Print Begin message.
	printf("BEGIN:\tRound-Robin scheduling simulation (Quantum: %d)\n", quantum);
	
	
	/* Duplicate process list */
	//Make a copy of prcess list, store in copy...
	tmpsrc = proc;
	copy = tmp = NULL;
	while (tmpsrc != NULL) {
		if (copy == NULL) {
			copy = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = copy;
		} else {
			tmp->next = init_process(tmpsrc->pid, tmpsrc->burst, tmpsrc->priority);
			tmp = tmp->next;
		};
		tmpsrc = tmpsrc->next;
	};

	/* Main routine */
	jobsremain = 1; //Set to get into the while() loop
	//If it were me, I would use a do {} while(); loop in this case... but I didn't code this.
	slot = NULL;
	while (jobsremain) {
		jobsremain = 0;	//Assume that there are no jobs waiting execution.

		/* Pick next working slot */
		if (slot == NULL) { //If there currently is no job executing...
			slot = copy;	//assign the first job to execute.
			jobsremain = 1; //ensure that we will stay in while() loop.
		} else {
			passes = 0;
			do {
				if (slot->next == NULL) { //if we reach the end of the list start over.
					passes++;
					slot = copy;
				} else { //else lets just get the next process...
					slot = slot->next;
				};
			} while (passes <= 2 && slot->burst == slot->working); 
			if (passes <= 2) {
				jobsremain = 1;
			};
		};

		/* Perform a cycle */
		tmp = copy;
		while (tmp != NULL) {
			if (tmp->burst > tmp->working) { //only look at non-completed jobs...
				if (tmp == slot) {
					tmp->working += quantum;
				} else {
					tmp->waiting += quantum;
				};
			};
			tmp = tmp->next;
		};
	};

	/* Display statistics and clean up copy */
	//Delete copy... and print stuff...
	tmp = copy;
	while (tmp != NULL) {
		printf("Process: %d\tWorking: %d\tWaiting: %d\tTurnaround: %d\n", tmp->pid, tmp->working, tmp->waiting, tmp->working + tmp->waiting);
		tmpsrc = tmp;
		tmp = tmp->next;
		free(tmpsrc);
	}; 

	printf("END:\tRR scheduling simulation\n\n");
};

Was This Post Helpful? 0
  • +
  • -

#4 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 09 April 2007 - 09:23 AM

thank you very very mutch for hlep me
but when you can to re-write it.
i wish to do it maximum until tomorrow AM pllllllllllllllllllllllz
with my constraints RR cpu scheduling whith context switch time=1, RR cpu scheduling whith context switch time=1 and time quntum=5

thank you to interest my problem . I would not forget this
reem9
Was This Post Helpful? 0
  • +
  • -

#5 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 09 April 2007 - 10:09 PM

I am sorry for your short time frame, I wish you had given us more time to help you, but we are NOT here to do your homework for you. If you want help understanding concepts, or debugging, cleaning code etc we can help, but you will have to burn the midnight oil coding yourself. That is just the nature of CS classes.

There is a neat link to "Live" programming help where someone gets paid and may be more willing to help, I don't know.
Was This Post Helpful? 0
  • +
  • -

#6 skyhawk133  Icon User is offline

  • Head DIC Head
  • member icon

Reputation: 1858
  • View blog
  • Posts: 20,275
  • Joined: 17-March 01

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 09 April 2007 - 10:15 PM

You can get live programming help here: http://www.kasamba.c...C...9&kbid=3005
Was This Post Helpful? 0
  • +
  • -

#7 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 10 April 2007 - 10:34 AM

I try to conect to live help but no one acept my problem
Iwont to under stand the problem not for my self not for the home work only and i wish to teach my how i can do this problem any time you can
thank you very much
Was This Post Helpful? 0
  • +
  • -

#8 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 15 April 2007 - 12:55 PM

why no one wont to help me?? :ohno: :sad3:
Was This Post Helpful? 0
  • +
  • -

#9 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 15 April 2007 - 01:07 PM

because you are not helping us help you. I answered what I knew to give you. I don't know how else to help unless I know what it is you don't understand.

If you don't understand ANYTHING about the program. Then find a good book on C and start on page 1. If you don't understand what the Round Robin scheduling is or how it works, then ask a spacific question: "What exactly is RR scheduling?" (although the links I posted should answer that). If you don't understand a notation is the above program, ask about it.

We are not mind readers. And you have the program, it has more than ussual commenting on it. You have discriptions of the algorithm, an entire web to google. -- Ask us spacific questions.

The best thing to do, would be to delete all the comments from the code and then try commenting it yourself. Then post the code with your thoughts and questions inside the code. This will help you understand, and will help us know how to answer you.
Was This Post Helpful? 0
  • +
  • -

#10 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 17 April 2007 - 08:03 AM

my Q is how i can implement fcfs and RR cpu scheduling whith context switch time=1 and time quntum=5 no I/O in c or c++ what is the steps ??
Was This Post Helpful? 0
  • +
  • -

#11 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 17 April 2007 - 10:45 AM

First question: Are you actually mannaging threads, or are you "simulating" it like the example you provided?

Well lets look at Round Robin. What does it do: It scrolls though a list of processes and lets each application have a certain amout of face-time (the quantum) with the processors. The amout of time the process has is the same for every process, and they have to wait until thier number comes up again before they get another shot.

So how do we implement this.

Well fist off we need a data structure to hold the processes. I would use a circular queue made from a linked structure. This list should contain all information nedded to call the process, and a link to the next process to call.

Then you set up the process for cycleling the list. look at the current node, call it, then set the current node to the next node. IF current node is NULL then have the processor wait a quantum for new process to be added, and try again.

Nothing too hard here.
Was This Post Helpful? 0
  • +
  • -

#12 reem9  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 10
  • Joined: 06-April 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 19 April 2007 - 07:44 AM

i wont "simulating" it like the example you provided

thank you
Was This Post Helpful? 0
  • +
  • -

#13 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2247
  • View blog
  • Posts: 9,237
  • Joined: 18-February 07

Re: help me plz RR cpu scheduling whith context switch time=1

Posted 19 April 2007 - 04:13 PM

Ok Begin mini-tutorial.

Step 1: Think about data modeling. We basicly need three models here. One for the processor, and one for the process. All that the model processor needs to do is keep track of the total time expired, the time needed to switch tasks, and the time given to each process (quanta). The process model has to keep track of how long the process will take, how much time it has had with the processor, how much time has passes since it began. Lastly we need a data structure to hold the process queue.

If we are in C++ then we need to make 3 classes. If we are in C we will probably want to add the queue to one of the other two modeles. (the example you provided made the process and queue models the same).

A list of functions needed for each model:
The processor model should have a "ExecuteProcess" function, that function will take a process as an argument and add the quanta to its executed time. It should print out the statistics for that model. If the process is not complete it should enqueue the process again.

The queue should have an "enqueue" and a "dequeue" function.

So remeber think: How do I MODEL these things. Start first with the data that you need to keep track of, group that in to the best models you can think of, then think about what functions you will need. If needed, go back and rearrange you data a little to make the implimentation work.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1