Select Currency
Translate this page

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

Format: MS WORD  |  Chapter: 1-5  |  Pages: 76  |  1785 Users found this project useful  |  Price NGN5,000

  DOWNLOAD THE FULL PROJECT

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 ………………………………………………………………………………………………………………………. 1

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

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 ……………………………………………………………………………………………………………………… 5

LITERATURE REVIEW………………………………………………………………………………………………………………. 5

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 ……………………………………………………………………………………………………………………23

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

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 …………………………………………………………………………………………………………………….28

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

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 …………………………………………………………………….47

CHAPTER FIVE……………………………………………………………………………………………………………………….53

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

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

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

5.3 Conclusion ……………………………………………………………………………………………………………..54

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

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

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

CHAPTER ONE

GENERAL INTRODUCTION

1.0 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.

Figure 1.1: Process state diagram

The process state is as follows:

a. New: Where processes enters the system.

b. Ready: It is a stage where queues are used to order the manner in which jobs arrived

c. 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 use.

d. Waiting: On a request for an I/O and later rescheduled on completion of request.

e. End/Exit: Process terminates.

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 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 the combination of two or more scheduling algorithm.

In this research, some of the existing scheduling algorithms basically the Shortest Job First (SJF) and the Longest Job First (LJF) algorithm will be looked into while putting latency and minimising total waiting time to achieve maximum utilization of the Central Processing Unit (CPU).

Furthermore, we propose a frame work to deal with the starvation (A condition that make processes waits stagnantly and denied allocation to the CPU) problems to curtail the convoy (A long queue of waiting processes) problem through fairness to shorter processes.

This research will also be focusing on making the Longest Job First (LJF) the approach to test and suggest how best the Shorter Jobs gets fairer allocation to the CPU through backfilling and combination of shorter jobs through ageing and burst-times merging. The process will be gaining access through comparing the merged burst-time and the incoming longer jobs.

1.1 OBJECTIVES OF STUDY

The objectives of this work is to minimise the overall waiting time and minimise the numbers of context switching of processes in a multiprocessing system; thereby coming up with a framework that will make fair consideration to shorter jobs on queue and suggest efficient time closer to the Longer Jobs in execution to minimise starvation in LJF.

1.2 SIGNIFICANCE OF STUDY

The research hopes to make a contribution to the existing problem faced by operating system by minimizing the starvation problem to achieve maximum efficiency, throughput, and CPU utilization by minimizing the overall waiting time of processes.

1.3 RESEARCH QUESTIONS

a. When does LJF compete with other algorithms?

b. Under what environment does LJF perform better than SJF, RR and FCFS?

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

1.4 SCOPE

The research will be focusing on the scheduling algorithm for Longer Job processes and propose a framework towards reducing long delays in queues. Shorter jobs will be merged up to make them a bit considerable to reduce starvation through fairness. The scope of this work is limited to reducing starvation problems and minimizing the overall waiting times and average turn-around time.

1.5 METHODOLOGY

These are approaches and series of steps to be taken in actualising our research objectives:

a. The first consideration on this work will be the generation of the processes using Random Number generators with an appropriate statistical distribution (Poisson and Exponential average).

b. The burst-time for each process will also be generated through a distribution.

c. Analysing the processes generated on Gantt charts and calculations of general process properties will be acquired and kept for comparison at the final Chapter.

d. Conditions for merging processes will be stated and designed by some algorithm and tested as implementation using Java and later a dispatch and schedule of the merged short jobs will be moved into the CPU by our algorithm.

1.6 ORGANIZATION OF THESIS

The thesis will be focusing on proposing a framework that will minimise starvation of processes in Longest Job First (LJF) scheduling algorithm through merging shorter jobs (Combinational Burst Time CBT) to maximise total utilization of the CPU to minimize total waiting time of the processes in the system.

Chapter two will be discussing on the existing literatures and researches conducted in the field of process scheduling.

Chapter three discusses the methodologies adopted to design the proposed framework for solving starvation problems in the Longest Job First (LJF) scheduling algorithm.

Chapter four will focus on the implementation and testing of the proposed algorithm.

Chapter five will summarise the work and propose areas for future work.

  DOWNLOAD THE FULL PROJECT

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

Not The Topic You Are Looking For?



For Quick Help Chat with Us Now!

+234 813 292 6373

+233 55 397 8005


HOW TO GET THE COMPLETE PROJECT ON PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM INSTANTLY

  • Click on the Download Button above.
  • Select any option to get the complete project immediately.
  • Chat with Our Instant Help Desk on +234 813 292 6373 for further assistance.
  • All projects on our website are well researched by professionals with high level of professionalism.

Here's what our amazing customers are saying

Emmanuel Essential
Kogi state University
I actually took the risk,you know first time stuff But i was suprised i received as requested. I love you guys 🌟 🌟 🌟 🌟
Very Good
Abdul Mateen Iddrisu
UDS
At first I taught is a site full of fraudsters until I saw my project in my Gmail after my payment.. THANK YOU IPROJECTMASTER and May God the almighty bless u guys abundantly
Excellent
Adam Alhassan Yakubu
UDS
Excellent work and delivery , I promise to share my testimonies everyone in need of this kind of work. You're the best
Excellent
Merry From BSU
I am now a graduate because of iprojectmaster.com, God Bless you guys for me.
Excellent
Abubakar Iliyasu Hashim
Federal college of education pankshin affiliated to university of jos
I am highly impressed with your unquantifiable efforts for the leaners, more grace to your elbow.I will inform my colleagues about your website.
Very Good
MATTHEW NGBEDE
Ahmadu Bello University
I wish I knew you guys when I wrote my first degree project, it took so much time and effort then. Now, with just a click of a button, I got my complete project in less than 15 minutes. You guys are too amazing!
Excellent
Abdulrahman Jibrin
Nti Abaji
Nice one work prompt delivery tanx
Very Good
Gbadamosi Solomon Oluwabunmi
Lasu
Swift delivery within 9 minutes of payment. Thank you project master
Excellent
Uduak From Uniuyo
IProjectMaster is the best project site for students. Their works are unique and free of plagiarism!
Excellent
Joseph M. Yohanna
Thanks a lot, am really grateful and will surely tell my friends about your website.
Excellent

FREQUENTLY ASKED QUESTIONS

How do I get this complete project on PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM?

Simply click on the Download button above and follow the procedure stated.

I have a fresh topic that is not on your website. How do I go about it?

How fast can I get this complete project on PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM?

Within 15 minutes if you want this exact project topic without adjustment

Is it a complete research project or just materials?

It is a Complete Research Project i.e Chapters 1-5, Abstract, Table of Contents, Full References, Questionnaires / Secondary Data

What if I want to change the case study for PROCESS SCHEDULING IN LONGEST JOB FIRST(LJF) ALGORITHM: A PROPOSED FRAMEWORK FOR STARVATION PROBLEM, What do i do?

Chat with Our Instant Help Desk Now: +234 813 292 6373 and you will be responded to immediately

How will I get my complete project?

Your Complete Project Material will be sent to your Email Address in Ms Word document format

Can I get my Complete Project through WhatsApp?

Yes! We can send your Complete Research Project to your WhatsApp Number

What if my Project Supervisor made some changes to a topic i picked from your website?

Call Our Instant Help Desk Now: +234 813 292 6373 and you will be responded to immediately

Do you assist students with Assignment and Project Proposal?

Yes! Call Our Instant Help Desk Now: +234 813 292 6373 and you will be responded to immediately

What if i do not have any project topic idea at all?

Smiles! We've Got You Covered. Chat with us on WhatsApp Now to Get Instant Help: +234 813 292 6373

How can i trust this site?

We are well aware of fraudulent activities that have been happening on the internet. It is regrettable, but hopefully declining. However, we wish to reinstate to our esteemed clients that we are genuine and duly registered with the Corporate Affairs Commission as "PRIMEDGE TECHNOLOGY". This site runs on Secure Sockets Layer (SSL), therefore all transactions on this site are HIGHLY secure and safe!