{"id":100383,"date":"2021-09-09T09:00:31","date_gmt":"2021-09-09T03:30:31","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=100383"},"modified":"2021-09-09T11:01:25","modified_gmt":"2021-09-09T05:31:25","slug":"shortest-job-first-sjf-scheduling-in-operating-system","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/","title":{"rendered":"Shortest Job First (SJF) Scheduling in Operating System"},"content":{"rendered":"

In case of Shortest Job First scheduling algorithm, the process with the smallest execution time gets executed next. Shortest Job First (SJF) reduces the average waiting time for other processes significantly.<\/p>\n

Types of Shortest Job First Algorithms<\/h3>\n

Following are the two types of SJF algorithms:<\/p>\n

1. Non-preemptive:<\/strong> The CPU is held by a process until the process reaches the waiting state or terminates.<\/p>\n

EXAMPLE:<\/strong> Consider the following five processes:<\/p>\n\n\n\n\n\n\n\n\n
Process Queue<\/b><\/td>\nBurst Time<\/b><\/td>\nArrival Time<\/b><\/td>\n<\/tr>\n
P1<\/span><\/td>\n6<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n
P2<\/span><\/td>\n2<\/span><\/td>\n3<\/span><\/td>\n<\/tr>\n
P3<\/span><\/td>\n2<\/span><\/td>\n0<\/span><\/td>\n<\/tr>\n
P4<\/span><\/td>\n5<\/span><\/td>\n4<\/span><\/td>\n<\/tr>\n
P5<\/span><\/td>\n8<\/span><\/td>\n4<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Step 1:<\/strong> At time = 0, P4 arrives and starts executing.<\/p>\n

Step 2:<\/strong> At time = 1, process P3 arrives in the waiting queue but P4 continues executing as it only needs to complete 2 units.<\/p>\n

Step 3:<\/strong> At time = 2, P1 arrives in the waiting queue and P4 continues executing.<\/p>\n

Step 4:<\/strong> At time = 3, P4 finishes executing and P1 starts executing as it has the least burst time.<\/p>\n

Step 5:<\/strong> At time = 4, P5 arrives in the waiting queue while P1 executes.<\/p>\n

Step 6:<\/strong> At time = 5, process P2 arrives and enters the waiting queue. P1 will continue execution.<\/p>\n

Step 7:<\/strong> At time = 9, P1 finishes execution and after comparing the burst time of P3, P5, and P2, P2 with the least burst time starts executing.<\/p>\n

Step 8:<\/strong> At time = 10, P2 continues executing while P3 and P5 are in the waiting queue.<\/p>\n

Step 9:<\/strong> At time = 11, P2 finishes execution, and P5 starts executing.<\/p>\n

Step 10:<\/strong> At time = 15, P5 finishes execution.<\/p>\n

Step 11:<\/strong> At time = 23, P3 finishes execution.<\/p>\n

Step 12:<\/strong> The average waiting time is:
\nP4 = 0 – 0 = 0
\nP1 = 3 – 2 = 1
\nP2 = 9 – 5 = 4
\nP5 = 11 – 4 = 7
\nP3 = 15 – 1 = 14<\/p>\n

Thus, the average waiting time is: (0 + 1 + 4 + 7 + 14)\/5 = 26\/5 = 5.2<\/p>\n

2. Preemptive:<\/strong> Jobs first enter the ready queue as they come. Then the process with the shortest burst time starts executing. The running process enters a waiting state when a process with shorter burst time than the one currently running arrives. It replaces the running process and starts executing.<\/p>\n

EXAMPLE:<\/strong> Consider the following five processes:<\/p>\n\n\n\n\n\n\n\n\n
Process Queue<\/b><\/td>\nBurst Time<\/b><\/td>\nArrival Time<\/b><\/td>\n<\/tr>\n
P1<\/span><\/td>\n6<\/span><\/td>\n2<\/span><\/td>\n<\/tr>\n
P2<\/span><\/td>\n2<\/span><\/td>\n5<\/span><\/td>\n<\/tr>\n
P3<\/span><\/td>\n8<\/span><\/td>\n1<\/span><\/td>\n<\/tr>\n
P4<\/span><\/td>\n3<\/span><\/td>\n0<\/span><\/td>\n<\/tr>\n
P5<\/span><\/td>\n4<\/span><\/td>\n4<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Step 1:<\/strong> At time = 0, P4 arrives and starts executing.<\/p>\n

Step 2:<\/strong> At time = 1, P3 arrives but P4 continues executing as it has a shorter burst time.<\/p>\n

Step 3:<\/strong> At time = 2, P1 arrives but P4 continues executing as it has a shorter burst time.<\/p>\n

Step 4:<\/strong> At time = 3, P4 finishes execution. After comparing the burst time of P3 and P1, P1 starts executing.<\/p>\n

Step 5:<\/strong> At time = 4, P5 arrives and starts executing as it has the lowest burst time amongst all the processes. P1 preempts.<\/p>\n

Step 6:<\/strong> At time = 5, P2 arrives and starts executing as it has the lowest burst time amongst all the processes. P5 preempts.<\/p>\n

Step 7:<\/strong> At time = 6, P2 is executing.<\/p>\n

Step 8:<\/strong> At time = 7, P2 finishes execution. After comparing the burst time of P1, P3, and P5, P5 resumes execution.<\/p>\n

Step 9:<\/strong> At time = 10, P5 finishes execution. After comparing the burst time of P1 and P3, P1 starts executing.<\/p>\n

Step 10:<\/strong> At time = 15, P1 finishes execution, and P3 starts executing.<\/p>\n

Step 11:<\/strong> At time = 23, P3 finishes execution.<\/p>\n

Step 12:<\/strong> The average waiting time is:
\nP4 = 0 – 0 = 0
\nP1 = 3 – 2 + 6 = 7
\nP2 = 5 – 5 = 0
\nP5 = 4 – 4 + 2 = 2
\nP3 = 15 – 1 = 14
\nThe average waiting time is: (0 + 7 + 0 + 2 + 14)\/5 = 23\/5 = 4.6<\/p>\n

Characteristics of SJF Scheduling<\/h3>\n

Following are some characteristics of SJF:<\/p>\n

    \n
  • Associated with every job as it requires a unit of time for a job to complete.<\/li>\n
  • Helpful for batch-type processing.<\/li>\n
  • Improves process throughput as shorter jobs execute first, further reducing the turnaround time.<\/li>\n
  • Offers shorter jobs that improve job output.<\/li>\n<\/ul>\n

    Advantages of SJF<\/h3>\n

    Following are the advantages of SJF:<\/p>\n

      \n
    • Used for long-term scheduling.<\/li>\n
    • Reduces average waiting time.<\/li>\n
    • Helpful for batch-type processing where runtimes are known in advance.<\/li>\n
    • For long-term scheduling, we can obtain a burst time estimate from the job description.<\/li>\n
    • It is necessary to predict the value of the next burst time for Short-Term Scheduling.<\/li>\n
    • Optimal with regard to average turnaround time.<\/li>\n<\/ul>\n

      Disadvantages of SJF<\/h3>\n

      Following are the disadvantages of SJF:<\/p>\n

        \n
      • It is necessary to know the job completion time beforehand as it is hard to predict.<\/li>\n
      • Used for long-term scheduling in a batch system.<\/li>\n
      • Can\u2019t implement this algorithm for CPU scheduling for the short term as we can\u2019t predict the length of the upcoming CPU burst.<\/li>\n
      • Cause extremely long turnaround times or starvation.<\/li>\n
      • Knowledge about the runtime length of a process is necessary.<\/li>\n
      • The length of the upcoming CPU request is hard to predict.<\/li>\n
      • Recording the elapsed time results in increased overhead on the processor.<\/li>\n<\/ul>\n

        Summary<\/h3>\n

        In case of Shortest Job First scheduling algorithm, the process with the smallest execution time gets executed next. There are two types of SJF: preemptive and non-preemptive. IT offers shorter jobs, this can improve job output. It is a greedy algorithm that can cause starvation if only shorter jobs keep executing.<\/p>\n","protected":false},"excerpt":{"rendered":"

        In case of Shortest Job First scheduling algorithm, the process with the smallest execution time gets executed next. Shortest Job First (SJF) reduces the average waiting time for other processes significantly. Types of Shortest...<\/p>\n","protected":false},"author":1,"featured_media":100536,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24565],"tags":[25056,25055,25057,25052,25054,25053],"class_list":["post-100383","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-operating-system-tutorials","tag-advantages-of-sjf","tag-characteristics-of-sjf","tag-disadvantages-of-sjf","tag-shortest-job-first","tag-shortest-job-first-in-os","tag-shortest-job-first-scheduling"],"yoast_head":"\nShortest Job First (SJF) Scheduling in Operating System - DataFlair<\/title>\n<meta name=\"description\" content=\"Learn about shortest job first scheduling algorithm in OS, its types - Preemptive & non-preemptive, features, advantages, disadvantages etc.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Shortest Job First (SJF) Scheduling in Operating System - DataFlair\" \/>\n<meta property=\"og:description\" content=\"Learn about shortest job first scheduling algorithm in OS, its types - Preemptive & non-preemptive, features, advantages, disadvantages etc.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-09-09T03:30:31+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2021-09-09T05:31:25+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"4 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Shortest Job First (SJF) Scheduling in Operating System - DataFlair","description":"Learn about shortest job first scheduling algorithm in OS, its types - Preemptive & non-preemptive, features, advantages, disadvantages etc.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/","og_locale":"en_US","og_type":"article","og_title":"Shortest Job First (SJF) Scheduling in Operating System - DataFlair","og_description":"Learn about shortest job first scheduling algorithm in OS, its types - Preemptive & non-preemptive, features, advantages, disadvantages etc.","og_url":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-09-09T03:30:31+00:00","article_modified_time":"2021-09-09T05:31:25+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"Shortest Job First (SJF) Scheduling in Operating System","datePublished":"2021-09-09T03:30:31+00:00","dateModified":"2021-09-09T05:31:25+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/"},"wordCount":763,"commentCount":1,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg","keywords":["Advantages of SJF","Characteristics of SJF","Disadvantages of SJF","Shortest Job First","Shortest Job First in OS","Shortest Job First scheduling"],"articleSection":["Operating System Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/","url":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/","name":"Shortest Job First (SJF) Scheduling in Operating System - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg","datePublished":"2021-09-09T03:30:31+00:00","dateModified":"2021-09-09T05:31:25+00:00","description":"Learn about shortest job first scheduling algorithm in OS, its types - Preemptive & non-preemptive, features, advantages, disadvantages etc.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/09\/Shortest-Job-First-scheduling-algorithm.jpg","width":1200,"height":628,"caption":"Shortest Job First scheduling algorithm"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/shortest-job-first-sjf-scheduling-in-operating-system\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Operating System Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/operating-system-tutorials\/"},{"@type":"ListItem","position":3,"name":"Shortest Job First (SJF) Scheduling in Operating System"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100383","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=100383"}],"version-history":[{"count":2,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100383\/revisions"}],"predecessor-version":[{"id":100537,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/100383\/revisions\/100537"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/100536"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=100383"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=100383"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=100383"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}