Article Search
닫기

Original Article

Split Viewer

International Journal of Fuzzy Logic and Intelligent Systems 2024; 24(1): 30-42

Published online March 25, 2024

https://doi.org/10.5391/IJFIS.2024.24.1.30

© The Korean Institute of Intelligent Systems

A Novel Fuzzy Logic Based Operating System Scheduling Scheme

Abdul Kareem1 and Varuna Kumara2

1Department of Electronics and Communication, MIT Kundapura, Karnataka, India
2Department of AI & ML, MIT Kundapura, Karnataka, India

Correspondence to :
Varuna Kumara (vkumarg.24@gmail.com)

Received: April 18, 2022; Revised: October 21, 2023; Accepted: November 27, 2023

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

For a computer-based system, a set of processes must be scheduled such that every process is completed within its deadline. CPU scheduling is the process of allocating CPU among various processes in a multi-processing system. The decision to allocate the CPU to a process has to take into consideration all aspects, including its priority and execution time, as scheduling is guided by a number of factors other than the execution time or priority. It is no longer one-dimensional and has become a multidimensional problem with vagueness and uncertainties such as different CPU loading scenarios. The vagueness and uncertainties associated with the decision to allocate a CPU to a particular process can be addressed using a fuzzy logic approach. In this study, we propose a fuzzy logic-based algorithm for CPU scheduling. The proposed algorithm was compared with conventional scheduling algorithms for different CPU loading scenarios. The proposed method can schedule and execute all processes well within the deadline with a reduced average turn-around and a reduced average waiting time. From the comparison results, it is evident that the proposed algorithm outperforms conventional algorithms in terms of the average turn-around and waiting times.

Keywords: Fuzzy logic, Scheduling, Waiting time, Turn-around time

When a computer boots up, different applications and software are initiated. Each piece of software or application can be considered a process. A central processing unit (CPU) is at the heart of all computational systems. A computer system may have a single processor or several processors for computation. In a single-processor system, the CPU must be shared among different processes. This process is simply a task that must be completed. These processes may be user- or system-level processes. The operating system (OS) bridges the gap between user applications and the underlying hardware. The OS efficiently manages the system resources that are available to users or system-level applications. In a multiprogramming environment, several processes may require the same resources, which must be shared among the processes in an efficient manner. It is the duty of the OS to ensure that the system resources are efficiently made available to the processes that require them. The allocation of system resources to various processes is called scheduling [117]. The scheduler is the one that decides how the scheduling needs to be carried out. Various scheduling algorithms have been adopted by various operating systems for scheduling in OSs. In real-time industrial systems, these processes are deterministic. They must be scheduled and executed well within the deadline, and any process failing to meet the deadline may result in the abrupt behavior of the system, leading to hazards and degraded performance. Care should be taken to ensure that the processes do not wait long. Hence, real-time scheduling is a tedious task, and a careful design of the scheduling algorithm is very important for supporting the parallelism of processes. The main parameters that determine the efficiency of the scheduling algorithm are the waiting time and turn-around time. Attempts have been made to reduce these factors in a given set of processes. Careful investigation of existing algorithms reveals that processes in the ready queue are scheduled by considering only one parameter. This parameter can be the execution time or priority. Because scheduling is guided by both the execution time and priority, it is no longer one-dimensional and has become a multidimensional problem. Thus, many parameters must be analyzed, and decisions must be made while scheduling the processes.

The vagueness in decisions can be addressed using a fuzzy logic approach. In this study, we propose a new scheduling algorithm based on fuzzy logic that considers both execution time and priority. The proposed system was developed using the MATLAB Fuzzy Logic Toolbox and a case study was conducted. In real-time operating systems, the execution time and priority of processes are not known; hence, random processes with random execution times and priorities are generated and scheduled using the proposed and conventional algorithms. The waiting and turn-around times of the processes are observed for the proposed and conventional algorithms. The experiment was conducted for several sets of processes, and the average waiting and turn-around times were compared. The algorithm was modified to fit into a real-time system, and the analysis was carried out. From the analysis, it was found that the proposed system makes a better decision to allocate the CPU to the processes, despite ambiguity. For real-time systems, the proposed algorithm ensures that all processes meet their deadlines. The analysis was extended to various CPU loading factors, and a comparison was made. Thus, the proposed algorithm adaptively addresses process scheduling even under overload conditions and effectively handles deadlines.

This study highlights the potential of a fuzzy logic-based scheduling algorithm to address the complexities of process scheduling in modern computing environments. This offers a promising solution for optimizing the allocation of system resources and ensuring the timely execution of processes, ultimately contributing to the stability and reliability of computer systems, particularly in real time. The proposed method can schedule and execute all the processes well within the deadline, with a reduced average turn-around time and a reduced average waiting time in comparison with conventional algorithms.

The remainder of this paper is organized as follows. Section 2 presents a literature review, emphasizing the feasibility test by Liu and Layland [4]. Section 3 outlines the algorithm that employs fuzzy logic. Section 4 substantiates its efficacy through a case study and results analysis, collectively highlighting its robustness and practical applications. Finally, Section 5 presents the conclusions of this study.

Scheduling is a fundamental function of an OS. The type of scheduling algorithm employed depends on the OS of interest, and different operating systems involve different scheduling algorithms. Extensive research has been conducted in the field of operating systems, and various researchers have developed new scheduling algorithms. Priority-based scheduling is the most widely used scheduling method.

In first-come first-serve (FCFS) scheduling, the processes that enter the ready queue are scheduled first. FCFS is a non-preemptive scheduling method in which the process entering the ready queue is first scheduled, and the process runs to its completion [18, 19]. The main disadvantage of FCFS is that the average waiting time and turn-around time are greater [19]. A process with a smaller burst time must wait for its turn, whereas processes with a high burst time are currently executing. In the shortest job-first (SJF) method, the process with the shortest burst time among the processes in the ready queue is given a CPU for execution. SJF may be preemptive or non-preemptive. In a preemptive environment, the OS may preempt the current execution process if a new process with a burst time shorter than that of the execution task enters a ready queue. In a non-preemptive environment, the scheduled process continues its execution, and no preemption occurs [8]. In the priority-based scheduling algorithm, priorities are assigned to a set of services, and scheduling is performed according to the priority assigned. Priority may be assigned by the OS or by the user. The interpretation of the values assigned to the priorities is OS-dependent. Different OSs were interpreted differently. In priority-based scheduling algorithms, the processes suffer from starvation. Processes with lower priority must wait for the completion of high-priority processes.

Real-time systems are deterministic, and the processes are time-critical. The waiting time for the processes is limited by the service deadline. All services must be executed within a deadline. For real-time operating systems, rate monotonic (RM) and deadline monotonic (DM) algorithms based on fixed-priority scheduling are commonly used. Recently, the earliest deadline first (EDF) and lowest laxity first (LLF) methods based on dynamic priority scheduling have been explored.

In the RM policy, the most frequently requested task is given the highest priority. Liu and Layland [4] proposed a feasibility test for the RM policy, thus defining the least upper bound as given in Eq. (1).

U=i=1m(CiTi)m(21m-1).

Several assumptions were made, and a feasibility test was proposed. The assumptions made are as follows: the requests for all tasks for which hard deadlines exist are periodic with constant intervals between requests; deadlines consist of run-ability constraints only, that is, each task must be completed before the next request for it occurs; the tasks are independent; the runtime for each task is constant for that task and does not vary with time; and any nonperiodic tasks in the system are special: they are initialization or failure recovery routines [4]. The rate-monotonic least upper bound (RMLUB) was just a sufficient test, meaning that the set of services that pass the RMLUB can be scheduled without missing the deadline, while the set of services failing to meet the RMLUB does not guarantee that they cannot be scheduled, because the RMLUB was just the necessary test to determine whether the set of services was feasible or not. Lehoczky et al. [5] developed an iterative feasibility study. This test is called the scheduling-point test and is a necessary and sufficient feasibility test. Eq. (2) describes the scheduling-point test as follows:

i,1in,minj=1icj(l)TkTj(l)Tk.

Completion time is another iterative method available in the literature to check for feasibility. Eq. (3) depicts the test completion time: one another important static priority policy [3]. In the DM, the deadline of services is considered. Eq. (4) describes the DM scheduling policy:

an(t)=j=1ntTjCj,i,1in,CiDi+IiDi1.0.

Several studies have been conducted on the development of new scheduling algorithms. One of them presented an optimum multilevel dynamic round-robin scheduling (OMDRRS) algorithm that maintains jobs based on factor analysis. The proposed algorithm was simulated, tested, and compared with existing scheduling [7]. The scheduling algorithm for real-time tasks proposed by Yaashuwanth and Ramesh [8] modified existing scheduling algorithms and rendered them suitable for implementation in embedded systems. Comparative results of the algorithm are presented. Research has been conducted to exploit the advantages of the existing algorithms and combine them to develop new algorithms. One such study is presented by Prajapati et al. [9]. Scheduling of processes is crucial in real-time systems. Some scheduling algorithms perform better under underloaded conditions, whereas they fail to perform better in overloaded conditions, and vice versa. A new scheduling algorithm was developed by exploiting the properties of the existing algorithms [1215].Different OSs adopt different scheduling algorithms. To implement a scheduling algorithm, the OS system must be modified to incorporate this change [13]. Efforts have been made to implement EDF scheduling algorithms in standard Linux environments [10]. All studies treated the scheduling algorithm as a one-dimensional problem without significant ambiguity in decision-making. When scheduling is viewed as a vague multidimensional problem, such as different CPU loading scenarios, the fuzzy logic approach is the best candidate. In this study, we developed a novel scheduling algorithm based on fuzzy logic.

Scheduling based on priority and execution time simultaneously is a tedious job, and ambiguities exist in decision-making. Fuzzy logic can handle problems or systems prone to uncertainties, vagueness, imprecision, approximations, partial truth, or qualitative moods [16]. Therefore, we propose a novel scheduling algorithm based on fuzzy logic.

3.1 Inputs and Output

The two parameters considered for analyzing the set of processes under consideration and deciding the scheduling were the execution time and priority assigned to the processes. Hence, the execution time and priority assigned to the processes were the inputs. Based on these inputs, the scheduler determines the process to which the CPU must be allotted. Hence, the priority at which the processes are allocated to the CPU for processing is the output, with the premise that “lesser the value, more is the priority.”

3.2 Fuzzification

The two input variables were normalized to the range [0, 1] the appropriate scaling factors. The inputs are crisp in nature; hence, they must be converted to a fuzzy logic form. This fuzzification process is performed by assigning membership values to the inputs, as shown in Figures 1 and 2. The membership functions of the fuzzy outputs are shown in Figure 3. The input “Execution Time” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 1. The input “Priority” with the premise “lesser the value, more is the priority” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 2. The output “CPU Allocation Priority” with a premise “lesser the value, more is the priority” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 3.

To combine two input parameters, Execution Time and Priority, to compute the output parameter, CPU Allocation Priority, there are no exact models or rules, resulting in uncertainties. However, certain approximate rules based on human reasoning can be applied to model this scenario. Fuzzy logic is an appropriate tool for incorporating approximation rules based on human reasoning into workable algorithms. The combination can be modeled by a Mamdani-type fuzzy inference system with a rule base developed using approximate reasoning, as given below. The relationship between the input and output is shown in Figure 4.

Rule 1: If (Priority is VH) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 2: If (Priority is VH) and (execution time is L), then (CPU Allocation Priority is VH).

Rule 3: If (Priority is VH) and (Execution Time is M), then (CPU Allocation Priority is VH).

Rule 4: If (Priority is VH) and (Execution Time is H), then (CPU Allocation Priority is H).

Rule 5: If (Priority is VH) and (Execution Time is VH), then (CPU Allocation Priority is M).

Rule 6: If (Priority is H) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 7: If (Priority is H) and (Execution Time is L), then (CPU Allocation Priority is VH).

Rule 8: If (Priority is H) and (Execution Time is M), then (CPU Allocation Priority is H).

Rule 9: If (Priority is H) and (Execution Time is H), then (CPU Allocation Priority is M).

Rule 10: If (Priority is H) and (Execution Time is VH), then (CPU Allocation Priority is L).

Rule 11: If (Priority is M) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 12: If (Priority is M) and (Execution Time is L), then (CPU Allocation Priority is H).

Rule 13: If (Priority is M) and (Execution Time is M), then (CPU Allocation Priority is M).

Rule 14: If (Priority is M) and (Execution Time is H), then (CPU Allocation Priority is L).

Rule 15: If (Priority is M) and (Execution Time is VH), then (CPU Allocation Priority is VL).

Rule 16: If (Priority is L) and (Execution Time is VL), then (CPU Allocation Priority is H).

Rule 17: If (Priority is L) and (Execution Time is L), then (CPU Allocation Priority is M).

Rule 18: If (Priority is L) and (Execution Time is M), then (CPU Allocation Priority is L).

Rule 19: If (Priority is L) and (Execution Time is H), then (CPU Allocation Priority is VL).

Rule 20: If (Priority is L) and (Execution Time is VH), then (CPU Allocation Priority is VL).

Rule 21: If (Priority is VL) and (Execution Time is VL), then (CPU Allocation Priority is M).

Rule 22: If (Priority is VL) and (Execution Time is L), then (CPU Allocation Priority is L).

Rule 23: If (Priority is VL) and (Execution Time is M), then (CPU Allocation Priority is VL).

Rule 24: If (Priority is VL) and (Execution Time is H), then (CPU Allocation Priority is VL).

Rule 25: If (Priority is VL) and (Execution Time is VH), (CPU Allocation Priority is VL)

3.3 Fuzzy Inference System

A Mamdani fuzzy inference system was designed for the proposed algorithm. In this inference system, the antecedent of a rule has two parts, “Priority” and “Execution Time,” and the operator between them is “and.” The “and” operation is performed by applying the “min” operator to the membership values of two inputs, and this value is computed as the truth value of the rule. This true value is then applied to the output fuzzy set to obtain the fuzzy output corresponding to the rule. The fuzzy outputs corresponding to all rules are obtained, and they are combined using the “max” operator to obtain the final fuzzy output [1620]. The inference for “Priority = 0.5” and “Execution Time = 0.5” is as shown in Figure 5.

3.4 Defuzzification

Defuzzification converts the fuzzy output of a fuzzy inference engine into a crisp value [16]. This can be achieved by computing the centroid of the fuzzy output, as expressed in Eq. (5). The centroid method was used as the defuzzification method because it provides higher accuracy and smoothness in the output.

X*=xμA(x)dxμA(x)dx.

μA(x) is a membership function of aggregated fuzzy output where xX.

The proposed fuzzy scheduling algorithm was verified for real-time processing. To verify the proposed algorithm, different cases of different sets of random processes were considered. Table 1 summarizes the average waiting time for different algorithms, with a sample size of five processes, considering five different cases, and the comparison is depicted in Figure 6. The sample size was increased to 10 to increase the confidence interval to a 95% level. The randomness of the processes also increases. Table 2 lists the experimental results for a set of ten processes, considering five different cases. A comparison of the results is presented in Figure 7.

The FCFS algorithm schedules the processes that occur early in the queue and does not consider the execution time and priority of the processes. Because the processes are random, the probability of processes with less execution time and high priority entering the ready queue is very low. Therefore, a random set of processes suffers from long waiting times. The SJF algorithm schedules processes by considering their execution time. SJF performs well with respect to the waiting time and turn-around time of the processes but does not consider the priority of the processes. Thus, a higher-priority process with a longer execution time must wait longer. Priority-based scheduling (PS) algorithms do not consider the execution time of the process.

The variations in waiting time for different sample sizes for the proposed scheme are shown in Figures 6 and 7. The turn-around times for the different processes are compared in Tables 3 and 4. It is clear that the average waiting and turn-around times are significantly reduced in comparison with existing algorithms. The proposed algorithm attempts to reduce waiting and turn-around times without compromising the process parameters. With increased randomness and an increased number of processes, the proposed algorithms perform almost equally to SJF, taking both execution time and priority into consideration. Hence, the ambiguity of considering multiple parameters is considered in the proposed approach.

The proposed fuzzy-based scheduling algorithm was extended to a preemptive environment by evaluating fuzzy priorities at regular time intervals for a set of processes. Fuzzy priorities are calculated at regular time intervals considering the execution time and process priorities. These newly obtained priority values are used for further priority computations. The one with the highest priority is scheduled. The proposed algorithm performs better than preemptive priority-based scheduling and is as efficient as the preemptive SJF scheduling algorithm.

4.1 The Proposed Algorithm for Real-Time Services

Table 5 lists the three processes, their execution times, and their execution periods, and shows shows the nonharmonic set of processes with a CPU loading factor of 0.98. These sets of processes were scheduled using the RM, EDF, and LLF scheduling policies, which are presented in Figures 8, 9, and 10, respectively. The same set of processes was scheduled using the proposed fuzzy scheduling algorithm, and a Gantt chart is presented in Figure 11.

From the Gantt chart, it was observed that although the CPU was not loaded at 100%, the RM policy failed to schedule the set of processes. RM fails to schedule a set of processes within a given deadline because the process that occurs more frequently has the highest priority. Processes P1 and P2 occur more frequently than process P3; hence, RM fails to schedule P3 within the given deadline, as depicted in Figure 8.

Figures 9 and 10 show the Gantt charts for scheduling the processes in Table 5 using EDF and LLF, respectively. We found that the set of processes could be scheduled effectively without missing deadlines for the time interval under consideration. The set of processes is scheduled using the proposed fuzzy scheduling algorithm and is presented in Figure 11. The proposed scheduling algorithm performed better than RM scheduling and was as efficient as the EDF and LLF scheduling algorithms for a CPU loading factor of less than or equal to 100%.

4.2 Deadline Over-Run Scenario

Handling a process that misses a deadline is an important task in real-time operating systems. Care should be taken to handle missed-deadline processes. The process of missing a deadline can be addressed using various methods. One way of handling the missed-deadline process is to continue to run the process that misses the deadline for a finite duration, or continue it to execute infinitely after missing the deadline. Another option was to terminate the process as soon as the deadline was missed. In the RM policy, if any process misses the deadline, then all services with priorities less than that of the process that missed the deadline continue to miss the deadline, while the other services with priorities greater than those of the process that missed the deadline are guaranteed to execute well before the deadline. In the EDF algorithm for scheduling, a process that misses the deadline causes all other processes to wait in the ready queue and potentially misses the deadline. In EDF, a process that misses the deadline will have a negative value for the TTD, hence making all other services wait and making them miss deadlines. One way to eliminate this problem is to have an additional process that will be given more priority than the overrunning process; as a result, the overrunning process will be preempted. A service added to the queue does not preempt the overrunning process because it has a negative TTD. This problem in handling missed-deadline processes was overcome by the proposed fuzzy algorithm for scheduling.

The analysis was conducted considering a heavily loaded scenario. Table 6 lists the four sets of processes, along with their execution times and deadlines. For the set of processes listed in Table 5, the CPU loading factor is 1.33. These processes were scheduled using an existing algorithm and were compared with the proposed algorithm. The proposed algorithm performed better than the RM policy and was as efficient as EDF and LLF. The CPU was overloaded, and P4 missed the deadline. The scheduling schemes are shown in Figures 1215, respectively.

The efficiency of the proposed algorithm was evaluated by considering a set of processes and scheduling the processes with a CPU loading factor of 1.125, as listed in Table 7. These processes are harmonic in nature, and the maximum time period considered is the least common multiple of the process periods, which is eight times the units in this case. The processes are scheduled, and observations are made. Table 8 presents the observations made during scheduling.

From Table 8, it is observed that all the algorithms fail to schedule process P3 because the extra execution time of P3 overloads the CPU; hence, it cannot be scheduled. To support the efficiency of the proposed algorithm, an additional process, P4, is added, whose period is 16 times the number of units and has to be executed once in 16 units. For the previously scheduled set of processes, it was obvious that the process P3 missed the deadline because the CPU is overloaded.

A different set of processes was considered with a loading factor of 1.1875, as shown in Table 9. If only processes P1, P2, and P4 were considered, the loading factor was 0.8125. These sets of processes were scheduled, and the observations are presented in Table 10.

From these observations, it is clear that process P4 is not scheduled by the conventional algorithms for execution, whereas the proposed fuzzy algorithm schedules process P4 for execution well within the deadline. As mentioned earlier, the set of processes P1, P2, and P4 provides a loading factor of 0.8125, whereas 1.1875 considers process P3. The proposed algorithm makes use of this, understands that processes P1, P2, and P4 can be effectively scheduled without missing the deadline, as observed by humans, and makes the decision accordingly. Thus, the deadline over-run scenario was effectively handled by the proposed algorithm.

The proposed scheduling algorithm provides higher quality than conventional scheduling algorithms. Several processes were considered with different loading factors, and the efficiency was calculated and plotted in Figure 16. For the over-loaded scenario, the proposed algorithm performed better than the existing algorithms for scheduling.

Decision-making for scheduling a process in an operating system is a very important and tedious task. A novel approach for scheduling a set of processes was presented and compared with existing scheduling algorithms. The proposed fuzzy algorithm for scheduling performs better than the commonly used FCFS and priority-based scheduling policies. The proposed algorithm not only considers priorities, but also their execution time for scheduling decisions. To schedule real-time processes, the fuzzy rules are modified, and the proposed algorithm is compared with existing algorithms for real-time processes with well-defined time durations for highly loaded scenarios. The proposed algorithm performs better than the conventional RM scheduling algorithm and is as efficient as the EDF and LLF scheduling algorithms. For the overloaded scenario, the proposed fuzzy scheduling algorithm performed better than the RMEDF and LLF scheduling algorithms. The proposed algorithm effectively handles the process of missing the deadline, ensuring that all other processes continue their execution safely without missing the deadline. From the analysis, it was concluded that the proposed algorithm makes its best effort to deliver maximum efficiency, making it suitable for real-time operating systems.

Fig. 1.

Membership functions of “Execution time.”


Fig. 2.

Membership functions of “Process priority.”


Fig. 3.

Membership functions of “CPU allocation priority.”


Fig. 4.

Output variation as a function of input parameters.


Fig. 5.

Fuzzy inference for “Priority = 0.5” and “Execution Time = 0.5.”


Fig. 6.

Variation of average waiting time for sample size of five processes.


Fig. 7.

Variation of waiting time for sample size of 10 processes.


Fig. 8.

Scheduled processes using RM policy.


Fig. 9.

Scheduled processes using EDF algorithm


Fig. 10.

Scheduled processes using LLF algorithm


Fig. 11.

Scheduled processes using the proposed algorithm.


Fig. 12.

Scheduling using RM algorithm.


Fig. 13.

Scheduling using EDF algorithm.


Fig. 14.

Scheduling using LLF algorithm.


Fig. 15.

Scheduling using proposed fuzzy algorithm.


Fig. 16.

Variation of efficiency with loading factor.


Table. 1.

Table 1. Average waiting time for randomly generated 5 processes.

AlgorithmAverage waiting time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS16.217.220.223.610.4
SJF1410.81121.210.4
PS19.81623.42519.8
Proposed1711.212.623.412.6

Table. 2.

Table 2. Average waiting time for randomly generated 10 processes.

AlgorithmAverage waiting time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS72.384.250.862.675.8
SJF43.565.727.440.947
PS64.981.366.665.175.2
Proposed48.170.436.948.458.9

Table. 3.

Table 3. Average turn-around time for randomly generated 5 processes.

AlgorithmAverage turn-around time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS26.427.430.23720.4
SJF24.2212134.620.4
PS3026.233.438.429.8
Proposed27.221.422.636.822.6

Table. 4.

Table 4. Average turn-around time for randomly generated 10 processes.

AlgorithmAverage turn-around time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS87.1104.563.276.591.8
SJF58.38639.854.862.4
PS79.7101.6797990.6
Proposed62.990.749.362.374.3

Table. 5.

Table 5. Highly loaded system with loading factor of 0.98.

Process IDPeriodExecution time
P121
P251
P372

Table. 6.

Table 6. Overloaded system with loading factor of 1.33.

Process IDPeriodExecution time
P121
P241
P372
P4103

Table. 7.

Table 7. Overloaded system with loading factor of 1.125.

Process IDPeriodExecution time
P121
P241
P383

Table. 8.

Table 8. Observations for the processes in Table 7.

AlgorithmP1P2P3
RMExpected423
Scheduled422
Miss001

EDFExpected423
Scheduled422
Miss001

LLFExpected423
Scheduled422
Miss001

ProposedExpected423
Scheduled422
Miss001

Table. 9.

Table 9. Overloaded system with loading factor of 1.1875.

Process IDPeriodExecution time
P121
P241
P383
P4161

Table. 10.

Table 10. Observations for the processes in Table 9.

AlgorithmP1P2P3P4
RMExpected8461
Scheduled8440
Miss0021

EDFExpected8461
Scheduled8440
Miss0021

LLFExpected8461
Scheduled8350
Miss0111

ProposedExpected8461
Scheduled8431
Miss0030

  1. Zouaoui, S, Boussaid, L, and Mtibaa, A (2019). Priority based round robin (PBRR) CPU scheduling algorithm. International Journal of Electrical & Computer Engineering. 9, 190-202. http://doi.org/10.11591/ijece.v9i1.pp190-202
    CrossRef
  2. Evwiekpaefe, AE, Ibrahim, A, and Musa, MN (2022). Improved shortest job first CPU scheduling algorithm. Dutse Journal of Pure and Applied Sciences (DUJOPAS). 8, 114-127.
  3. Omotehinwa, TO (2022). Examining the developments in scheduling algorithms research: a bibliometric approach. Heliyon. 8. article no. e09510. https://doi.org/10.1016/j.heliyon.2022.e09510
    Pubmed KoreaMed CrossRef
  4. Liu, CL, and Layland, JW (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM. 20, 46-61. https://doi.org/10.1145/321738.321743
    CrossRef
  5. Lehoczky, J, Sha, L, and Ding, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior, Proceedings of Real-Time Systems Symposium (RTSS), Santa Monica, CA, USA, 1989, pp. 166-171. https://doi.org/10.1109/REAL.1989.63567
    CrossRef
  6. Audsley, NC, Burns, A, Richardson, MF, and Wellings, AJ (1991). Hard real-time scheduling: the deadline-monotonic approach. IFAC Proceedings Volumes. 24, 127-132. https://doi.org/10.1016/S1474-6670(17)51283-5
    CrossRef
  7. Goel, N, and Garg, RB (2016). Performance analysis of CPU scheduling algorithms with novel OMDRRS algorithm. International Journal of Advanced Computer Science and Applications. 7, 216-221. https://dx.doi.org/10.14569/IJACSA.2016.070130
    CrossRef
  8. Yaashuwanth, C, and Ramesh, DR (2009). A new scheduling algorithms for real time tasks. International Journal of Computer Science and Information Security. 6, 61-66. https://doi.org/10.48550/arXiv.0912.0606
    CrossRef
  9. Prajapati, V, Shah, A, and Balani, P. Design of new scheduling algorithm LLF DM and its comparison with existing EDF, LLF, and DM algorithms for periodic tasks, Proceedings of 2013 International Conference on Intelligent Systems and Signal Processing (ISSP), Vallabh Vidyanagar, India, 2013, pp. 42-46. https://doi.org/10.1109/ISSP.2013.6526871
    CrossRef
  10. Mattihalli, C. Designing and implementing of earliest deadline first scheduling algorithm on standard Linux, Proceedings of 2010 IEEE/ACM Int’l Conference on Green Computing and Communications & Int’l Conference on Cyber, Physical and Social Computing, Hangzhou, China, 2010, pp. 901-906. https://doi.org/10.1109/GreenCom-CPSCom.2010.82
    CrossRef
  11. Kareem, A (2017). Super-twisting sliding mode controller with fuzzy logic based moving sliding surface for electronic throttle control. International Journal of Advanced Mechatronic Systems. 7, 174-182. https://doi.org/10.1504/IJAMECHS.2017.086211
    CrossRef
  12. Kareem, A, and Azeem, MF (2013). A novel adaptive super-twisting sliding mode controller with a single input-single output fuzzy logic control based moving sliding surface. International Journal of Control and Automation. 6, 183-198.
  13. Jin, X, and Yu, L (2022). Research and implementation of high priority scheduling algorithm based on intelligent storage of power materials. Energy Reports. 8, 398-405. https://doi.org/10.1016/j.egyr.2022.03.126
    CrossRef
  14. Dai, X, Zhao, S, Jiang, Y, Jiao, X, Hu, XS, and Chang, W. Fixed-priority scheduling and controller co-design for time-sensitive networks, Proceedings of the 39th International Conference on Computer-Aided Design, Virtual Event, USA, 2020, pp. 1-9. https://doi.org/10.1145/3400302.3415715
    CrossRef
  15. Chandiramani, K, Verma, R, and Sivagami, M (2019). A modified priority preemptive algorithm for CPU scheduling. Procedia Computer Science. 165, 363-369. https://doi.org/10.1016/j.procs.2020.01.037
    CrossRef
  16. Ross, TJ (2004). Fuzzy Logic with Engineering Applications. Chichester, UK: John Wiley & Sons.
  17. Zouaoui, S, Boussaid, L, and Mtibaa, A. CPU scheduling algorithms: case & comparative study, Proceedings of 2016 17th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering (STA), Sousse, Tunisia, 2016, pp. 158-164. https://doi.org/10.1109/STA.2016.7951997
    CrossRef
  18. Siahaan, APU (2006). Comparison analysis of CPU scheduling: FCFS, SJF and Round Robin. International Journal of Engineering Development and Research. 4, 124-132. https://doi.org/10.31227/osf.io/6dq3p
    CrossRef
  19. Husain, H, Gupta, K, and Taneja, S (2014). Modified first come first serve (MFCFS). International Journal of Advanced Computational Engineering and Networking. 2, 11-15.
  20. Mamdani, (1977). Application of fuzzy logic to approximate reasoning using linguistic synthesis. IEEE Transactions on Computers. 26, 1182-1191. https://doi.org/10.1109/TC.1977.1674779
    CrossRef
  21. Suyyagh, A, Tong, JG, and Zilic, Z (2016). Performance evaluation of meta-heuristics in energy aware real-time scheduling problems. Jordanian Journal of Computers and Information Technology (JJCIT). 2, 68-85.
    CrossRef

Abdul Kareem holds a Doctor of Philosophy from St Peter’s Institute of Higher Education and Research, Chennai, India. He also received his B.Tech. and M. Tech from Kannur University, India in 2003 and Visvesvaraya Technological University, Belagavi, India in 2008 respectively. He is currently Principal and a Professor at Electronics and Communication Engineering in Moodlakatte Institute of Technology, Kundapura, India. His research interests are in artificial intelligence, machine learning, control systems and microelectronics. He has published over 15 papers in international journals and conferences. He is a senior member of IEEE.

E-mail: afthabakareem@gmail.com.

Varuna Kumara is a research scholar in the Department of Electronics Engineering at JAIN (Deemed to be University), Bengaluru, India. He also received his B.E. and M.Tech. from Visvesvaraya Technological University, Belagavi, India in 2009 and 2012 respectively. He is currently assistant professor at Electronics and Communication Engineering in Moodlakatte Institute of Technology, Kundapura, India. His research interests are in artificial intelligence, signal processing, and control systems.

E-mail: vkumarg.24@gmail.com.

Article

Original Article

International Journal of Fuzzy Logic and Intelligent Systems 2024; 24(1): 30-42

Published online March 25, 2024 https://doi.org/10.5391/IJFIS.2024.24.1.30

Copyright © The Korean Institute of Intelligent Systems.

A Novel Fuzzy Logic Based Operating System Scheduling Scheme

Abdul Kareem1 and Varuna Kumara2

1Department of Electronics and Communication, MIT Kundapura, Karnataka, India
2Department of AI & ML, MIT Kundapura, Karnataka, India

Correspondence to:Varuna Kumara (vkumarg.24@gmail.com)

Received: April 18, 2022; Revised: October 21, 2023; Accepted: November 27, 2023

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted noncommercial use, distribution, and reproduction in any medium, provided the original work is properly cited.

Abstract

For a computer-based system, a set of processes must be scheduled such that every process is completed within its deadline. CPU scheduling is the process of allocating CPU among various processes in a multi-processing system. The decision to allocate the CPU to a process has to take into consideration all aspects, including its priority and execution time, as scheduling is guided by a number of factors other than the execution time or priority. It is no longer one-dimensional and has become a multidimensional problem with vagueness and uncertainties such as different CPU loading scenarios. The vagueness and uncertainties associated with the decision to allocate a CPU to a particular process can be addressed using a fuzzy logic approach. In this study, we propose a fuzzy logic-based algorithm for CPU scheduling. The proposed algorithm was compared with conventional scheduling algorithms for different CPU loading scenarios. The proposed method can schedule and execute all processes well within the deadline with a reduced average turn-around and a reduced average waiting time. From the comparison results, it is evident that the proposed algorithm outperforms conventional algorithms in terms of the average turn-around and waiting times.

Keywords: Fuzzy logic, Scheduling, Waiting time, Turn-around time

1. Introduction

When a computer boots up, different applications and software are initiated. Each piece of software or application can be considered a process. A central processing unit (CPU) is at the heart of all computational systems. A computer system may have a single processor or several processors for computation. In a single-processor system, the CPU must be shared among different processes. This process is simply a task that must be completed. These processes may be user- or system-level processes. The operating system (OS) bridges the gap between user applications and the underlying hardware. The OS efficiently manages the system resources that are available to users or system-level applications. In a multiprogramming environment, several processes may require the same resources, which must be shared among the processes in an efficient manner. It is the duty of the OS to ensure that the system resources are efficiently made available to the processes that require them. The allocation of system resources to various processes is called scheduling [117]. The scheduler is the one that decides how the scheduling needs to be carried out. Various scheduling algorithms have been adopted by various operating systems for scheduling in OSs. In real-time industrial systems, these processes are deterministic. They must be scheduled and executed well within the deadline, and any process failing to meet the deadline may result in the abrupt behavior of the system, leading to hazards and degraded performance. Care should be taken to ensure that the processes do not wait long. Hence, real-time scheduling is a tedious task, and a careful design of the scheduling algorithm is very important for supporting the parallelism of processes. The main parameters that determine the efficiency of the scheduling algorithm are the waiting time and turn-around time. Attempts have been made to reduce these factors in a given set of processes. Careful investigation of existing algorithms reveals that processes in the ready queue are scheduled by considering only one parameter. This parameter can be the execution time or priority. Because scheduling is guided by both the execution time and priority, it is no longer one-dimensional and has become a multidimensional problem. Thus, many parameters must be analyzed, and decisions must be made while scheduling the processes.

The vagueness in decisions can be addressed using a fuzzy logic approach. In this study, we propose a new scheduling algorithm based on fuzzy logic that considers both execution time and priority. The proposed system was developed using the MATLAB Fuzzy Logic Toolbox and a case study was conducted. In real-time operating systems, the execution time and priority of processes are not known; hence, random processes with random execution times and priorities are generated and scheduled using the proposed and conventional algorithms. The waiting and turn-around times of the processes are observed for the proposed and conventional algorithms. The experiment was conducted for several sets of processes, and the average waiting and turn-around times were compared. The algorithm was modified to fit into a real-time system, and the analysis was carried out. From the analysis, it was found that the proposed system makes a better decision to allocate the CPU to the processes, despite ambiguity. For real-time systems, the proposed algorithm ensures that all processes meet their deadlines. The analysis was extended to various CPU loading factors, and a comparison was made. Thus, the proposed algorithm adaptively addresses process scheduling even under overload conditions and effectively handles deadlines.

This study highlights the potential of a fuzzy logic-based scheduling algorithm to address the complexities of process scheduling in modern computing environments. This offers a promising solution for optimizing the allocation of system resources and ensuring the timely execution of processes, ultimately contributing to the stability and reliability of computer systems, particularly in real time. The proposed method can schedule and execute all the processes well within the deadline, with a reduced average turn-around time and a reduced average waiting time in comparison with conventional algorithms.

The remainder of this paper is organized as follows. Section 2 presents a literature review, emphasizing the feasibility test by Liu and Layland [4]. Section 3 outlines the algorithm that employs fuzzy logic. Section 4 substantiates its efficacy through a case study and results analysis, collectively highlighting its robustness and practical applications. Finally, Section 5 presents the conclusions of this study.

2. Literature Review

Scheduling is a fundamental function of an OS. The type of scheduling algorithm employed depends on the OS of interest, and different operating systems involve different scheduling algorithms. Extensive research has been conducted in the field of operating systems, and various researchers have developed new scheduling algorithms. Priority-based scheduling is the most widely used scheduling method.

In first-come first-serve (FCFS) scheduling, the processes that enter the ready queue are scheduled first. FCFS is a non-preemptive scheduling method in which the process entering the ready queue is first scheduled, and the process runs to its completion [18, 19]. The main disadvantage of FCFS is that the average waiting time and turn-around time are greater [19]. A process with a smaller burst time must wait for its turn, whereas processes with a high burst time are currently executing. In the shortest job-first (SJF) method, the process with the shortest burst time among the processes in the ready queue is given a CPU for execution. SJF may be preemptive or non-preemptive. In a preemptive environment, the OS may preempt the current execution process if a new process with a burst time shorter than that of the execution task enters a ready queue. In a non-preemptive environment, the scheduled process continues its execution, and no preemption occurs [8]. In the priority-based scheduling algorithm, priorities are assigned to a set of services, and scheduling is performed according to the priority assigned. Priority may be assigned by the OS or by the user. The interpretation of the values assigned to the priorities is OS-dependent. Different OSs were interpreted differently. In priority-based scheduling algorithms, the processes suffer from starvation. Processes with lower priority must wait for the completion of high-priority processes.

Real-time systems are deterministic, and the processes are time-critical. The waiting time for the processes is limited by the service deadline. All services must be executed within a deadline. For real-time operating systems, rate monotonic (RM) and deadline monotonic (DM) algorithms based on fixed-priority scheduling are commonly used. Recently, the earliest deadline first (EDF) and lowest laxity first (LLF) methods based on dynamic priority scheduling have been explored.

In the RM policy, the most frequently requested task is given the highest priority. Liu and Layland [4] proposed a feasibility test for the RM policy, thus defining the least upper bound as given in Eq. (1).

U=i=1m(CiTi)m(21m-1).

Several assumptions were made, and a feasibility test was proposed. The assumptions made are as follows: the requests for all tasks for which hard deadlines exist are periodic with constant intervals between requests; deadlines consist of run-ability constraints only, that is, each task must be completed before the next request for it occurs; the tasks are independent; the runtime for each task is constant for that task and does not vary with time; and any nonperiodic tasks in the system are special: they are initialization or failure recovery routines [4]. The rate-monotonic least upper bound (RMLUB) was just a sufficient test, meaning that the set of services that pass the RMLUB can be scheduled without missing the deadline, while the set of services failing to meet the RMLUB does not guarantee that they cannot be scheduled, because the RMLUB was just the necessary test to determine whether the set of services was feasible or not. Lehoczky et al. [5] developed an iterative feasibility study. This test is called the scheduling-point test and is a necessary and sufficient feasibility test. Eq. (2) describes the scheduling-point test as follows:

i,1in,minj=1icj(l)TkTj(l)Tk.

Completion time is another iterative method available in the literature to check for feasibility. Eq. (3) depicts the test completion time: one another important static priority policy [3]. In the DM, the deadline of services is considered. Eq. (4) describes the DM scheduling policy:

an(t)=j=1ntTjCj,i,1in,CiDi+IiDi1.0.

Several studies have been conducted on the development of new scheduling algorithms. One of them presented an optimum multilevel dynamic round-robin scheduling (OMDRRS) algorithm that maintains jobs based on factor analysis. The proposed algorithm was simulated, tested, and compared with existing scheduling [7]. The scheduling algorithm for real-time tasks proposed by Yaashuwanth and Ramesh [8] modified existing scheduling algorithms and rendered them suitable for implementation in embedded systems. Comparative results of the algorithm are presented. Research has been conducted to exploit the advantages of the existing algorithms and combine them to develop new algorithms. One such study is presented by Prajapati et al. [9]. Scheduling of processes is crucial in real-time systems. Some scheduling algorithms perform better under underloaded conditions, whereas they fail to perform better in overloaded conditions, and vice versa. A new scheduling algorithm was developed by exploiting the properties of the existing algorithms [1215].Different OSs adopt different scheduling algorithms. To implement a scheduling algorithm, the OS system must be modified to incorporate this change [13]. Efforts have been made to implement EDF scheduling algorithms in standard Linux environments [10]. All studies treated the scheduling algorithm as a one-dimensional problem without significant ambiguity in decision-making. When scheduling is viewed as a vague multidimensional problem, such as different CPU loading scenarios, the fuzzy logic approach is the best candidate. In this study, we developed a novel scheduling algorithm based on fuzzy logic.

3. Proposed Fuzzy Logic-based Scheduling Algorithms

Scheduling based on priority and execution time simultaneously is a tedious job, and ambiguities exist in decision-making. Fuzzy logic can handle problems or systems prone to uncertainties, vagueness, imprecision, approximations, partial truth, or qualitative moods [16]. Therefore, we propose a novel scheduling algorithm based on fuzzy logic.

3.1 Inputs and Output

The two parameters considered for analyzing the set of processes under consideration and deciding the scheduling were the execution time and priority assigned to the processes. Hence, the execution time and priority assigned to the processes were the inputs. Based on these inputs, the scheduler determines the process to which the CPU must be allotted. Hence, the priority at which the processes are allocated to the CPU for processing is the output, with the premise that “lesser the value, more is the priority.”

3.2 Fuzzification

The two input variables were normalized to the range [0, 1] the appropriate scaling factors. The inputs are crisp in nature; hence, they must be converted to a fuzzy logic form. This fuzzification process is performed by assigning membership values to the inputs, as shown in Figures 1 and 2. The membership functions of the fuzzy outputs are shown in Figure 3. The input “Execution Time” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 1. The input “Priority” with the premise “lesser the value, more is the priority” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 2. The output “CPU Allocation Priority” with a premise “lesser the value, more is the priority” has triangular membership functions for linguistic variables, VL (very low), L (low), M (medium), H (high), and VH (very high), as shown in Figure 3.

To combine two input parameters, Execution Time and Priority, to compute the output parameter, CPU Allocation Priority, there are no exact models or rules, resulting in uncertainties. However, certain approximate rules based on human reasoning can be applied to model this scenario. Fuzzy logic is an appropriate tool for incorporating approximation rules based on human reasoning into workable algorithms. The combination can be modeled by a Mamdani-type fuzzy inference system with a rule base developed using approximate reasoning, as given below. The relationship between the input and output is shown in Figure 4.

Rule 1: If (Priority is VH) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 2: If (Priority is VH) and (execution time is L), then (CPU Allocation Priority is VH).

Rule 3: If (Priority is VH) and (Execution Time is M), then (CPU Allocation Priority is VH).

Rule 4: If (Priority is VH) and (Execution Time is H), then (CPU Allocation Priority is H).

Rule 5: If (Priority is VH) and (Execution Time is VH), then (CPU Allocation Priority is M).

Rule 6: If (Priority is H) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 7: If (Priority is H) and (Execution Time is L), then (CPU Allocation Priority is VH).

Rule 8: If (Priority is H) and (Execution Time is M), then (CPU Allocation Priority is H).

Rule 9: If (Priority is H) and (Execution Time is H), then (CPU Allocation Priority is M).

Rule 10: If (Priority is H) and (Execution Time is VH), then (CPU Allocation Priority is L).

Rule 11: If (Priority is M) and (Execution Time is VL), then (CPU Allocation Priority is VH).

Rule 12: If (Priority is M) and (Execution Time is L), then (CPU Allocation Priority is H).

Rule 13: If (Priority is M) and (Execution Time is M), then (CPU Allocation Priority is M).

Rule 14: If (Priority is M) and (Execution Time is H), then (CPU Allocation Priority is L).

Rule 15: If (Priority is M) and (Execution Time is VH), then (CPU Allocation Priority is VL).

Rule 16: If (Priority is L) and (Execution Time is VL), then (CPU Allocation Priority is H).

Rule 17: If (Priority is L) and (Execution Time is L), then (CPU Allocation Priority is M).

Rule 18: If (Priority is L) and (Execution Time is M), then (CPU Allocation Priority is L).

Rule 19: If (Priority is L) and (Execution Time is H), then (CPU Allocation Priority is VL).

Rule 20: If (Priority is L) and (Execution Time is VH), then (CPU Allocation Priority is VL).

Rule 21: If (Priority is VL) and (Execution Time is VL), then (CPU Allocation Priority is M).

Rule 22: If (Priority is VL) and (Execution Time is L), then (CPU Allocation Priority is L).

Rule 23: If (Priority is VL) and (Execution Time is M), then (CPU Allocation Priority is VL).

Rule 24: If (Priority is VL) and (Execution Time is H), then (CPU Allocation Priority is VL).

Rule 25: If (Priority is VL) and (Execution Time is VH), (CPU Allocation Priority is VL)

3.3 Fuzzy Inference System

A Mamdani fuzzy inference system was designed for the proposed algorithm. In this inference system, the antecedent of a rule has two parts, “Priority” and “Execution Time,” and the operator between them is “and.” The “and” operation is performed by applying the “min” operator to the membership values of two inputs, and this value is computed as the truth value of the rule. This true value is then applied to the output fuzzy set to obtain the fuzzy output corresponding to the rule. The fuzzy outputs corresponding to all rules are obtained, and they are combined using the “max” operator to obtain the final fuzzy output [1620]. The inference for “Priority = 0.5” and “Execution Time = 0.5” is as shown in Figure 5.

3.4 Defuzzification

Defuzzification converts the fuzzy output of a fuzzy inference engine into a crisp value [16]. This can be achieved by computing the centroid of the fuzzy output, as expressed in Eq. (5). The centroid method was used as the defuzzification method because it provides higher accuracy and smoothness in the output.

X*=xμA(x)dxμA(x)dx.

μA(x) is a membership function of aggregated fuzzy output where xX.

4. Results and Discussion

The proposed fuzzy scheduling algorithm was verified for real-time processing. To verify the proposed algorithm, different cases of different sets of random processes were considered. Table 1 summarizes the average waiting time for different algorithms, with a sample size of five processes, considering five different cases, and the comparison is depicted in Figure 6. The sample size was increased to 10 to increase the confidence interval to a 95% level. The randomness of the processes also increases. Table 2 lists the experimental results for a set of ten processes, considering five different cases. A comparison of the results is presented in Figure 7.

The FCFS algorithm schedules the processes that occur early in the queue and does not consider the execution time and priority of the processes. Because the processes are random, the probability of processes with less execution time and high priority entering the ready queue is very low. Therefore, a random set of processes suffers from long waiting times. The SJF algorithm schedules processes by considering their execution time. SJF performs well with respect to the waiting time and turn-around time of the processes but does not consider the priority of the processes. Thus, a higher-priority process with a longer execution time must wait longer. Priority-based scheduling (PS) algorithms do not consider the execution time of the process.

The variations in waiting time for different sample sizes for the proposed scheme are shown in Figures 6 and 7. The turn-around times for the different processes are compared in Tables 3 and 4. It is clear that the average waiting and turn-around times are significantly reduced in comparison with existing algorithms. The proposed algorithm attempts to reduce waiting and turn-around times without compromising the process parameters. With increased randomness and an increased number of processes, the proposed algorithms perform almost equally to SJF, taking both execution time and priority into consideration. Hence, the ambiguity of considering multiple parameters is considered in the proposed approach.

The proposed fuzzy-based scheduling algorithm was extended to a preemptive environment by evaluating fuzzy priorities at regular time intervals for a set of processes. Fuzzy priorities are calculated at regular time intervals considering the execution time and process priorities. These newly obtained priority values are used for further priority computations. The one with the highest priority is scheduled. The proposed algorithm performs better than preemptive priority-based scheduling and is as efficient as the preemptive SJF scheduling algorithm.

4.1 The Proposed Algorithm for Real-Time Services

Table 5 lists the three processes, their execution times, and their execution periods, and shows shows the nonharmonic set of processes with a CPU loading factor of 0.98. These sets of processes were scheduled using the RM, EDF, and LLF scheduling policies, which are presented in Figures 8, 9, and 10, respectively. The same set of processes was scheduled using the proposed fuzzy scheduling algorithm, and a Gantt chart is presented in Figure 11.

From the Gantt chart, it was observed that although the CPU was not loaded at 100%, the RM policy failed to schedule the set of processes. RM fails to schedule a set of processes within a given deadline because the process that occurs more frequently has the highest priority. Processes P1 and P2 occur more frequently than process P3; hence, RM fails to schedule P3 within the given deadline, as depicted in Figure 8.

Figures 9 and 10 show the Gantt charts for scheduling the processes in Table 5 using EDF and LLF, respectively. We found that the set of processes could be scheduled effectively without missing deadlines for the time interval under consideration. The set of processes is scheduled using the proposed fuzzy scheduling algorithm and is presented in Figure 11. The proposed scheduling algorithm performed better than RM scheduling and was as efficient as the EDF and LLF scheduling algorithms for a CPU loading factor of less than or equal to 100%.

4.2 Deadline Over-Run Scenario

Handling a process that misses a deadline is an important task in real-time operating systems. Care should be taken to handle missed-deadline processes. The process of missing a deadline can be addressed using various methods. One way of handling the missed-deadline process is to continue to run the process that misses the deadline for a finite duration, or continue it to execute infinitely after missing the deadline. Another option was to terminate the process as soon as the deadline was missed. In the RM policy, if any process misses the deadline, then all services with priorities less than that of the process that missed the deadline continue to miss the deadline, while the other services with priorities greater than those of the process that missed the deadline are guaranteed to execute well before the deadline. In the EDF algorithm for scheduling, a process that misses the deadline causes all other processes to wait in the ready queue and potentially misses the deadline. In EDF, a process that misses the deadline will have a negative value for the TTD, hence making all other services wait and making them miss deadlines. One way to eliminate this problem is to have an additional process that will be given more priority than the overrunning process; as a result, the overrunning process will be preempted. A service added to the queue does not preempt the overrunning process because it has a negative TTD. This problem in handling missed-deadline processes was overcome by the proposed fuzzy algorithm for scheduling.

The analysis was conducted considering a heavily loaded scenario. Table 6 lists the four sets of processes, along with their execution times and deadlines. For the set of processes listed in Table 5, the CPU loading factor is 1.33. These processes were scheduled using an existing algorithm and were compared with the proposed algorithm. The proposed algorithm performed better than the RM policy and was as efficient as EDF and LLF. The CPU was overloaded, and P4 missed the deadline. The scheduling schemes are shown in Figures 1215, respectively.

The efficiency of the proposed algorithm was evaluated by considering a set of processes and scheduling the processes with a CPU loading factor of 1.125, as listed in Table 7. These processes are harmonic in nature, and the maximum time period considered is the least common multiple of the process periods, which is eight times the units in this case. The processes are scheduled, and observations are made. Table 8 presents the observations made during scheduling.

From Table 8, it is observed that all the algorithms fail to schedule process P3 because the extra execution time of P3 overloads the CPU; hence, it cannot be scheduled. To support the efficiency of the proposed algorithm, an additional process, P4, is added, whose period is 16 times the number of units and has to be executed once in 16 units. For the previously scheduled set of processes, it was obvious that the process P3 missed the deadline because the CPU is overloaded.

A different set of processes was considered with a loading factor of 1.1875, as shown in Table 9. If only processes P1, P2, and P4 were considered, the loading factor was 0.8125. These sets of processes were scheduled, and the observations are presented in Table 10.

From these observations, it is clear that process P4 is not scheduled by the conventional algorithms for execution, whereas the proposed fuzzy algorithm schedules process P4 for execution well within the deadline. As mentioned earlier, the set of processes P1, P2, and P4 provides a loading factor of 0.8125, whereas 1.1875 considers process P3. The proposed algorithm makes use of this, understands that processes P1, P2, and P4 can be effectively scheduled without missing the deadline, as observed by humans, and makes the decision accordingly. Thus, the deadline over-run scenario was effectively handled by the proposed algorithm.

The proposed scheduling algorithm provides higher quality than conventional scheduling algorithms. Several processes were considered with different loading factors, and the efficiency was calculated and plotted in Figure 16. For the over-loaded scenario, the proposed algorithm performed better than the existing algorithms for scheduling.

5. Conclusion

Decision-making for scheduling a process in an operating system is a very important and tedious task. A novel approach for scheduling a set of processes was presented and compared with existing scheduling algorithms. The proposed fuzzy algorithm for scheduling performs better than the commonly used FCFS and priority-based scheduling policies. The proposed algorithm not only considers priorities, but also their execution time for scheduling decisions. To schedule real-time processes, the fuzzy rules are modified, and the proposed algorithm is compared with existing algorithms for real-time processes with well-defined time durations for highly loaded scenarios. The proposed algorithm performs better than the conventional RM scheduling algorithm and is as efficient as the EDF and LLF scheduling algorithms. For the overloaded scenario, the proposed fuzzy scheduling algorithm performed better than the RMEDF and LLF scheduling algorithms. The proposed algorithm effectively handles the process of missing the deadline, ensuring that all other processes continue their execution safely without missing the deadline. From the analysis, it was concluded that the proposed algorithm makes its best effort to deliver maximum efficiency, making it suitable for real-time operating systems.

Fig 1.

Figure 1.

Membership functions of “Execution time.”

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 2.

Figure 2.

Membership functions of “Process priority.”

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 3.

Figure 3.

Membership functions of “CPU allocation priority.”

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 4.

Figure 4.

Output variation as a function of input parameters.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 5.

Figure 5.

Fuzzy inference for “Priority = 0.5” and “Execution Time = 0.5.”

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 6.

Figure 6.

Variation of average waiting time for sample size of five processes.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 7.

Figure 7.

Variation of waiting time for sample size of 10 processes.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 8.

Figure 8.

Scheduled processes using RM policy.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 9.

Figure 9.

Scheduled processes using EDF algorithm

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 10.

Figure 10.

Scheduled processes using LLF algorithm

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 11.

Figure 11.

Scheduled processes using the proposed algorithm.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 12.

Figure 12.

Scheduling using RM algorithm.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 13.

Figure 13.

Scheduling using EDF algorithm.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 14.

Figure 14.

Scheduling using LLF algorithm.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 15.

Figure 15.

Scheduling using proposed fuzzy algorithm.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Fig 16.

Figure 16.

Variation of efficiency with loading factor.

The International Journal of Fuzzy Logic and Intelligent Systems 2024; 24: 30-42https://doi.org/10.5391/IJFIS.2024.24.1.30

Table 1 . Average waiting time for randomly generated 5 processes.

AlgorithmAverage waiting time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS16.217.220.223.610.4
SJF1410.81121.210.4
PS19.81623.42519.8
Proposed1711.212.623.412.6

Table 2 . Average waiting time for randomly generated 10 processes.

AlgorithmAverage waiting time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS72.384.250.862.675.8
SJF43.565.727.440.947
PS64.981.366.665.175.2
Proposed48.170.436.948.458.9

Table 3 . Average turn-around time for randomly generated 5 processes.

AlgorithmAverage turn-around time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS26.427.430.23720.4
SJF24.2212134.620.4
PS3026.233.438.429.8
Proposed27.221.422.636.822.6

Table 4 . Average turn-around time for randomly generated 10 processes.

AlgorithmAverage turn-around time (ms)
Case 1Case 2Case 3Case 4Case 5
FCFS87.1104.563.276.591.8
SJF58.38639.854.862.4
PS79.7101.6797990.6
Proposed62.990.749.362.374.3

Table 5 . Highly loaded system with loading factor of 0.98.

Process IDPeriodExecution time
P121
P251
P372

Table 6 . Overloaded system with loading factor of 1.33.

Process IDPeriodExecution time
P121
P241
P372
P4103

Table 7 . Overloaded system with loading factor of 1.125.

Process IDPeriodExecution time
P121
P241
P383

Table 8 . Observations for the processes in Table 7.

AlgorithmP1P2P3
RMExpected423
Scheduled422
Miss001

EDFExpected423
Scheduled422
Miss001

LLFExpected423
Scheduled422
Miss001

ProposedExpected423
Scheduled422
Miss001

Table 9 . Overloaded system with loading factor of 1.1875.

Process IDPeriodExecution time
P121
P241
P383
P4161

Table 10 . Observations for the processes in Table 9.

AlgorithmP1P2P3P4
RMExpected8461
Scheduled8440
Miss0021

EDFExpected8461
Scheduled8440
Miss0021

LLFExpected8461
Scheduled8350
Miss0111

ProposedExpected8461
Scheduled8431
Miss0030

References

  1. Zouaoui, S, Boussaid, L, and Mtibaa, A (2019). Priority based round robin (PBRR) CPU scheduling algorithm. International Journal of Electrical & Computer Engineering. 9, 190-202. http://doi.org/10.11591/ijece.v9i1.pp190-202
    CrossRef
  2. Evwiekpaefe, AE, Ibrahim, A, and Musa, MN (2022). Improved shortest job first CPU scheduling algorithm. Dutse Journal of Pure and Applied Sciences (DUJOPAS). 8, 114-127.
  3. Omotehinwa, TO (2022). Examining the developments in scheduling algorithms research: a bibliometric approach. Heliyon. 8. article no. e09510. https://doi.org/10.1016/j.heliyon.2022.e09510
    Pubmed KoreaMed CrossRef
  4. Liu, CL, and Layland, JW (1973). Scheduling algorithms for multiprogramming in a hard-real-time environment. Journal of the ACM. 20, 46-61. https://doi.org/10.1145/321738.321743
    CrossRef
  5. Lehoczky, J, Sha, L, and Ding, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior, Proceedings of Real-Time Systems Symposium (RTSS), Santa Monica, CA, USA, 1989, pp. 166-171. https://doi.org/10.1109/REAL.1989.63567
    CrossRef
  6. Audsley, NC, Burns, A, Richardson, MF, and Wellings, AJ (1991). Hard real-time scheduling: the deadline-monotonic approach. IFAC Proceedings Volumes. 24, 127-132. https://doi.org/10.1016/S1474-6670(17)51283-5
    CrossRef
  7. Goel, N, and Garg, RB (2016). Performance analysis of CPU scheduling algorithms with novel OMDRRS algorithm. International Journal of Advanced Computer Science and Applications. 7, 216-221. https://dx.doi.org/10.14569/IJACSA.2016.070130
    CrossRef
  8. Yaashuwanth, C, and Ramesh, DR (2009). A new scheduling algorithms for real time tasks. International Journal of Computer Science and Information Security. 6, 61-66. https://doi.org/10.48550/arXiv.0912.0606
    CrossRef
  9. Prajapati, V, Shah, A, and Balani, P. Design of new scheduling algorithm LLF DM and its comparison with existing EDF, LLF, and DM algorithms for periodic tasks, Proceedings of 2013 International Conference on Intelligent Systems and Signal Processing (ISSP), Vallabh Vidyanagar, India, 2013, pp. 42-46. https://doi.org/10.1109/ISSP.2013.6526871
    CrossRef
  10. Mattihalli, C. Designing and implementing of earliest deadline first scheduling algorithm on standard Linux, Proceedings of 2010 IEEE/ACM Int’l Conference on Green Computing and Communications & Int’l Conference on Cyber, Physical and Social Computing, Hangzhou, China, 2010, pp. 901-906. https://doi.org/10.1109/GreenCom-CPSCom.2010.82
    CrossRef
  11. Kareem, A (2017). Super-twisting sliding mode controller with fuzzy logic based moving sliding surface for electronic throttle control. International Journal of Advanced Mechatronic Systems. 7, 174-182. https://doi.org/10.1504/IJAMECHS.2017.086211
    CrossRef
  12. Kareem, A, and Azeem, MF (2013). A novel adaptive super-twisting sliding mode controller with a single input-single output fuzzy logic control based moving sliding surface. International Journal of Control and Automation. 6, 183-198.
  13. Jin, X, and Yu, L (2022). Research and implementation of high priority scheduling algorithm based on intelligent storage of power materials. Energy Reports. 8, 398-405. https://doi.org/10.1016/j.egyr.2022.03.126
    CrossRef
  14. Dai, X, Zhao, S, Jiang, Y, Jiao, X, Hu, XS, and Chang, W. Fixed-priority scheduling and controller co-design for time-sensitive networks, Proceedings of the 39th International Conference on Computer-Aided Design, Virtual Event, USA, 2020, pp. 1-9. https://doi.org/10.1145/3400302.3415715
    CrossRef
  15. Chandiramani, K, Verma, R, and Sivagami, M (2019). A modified priority preemptive algorithm for CPU scheduling. Procedia Computer Science. 165, 363-369. https://doi.org/10.1016/j.procs.2020.01.037
    CrossRef
  16. Ross, TJ (2004). Fuzzy Logic with Engineering Applications. Chichester, UK: John Wiley & Sons.
  17. Zouaoui, S, Boussaid, L, and Mtibaa, A. CPU scheduling algorithms: case & comparative study, Proceedings of 2016 17th International Conference on Sciences and Techniques of Automatic Control and Computer Engineering (STA), Sousse, Tunisia, 2016, pp. 158-164. https://doi.org/10.1109/STA.2016.7951997
    CrossRef
  18. Siahaan, APU (2006). Comparison analysis of CPU scheduling: FCFS, SJF and Round Robin. International Journal of Engineering Development and Research. 4, 124-132. https://doi.org/10.31227/osf.io/6dq3p
    CrossRef
  19. Husain, H, Gupta, K, and Taneja, S (2014). Modified first come first serve (MFCFS). International Journal of Advanced Computational Engineering and Networking. 2, 11-15.
  20. Mamdani, (1977). Application of fuzzy logic to approximate reasoning using linguistic synthesis. IEEE Transactions on Computers. 26, 1182-1191. https://doi.org/10.1109/TC.1977.1674779
    CrossRef
  21. Suyyagh, A, Tong, JG, and Zilic, Z (2016). Performance evaluation of meta-heuristics in energy aware real-time scheduling problems. Jordanian Journal of Computers and Information Technology (JJCIT). 2, 68-85.
    CrossRef

Share this article on :

Related articles in IJFIS