Operating Systems: Lab 1 SPF(Shortest-Process-First)

Shortest-Process-First(or Shortest-Job-First) Scheduling.
This algorithm is sort with the brust time or remaining time, and chooses the least of it to executing.

This algorithm is the minimize average waiting time for given set of processes. And it is a special priority algorithm.

The aim of this Lab is realize this algorithm (with preemptive).

Process Scheduling

Scheduling chooses which processes need to be execute.

Context Switch

Each process has a PCB to store the state. When the process turn to terminate or ready(waiting),
Operating System will save the PCB of old process and load the PCB of new process.
This called context switch.

A context is the contents of a CPU’s registers and program counter at any point in time
A context switch is the switching of the CPU from one process or thread to another

Usually, context switch will happen when the interrupt/system call occur.

Preemptive and Non-preemptive.

About SPF algorithm, there have Non-preemptive and preemptive.

Non-preemptive:
The process state may switch iff the executing process was terminated.

Preemptive:
The process state may switch when new process insert to ready queue or the executing process was terminated.

We need to check who is the least remaining time when process arrived.

Using Heap

Simple way to choice the least time is sort process every times or scan each process.
But time complexity is higher.
Here used the heap of data structure.

Heap is an easy data structure, can get the least or biggest element from top.
Advantage of this is dynamic maintenance the least element and lower time complexity.

More information please click here: 面向对象的数据结构 – 以 Heap 为例

Thinking About Realize

There are two methods here to solve the problem.

Method 1

Set a time counter, expression the time elapse.
On each time, we need to check the if the process terminate or new process arrive.

The advantage of the method is simulation the real elapse, but will pay the more time.

Method 2

The other method is memory each time point of process, and then to check if the process needed switch.
The time point likes arrive time, burst time, and so on.

The advantage of the method is may be use the less time, but is not conform to the operating running.

In this Lab, we chose the first method.

Algorithm Realize

Basic element – PCB

Here use the PCB instead the process.

Instance Fields

• static int numberOfProcess: Static variable, provie the PID to each process.
• private int arriveTime: Store the arrive time of the process.
• private int burstTime: Store the burst time of process.
• private int remainingTime: Remaining time of the process.
• private int startTime: The time when the process first turn to running, is unique.
• private int endTime: The time when the process remaining time is zero.
• private int runTime:The time when the process turn to running.
• private int preemptTime: The time when the process is preempted.
• private int PID: The unique identity of process.
• private int queueID: The order of push to heap;

remainingTime,arriveTime and PID will be the key word to compare in Heap.

Constructors

There are four constructors:

• PCB(): Default constructor, it will allocation PID to process.
• PCB(int): In order make the index of first process is one, we need use the constructor to push ’empyt process’ to the heap.
• PCB(int, int): Ths constructor will called PCB() and initialize arriveTime,burstTime.
• PCB(int, int, int, int, int, int, int, int): To complete the deep copy.

When the Switch

• void preempt(int): When the process turn to running, program will call this method.
  • It store the startTime and change the runTime.
• void isPreempted(int): When the process is preempted or terminated, program will call this method.
  • It store the endTime and change the preemptedTime.

Other methods

• void elapse(): Substract one from remaining time.
• PCB copy(): return a deep copy of the process.

Heap and ProcessQueue

ProcessQueue is extends from Heap, and override the Compare(int, int) method.

Instance Fields and Constructors

private ArrayList<PCB> heap;

• private ArrayList<PCB> heap: Container of element. Usually we used the array to instead the tree struct.
• private static int order: Order of elements.
• Heap(): create an ArrayList instance, and push an ’empty process’.

Common Methods

• void up(int): Make the lesser element to upper layer.
• void down(int): Make the bigger element to lower layer.
• PCB top(): Return the least element
• void push(PCB): Push an element to heap
• void pop():Pop an element from heap
• int size(): Return the number of elements.(’empty process’ is not included)
• boolean empyt(): Return is the Heap empty or not.

Other Methods

• void swap(int, int): Swap two element that index is u and v;
• int compare(int, int): Compare two elements by three keywords.Positive is u bigger than v, negative is v bigger than u.
  • Compare the element in ArrayList.
  • The first keyword is remaining time,
  • The second keyword is queue id.
  • Queue id is the order of the element push the heap.
  • As we know that remaining time may be the same, but queueID is unique.
  • So according to the queueID to compare can always be true.

Queue

• Queue(): constructor, to create a queue instance.
• void push(PCB): Push an element to the queue.
• PCB back():Return the last element of queue.
• boolean empty():Return is the Queue empty or not.

Print Result

Queue stores the result of process scheduling, we need print result to screen.

Extra, we can use Python to draw the Gantt Chart, so we print the result to csv, too.

public void out()
{
    System.out.println("\t\tRT\tPT"); 
    for(PCB pcb : queue)
    {
        System.out.println("process "+pcb.getPID()+":\t"+pcb.getRunTime()+"\t"+pcb.getPreemptTime());
    }

    File writeFile = new File(".\\write.csv");

    try {
        
        BufferedWriter writeText = new BufferedWriter(new FileWriter(writeFile));
        
        writeText.write("PID,RT,PT");

        
        for(PCB pcb : queue) 
        {
            writeText.newLine(); 
            writeText.write("process "+pcb.getPID()+","+pcb.getRunTime()+","+pcb.getPreemptTime());
        }

        writeText.close();
    } catch (FileNotFoundException e) {
        System.out.println("Cannot find file.");
    } catch (IOException e) {
        System.out.println("Error when reading file.");
    }
}

SPF

The main part of the algorithm implementation.

Instance Fields and Constructor

• Heap readyQueue: Process which arrived will push to the readyQueue.
• ProcessQueue processQueue: All the process will store here, and move it to readyQueue when the process arrived.
• Queue queue: Store each process switch.
• SPF(): Initialize instance.

Input the Process State

At first, program will print prompt message to the screen.

Program will receives an integer.Then, you need enter arrived time and brust time of each process.

Simulation

We set a time tag to represents the real passage of time.

If and only if the readyQueue, processQueue both are empty and no process is running that the program can be exit.

According the scheduling policy, new process should push to ready queue first.
Then, if the process which the least remaining time is changed, the running process needed too.
In other ways, if the running process terminated, now we need choses the process which remaining time is least.

When the process switch, we will call two methods:

• void save(): Call the isPreempted(int), and push PCB to queue.
• void load(): Call the preempt(int).

Draw Gantt Chart

After the program, we can execute the Python to draw the Gantt Chart.

import plotly as py
import plotly.figure_factory as ff
import pandas as pd
import numpy as np
import os
 
pyplt = py.offline.plot

process = []

_data = pd.read_csv("./write.csv")
processID = _data["PID"]
runTime = _data["RT"]
preemptTime = _data["PT"]  
RTList = np.array(runTime)
PTList = np.array(preemptTime)
idx=0;
for newName in processID:
    st=runTime[idx]
    et=preemptTime[idx]
    single = dict(Task = newName , Start = pd.to_datetime(st,format='%M'), Finish = pd.to_datetime(et,format='%M'))
    idx+=1
    process.append(single)
print(process) 

 
fig = ff.create_gantt(process,index_col='Task',showgrid_x=True,show_colorbar=True,group_tasks=True)
fig.write_image('./Gantt.png')

Example

Class Main

public class Main{
    public static void main(String []args)
    {
        SPF spf= new SPF();
        spf.start();
    }
}

/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */

Class PCB

public class PCB 
{
    static int numberOfProcess;
    private int arriveTime;
    private int burstTime;
    private int remainingTime;
    private int startTime;
    private int endTime;
    private int runTime;
    private int preemptTime;
    private int PID;
    private int queueID;

    /*
     * This are three constructor.
     */
    PCB() 
    {
        this.PID = numberOfProcess;
        numberOfProcess++;
        this.startTime = -1;
        this.endTime = -1;
        this.runTime = -1;
        this.preemptTime = -1;
    }

    PCB(int empty_PID)
    {
        this.PID=empty_PID;
    }

    PCB(int _arriveTime, int _burstTime) 
    {
        this();
        this.arriveTime = _arriveTime;
        this.burstTime = _burstTime;
        this.remainingTime = _burstTime;
    }

    PCB(int arriveTime, int burstTime, int remainingTime, int preemptTime, 
        int startTime, int runTime, int endTime, int PID)
    {
        this.arriveTime = arriveTime;
        this.burstTime = burstTime;
        this.remainingTime = remainingTime;
        this.preemptTime = preemptTime;
        this.startTime = startTime;
        this.runTime = runTime;
        this.endTime = endTime;
        this.PID = PID;
    }

    /*
     * When the process is preempted or preempt other process,
     * it will calls the following two methods;
     */

    public void preempt(int nowTime)
    {
        this.runTime = nowTime;

        if(this.startTime == -1)
        {
            this.startTime = nowTime;
        }
    }

    public void isPreempted(int nowTime) 
    {
        this.preemptTime = nowTime;
        if(this.remainingTime == 0)
        {
            this.endTime = nowTime;
        }
    }

    /*
     * There are some accessor.
     */
    public int getArriveTime()
    {
        return this.arriveTime;    
    }

    public int getStartTime()
    {
        return this.startTime;
    }

    public int getEndTime()
    {
        return this.endTime;
    }

    public int getRunTime()
    {
        return this.runTime;
    }

    public int getPreemptTime()
    {
        return this.preemptTime;
    }
    
    public int getRemaining()
    {
        return this.remainingTime;
    }

    public int getPID()
    {
        return this.PID;
    }
    public int getQueueID()
    {
        return this.queueID;
    }


    /*
     * There are some mutator.
     */

    public void elapse()
    {
        this.remainingTime --;
    }
    public void setQueueID(int qID)
    {
        this.queueID = qID;
    }

    /*
     * Make deepcopy.
     */
    public PCB copy()
    {
        PCB PCB_COPY = new PCB(this.arriveTime, this.burstTime, this.remainingTime, 
                               this.preemptTime, this.startTime, this.runTime, 
                               this.endTime, this.PID);
        return PCB_COPY;
    }
}


/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */

Class Heap (And Class ProcessQueue)

Heap:

import java.util.*;

public class Heap 
{
    ArrayList<PCB> heap;
    private static int order;

    /*
     * Initialize the heap.
     * In order make the index of first process is one, 
     * we need use the constructor to push 'empyt process' to the heap.
     */
    Heap()
    {
        heap = new ArrayList<PCB>();
        PCB emptyPCB = new PCB(-1);
        heap.add(emptyPCB);
        order = 0;
    }

    /*
     * Swap the element in ArrayList.
     */
    void swap(int u, int v)
    {
        PCB Temp = heap.get(u);
        heap.set(u, heap.get(v));
        heap.set(v, Temp);
    }

    /*
     * Compare the element in ArrayList.
     * The first keyword is remaining time,
     * The second keyword is queue id.
     * 
     * Queue id is the order of the element push the heap.
     * 
     * As we know that remaining time may be the same, but queueID is unique.
     * So according to the queueID to compare can always be true.
     */
    int compare(int u, int v) 
    {
        PCB pcb1 = heap.get(u);
        PCB pcb2 = heap.get(v);

        if (pcb1.getRemaining() == pcb2.getRemaining()) 
        {
            if(pcb1.getQueueID() > pcb2.getQueueID())
            {
                return 1;
            }else{
                return -1;
            }
        }

        if (pcb1.getRemaining() > pcb2.getRemaining()) 
        {
            return 1;
        }

        if (pcb1.getRemaining() < pcb2.getRemaining()) 
        {
            return -1;
        }

        System.out.println("Error, please check the method!");
        return 0;
    }

    /*
     * We need two operations to make the heap is legal.
     * The purpose of up() is make the lesser element to upper layer.
     * The purpose of down() is make the bigger element to lower layer.
     */
    public void up(int point) 
    {
        while (point != 0 && (this.compare(point, point / 2) < 0)) {
            this.swap(point, point / 2);
            point /= 2;
        }
    }

    public void down(int point) 
    {
        int size=heap.size()-1;
        while(point * 2 <= size)
        {
            int temp = point;
            if(point * 2 <= size && (this.compare(point, point * 2) > 0)) 
            {
                temp = 2 * point;
            }
            if(point * 2 + 1 <= size && (this.compare(temp,point * 2 + 1) > 0)) 
            { 
                temp = 2 * point + 1;
            }
            if(point != temp)
            {
                this.swap(point,temp);
                point = temp;
            }else break;
        }
    }

    /*
     * There is some common method of data structure. 
     */
    public void push(PCB newNode)
    {
        newNode.setQueueID(order);
        heap.add(newNode);
        order++;
        this.up(heap.size() - 1);
    }

    public PCB top()
    {
        if(this.empty()) return null;
        else return heap.get(1);
    }

    public void pop() 
    {
        int size = heap.size();
        heap.set(1,heap.get(size - 1));
        heap.remove(size-1);
        down(1);
    }

    public boolean empty()
    {
        if(heap.size() > 1) 
        {
            return false;
        }else{
            return true;
        }
    }

    public int size()
    {
        return heap.size();
    }

}

/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */

ProcessQueue:

public class ProcessQueue extends Heap{

    int compare(int u, int v) 
    {
        PCB pcb1 = heap.get(u);
        PCB pcb2 = heap.get(v);

        if (pcb1.getArriveTime() == pcb2.getArriveTime()) 
        {
            if(pcb1.getPID() > pcb2.getPID())
            {
                return 1;
            }else{
                return -1;
            }
        }

        if (pcb1.getArriveTime() > pcb2.getArriveTime()) 
        {
            return 1;
        }

        if (pcb1.getArriveTime() < pcb2.getArriveTime()) 
        {
            return -1;
        }

        System.out.println("Error, please check the method!");
        return -2;
    }
    
}


/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */

Class Queue

import java.util.*;
import java.io.*;
public class Queue {
    ArrayList<PCB> queue;
    
    Queue()
    {
        this.queue = new ArrayList<PCB>();
    }

    public void push(PCB pcb)
    {
        queue.add(pcb.copy());
    }    

    public PCB back()
    {
        if(queue.size() == 0) return null;

        return queue.get(queue.size()-1);
    }       
    
    public boolean empty()
    {
        if(queue.size() == 0)
        {
            return true;
        }else{
            return false;
        }
    }

    public void out()
    {
        System.out.println("\t\tRT\tPT"); 
        for(PCB pcb : queue)
        {
            System.out.println("process "+pcb.getPID()+":\t"+pcb.getRunTime()+"\t"+pcb.getPreemptTime());
        }

        File writeFile = new File(".\\write.csv");

        try {
            
            BufferedWriter writeText = new BufferedWriter(new FileWriter(writeFile));
            
            writeText.write("PID,RT,PT");

            
            for(PCB pcb : queue) 
            {
                writeText.newLine(); 
                writeText.write("process "+pcb.getPID()+","+pcb.getRunTime()+","+pcb.getPreemptTime());
            }

            writeText.close();
        } catch (FileNotFoundException e) {
            System.out.println("没有找到指定文件");
        } catch (IOException e) {
            System.out.println("文件读写出错");
        }
    }
}


/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */

Class SPF

import java.util.*;

public class SPF {

    private Heap readyQueue;
    private ProcessQueue processQueue;
    private Queue queue;

    SPF()
    {
        this.readyQueue = new Heap();
        this.processQueue = new ProcessQueue();
        this.queue = new Queue();
    }

    public void inputProcess()
    {
        Scanner in = new Scanner(System.in);
        /* 
         * Prompt message for the program.
         */
        System.out.println("Please enter the number of the process:");
        int numberOfProcess = in.nextInt();// Enter the number of process
        System.out.println("Please enter the information about the each process:");
        System.out.println("Use the AT for 'Arrive Time, and the BT for 'Brust Time");
        System.out.println("\t\tAT\tBT"); 

        /*
         * Enter the state of each process.
         * About arrive time and burst time.
         * And then, process will join the process queue.
         */
        int _arriveTime;
        int _burstTime;
        for(int i = 0; i < numberOfProcess; i++)
        {
            System.out.print("Process " + i +":\t");
            _arriveTime = in.nextInt();
            _burstTime = in.nextInt();
            PCB test = new PCB(_arriveTime, _burstTime);
            processQueue.push(test);
        }

        in.close();
    }

    public void save(int nowTime, PCB process)
    {
        if(process == null) return;
        
        process.isPreempted(nowTime);
        queue.push(process);
    }

    public void load(int nowTime, PCB process)
    {
        process.preempt(nowTime);
    }

    public void simulation()
    {
        /*
         * Process queue is a queue of process which is not arrive.
         * When the top of process queue is arriving and move it to ready queue.
         * 
         * Ready queue is a queue of process which is arrived but not terminated.
         * And it use a heap to organize the data.
         * 
         * There used the loop to simulate the time lapses.
         */
        int nowTime = 0;
        PCB runningProcess = null;
        /*
         * If and only if the readyQueue, processQueue both are empty 
         * and no process is running that the program can be exit.
         */
        while( !processQueue.empty() || !readyQueue.empty() || runningProcess != null)
        {
            /*
             * Check the top of process queue,
             * When the process arrived, move it to ready queue.
             * Because of the multiple process may be arrived at the same time,
             * we need to check the top of process queue until the process is not arrived.
             */
            while(!processQueue.empty())
            {
                PCB newProcess = processQueue.top();
                if(newProcess.getArriveTime() == nowTime)
                {
                    readyQueue.push(newProcess);
                    processQueue.pop();
                }else{
                    break;
                }
            }

            /*
             * Check the running process, and make it remaining time subtract 1.
             * After elapse, we need check the remaining time of running process.
             */

            if(runningProcess != null)
            {
                runningProcess.elapse();
                /*
                 * Check if the running process needed to be terminated.
                 */
                if(runningProcess.getRemaining() == 0)
                {
                    this.save(nowTime,runningProcess);
                    runningProcess = null;
                }
            }

            /*
             * About ready queue:
             * In preempt-SJF,
             * process state may switch when new process insert to ready queue
             * or the executing process was terminated.
             * In non-preempt-SJF, 
             * process state may switch iff the executing process was terminated.
             * 
             * There is preempt-SJF, so we need to check who is the least remaining time when process arrived.
             */
            PCB topProcess = readyQueue.top();
            /*
             * Check if the running process needed to switch.
             */
            if(topProcess == null)
            {
                /*
                 * Ready queue is empty.
                 */
                nowTime++;
                continue;
            }
            if(runningProcess == null)
            {
                /*
                 * No process is running now, 
                 * just let topProcess turn to running.
                 */
                this.load(nowTime,topProcess);
                runningProcess = topProcess;
                readyQueue.pop();
            }
            else if( topProcess.getRemaining() < runningProcess.getRemaining())
            {
                /*
                 * topProcess is lesser than runningProcess,
                 * We need save runningProcess at first,
                 * then load the topProcess
                 */

                this.save(nowTime,runningProcess);
                readyQueue.push(runningProcess);

                this.load(nowTime,topProcess);
                runningProcess = topProcess;
                readyQueue.pop();               
            }
            nowTime++;
        }
    }

    public void start()
    {
        this.inputProcess();
        
        this.simulation();

        queue.out();
    }
}


/*
 * ----------------In Sept.2022----------------
 * SDUT Operating Systems: Lab 1 SPF
 * By SDUT Bulbul.
 * Blog: https://bulbul559.cn
 * ----------------In Sept.2022----------------
 */