Question

Implement the CPU scheduling algorithm MLFQ in python. Have the program answer the table.

Multilevel Feedback Queue (absolute priority in higher queues)

            Queue 1 uses RR scheduling with Tq = 5

            Queue 2 uses RR scheduling with Tq = 10

            Queue 3 uses FCFS

All processes enter first queue 1. If time quantum (Tq) expires before CPU burst is complete, the process is downgraded to next lower priority queue. Processes are not downgraded when preempted by a higher queue level process. Once a process has been downgraded, it will not be upgraded.

Simulate and evaluate with the set of eight processes below.

Assumptions:

1. All processes are activated at time 0
2. Assume that no process waits on I/O devices.
3. After completing an I/O event, a process is transferred to the ready queue.
4. Waiting time is accumulated while a process waits in the ready queue.
5. Turnaround time is a total of (Waiting time) + (CPU burst time) + (I/O time)
6. Response time is the first measure of waiting time from arrival at time 0 until the first time on the CPU.

Process Data:

process goes {CPU burst, I/O time, CPU burst, I/O time, CPU burst, I/O time,…….., last CPU burst}

P1 {5, 27, 3, 31, 5, 43, 4, 18, 6, 22, 4, 26, 3, 24, 4}

P2 {4, 48, 5, 44, 7, 42, 12, 37, 9, 76, 4, 41, 9, 31, 7, 43, 8}

P3 {8, 33, 12, 41, 18, 65, 14, 21, 4, 61, 15, 18, 14, 26, 5, 31, 6}

P4 {3, 35, 4, 41, 5, 45, 3, 51, 4, 61, 5, 54, 6, 82, 5, 77, 3}

P5 {16, 24, 17, 21, 5, 36, 16, 26, 7, 31, 13, 28, 11, 21, 6, 13, 3, 11, 4}

P6 {11, 22, 4, 8, 5, 10, 6, 12, 7, 14, 9, 18, 12, 24, 15, 30, 8}

P7 {14, 46, 17, 41, 11, 42, 15, 21, 4, 32, 7, 19, 16, 33, 10}

P8 {4, 14, 5, 33, 6, 51, 14, 73, 16, 87, 6}

	MLFQ
CPU utilization
Avg Waiting time (Tw)
Avg Turnaround time (Ttr)
Avg Response time (Tr)

	MLFQ CPU utilization:
	Tw	Ttr	Tr
P1
P2
P3
P4
P5
P6
P7
P8
Avg

Answer 1

main.py

# Multi-level Feedback Queue Scheduling for tasks

import Queue from queue

queues = [ Queue(i*10, i) for i in range(256)]
# pendingProcs: [(pid, QIndex)]
pendingProcs = []
currProc = None
# At each timer tick (timer interval iterrupt triggered
# and this is the kernel-level handler)
def schedule():
    global currProc
    # is true except for the very first process to be scheduled at boot up
    if currProc is not None:
        # index and queue of residence of currently executing process
        index = currProc.priority

        Q = queues[index]

        p = currProc
        # if p is blocking for I/O
        if p.blocking == 1:
            # save process state to PCB
            # TODO
            Q.dequeue()

            # if p is at the top level
            if index == 0:
                Q.enqueue(p)

            # if p is not at the top level
            else:
                queues[index-1].enqueue(p)

        # if p leaves voluntarily
        elif p.leave == 1:
            # save process state to PCB
            # TODO
            Q.dequeue()

            pendingProcs.append({"pid" : p.PID, "Qindex" : index})

        # in all other cases, the process is marked as running
        # one cycle in the CPU
        else:
            # 1 unit in queue's quantum time for task has been used up
            p.Qtime =-1
            # 1 unit of task's time has been completed
            p.time -=1
            # if the task has used up available quantum time
            if p.Qtime <= 0:
                # save process state to PCB
                # TODO

                # remove from current queue
                Q.dequeue()
                # and is not yet completed
                if p.time > 0:
                    # add to next lowest queue
                    queues[index + 1].enqueue(p)
                # and is completed
                else:
                    # TODO: destroy p
                    pass

            # if quantum time is not complete but task is completed
            elif p.time <= 0:
                Q.dequeue()
                # TODO: destroy p

            #nothing to be done. Else clause only included for completeness
            else:
                pass

    # goes through each of the 256 queues
    for Q in enumerate(queues):
        # empty queues are disregarded
        if not Q.isEmpty():
            # assign CPU to first process in first nonempty queue
            p = Q.peek()
            currProc = p
            # send p to CPU
            break

def addToQueue(process):
    # if the process previously yielded and is now returning to the queue
    if (entry = filter(lambda pp: pp["pid"] == process, pendingProcs)) is not None:
        # place back in the queue it yielded from
        queues[entry["Qindex"]].enqueue(process)
    else:
        # place in the top queue
        queues[0].enqueue(process)

queue.py

class Queue():

    def __init__(self, quantum, priority):
        self.items = []
        self.quantum = quantum
        self.priority = priority

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        item.Qtime = self.quantum
        item.priority = self.priority
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

    def peek(self):
        return self.items[-1]

task.py

class Task():
    def __init__(self, taskTime):
        self.taskTime = taskTime
        self.Qtime = 0
        self.priority = 0