{"id":63,"date":"2025-01-08T03:42:23","date_gmt":"2025-01-08T03:42:23","guid":{"rendered":"https:\/\/mitalgoswami.in\/?p=63"},"modified":"2025-12-06T07:02:15","modified_gmt":"2025-12-06T07:02:15","slug":"sjf-algorithm","status":"publish","type":"post","link":"https:\/\/mitalgoswami.in\/?p=63","title":{"rendered":"SJF (algorithm)"},"content":{"rendered":"\n

Example of Non-Preemptive SJF<\/strong><\/h3>\n\n\n\n

Given Processes:<\/h4>\n\n\n\n
Process<\/th>Arrival Time<\/th>Burst Time<\/th><\/tr><\/thead>
P1<\/td>0<\/td>7<\/td><\/tr>
P2<\/td>2<\/td>4<\/td><\/tr>
P3<\/td>4<\/td>1<\/td><\/tr>
P4<\/td>5<\/td>4<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
\n\n\n\n

Step 1: Order of Execution<\/h4>\n\n\n\n
    \n
  • At time t=0<\/code>, only P1<\/strong> is available, so it starts execution.<\/li>\n\n\n\n
  • At time t=2<\/code>, P2<\/strong> arrives, but P1<\/strong> continues execution because this is non-preemptive SJF.<\/li>\n\n\n\n
  • At time t=4<\/code>, P3<\/strong> arrives, and after P1<\/strong> completes, P3<\/strong> (shortest burst time) is executed.<\/li>\n\n\n\n
  • At time t=5<\/code>, P4<\/strong> arrives, and P2<\/strong> is scheduled next after P3<\/strong>.<\/li>\n<\/ul>\n\n\n\n
    \n\n\n\n

    Gantt Chart:<\/h4>\n\n\n\n
    Time<\/th>0 – 7<\/th>7 – 8<\/th>8 – 12<\/th>12 – 16<\/th><\/tr><\/thead>
    P<\/td>P1<\/td>P3<\/td>P2<\/td>P4<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    \n\n\n\n

    Step 2: Calculations<\/h4>\n\n\n\n

    Turnaround Time (TAT)<\/strong> = Completion Time – Arrival Time
    Waiting Time (WT)<\/strong> = Turnaround Time – Burst Time<\/p>\n\n\n\n

    Process<\/th>Arrival Time<\/th>Burst Time<\/th>Completion Time<\/th>TAT<\/th>WT<\/th><\/tr><\/thead>
    P1<\/td>0<\/td>7<\/td>7<\/td>7<\/td>0<\/td><\/tr>
    P2<\/td>2<\/td>4<\/td>12<\/td>10<\/td>6<\/td><\/tr>
    P3<\/td>4<\/td>1<\/td>8<\/td>4<\/td>3<\/td><\/tr>
    P4<\/td>5<\/td>4<\/td>16<\/td>11<\/td>7<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
    \n\n\n\n

    Step 3: Averages<\/h4>\n\n\n\n
      \n
    • Average Turnaround Time (TAT)<\/strong> = 7+10+4+114=8\\frac{7 + 10 + 4 + 11}{4} = 847+10+4+11\u200b=8<\/li>\n\n\n\n
    • Average Waiting Time (WT)<\/strong> = 0+6+3+74=4\\frac{0 + 6 + 3 + 7}{4} = 440+6+3+7\u200b=4<\/li>\n<\/ul>\n\n\n\n
      \n\n\n\n

      Advantages of SJF<\/strong><\/h3>\n\n\n\n
        \n
      1. Minimizes average waiting time.<\/li>\n\n\n\n
      2. Optimal for systems where short tasks dominate.<\/li>\n<\/ol>\n\n\n\n

        Disadvantages of SJF<\/strong><\/h3>\n\n\n\n
          \n
        1. Difficult to predict the exact burst time of a process.<\/li>\n\n\n\n
        2. Starvation of longer processes if shorter ones keep arriving.<\/li>\n<\/ol>\n\n\n\n

          Example -2:<\/strong>Below is the full solution for SJF (Shortest Job First) Non-Preemptive<\/strong> scheduling for the given processes.<\/p>\n\n\n\n

          \n\n\n\n

          Given Processes<\/strong><\/h1>\n\n\n\n
          Process<\/th>Arrival Time<\/th>Burst Time<\/th><\/tr><\/thead>
          P1<\/strong><\/td>0<\/td>5<\/td><\/tr>
          P2<\/strong><\/td>2<\/td>3<\/td><\/tr>
          P3<\/strong><\/td>3<\/td>2<\/td><\/tr>
          P4<\/strong><\/td>1<\/td>3<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
          \n\n\n\n

          SJF (Non-Preemptive) Scheduling<\/strong><\/h1>\n\n\n\n

          Step 1: Sort by arrival, choose shortest burst among available processes<\/strong><\/h3>\n\n\n\n

          Timeline Execution<\/strong><\/h3>\n\n\n\n

          At time = 0<\/strong><\/h3>\n\n\n\n

          Available: P1
          \u2192 Run P1<\/strong> (burst 5) until completion (non-preemptive)<\/p>\n\n\n\n

          P1 runs from 0 \u2192 5<\/strong><\/p>\n\n\n\n

          At time = 5<\/strong><\/h3>\n\n\n\n

          Now available: P2 (3), P3 (2), P4 (3)
          Shortest = P3<\/strong><\/p>\n\n\n\n

          P3 runs from 5 \u2192 7<\/strong><\/p>\n\n\n\n

          At time = 7<\/strong><\/h3>\n\n\n\n

          Remaining: P2 (3), P4 (3)
          Tie \u2192 choose the one that arrived first \u2192 P4<\/strong><\/p>\n\n\n\n

          P4 runs from 7 \u2192 10<\/strong><\/p>\n\n\n\n

          At time = 10<\/strong><\/h3>\n\n\n\n

          Last: P2 (3)<\/p>\n\n\n\n

          P2 runs from 10 \u2192 13<\/strong><\/p>\n\n\n\n

          \n\n\n\n

          Gantt Chart<\/strong><\/h1>\n\n\n\n
          |  P1  | P3 |  P4  |  P2  |\n0      5    7     10     13\n<\/code><\/pre>\n\n\n\n
          \n\n\n\n
          Completion, Turnaround, and Waiting Times<\/strong><\/h1>\n\n\n\n
          Process<\/th>AT<\/th>BT<\/th>CT<\/th>TAT = CT-AT<\/th>WT = TAT-BT<\/th><\/tr><\/thead>
          P1<\/strong><\/td>0<\/td>5<\/td>5<\/td>5<\/td>0<\/td><\/tr>
          P3<\/strong><\/td>3<\/td>2<\/td>7<\/td>4<\/td>2<\/td><\/tr>
          P4<\/strong><\/td>1<\/td>3<\/td>10<\/td>9<\/td>6<\/td><\/tr>
          P2<\/strong><\/td>2<\/td>3<\/td>13<\/td>11<\/td>8<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n
          \n\n\n\n
           Average Times<\/strong><\/h1>\n\n\n\n
          Average Turnaround Time<\/strong><\/h3>\n\n\n\n
          5+4+9+11\/=4  29\/4 \u200b<\/p>\n\n\n\n
          =7.25\u00a0ms<\/p>\n\n\n\n
          Average Waiting Time<\/strong><\/h3>\n\n\n\n
          0+2+6+8\/4=16\/4= 4 ms<\/p>\n\n\n\n
          \n\n\n\n
          \u2705 Final Answer Summary<\/strong><\/h1>\n\n\n\n
          Gantt Chart:<\/strong><\/h3>\n\n\n\n
          0\u20135(P1), 5\u20137(P3), 7\u201310(P4), 10\u201313(P2)<\/code><\/p>\n\n\n\n
          Average Waiting Time = 4 ms<\/strong><\/h3>\n\n\n\n
          Average Turnaround Time = 7.25 ms<\/strong><\/h3>\n","protected":false},"excerpt":{"rendered":"
          Example of Non-Preemptive SJF Given Processes: Process Arrival Time Burst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 Step 1: Order of Execution Gantt Chart: Time 0 – 7 7 – 8 8 – 12 12 – 16 P P1 P3 P2 P4 Step 2: Calculations Turnaround Time (TAT) = […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[],"class_list":["post-63","post","type-post","status-publish","format-standard","hentry","category-unix"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/posts\/63","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=63"}],"version-history":[{"count":2,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/posts\/63\/revisions"}],"predecessor-version":[{"id":353,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=\/wp\/v2\/posts\/63\/revisions\/353"}],"wp:attachment":[{"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=63"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=63"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mitalgoswami.in\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=63"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}