5 Replies - 362 Views - Last Post: 22 August 2019 - 06:06 PM Rate Topic: -----

#1 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

FIFO scheduling vs Priority Based Round Robin

Posted 19 August 2019 - 09:15 AM

Hi everyone,

I am working on trying to implement a FIFO scheduling policy as opposed to the Priority Based Round Robin Scheduling policy.

I was trying to implement it using queues but I am running into a small challenge: I am trying to enqueue each process I create and then let the first process run infinitely after every process has run one time.

This is what I have so far

int main(int argc, char **argv)
{
  pid32 process2, process3, process4; // main is process1
  process2 = create(processRun, 1024, 5, "Process2", 0); // first param is name of function, size, priority, name of process, how many arguments
  process3 = create(processRun, 1024, 10, "Process3", 0);
  process4 = create(processRun, 1024, 20, "Process4", 0);

  enqueue(process2, readylist); // readylist is defined in another file as a global variable
  enqueue(process3, readylist);
  enqueue(process4, readylist);

  return OK;
}

void processRun()
{
  while(1)
  {
    kprintf("Process %d is running\n", getpid());
    sleep(1); // sleeps the process so another process can run
  }
  return; // will only be executed when the loop breaks
}



I am having a hard time trying to get the values in the queue so that I can either wait or break the loop for the processes that do not need to run anymore after that.

Any insight would be helpful

This is what's in my queue
struct qentry queuetab [NQENT]; /* table of process queues */

// insert a process at the tail of a queue
pid32 enqueue(pid32 pid, qid16 q)
{
  int tail, prev; // tail and previous node indexes
  
  if(isbadqid(q) || isbadpid(pid)
    return SYSERR;

  tail = queuetail(q);
  prev = queuetab[tail].qrev;
  queuetab[pid].qnext = tail; // insert just before tail node
  queuetab[pid].qprev = prev;
  queuetab[prev].qnext = pid;
  queuetab[tail].qprev = pid;

  return pid;
}


This post has been edited by fearfulsc2: 19 August 2019 - 10:41 AM


Is This A Good Question/Topic? 0
  • +

Replies To: FIFO scheduling vs Priority Based Round Robin

#2 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: FIFO scheduling vs Priority Based Round Robin

Posted 21 August 2019 - 07:14 PM

First question: Why are you trying to implement a complicated queue by building a doubly-linked list within an array? It looks like your queue only holds PIDs which are integers? In the grand scheme of things, it's not that expensive to pay the O(n) price of shifting integers in an array of integers when the first item is removed. Furthermore since you are doing FIFO anyway, it's not like you need to quickly find out what next PID is going to be since you need first process to completely die before you move on to the next process.

Next question: How do you ever expect to get past your first process? Your runProcess() is an infinite loop. That means it will never end. Sure your first process will go in, but it will never go out. Or is there some magic meaning regarding sleep() where it actually means yield control to the next process and kick the current process out?
Was This Post Helpful? 0
  • +
  • -

#3 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: FIFO scheduling vs Priority Based Round Robin

Posted 22 August 2019 - 06:12 AM

Yes, that is the problem I am dealing with. Each process is supposed to be an infinite running process until they are either killed or interrupted.

Right now the system is a round-robin highest priority first approach. So the process with the highest priority will run first while the other processes are being starved if the first process never completes or gets interrupted. As for the magic meaning of sleep, it's a personal function not the standard sleep function from C

syscall	sleep(
	  uint32	delay		/* time to delay in seconds	*/
	)
{
	if (delay > MAXSECONDS) {
		return(SYSERR);
	}
	sleepms(1000*delay);
	return OK;
}


syscall	sleepms(
	  uint32	delay		/* time to delay in msec.	*/
	)
{
	intmask	mask;			/* saved interrupt mask		*/

	mask = disable();
	if (delay == 0) {
		yield();
		restore(mask);
		return OK;
	}

	/* Delay calling process */

	if (insertd(currpid, sleepq, delay) == SYSERR) {
		restore(mask);
		return SYSERR;
	}
	sltop = &queuetab[firstid(sleepq)].qkey;
	slnonempty = TRUE;
	proctab[currpid].prstate = PR_SLEEP;
	resched();
	restore(mask);
	return OK;
}


Was This Post Helpful? 0
  • +
  • -

#4 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: FIFO scheduling vs Priority Based Round Robin

Posted 22 August 2019 - 06:51 AM

But with FIFO, there is no yielding. There is no time slicing like round robin. In FIFO, when an app gets the CPU, it gets it full time until it is done or is terminated by the OS. If it is in an infinite loop, then too bad, nobody gets the CPU.
Was This Post Helpful? 0
  • +
  • -

#5 fearfulsc2   User is offline

  • D.I.C Regular

Reputation: 16
  • View blog
  • Posts: 276
  • Joined: 25-May 16

Re: FIFO scheduling vs Priority Based Round Robin

Posted 22 August 2019 - 06:59 AM

Then I am really confused

Because as of right now, when I enqueue, the processes will run in order and the next process will run when I call sleep.

So right now, it will be
Process 2
Process 3
Process 4
Process 2
Process 3
Process 4
Process 2
Process 3
Process 4
Process 2
Process 3
Process 4
Process 2
Process 3
Process 4
Process 2
Process 3
Process 4
........

So I figured that the FIFO was working. The problem is that I need to have it be like this
Process 2
Process 3
Process 4
Process 2
Process 2
Process 2
Process 2
....
Was This Post Helpful? 0
  • +
  • -

#6 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7020
  • View blog
  • Posts: 23,840
  • Joined: 05-May 12

Re: FIFO scheduling vs Priority Based Round Robin

Posted 22 August 2019 - 06:06 PM

It looks like you are still trying to do round-robin with your first-in, first-out.

From Wikipedia's computing scheduling regarding first-in, first-out:

Quote

  • Since context switches only occur upon process termination, and no reorganization of the process queue is required, scheduling overhead is minimal.
    :
  • The lack of prioritization means that as long as every process eventually completes, there is no starvation. In an environment where some processes might not complete, there can be starvation.
    :

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1