An intuitionistic based novel approach to highest response ratio next CPU scheduler

Abstract

The extension of CPU schedulers with fuzzy logic has been ascertained better because of its capability of handling imprecise information. Though, other generalized forms of fuzzy logic can be used which can further extend the performance of the scheduler. This paper introduces a novel approach for Highest Response Ratio Next (HRRN) CPU scheduler which uses the concept of intuitionistic fuzzy set theory. The proposed scheduler has the capability to dynamically deal with the impreciseness of the response ratio and to make the system adaptive based on the continuous feedback. An intuitionistic fuzzy inference system has been implemented. In this paper, to validate the performance of the scheduler a simulation environment has been implemented and the performance is compared with the other three baseline schedulers (Conventional HRRN scheduler, Fuzzy based HRRN scheduler and Vague based HRRN scheduler). Simulation results prove the effectiveness and efficiency of intuitionistic fuzzy based HRRN scheduler.

Keywords

CPU schedulers intuitionistic fuzzy set theory highest response ratio next (HRRN) scheduling intuitionistic fuzzy based HRRN scheduler

1. Introduction

The efficacy of any operating system majorly depends on the CPU scheduler used. The prime function of CPU scheduler is to support the multitasking. A CPU scheduler selects one task among different ready tasks and assigns the CPU to it. The decision of the CPU scheduler is subject to the scheduling algorithm used [1, 2, 3]. Several scheduling algorithms have been explored by different researchers. Each scheduling algorithm has its own characteristics and importance [4, 5]. However, the common goal is to assure the performance of the system in terms of response time, waiting time, throughput etc. This paper explores the Highest Response Ratio Next scheduling algorithm for handling the impreciseness of response ratio.

Global scheduling scheme always schedules the highest priority task available for execution. However, in real world, scenario may be different [6]. It would be more realistic to find possible compromises between parameters which help the scheduler to choose the next best task. Even, in an operating system, there is no option to determine the exact value of parameters [7]. These parameters may have imprecise values which can affect the functioning and efficiency of the operating system. Likewise, the imprecise values of the parameters may affect the decision of the CPU scheduler. HRRN based scheduler takes the decision based on the response ratio [8]. The impreciseness may be the part of response ratio which can affect the performance. Fuzzy set theory and its extended theories have the capabilities to handle the impreciseness of data and to decide in what order the requests should be executed to better utilize the system [4].

Fuzzy set theory works on a single membership value that has some limitations [12]. It cannot address both the evidences: evidence in favor and evidence against. Numerous extended theories like vague set theory, intuitionistic fuzzy set theory, rough set theory, neutrosophic theory etc. are available in the literature to overcome the limitations of single membership value [13, 14, 15]. In literature, only a few of the authors have explored the response ratio with fuzzy set theory and vague set theory [9, 10, 11].

Although, these approaches obtain respectable solutions but none of these algorithms have explored the intuitionistic fuzzy set theory for the same. Intuitionistic fuzzy set theory has many advantages over fuzzy set theory [16, 17] and has very much similarity with vague set theory [18, 19]. Therefore, in this paper a novel intuitionistic fuzzy logic approach to HRRN CPU scheduler has been introduced. Intuitionistic HRRN (IHRRN) CPU scheduler dynamically computes the response ratio considering the impreciseness present in the data of each task and then makes the decision in scheduling of those tasks. The performance of IHRRN CPU scheduler is evaluated and compared with HRRN, Fuzzy HRRN (FHRRN) and Vague HRRN (VHRRN) algorithms [7, 8, 10]. Results prove IHRRN performs much better.

The rest of the paper is as follows: Section 2 briefly discusses the basic HRRN scheduling algorithm and its related work. Section 3 describes the intuitionistic fuzzy set theory. Section IV defines the proposed IHRRN CPU scheduler in detail. Section 4 represents the simulation model and performance evaluation of IHRRN scheduler with the other baseline HRRN scheduling techniques. Finally, last section concludes the efficiency and performance of IHRRN CPU scheduler.

2. HRRN CPU scheduler and state of the art

Brinch Hansen introduced a non-preemptive sched- uling called Highest Response Ratio Next (HRRN) over the biased policy of Shortest Job First (SJF) scheduling in which shortest tasks take priority over the longer tasks. HRRN is a kind of heuristic non-preemptive scheduling that combines the SJF and FCFS scheduling techniques which works on response ratio. Unlike SJF, the task’s priority not only depends on its estimated burst time, but also on its time spent waiting for CPU as given in Eq. (2). It behaves like SJF for short tasks but increases the priority of longer tasks as they wait to prevent starvation. Therefore, the task with highest response ratio is scheduled first with CPU. Ready queue is updated or rearranged every time based on the highest response ratio.

$\displaystyle\text{Response ratio}=(\text{Waiting time}+\text{Estimated}$

(1) $\displaystyle\quad\text{Burst Time})/(\text{Estimated Burst Time})$

The tasks with same waiting time are prioritized by the scheduler based on the shortest burst time. If multiple tasks are having same burst time, then the priority goes to the task with longest waiting time. Minimum value for response ratio is 1 and it is possible when waiting time is 0. Otherwise, it is directly proportional to the waiting time. For each task, the system should have the strategy which can reduce the response ratio.

In comparison to other scheduling algorithms, HRRN scheduling algorithm will return the high throu-ghput and low/good response time but increases overhead on CPU. However, in literature; HRRN algorithm is concluded as the best scheduling algorithm among various scheduling algorithms [20, 21]. Therefore, the increased overhead can be ignored.

A small number of the researchers have explored the HRRN scheduling heuristic. Therefore, limited literature is available on it. In 2011, Nie et al. have introduced a new scheduling algorithm in order to share the CPU time to the longest tasks and to maintain the HRRN transcendency status. Authors have used the HRRN scheduling algorithm to schedule the task and proposed a time slice using the concept of median [22]. Task is partitioned into multiple parts based on the burst time of the task and on the calculated median of burst time of the tasks. Each part of the new task queue follows HRRN for scheduling. Different applications like grid computing, wireless network scheduling etc are also available in literature where researchers have applied HRRN scheduling algorithms.

As stated in the literature, when a task enters in to the machine, system is unaware of exact values of the parameters associated with the task such as burst time/service time, priority (high/medium/low) of tasks etc. [23]. Unawareness can affect the decisions of CPU scheduler due to the possibility of impreciseness which can further affect the performance of system. Very few of the researchers have also worked on this impreciseness to enhance the performance of the system [24].

In 2008, Moallemi and Asgharilarimi have used the fuzzy logic approach to deal with the impreciseness and inexactness of HRRN parameters: burst time and waiting time. The proposed non-preemptive algorithm set the priorities of the tasks in a more accurate way [9]. In same year, Abdurazzag Ali Aburas and Vladimir Miho also introduced a fuzzy logic based algorithm that was similar to HRRN scheduling algorithm [25]. This inference system has used two input parameters service time and waiting time to generate the optimized priority which changes dynamically.

In 2011, Bashir Alam et al. have proposed another Fuzzy approach to HRRN scheduling. Authors have considered impreciseness of three input parameters: static priority, expected remaining time and the response ratio to generate the dynamic priority. The work assumed random arrival and burst time values of tasks. Authors claimed that Fuzzy HRRN (FHRRN) performs better than HRRN [10]. There are several other generalized fuzzy set theories that are available in the literature which handles impreciseness in a better way. In 2013, Supriya et al. have applied the concept of vague set theory over the parameters of HRRN scheduling. Authors considered two important factors: burst time and waiting time to generate the dynamic response ratio [8]. Authors claimed that Vague HRRN (VHRRN) scheduling algorithm performs better than the FHRRN scheduling algorithm.

This work explores the other important generalized theory of fuzzy set i.e. intuitionistic fuzzy set theory on the parameters of HRRN. The next section introduces the preliminaries of intuitionistic fuzzy set theory which is the central part of the proposed work.
3. Intuitionistic fuzzy set theory

Prof. Zadeh had presented fuzzy set theory to tackle the incomplete and imprecise knowledge. In fuzzy set, each element of a set is having a single degree of membership in interval [0, 1].

Definition 1 (Fuzzy Set): Consider $X=\{x_{1},x_{2},\ldots,$ $x_{n}\}$ as the universal set. A fuzzy set F is defined as $\{x,\mu_{F}(x)\}$ where $\mu_{F}(x)\to[0,1]$ . The membership value $\mu F(x)$ denotes the degree of membership or belongingness of element $x$ in $F$ [26, 27].

As stated earlier, there are other several generalized forms of fuzzy set theory exist [12]. In 1986, Atanassov had introduced intuitionistic fuzzy set theory which extends the concept of fuzzy single membership into two membership functions: degree of membership and degree of non-membership but both functions should be in the same interim [28]. Pawlak had presented another theory of impreciseness called rough set. Like intuitionistic fuzzy approach, it expresses impreciseness with lower and upper approximation of the set. Lower approximation states the membership of those elements which belongs to the set. Opposite to that upper approximation represents those elements that possibly belong to the set [29]. Gau et al. had introduced vague set theory which has again replaced the concept of fuzzy single membership function into two individual membership functions: truth membership function and false membership function [15]. Some of the researchers claimed that both vague and intuitionistic fuzzy set theory are like each other [18]. However, author is treating both theories as different and considering intuitionistic fuzzy set approach for this work.

Definition 2 (Intuitionistic Fuzzy Set): An intuitionistic fuzzy set $I$ in the universal set $X=\{x_{1},x_{2},$ $\ldots,x_{n}\}$ is defined by two functions: $D_{I}$ and $N_{I}$ . Here, $D_{I}$ denotes the degree of membership and $N_{I}$ denotes the non-degree of membership function. $I$ in $X$ can be symbolized as

Figure 1.

Architectural view of IHRRN CPU scheduler.

$I=\{<x,D_{I}(x),N_{I}(x)>:x\in X\}$ Where, $D_{I}(x)$ $\in[0,1],N_{I}(x)\in[0,1]$ . Though, these two membership functions can be used individually but must satisfy the relation given in Eq. (2).

$\displaystyle 0\leqslant D_{I}(x)+N_{I}(x)\leqslant 1$ (2)

Definition 3 (Intuitionistic Fuzzy Set Index): The degree of indeterminacy of element $x$ in the intuitionistic fuzzy set $I$ and is represented by $I_{I}(x)$ where $x\in X$ [30]. In other words, it defines the lack of knowledge for the membership of element $x$ in the set $I$ . It is calculated as mentioned in Eq. (3).

$\displaystyle I_{I}(x)=1-D_{I}(x)-N_{I}(x)\ \text{where}0\leqslant I_{I}(x)\leqslant 1$ (3)

Definition 4 (Intuitionistic Fuzzy Value): The degree of membership of element $x$ in the intuitionistic fuzzy set $I$ is confined by a subinterval $<D_{I}(x),N_{I}(x)>$ of [0,1], here $<D_{I}(x),N_{I}(x)>$ signifies the intuitionistic fuzzy value of element $x$ in $I$ .

Let us suppose $X$ as universal set of different tasks in a system where $X\in$ to be expected burst time of system tasks. Assume that the intuitionistic fuzzy value for burst time/execution time of a system task $\textit{ST}_{1}$ is given as $<\textit{ST}_{1},0.6,0.2>$ . This interval value defines the degree of membership of $\textit{ST}_{1}$ ( $D_{I}(\textit{ST}_{1})$ ) as 0.6; non-degree of membership of $\textit{ST}_{1}$ ( $N_{I}(\textit{ST}_{1})$ ) as 0.2 although remaining value of 0.2 denotes the intuitionistic fuzzy set index of $\textit{ST}_{1}$ ( $I_{I}(\textit{ST}_{1})$ ) in set $I$ .

Definition 5 (Evidence Membership Function): The overall evidence of an element contained in an intuitionistic fuzzy value. It is computed as given in Eq. (4).

$\displaystyle M_{E}=\frac{(D_{I}+1+N_{I})}{2},0\leqslant M_{E}\leqslant 1$ (4)

4. IHRRN CPU scheduler

IHRRN CPU scheduler performs the adaptive sched- uling methodology over open loop scheduling methodology. As open loop scheduling algorithms performs poorly in unpredictable dynamic environment, therefore IHRRN scheduler uses intuitionistic fuzzy set approach which performs better in unpredictable and uncertain environment [31, 33, 34, 35, 36].

IHRRN CPU Scheduler has mainly two objectives:

a)
To deal with the impreciseness allied with the parameters of each task and to calculate the response ratio dynamically. It makes the system adaptive by adjusting the system based on continuous feedback provided w.r.t response ratio (illustrated in Fig. 1).
b)
To schedule each task based on the calculated response ratio which concurrently improves the performance of the system.

For achieving these objectives, proposed IHRRN scheduler contains two modules: Intuitionistic Fuzzy Inference System (IFIS) and IHRRN scheduling algorithm.
4.1 IHRRN-Intuitionistic Fuzzy Inference System (IFIS)

It is used to generate the response ratio for each task. As mentioned in Section 2, response ratio of any task depends on burst time and on waiting time. Proposed IFIS works on the impreciseness of these factors while calculating the response ratio. It has four main components as illustrated in Fig. 2.

1.
Intuitionistic Fuzzification
2.
Intuitionistic Fuzzy Inference Engine
3.
Data Base
4.
Intuitionistic Defuzzification

Figure 2.
IHRRN-Intuitionistic Fuzzy Inference System.

4.1.1 Intuitionistic Fuzzification (IF)

It maps the crisp inputs in to two membership functions; degree of membership $D_{I}$ and non-degree of membership $N_{I}$ . In this way, it transforms each input parameter into their respective intuitionistic fuzzy value $<D_{I},N_{I}>$ .

Intuitionistic Fuzzification maps each input into their respective intuitionistic fuzzy values based on Eqs (5) and (6).

$\displaystyle D_{I}=\left.\left(\!\textit{round}\left(\!\left(\!\frac{I_{% \textit{max}}-I_{c}}{I_{\textit{max}}-I_{\textit{min}}}\!\right)\!\right)*100% \!\right)\right/\!\!100$ (5) $\displaystyle N_{I}=\left.\left(\!\textit{round}\left(\!\left(\!\frac{I_{c}-I_% {\textit{min}}}{I_{\textit{max}}-I_{\textit{min}}}\!\right)\!\right)*100\!% \right)\right/\!\!100$ (6)

Where both $D_{I}\leqslant 1$ and $N_{I}\leqslant 1$ . $I_{\textit{max}}$ , $I_{\textit{min}}$ and $I_{c}$ represents maximum input value, minimum input value and the current input value respectively. The intuitionistic fuzzy value must follow the axiom 1:

Axiom 1: $0\leqslant D_{I}+N_{I}\leqslant 1$

Let us assume a uniprocessor system with $n$ tasks $T=\{T_{i}\in 1\ldots.n\}$ having two imprecise parameters burst time ( $B_{i}\in T_{i}$ ) and waiting time ( $W_{i}\in T_{i}$ ) where $i=1,\ldots,n$ . It transforms imprecise values into their respective intuitionistic fuzzy values $<D_{\textit{Bi}}$ , $N_{\textit{Bi}}>$ and $<D_{\textit{Wi}},N_{\textit{Wi}}>$ as given in Eqs (7) and (8). This component continuously receives data from database to adapt the changes.

$\displaystyle<\!D_{\textit{Bi}},N_{\textit{Bi}}\!>\!\!\left<\!\!\left(\!\!% \left(\textit{round}\left(\!\!\left(\!\frac{B_{\textit{max}}-B_{i}}{B_{\textit% {max}}-B_{\textit{min}}}\!\right)\!\!\right)*100\!\right)\!\right.\right.$ $\displaystyle\left.\left.\hskip-42.679134pt\phantom{\frac{B_{\textit{max}}-B_{% i}}{B_{\textit{max}}-B_{\textit{min}}}}\!\!\right/\!100\!\right)\left(\!\!% \left(\textit{round}\left(\!\!\left(\frac{B_{i}-B_{\textit{min}}}{B_{\textit{% max}}-B_{\textit{min}}}\right)\!\!\right)*100\right)\right.$ $\displaystyle\left.\left.\left.\hskip-42.679134pt\phantom{\frac{B_{\textit{max% }}-B_{i}}{B_{\textit{max}}-B_{\textit{min}}}}\!\!\right/\!100\!\right)\!\right% >\ \textit{where}\ D_{\textit{Bi}}\leqslant 1,N_{\textit{Bi}}\leqslant 1$ (7)

$\displaystyle<\!D_{\textit{Wi}},N_{\textit{Wi}}\!>\!\!\left<\!\!\left(\!\!% \left(\textit{round}\left(\!\!\left(\!\frac{W_{\textit{max}}-W_{i}}{W_{\textit% {max}}-W_{\textit{min}}}\!\right)\!\!\right)*100\!\right)\!\right.\right.$ $\displaystyle\left.\left.\hskip-42.679134pt\phantom{\frac{W_{\textit{max}}-W_{% i}}{W_{\textit{max}}-W_{\textit{min}}}}\!\!\right/\!100\!\right)\left(\!\!% \left(\textit{round}\left(\!\!\left(\frac{W_{i}-W_{\textit{min}}}{W_{\textit{% max}}-W_{\textit{min}}}\right)\!\!\right)*100\right)\right.$ $\displaystyle\left.\left.\left.\hskip-42.679134pt\phantom{\frac{W_{\textit{max% }}-W_{i}}{W_{\textit{max}}-W_{\textit{min}}}}\!\!\right/\!100\!\right)\!\right% >\ \textit{where}\ D_{\textit{Wi}}\leqslant 1,N_{\textit{Wi}}\leqslant 1$ (8)

4.1.2 Intuitionistic fuzzy inference engine (IFIE)

IFIE maps the resulted intuitionistic fuzzy value into a distinct fuzzy value. It has calculated using the concept of evidence membership function as specified in Eq. (9).

$\displaystyle E_{i}=\frac{(D_{i}-N_{i}+1)}{2}$ (9)

Here $E_{i}$ represents the overall evidence value of each input parameter in a specified set. Suppose the value of $\textit{DB}_{1}$ is 0.6 and $\textit{NB}_{1}$ is 0.3, then the value of $\textit{EB}_{1}$ is 0.65. $\textit{EB}_{1}$ represents the total evidence value of burst time of current task in the set of $n$ tasks $\{B1,B2,\ldots,Bn\}$ . $E_{i}$ must follow the axiom 2.

Axiom 2: $0\leqslant Ei\leqslant 1$

IFIE maps both input parameters $B_{i}$ and $W_{i}$ into a distinct fuzzy value $\textit{EB}_{i}$ and $\textit{EW}_{i}$ respectively as given in Eqs (10) and (11).

$\displaystyle E_{\textit{Bi}}=\frac{(D_{\textit{Bi}}-N_{\textit{Bi}}+1)}{2}$ (10) $\displaystyle E_{\textit{Wi}}=\frac{(D_{\textit{Wi}}-N_{\textit{Wi}}+1)}{2}$ (11)

4.1.3 Data Base

Data Base unit takes the task’s attributes from the ready queue and stores all the required information within. It provides all the required data like burst time of current task, minimum burst time available, maximum burst time available, waiting time of current task, maximum and minimum waiting time available etc. to all other units. Database component of IFIS plays the major role as it constantly shares all the current information to the other components that helps the scheduler to adapt the changes dynamically.

4.1.4 Intuitionistic defuzzification

Intuitionistic defuzzification process takes the evidence values ( $E_{i}$ ) of both the input parameters from the IFIE and finally converts it into a single crisp value $R_{i}$ as given in Eq. (12). IHRRN CPU scheduler uses $R_{i}$ as the response ratio fora task $T_{i}$ .

$\displaystyle R_{i}=(E_{\textit{Bi}}+E_{\textit{Wi}})/E_{\textit{BI}}$ (12)

Likewise, IHRRN-IFIS deals with the impreciseness of all active tasks.

4.2 IHRRN scheduling algorithm

Second module of proposed scheduler considers the response ratio ( $R_{i}$ ) as dynamic priority for $i^{th}$ task. The task with highest response ratio is treated as highest priority task by scheduler and vice versa. Ready queue is arranged in such a way that the highest priority task will be scheduled first with CPU. Subsequently, response ratio is recalculated dynamically at the end of the execution of each task and ready queue is rearranged accordingly. This section presents the algorithm and the pseudo code for the proposed work.

4.2.1 Algorithm

Input: Burst time ( $B$ ) and waiting time ( $W$ ) of all tasks ( $T_{i}$ where $i=$ 1 to $n$ ) in ready queue.

Output: average waiting time ( $W_{\textit{AT}}$ ), average turnar-ound time ( $T_{\textit{AT}}$ ) and average normalized turnaround time ( $N_{\textit{AT}}$ ).

1.
Initialize the variables $B_{i}$ , $B_{\textit{max}}$ , and $B_{\textit{min}}$ .
2.
Initialize the variables $W_{i}$ , $W_{\textit{max}}$ , and $W_{\textit{min}}$ .
3.
Calculate the Response Ratio $R_{i}$ by executing IFIS.
4.
Dispatch and execute the task $T_{i}$ with highest response ratio.
5.
Repeat the steps from 1 to 4 until ready queue is empty.
6.
Calculate the waiting time ( $W_{T}$ ), turnaround time ( $T_{T}$ ), response time ( $R_{T}$ ) and normalized turnaround time ( $N_{T}$ ) for each task $T_{i}$ .
7.
Finally calculate the average waiting time ( $W_{\textit{AT}}$ ), average turnaround time ( $T_{\textit{AT}}$ ), average response time ( $R_{\textit{AT}}$ ) and average normalized turnaround time ( $N_{\textit{AT}}$ ).

4.2.2 Detailed pseudo code for IFIS

Begin

Initialize the variable

n

n=

number of tasks

Do Loop

/*Initialize the variables B and W*/

B[n]

=

burst time of task

W[n]

=

waiting time of task

n=n-1

Until (

n==

Do Loop

/*Initialize the variables

B_{c}

B_{\textit{max}}

, and

B_{\textit{min}}

B_{c}=

burst time of current task

B_{max}=

max(

B

)

B_{min}=

min(

B

)

/*Initialize the variables

W_{c}

W_{\textit{max}}

, and

W_{\textit{min}}

W_{c}=

waiting time of current task

W_{max}=

max(

W

)

W_{min}=

min(

W

)

/*Calculate response ratio*/

R[n]

=

Response_ratio()

n=n-1

until(

n==

Do Loop

\textit{if}(R[n]>R[n-1])

/*dispatch task having high response ratio i.e. nth task*/

endif

n=n-1

GOTO Begin

until

n==

/*Compute the performance matrics

avg_calc()

end

degree_membership (

I_{c}

I_{\textit{max}},\ I_{\textit{min}})

Calculate degree of membership value

D_{I}

$\displaystyle D_{I}=\left.\left(\textit{round}\left(\frac{I_{\textit{max}}-I_{% c}}{I_{\textit{max}}-I_{\textit{min}}}\right)*100\right)\right/100$

return (

{\ D}_{I}

)

endfunction

nondegree_membership (

I_{c}

I_{\textit{max}},\ I_{\textit{min}}

)

Calculate non-degree membership value

N_{I}

$\displaystyle N_{I}=\left.\left(\textit{round}\left(\frac{I_{c}-I_{\textit{min% }}}{I_{\textit{max}}-I_{\textit{min}}}\right)*100\right)\right/100$

return (

{\ N}_{I})

endfunction

evidence_value(

I_{c}

I_{\textit{max}},\ I_{\textit{min}}

)

D_{I}=

degree_membership(

I_{c}

I_{\textit{max}},\ I_{\textit{min}}

)

N_{I}=

nondegree_membership(

I_{c}

I_{\textit{max}}

I_{\textit{min}}

)

$\displaystyle\textit{EI}=(\textit{DI}-\textit{NI}+1)/2$

return (

E_{I}

)

endfunction

Response_ratio ()

E_{B}=

evidence_value(

B_{c}

B_{\textit{max}},\ B_{\textit{min}}

)

E_{W}=

evidence_value(

W_{c}

W_{\textit{max}},\ W_{\textit{min}}

)

$\displaystyle R=(E_{B}+E_{W})/E_{B}$

return (R)

endfunction

avg_calc ( )

Calculate average waiting time (

W_{\textit{AT}}

)

$\displaystyle W_{\textit{AT}}=\sum^{n}_{i=1}\frac{W_{T}}{n}$

Calculate average response time (

R_{\textit{AT}}

)

$\displaystyle R_{\textit{AT}}=\sum^{n}_{i=1}\frac{R_{T}}{n}$

Calculate average turnaround time (

T_{\textit{AT}}

)

$\displaystyle T_{\textit{AT}}=\sum^{n}_{i=1}\frac{T_{T}}{n}$

Calculate average normalized turnaround time (

N_{\textit{AT}}

)

$\displaystyle N_{\textit{AT}}=\sum^{n}_{i=1}\frac{N_{T}}{n}$

endfunction

Figure 3.

Detailed architecture of simulation model.

5. Simulation and results

To prove the performance and efficiency of IHRRN CPU scheduler, author has compared the proposed algorithm with the existing HRRN scheduling algorithms such as conventional HRRN, fuzzy based HRRN (FHRRN) and vague based HRRN (VHRRN) scheduling algorithms. Thus, proposed scheduler achieves it’s both objectives: dealing with the uncertainty and impreciseness allied with the task’s attributes which can affect the response ratio and improving the performance of scheduling algorithm that lies in its ability to reduce the values of performance metrics.

5.1 Performance metrics

Each scheduling algorithm has different role and characteristics, but not a single algorithm is ideal for all situations [32]. Therefore, it is necessary to specify methods for quantifying the features of each algorithm. So that it would be possible to investigate a new scheduler over the existing/baseline scheduling algorithms. A scheduler is said to be efficient when the following metrics are to be considered in it.

The performance of CPU scheduling algorithms mainly quantifies based on CPU utilization, throughput, average waiting time ( $W_{\textit{AT}}$ ), average response time ( $R_{\textit{AT}}$ ), average turnaround time ( $T_{\textit{AT}}$ ) and on the average normalized turnaround time ( $N_{\textit{AT}}$ ). The performance of any CPU scheduler can be improved by reducing the value of these metrics ( $W_{\textit{AT}}$ , $R_{\textit{AT}}$ , $T_{\textit{AT}}$ , $N_{\textit{AT}}$ ) and increasing CPU utilization and throughput. This section discusses all these performance metrics in detail.

Definition 6 (CPU Utilization): is the measurement of usage of CPU. It can be improved by keeping CPU as busy as possible.

Definition 7 (Throughput): is the number of tasks completed their execution per unit time.

Definition 8 (Average Response Time): Response time is the time between the submission of request to the first response to that request. Let us consider the time, when task has arrived in the system as arrival time ( $A_{T}$ ) and when task has got the CPU as start time ( $S_{T}$ ). It is calculated as:

$\displaystyle R_{T}=S_{T}-A_{T}$

Average response time can be calculated by calculating average of response time of all the active tasks as given in Eq. (13).

$\displaystyle R_{\textit{AT}}=\left.\left(\sum_{i=1}^{n}R_{\textit{Ti}}\right)% \right/n$ (13)

Definition 9 (Average Waiting Time): Waiting time is the total time a task waits in ready queue for its turn of execution. Waiting time can be calculated as

$\displaystyle W_{T}=S_{T}-A_{T}$

Average waiting time can be calculated as mentioned in Eq. (14).

$\displaystyle W_{\textit{AT}}=\left.\left(\sum_{i=1}^{n}W_{\textit{Ti}}\right)% \right/n$ (14)

Definition 10 (Average Turnaround Time): Turn-around time is the total life time of a task means the total time task takes to finish its execution. It can be calculated as

$\displaystyle T_{T}=B+W_{T}$

Figure 4.

Average Waiting Time (a) when $\Delta t=$ 1 & $1\leqslant n\leqslant 5$ (b) when $\Delta t=$ 2 & $1\leqslant n\leqslant 5$ (c) when $\Delta t=$ 3 & $1\leqslant n\leqslant$ 5.

Figure 5.

Average Turnaround Time (a) when $\Delta t=$ 1 & $1\leqslant n\leqslant$ 5 (b) when $\Delta t=$ 2 & $1\leqslant n\leqslant$ 5 (c) when $\Delta t=$ 3 & $1\leqslant n\leqslant$ 5.

Similarly, average turnaround time is calculated using Eq. (15).

$\displaystyle T_{\textit{AT}}=\left.\left(\sum_{i=1}^{n}T_{\textit{Ti}}\right)% \right/n$ (15)

Definition 11 (Average Normalized Turnaround Time): It represents the relative delay of a task and can be simply calculated as ratio of turnaround time to burst time.

$\displaystyle N_{T}=T_{T}/B$

Figure 6.

Average Normalized Turnaround Time (a) when $\Delta t=$ 1 & $1\leqslant n\leqslant 5$ (b) when $\Delta t=$ 2 & $1\leqslant n\leqslant 5$ (c) when $\Delta t=$ 3 & $1\leqslant n\leqslant$ 5.

Figure 7.

Average Response Time (a) when $\Delta t=$ 1 & $1\leqslant n\leqslant 5$ (b) when $\Delta t=$ 2 & $1\leqslant n\leqslant 5$ (c) when $\Delta t=$ 3 & $1\leqslant n\leqslant$ 5.

Figure 8.

Average Waiting Time and Average Response Time (a) when $\Delta t=$ 1 & $n\geqslant$ 6 (b) when $\Delta t=$ 2 & $n\geqslant 6$ (c) when $\Delta t=$ 3 & $n\geqslant$ 6.

Likewise, average normalized turnaround time is calculated as given in Eq. (16).

$\displaystyle N_{\textit{AT}}=\left.\left(\sum_{i=1}^{n}N_{\textit{Ti}}\right)% \right/n$ (16)

Throughput and CPU utilization will be the same for all scheduling algorithms as the simulation model is considering the uniprocessor system with estimated burst time for all tasks. Therefore, the proposed work has considered the rest of the performance metrics.

Figure 9.

Average Turnaround Time (a) when $\Delta t=$ 1 & $n\geqslant 6$ (b) when $\Delta t=$ 2 & $n\geqslant 6$ (c) when $\Delta t=$ 3 & $n\geqslant$ 6.

5.2 Simulation model

A uniprocessor system has used for simulation to evaluate the performance of IHRRN and other baseline scheduling techniques. Tasks can be CPU bound or I/O bound. If the time to complete the tasks is determinable, then task is CPU bound otherwise I/O bound. CPU bound tasks only execute CPU related operations and cannot execute I/O operations. The workload consists of independent tasks and even all tasks are assumed to be CPU bound tasks. Each task instance is supposed to complete their execution within the assigned time frame.

The simulator has two components as shown in Fig. 3; Intuitionistic fuzzy inference system and sch-eduling algorithm. IFIS which controls the allied impreciseness of the task parameters to generate the response ratio and scheduling algorithm which models the execution of tasks and collects the performance statistics of the IHRRN scheduler.

5.3 Workload model

Each task is characterized with a set of estimated burst times $\{B_{i}\}$ , arrival times $\{A_{i}\}$ and a set of waiting times $\{W_{i}\}$ . In our experiments, workload can vary from 1 to 15 tasks i.e. $1\leqslant ni\leqslant 15$ . Each different experiment has a varied average work load. The burst time $\{B_{i}\}$ of each task is distributed from 1 to 50 ms i.e. 1 ms $\leqslant B_{i}\leqslant$ 50 ms.The larger the value of $W_{i}$ , high the value of response ratio ( $R_{i}$ ) which ultimately increases the priority of the task i.e. $R_{i}\propto W_{i}$ .

If workload is in between 1 to 5, IHRRN scheduler performs well however at some points it behaves much like VHRRN. Moreover, as workload increases from 6 to 15; system still shows better performance of IHRRN over baseline schedulers.

5.4 Evaluation

To evaluate the performance, simulation is divided into two phases. Phase 1 consider the task sets with $0\leqslant\Delta t\leqslant 3$ and $1\leqslant n\leqslant 5$ (less number of tasks in the system) where $\Delta t=A_{i}-A_{i-1}$ . Phase 2 consider the task set with $0\leqslant\Delta t\leqslant 3$ and $n\geqslant 6$ (more number of tasks in the system). For both phases, frequent arrival of tasks is considered for simulation.

5.4.1 Phase 1

Table 1
Parameters settings for phase 1

$\Delta t$	Average burst time ( $B_{\textit{AT}}$ )
1	0–25
2	0–25
3	0–25

Different experiments evaluate the performance of the scheduling algorithms (IHRRN, VHRRN, FHRRN, HRRN) when the average burst time of different task sets can vary within the specified range and with constant $\Delta t$ for each run (refer Table 1). However, the actual burst time of each task in a task set is a random value. Author has assumed that average burst time is directly proportional to the number of tasks ( $B_{\textit{AT}}\propto n$ ). It increases with increase in number and vice versa. Each algorithm made 15 set of runs where each set has average burst time in between 0–25 with varying $\Delta t$ values. The results of phase 1 are illustrated in Figs 4–7 in terms of average waiting time, average turnaround time, average normalized turnaround time and average response time respectively.

Figure 10.

Average Normalized Turnaround Time (a) when $\Delta t=$ 1 & $n\geqslant 6$ (b) when $\Delta t=$ 2 & $n\geqslant$ 6 (c) when $\Delta t=$ 3 & $n\geqslant$ 6.

Figure 11.

Overall performance of IHRRN Scheduler over Baseline Schedulers (Phases 1 and 2).

Each point in Figs 4–7 represent the average value (average waiting time, average turnaround time, average normalized turnaround time and average response time) of sample task set. From Fig. 4, it can be seen that over more than 90% points, IHRRN scheduler proved to be better than other baseline schedulers. Moreover, for remaining 10% it is closer to the VHRRN scheduler but proved better over other two baseline schedulers. Figure 5 compares the average turnaround time of IHRRN scheduler with other three baseline schedulers. It can be seen that at $\Delta t=$ 1, it performs better as compare to performance at $\Delta t=$ 2 and $\Delta t=$ 3. At $\Delta t=$ 2, it performs better as compare to performance at $\Delta t=$ 3. From these results, it can be realized that both the workload and the frequency of task arrival directly affects the turnaround time of the system.

Figure 6 compare the average normalized turn-around time among four schedulers. IHRRN successfully proves itself better over baseline schedulers at all varied values of $\Delta t$ . Figure 7 compares the average response time. It can be seen that the results of average waiting time and average response time are exactly same as HRRN is supposed to be treated as non-preemptive scheduling algorithm.

In summary, phase 1 experiments demonstrate that under all situations when the estimated execution time differs with the change in time, IHRRN scheduler is able (1) to deal with the inexactness of the response ratio of admitted tasks; (2) to achieve high performance in terms of average waiting time, average turnaround time, average normalized turnaround time and average response time; (3) to attain high system utilization.

5.4.2 Phase 2

Table 2
Parameters settings for phase 2

$\Delta t$	Average burst time ( $B_{\textit{AT}}$ )
1	25–50
2	25–50
3	25–50

Phase 2 considers $n\geqslant$ 6 and its other settings are listed in Table 2. Just like phase 1, each algorithm made 15 set of runs having average burst time in between 25–50 along with varying $\Delta t$ values.

Figures 8–10 illustrate the performance of sample task sets with phase 2 settings. In phase 2 experiments also, the results of average waiting time and average response time are exactly same. Figure 8 clarifies the performance of IHRRN scheduler over more than 90% points. Moreover, for remaining 10% it is closer to the VHRRN scheduler but proved better over other two baseline schedulers. Figure 9 compares the average turnaround time of IHRRN scheduler with other three baseline schedulers. Figure 10 compares the average normalized turnaround time among four schedulers. IHRRN successfully proves itself better over baseline schedulers at all varied values of $\Delta t$ . So, from experimental results, it can be seen that when workload is increasing on the system; it does not affect the performance of the system. System still responds better on increasing the workload. Phase 2 experiments consider workload up to 15 and maintain a high CPU utilization; even system can work perfectly after 15.

Figure 11 illustrates the overall performance of IHRRN scheduler in phases 1 and 2 as compare to other three baseline schedulers (IHRRN vs HRRN, IHRRN vs FHRRN and IHRRN vs VHRRN). In overall performance, IHRRN scheduler effectively showed the improved performance in both phases. However, there is a slight drop in the performance of IHRRN with increase in system workload as compare to phase 1. Through Fig. 11, it can be seen that the overall performance of IHRRN scheduler is better than other baseline schedulers during phases 1 and 2. Hence, based on the results it can be concluded that, it effectively adapts the dynamically changes of burst time and the waiting time of task. It also maintains the satisfactory performance throughout the execution cycle of scheduler.

6. Conclusion

This paper presented a novel approach to highest response ratio next CPU scheduler called Intuitionistic fuzzy based HRRN (IHRRN) scheduler. To deal with the impreciseness of input parameters, an intuitionistic fuzzy inference system has implemented. This inference system is used by the scheduler to dynamically generate the precise value of response ratio. IHRRN scheduler has the capability to adapt the suggested dynamic changes w.r.t. response ratio. An IHRRN scheduling algorithm is also implemented which dispatches the highest response ratio task with the CPU. This paper compared and analysed the performance of four schedulers: IHRRN, VHRRN, FHRRN and HRRN scheduler. Simulation is divided in to two phases based on the number of tasks. Analysis results of both the phases proved the improvement in performance of IHRRN scheduler over other three baseline schedulers.

References

Silberschatz

Galvin

Gagne

. Operating System Concepts, John Wiley & Sons, 9th Edition, 2012.

Stallings

. Operating Systems Internal and Design Principles, William Stallings, 8th Edition, 2014.

Raheja

. Designing of vague logic based 2-layered framework for CPU scheduler. Advances in Fuzzy Systems. 2016; 16: 1-11.

Zaim

. Design of a scheduler: Comparison of different scheduling algorithms. Journal of Electrical & Electronics Engineering. 2003; 3: 859-877.

Panduranga Rao

Shet

. Analysis of new multi-level feedback queue scheduler for real time kernel. International Journal of Computational Cognition. 2010; 8: 5-16.

Blevins

Rama Moorthy

. Aspects of a dynamically adaptive operating systems. IEEE Transactions on Computers. 1976; 25: 713-725.

Andrew

Tanenbaum

Woodfhull

. Operating Systems Design and Implementation, Prentice Hall, Third Edition, 2006.

Raheja

Dhadich

Rajpal

. Vague oriented highest response ratio next scheduling algorithm. IEEE International Conference on Fuzzy Systems (Fuzz-2013), 2013, pp. 1-7.

Moallemi

Asgharilarimi

. A fuzzy scheduling algorithm based on highest response ratio next algorithm, K. Elleithy (ed.), Innovations and Advanced Techniques in Systems, Computing Sciences and Software Engineering, Springer, 2008, pp. 75-80.

10.

Alam

Doja

Biswas

Alam

. Fuzzy HRRN CPU Scheduling Algorithm. International Journal of Computer Science and Information Security. 2011; 9: 120-124.

11.

Raheja

Dhadich

Rajpal

. 2-layered architecture of vague logic based multilevel queue scheduler. Applied Compuational Intelligence and Soft Computing. 2014; 2014: 1-12.

12.

Zadeh

. Fuzzy sets, Information and Control. 1965; 8: 338-356.

13.

Atanassov

. Intuitionistic fuzzy sets. Fuzzy Sets and Systems. 1986; 20: 87-96.

14.

Atanassov

. More on intuitionistic fuzzy sets. Fuzzy Sets Systems. 1989; 33: 37-46.

15.

Gau

Buehrer

. Vague sets. IEEE Transaction on Systems, Man and Cybernetics. 1993; 23: 610-614.

16.

Atanassov

. Intuitionistic Fuzzy Sets: Theory and Applications, Studies in Fuzziness and Soft Computing, Physica-Verlag, New York, 2000. 35.

17.

Atanassov

Gargov

. Intuitionistic fuzzy logic. CR Acad. Bulg. Soc. 1990; 43: 9-12.

18.

Bustince

Burillo

. Vague sets are intuitionistic fuzzy sets. Fuzzy sets and systems. 1996; 79: 403-405.

19.

Wilfred

. Vague sets or intuitionistic fuzzy sets for handling vague data: Which one is better? Lecture Notes in Computer Science, Springer. 2005; 3916: 401-416.

20.

Zain

Mohd

WMBW

El-Qawasmeh

. Highest Response Ratio Next (HRRN) vs. First Come First Serve (FCFS) scheduling Algorithm in Grid Environment, Software Engineering and Computer Systems – Second International Conference, June 27–29 2011.

21.

Surendra Varma

. Design of modified HRRN scheduling algorithm for priority systems using hybrid priority scheme. Journal of Telematics and Informatics. 2013; 1: 14-19.

22.

Nie

Guoliang

Liu

Wen

. A new operating system scheduling algorithm. Advanced Research on Electronic Commerce, Web Application, and Communication, Springer. 2011; 143: 92-96.

23.

Jane

Liu

Lin

Shih

. Algorithms for scheduling imprecise computations. IEEE Computer. 1991; 24: 58-68.

24.

Lim

Cho

. Intelligent OS process scheduling using fuzzy inference with user models. New Trends in Applied Artificial Intelligence, Lecture Notes in Computer Science. 2007; 45: 725-734.

25.

Aburas Abdurazzag

Vladimir

. Fuzzy logic based algorithm for uniprocessor scheduling, Proceedings of the International Conference on Computer and Communication Engineering, 2008. pp. 499-504.

26.

Zadeh

. Making computers think like people. IEEE Spectrum. 1984; 8: 26-32.

27.

Zadeh

. Is there a need for Fuzzy Logic. Information Science. 2008; 178: 2751-2779.

28.

Atanassov

. New operations defined over the intuitionistic fuzzy sets. Fuzzy Sets Systems. 1994; 61: 137-142.

29.

Pawlak

. Rough Sets. International Journal of Computer and Information Sciences. 1982; 11: 341-356.

30.

Atanassov

. Operations over interval valued intuitionistic fuzzy sets. Fuzzy Sets Systems. 1994; 64: 159-174.

31.

Raheja

. Intuitionistic Fuzzy Set Theory with Fair Share CPU Scheduler: A Dynamic Approach in Theoretical and Practical Advancements for Fuzzy System Integration, 2017, pp. 126-153.

32.

Zanjirani

Esmaelian

. An integrated approach based on Fuzzy Inference System for scheduling and process planning through multiple objectives, American Institute of Mathematical Sciences, Dec 2018.

33.

Raheja

Jain

. Designing of a new intuitionistic fuzzy based diabetic diagnostic system. International Journal of Fuzzy System Applications (IJFSA). 2018; 7: 32-45.

34.

Pauzia

Abdullah

. Implementation of intuitionistic fuzzy inference systems to assess air quality forecast: Case of Malaysia, AIP Conference Proceedings, 1974, June 2018.

35.

Mohammed

Mostafa

. Task parameters impacts in fuzzy real time scheduling in recent advances in intuitionistic fuzzy logic system, 2018.

36.

Raheja

. An intuitionistic fuzzy based novel approach to CPU scheduler. Current Medical Imaging. 2019; 14.

An intuitionistic based novel approach to highest response ratio next CPU scheduler

Abstract

Keywords

1. Introduction

2. HRRN CPU scheduler and state of the art

1. Intuitionistic Fuzzification 2. Intuitionistic Fuzzy Inference Engine 3. Data Base 4. Intuitionistic Defuzzification OPEN IN VIEWERFigure 2.IHRRN-Intuitionistic Fuzzy Inference System. 4.1.1 Intuitionistic Fuzzification (IF)

4.1.4 Intuitionistic defuzzification

4.2.1 Algorithm

5.1 Performance metrics

5.3 Workload model

5.4 Evaluation

5.4.1 Phase 1

Table 1 Parameters settings for phase 1

Table 2 Parameters settings for phase 2

References

1.
Intuitionistic Fuzzification
2.
Intuitionistic Fuzzy Inference Engine
3.
Data Base
4.
Intuitionistic Defuzzification

Figure 2.
IHRRN-Intuitionistic Fuzzy Inference System.

4.1.1 Intuitionistic Fuzzification (IF)

Table 1
Parameters settings for phase 1

Table 2
Parameters settings for phase 2