PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM

PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM

ABSTRACT

Processes, as individualistic programs in execution, form the foundation of all computer system functionality, with the Central Processing Unit (CPU) becoming the primary target of every process execution. The best ordering and sequence of assigning these processes to the CPU becomes the most difficult problem to solve in order to achieve the best results. This thesis work in the field of CPU scheduling by carefully studying all popular scheduling algorithms and proposing an alternative scheduling algorithm, Longest Job First (LJF), to compete alongside others. The major cause of starvation was mitigated by introducing a model into the LJF. The model was designed and tested, thereby suggesting ways in which LJF could be improved to address some of the starvation issues, wait times, and other issues.

TABLE OF MATERIALS

Declaration ……………………………………………………………………………………………………………………………. I

Certification ………………………………………………………………………………………………………………………….. ii

Dedication ……………………………………………………………………………………………………………………………. iii

Acknowledgement

…………………………………………………………………………………………………………………. iv

Abstract ……………………………………………………………………………………………………………………………….. v

Table of Contents

Tables Catalogue … ……………………………………………………………………………………………………………………… ix

Figures Catalogue … ……………………………………………………………………………………………………………………… x

List of Abbreviations ………………………………………………………………………………………………………………. xi

CHAPTER ONE

GENERAL INTRODUCTION ……………………………………………………………………………………………………….. 1

1.0 BEGINNING ……………………………………………………………………………………………………. 1

1.1 STUDY OBJECTIVES …………………………………………………………………………………………… 3

1.2 SIGNIFICANCE OF STUDY ……………………………………………………………………………………….. 3

1.3 QUESTIONS FOR RESEARCH ………………………………………………………………………………………….. 3

1.4 SCOPE ………………………………………………………………………………………………………………… 3

1.5 THE METHODOLOGY …………………………………………………………………………………………………… 3

1.6 ORGANIZATION OF THESIS …………………………………………………………………………………….. 4

CHAPITRE TWO ……………………………………………………………………………………………………………………… 5

REVIEW OF LITERATURE

………………………………………………………………………………………………………………. 5

INTRODUCTION 2.0 ……………………………………………………………………………………………………….. 5

2.1 PROCESSES/ MULTIPROGRAMMING……………………………………………………………………………. 6

2.2 SCHEDULE …………………………………………………………………………………………………………… 7

SCHEDULERS 2.3 …………………………………………………………………………………………………………… 9

2.3.1 Long-term Scheduler/Admission Scheduler……………………………………………………………. 9

2.3.2 Scheduler for the Mid/Long Term ……………………………………………………………………………..10

2.3.3 Temporary Scheduler/CPU scheduler …………………………………………………………………..10

2.4 DISTRIBUTOR ……………………………………………………………………………………………………………11

2.5 OPERATING SYSTEM SCHEDULING ALGORITHMS. ……………………………………………………..12

2.5.1 First-come, first-served basis (FCFS) …………………………………………………………………………….12

2.5.2 Shortest Job First/Shortest Remaining Processing Time (SJF/SRPT)…………………………..14

2.5.3 Order of precedence

………………………………………………………………………………………………….17

2.5.4 The Round-Robin System (RR) ……………………………………………………………………………………………..18

2.5.5 Start with the longest job (LJF) ………………………………………………………………………………………..18

2.6 CONNECTED WORK ……………………………………………………………………………………………………….19

CHAPITRE THREE ……………………………………………………………………………………………………………………23

STARVATION PROBLEM FRAMEWORK MODEL ……………………………………………………………………………23

3.0 BEGINNING ……………………………………………………………………………………………………….23

3.1 APPROACH OF THE MODEL ……………………………………………………………………………………….24

3.1.1 Analysis of the CBT model ………………………………………………………………………………….26

CBT ALGORITHM 3.2 ……………………………………………………………………………………………………..27

CHAPITRE FOUR …………………………………………………………………………………………………………………….28

IMPLEMENTATION AND TEST OF THE CBT MODEL ………………………………………………………………………28

4.0 INVESTIGATION ……………………………………………………………………………………………………….28

4.1 ASSUMPTION OF CASE ………………………………………………………………………………………………….28

4.2 SIMULATION FRAME WORK ………………………………………………………………………………………28

4.2.1 Processes Case 1……………………………………………………………………………………………….29

4.3 CBT PERFORMANCE EVALUATION ………………………………………………………………………………31

4.4 EXPERIMENT CASE …………………………………………………………………………………………………..32

4.4.1 First-come, first-served basis (FCFS) …………………………………………………………………………….32

4.4.2 Start with the shortest job (SJF) ……………………………………………………………………………………….34

4.4.3 Round Robin ……………………………………………………………………………………………………..36

4.4.4 Scheduling Priorities ……………………………………………………………………………………………….38

4.4.5 Longest Job First (LJF) ………………………………………………………………………………………………40

4.4.6. Longest Job First + CBT ………………………………………………………………………………………42

4.5. COMPARING EXISTING SCHEDULING ALGORITHMS WITH LJF+CBT …………………………………..45

4.5.1 Comparing FCFS and

LJF+CBT ……………………………………………………………………………..45

4.4.2 SJF and LJF+CBT Comparison ………………………………………………………………………………..46

4.4.3 LJF and LJF+CBT Comparison ………………………………………………………………………………..46

4.4.4 RR and LJF+CBT Comparison …………………………………………………………………………………46

4.4.5 Priority Scheduling versus LJF+CBT …………………………………………………………..46

4.5. DISCUSSION OF RESULTS AND CONCLUSION …………………………………………………………………….47

CHAPITRE FIVE

……………………………………………………………………………………………………………………….53

5.0 SUMMARY, CONCLUSION, AND RECOMMENDATION……………………………………………………..53

5.1 Summary………………………………………………………………………………………………………………..53

5.2 Future work ……………………………………………………………………………………………………………54

5.3 Final Thoughts ……………………………………………………………………………………………………………..54

References …………………………………………………………………………………………………………………………..55

APPENDIX A: SIMULATION RESULTS IN LOG.TXT………………………………………………………………58

APPENDIX B: LJF+CBT JAVA SOURCE CODES…………………………………………………………………….63

CHAPTER ONE

GENERAL INTRODUCTION

1.0 INTRODUCTION

Process scheduling algorithms have been a fascinating area of study in the field of operating systems.

Scheduling is an important concept in the design of computer multitasking, multiprocessing, and real-time operating systems.

Scheduling is the process of assigning processes to run on available Central Processing Units (CPUs) (Galvin, 2004). Each Process (a program in execution) goes through some stages in its execution and allocation to the CPU, as shown in the process-state diagram. At arrival time, a Process is started, which enters the Ready Queue based on some scheduling algorithm and waits for the Job scheduler/ dispatcher to decide which scheduling algorithm to use. The process state diagram in Figure 1.1 shows this.

Figure 1.1: State diagram of the process

The current state of the process is as follows:

a. Fresh: Where

Processes are introduced into the system.

b. Ready: This is a stage in which queues are used to organize the order in which jobs arrive.

c. Running: The Scheduler and Dispatcher move Ready jobs to Running based on selected algorithms; a job may be pre-empted back to Ready depending on the scheduling algorithm in use.

d. Waiting: On an I/O request that was later rescheduled after the request was completed.

e. End/Exit: The process is terminated.

According to the literature, there is no world most preferred scheduling algorithm at the moment (Stallings, 2000), because most operating systems use the most common scheduling algorithms, which include: First Come First Serve (FCFS), Shortest Job Next (SJN), Shortest Job First (SJF), Round Robin (RR), and Priority Scheduling as an extension or combination.

of two or more scheduling algorithm.

In this study, some existing scheduling algorithms, primarily the Shortest Job First (SJF) and Longest Job First (LJF) algorithms, will be investigated while minimizing latency and total waiting time to achieve maximum utilization of the Central Processing Unit (CPU).

Furthermore, we propose a framework for dealing with starvation (a condition in which processes wait indefinitely and are denied CPU allocation) problems in order to reduce the convoy (a long queue of waiting processes) problem through fairness to shorter processes.

This research will also focus on using the Longest Job First (LJF) approach to test and suggest how to best allocate Shorter Jobs to the CPU through backfilling and combination. Shorter jobs are becoming more common as people age and burst-times combine. Gaining access will be accomplished by comparing the merged burst-time and the incoming longer jobs.

1.1 OBJECTIVES OF STUDY

The goals of this work are to reduce overall waiting time and the number of context switches of processes in a multiprocessing system, resulting in a framework that gives fair consideration to shorter jobs on queue and suggests efficient time closer to Longer Jobs in execution to reduce starvation in LJF.

1.2 SIGNIFICANCE OF STUDY

The research hopes to contribute to the existing problem of operating system starvation by minimizing the overall waiting time of processes in order to achieve maximum efficiency, throughput, and CPU utilization.

1.3 RESEARCH QUESTIONS

a. When is LJF in competition with other algorithms?

b. In what environment does LJF outperform SJF, RR, and FCFS?

c. Can the Starvation problem be minimized using LJF in a multiprocessor environment?

1.4 SCOPE

The research will concentrate on the scheduling algorithm for Longer Job processes and will propose a framework for reducing long queue delays. Shorter jobs will be merged to make them more substantial in order to reduce starvation through fairness. The scope of this work is limited to reducing starvation issues and reducing overall wait times and average turnaround time.

1.5 METHODOLOGY

These are the approaches and steps that will be taken to achieve our research objectives:

a. The first consideration in this work will be the process generation using Random Number Generators with an appropriate statistical distribution (Poisson and Exponential average).

b. A distribution will also be used to generate the burst-time for each process.

c. Processes generated on Gantt charts will be analyzed, and general process properties will be calculated and saved for comparison in the final Chapter.

d. The conditions for merging processes will be stated and designed by some algorithm and tested as an implementation using Java, and our algorithm will then dispatch and schedule the merged short jobs into the CPU.

1.6 ORGANIZATION OF THESIS

The thesis will propose a framework that will minimize process starvation in the Longest Job First (LJF) scheduling algorithm by merging shorter jobs (Combinational Burst Time CBT) to maximize total CPU utilization and minimize total waiting time of the processes in the system.

The second chapter will go over the existing literature and research in the field of process scheduling.

The third chapter discusses the methodologies used to create the proposed framework for dealing with starvation issues in the Longest Job First (LJF) scheduling algorithm.

The fourth chapter will concentrate on the implementation and testing of the proposed algorithm.

The fifth chapter will summarize the work and suggest areas for future research.