Process Scheduling in Longest Job First (LJF) Algorithm: a Proposed : Current School News

Process Scheduling in Longest Job First (LJF) Algorithm: a Proposed Framework for Starvation Problem

APPLY NOW 👉 WORK IN CANADA WITH FREE SPONSORSHIP!


 

Process Scheduling in Longest Job First (LJF) Algorithm: a Proposed Framework for Starvation Problem.

ABSTRACT

Process as an individualistic program in execution forms the bases of everything in the computer system functionality, Central Processing Unit (CPU) becomes the main target of every process execution. The best ordering and sequence of assigning these processes to the CPU becomes the most difficult problem to obtain best performances.

This thesis work in the field of CPU scheduling by carefully studying all popular scheduling algorithms  thereby proposing  an  option to the most uncommon scheduling algorithm: Longest Job First (LJF), to compete along side others.

The major problem leading to starvation was reduced by proposing a model into the LJF. The model was designed and tested thereby suggesting ways by which LJF could be enhanced to solve parts of the starvation problems, waiting times and context switches.

TABLE OF CONTENTS 

Declaration ………….. i
Certification ………. ii
Dedication …… iii
Acknowledgement. iv
Abstract ………. v
Table of Content …..vi
List of Tables ……… ix
List of Figures ……………. x
List of Abbreviations ……….. xi

CHAPTER ONE  GENERAL INTRODUCTION

1.0 INTRODUCTION …….. 1
1.1 OBJECTIVES OF STUDY ……….. 3
1.2 SIGNIFICANCE OF STUDY ….. 3
1.3 RESEARCH QUESTIONS ……… 3
1.4 SCOPE ……… 3
1.5 METHODOLOGY ………………. 3
1.6 ORGANIZATION OF THESIS …. 4

CHAPTER TWO LITERATURE REVIEW

2.0 INTRODUCTION ………. 5
2.1 PROCESSES/ MULTIPROGRAMMING……….. 6
2.2 SCHEDULING ……… 7
2.3 SCHEDULERS ………… 9
2.3.1 Long-term Scheduler/admission Scheduler … 9
2.3.2 Mid/Medium-term Scheduler ………10
2.3.3 Short-term Scheduler/CPU scheduler …..10
2.4 DISPATCHER …………..11
2.5 SCHEDULING ALGORITHMS IN OPERATING SYSTEM. ………12
2.5.1 First Come First Served (FCFS) ……12
2.5.2 Shortest Job First/ Shortest Remaining Processing Time (SJF/SRPT) ……..14
2.5.3 Priority scheduling ………17
2.5.4 Round-Robin (RR) ………….18
2.5.5 Longest Job First (LJF) …………..18
2.6 RELATED WORK …….19

CHAPTER THREE STARVATION PROBLEM FRAMEWORK MODEL

3.0 INTRODUCTION …………..23
3.1 APPROACH OF THE MODEL ..24
3.1.1 Analysis of the CBT model …….26
3.2 CBT ALGORITHM ……27

CHAPTER FOUR IMPLEMENTATION AND TEST OF THE CBT MODEL

4.0 INTRODUCTION ……………………28
4.1 CASE ASSUMPTION ……….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 (FCFS) …………..32
4.4.2 Shortest Job First (SJF) ………..34
4.4.3 Round Robin …………….36
4.4.4 Priority Scheduling …..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 Comparing SJF and LJF+CBT ……………….46
4.4.3. Comparing LJF and LJF+CBT …46
4.4.4 Comparing RR and LJF+CBT ……….46
4.4.5 Comparing Priority Scheduling and LJF+CBT …..46
4.5. RESULTS DISCUSSION AND CONCLUSION

CHAPTER FIVE

5.0 SUMMARY, CONCLUSION AND RECOMMENDATION ………53
5.1 Summary…………………….53
5.2 Future work ……..54
5.3 Conclusion …….54
References ………..55

INTRODUCTION

Process scheduling algorithms has been an interesting field of study in Operating Systems. Scheduling is a key concept in computer multitasking, multiprocessing and real-time operating system designs. Scheduling refers to the way processes are assigned to run on available Central Processing Unit (CPU) (Galvin, 2004). Each Process (a program in execution)  passes through  some  stages  in their execution and allocation to CPU as will be illustrated in process-state diagram.

A Process is started at arrival time which gets into the Ready Queue based on some scheduling algorithm and waits for the Job scheduler/ dispatcher which decide on what scheduling algorithm to use. The process state diagram of Fig 1.1 illustrates this. The process state is as follows: New: Where processes enters. Ready: It is a stage where queues are used to order the manner in which jobs arrived.

Running: The Scheduler and Dispatcher, based on selected algorithms, move Ready jobs to Running, a job may be pre-empted back to the ready depending on the scheduling algorithm in. Waiting: On a request for an I/O and later rescheduled on completion. At the moment, based on literature, there isn’t a world most preferable scheduling algorithm (Stallings, 2000) as most operating systems use the most common scheduling algorithms.

REFERENCES

A Scheduling: Computer Scheduling. Retrieved October 27, 2011, from Scheduling: http://www.cs.sunysb.edu/~algorith/files/scheduling.shtml
Achim, S. (2005). On Performance Evaluation of Slackness option for the Self-turning dynP scheduler. Central Institute for Applied Mathematics. Julich, Germany: RSJ.
Ali Bagherinia, Ali Jaharpour and Sohrab Hojatkhah (2011). Backtracking Algorithm for Process Scheduling in Multi Processor Systems.International Conference on Computational Techniques and Artificial Intelligence (ICCTAI). pp 17-18.
Baptiste, P. (1994). Constraint- Based Scheduling : Two Extensions. University of Strathclyde, Department of Manufacturing and Engineering . Scotland:
Boleslaw, S. K. (1990). Mutual Exclusion Revisited. Fifth Jerusalem Conference in Information Technology (pp. 110-117). Israel, Jerusalem: IEEE Computer Society Press.
Cheng, T., & Kahlbacher, H. (2006). A proof for the Longest Job First Policy in one machine Scheduling. CA: Naval Research Logistics Vol 38, Issues 5, pp 715-720.

CSN Team.

APPLY NOW 👉 WORK IN CANADA WITH FREE SPONSORSHIP!


 

    Hey You!

    Don't Miss These Opportunity! Enter Your Details Below!


    => FOLLOW US ON INSTAGRAM | FACEBOOK & TWITTER FOR LATEST UPDATE

    Tags: , , , ,

    Comments are closed.

    %d bloggers like this: