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 [1–17]. 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).

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:

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:

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 [12–15].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 [16–20]. 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.

μ_A(x) is a membership function of aggregated fuzzy output where x ∈ X.

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 12–15, 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.

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

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

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

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

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

Table 6. Overloaded system with loading factor of 1.33.

Table 7. Overloaded system with loading factor of 1.125.

Table 8. Observations for the processes in Table 7.

Table 9. Overloaded system with loading factor of 1.1875.

Table 10. Observations for the processes in Table 9.