Penjadwalan Proses

                                      DESKRIPSI PENJADWALAN PROSES

 Penjadwalan merupakan kumpulan kebijaksanaan dan  mekanisme di sistem operasi yang berkaitan dengan urutan kerja yang dilakukan sistem komputer.

Penjadwalan bertugas memutuskan hal-hal berikut:
1. Proses harus berjalan,
2. Kapan dan berapa lama proses itu berjalan.

Sasaran utama penjadwalan proses adalah optimasi kinerja sistem komputer menurut kriteria tertentu.

KRITERIA/TUJUAN PENJADWALAN PROSES

1. Adil (Fairness) adalah proses-proses diperlakukan sama yaitu mendapat jatah waktu layanan pemroses yang sama dan tidak ada proses yang tidak kebagian layanan pemroses.  

2. Efisiensi (Utilisasi) adalah pemroses yang dihitung dengan perbandingan (rasio) waktu sibuk pemroses dengan total waktu operasi sistem komputer.      

3. Waktu Tanggap (Response Time)
    -  Sistem Interaktif didefinisikan sebagai waktu yang dihabiskan dari saat katakter terakhir dari perintah dimasukkan oleh program sampai hasil pertama muncul diperangkat masukan keluaran seperti layar.
    -  Sistem waktu nyata didefinisikan sebagai waktu dari saat kemunculan suatu kejadian sampai instruksi pertama rutin layanan terhadap kejadian dieksekusi.

4. Turn Arround Time adalah waktu yang dihabiskan dari saat proses atau job mulai masuk kesistem sampai proses itu diselesaikan sistem. Waktu yang dimaksud adalah waktu yang dihabiskan proses berada disistem, diekspresikan sebagai penjumlahan waktu eksekusi dan waktu menunggu dari proses itu, yaitu:
Turn arround time = waktu eksekusi + waktu menunggu

5. Throughput adalah jumlah kerja yang dapat diselesaikan selama satu selang/unit waktu. Cara untuk mengekspresikan throughput adalah dengan jumlah proses/job pemakai yang dapat dieksekusi dalam satu unit/interval waktu tertentu.

TIPE-TIPE PENJADWALAN

1. Penjadwalan Jangka Pendek

Bertugas menjadwalkan alokasi pemroses di antara proses-proses ready di memori utama. Penjadwalan dijadwalkan setiap terjadi pengalihan proses untuk memilih proses berikutnya yang harus dijalankan.

2. Penjadwalan Jangka Menengah

Proses status ready - running - waiting - ready

3. Penjadwalan Jangka Panjang

Penjadwal ini bekerja terhadap antrian batch dan memilih batch berikutnya yang harus dieksekusi. Batch biasanya adalah proses - proses dengan penggunaan sumber daya yang intensif (yaitu waktu pemroses, memori, perangkat masukan/keluaran), program-program ini berprioritas rendah, digunakan sebagai pengisi (agar pemroses sibuk) selama periode aktivitas job - job interaktif rendah.

PENJADWALAN PROSES

3 istilah yang digunakan pada penjadwalan proses

1. Antrian

- Sejumlah proses yang menunggu menggunakan prosesor dan akan diproses sesuai dengan urutan antrian proses.

- Proses berada dalam memori utama.

2. Prioritas

Mendahului pada antrian proses, kalau proses itu berada di bagian belakang antrian, maka dengan pemberian prioritas, proses itu langsung berada dibagian paling depan pada antrian itu sambil menunggu sampai kerja prosesor selesai.

3. Prempsi

Mendahului pada antrian proses, kalau proses itu berada di bagian belakang antrian, maka dengan pemberian prempsi, proses itu langsung berada dibagian paling depan pada antrian itu bahkan akan memberhentikan kerja prosesor untuk mengerjakan proses yang prempsi tersebut.

PERHITUNGAN PADA KERJA PROSESOR

• Lama Proses (t) adalah lama waktu yang diperlukan untuk mengolah proses itu di dalam prosesor
• Lama Tanggap (T) adalah waktu yang diperlukan untuk proses sejak mulai sampai selesai diolah oleh prosesor.

Terdapat 2 macam lama tanggap :
- Turn around time, Dengan memperhitungkan lama waktu.
- Respon time, Tidak memperhitungkan lama waktu.

TEKNIK PENJADWALAN PROSESOR

1. Kategori penjadwalan prosesor
    - Tanpa prioritas tanpa prempsi

    - Dengan prioritas tanpa prempsi

    - Tanpa prioritas dengan prempsi

    - Dengan prioritas dengan prempsi

2. Teknik penjadwalan prosesor

    - Penjadwalan satu tingkat

    - Penjadwalan multi tingkat

3. Teknik penjadwalan satu tingkat.

 

RUMUS PENJADWALAN

•  Jika terdapat N proses serentak, serta setiap proses memiliki lama tanggap sebesar T, maka rerata lama tanggap Tr adalah :

          - Tr = (jumlah Ti)/N

• Waktu sia-sia (T - t), waktu yang terbuang dalam antrian atau selama terkena prempsi.
• Rasio tanggap (Rt), perbandingan di antara lama proses terhadap lama tanggap.
• Rasio pinalti (Rp), perbandingan diantara lama tanggap terhadap lama proses.

         - Rt = t/T dan

         - Rp = T/t

 

ALGORITMA PENJADWALAN PROSES

1. Algoritma First Come First Served (FCFS)/FIFO (First In First Out)
2. Algoritma PTD/SJF (Shortest Job First)
3. Algoritma PTDP (Penjadwalan proses terpendek dipertamakan prempsi)
4. Algoritma RPTD (Ratio penalti tertinggi dipertamakan)
5. Algoritma Roun Robin 

Penjelasan algoritma penjadwalan proses

1. Algoritma penjadwalan proses terpendek dipertamakan prempsi (PTDP/FCFS/FIFO)

Merupakan algoritma penjadwalan CPU yang paling sederhana. Proses yang tiba lebih dahulu akan dilayani lebih dahulu. Jika ada proses tiba pada waktu yang sama, maka pelayanan mereka dilaksanakan berdasarkan urutan  dalam antrian. Proses di antrian belakang harus menunggu sampai semua proses di depannya selesai.

 

Contoh :

Misalkan ada tigas proses P1,P2,P3 yang datang dengan lama waktu kerja CPU(CPU Waiting Time) masing-masing sebagai berikut :

Proses                        Waiting Time

   P1                                     24

   P2                                       3

   P3                                       3

Jika proses datang dengan urutan P1,P2,P3 dan dilayani dengan algoritma FIFO, maka dapat digambarkan Gantt Chart-nya :

 

• Dari Gantt Chart dapat diambil kesimpulan waktu tunggu untuk P1 adalah 0 milidetiktunggu  untuk P2 adalah 24 milidetik, waktu tunggu P3 adalah 27 milidetik.

• Jadi rata-rata waktu tunggu  (Average Waiting Time/AWT) adalah (0+24+27)/3 = 17 milidetik.  

• Kemudian jika waktu kedatangan proses adalah P3, P2, P1 maka Gantt Chartnya adalah

 

• Turn around time (waktu penyelesaian) P3 adalah 0, P2 = 3, P1=6, maka rata-rata turn around time = (0+3+6)/3 = 3 milidetik.

2. Algoritma PTD/SJF

Penjadwalan dengan prioritas tanpa prempsi, terdapat 2 langkah :

- Langkah I : tentukan urutan prioritas berdasarkan pendeknya proses yang dilayani

- Langkah II : penentuan proses mana yang dilayani oleh pemroses.

•  Setiap proses yang ada dalam ready queue akan dieksekusi berdasarkan burst time terkecil
• Hal ini mengakibatkan waiting time yang terpendek untuk setiap proses, maka rerata waiting time (AWT) juga menjadi pendek
• Algoritma ini dikatakan optimal.

contoh :

Nama Proses                     Waktu Tiba                  Lama Eksekusi

        A                                             0                                        10

        B                                             0                                          5

        C                                             0                                          7

        D                                             0                                          1

        E                                             0                                          3

Proses Lanjutan

 

Nama Proses                     Waktu Tiba                  Lama Eksekusi

        D                                             0                                          1

        E                                             0                                          3

        B                                             0                                          5

        C                                             0                                          7

        A                                             0                                         10

 

 

Proses Lanjutan

 

 

Nama         Waktu      Lama                  Mulai            Selesai              TA

Proses        Tiba       Eksekusi         Eksekusi       Eksekusi

     D                  0                1                         0                       1                       1

     E                   0               3                          1                      4                        4

     B                   0               5                          4                      9                       9

     C                   0               7                          9                    16                      16

     A                  0              10                         16                 26                       26

                                ∑TA = 56

                                 rata2 TA = 11,2

 Proses Lanjutan

Nama Proses                 Lama Eksekusi           Waktu Tiba

        D                                             1                                       0

        E                                             3                                        2

        B                                             5                                        5

        C                                             7                                        7

        A                                           10                                       9

 

Proses Lanjutan

Nama         Waktu      Lama                  Mulai            Selesai          Waktu         TA

Proses        Tiba       Eksekusi         Eksekusi       Eksekusi       Tunggu

     D                  0                1                         0                       1                      0                 1

     E                   2               3                          2                      5                       0                 3

     B                   5               5                          5                   10                       0                 5

     C                   7               7                          10                 17                      3               10

     A                  9              10                         17                 27                       8              18

                                                              ∑TA = 37

                                                                  Rerata = 7,4

3. Algoritma penjadwalan proses terpendek dipertamakan prempsi (PTDP/PSPN/SRT)

Penjadwalan dengan prioritas dengan prempsi beberapa ketentuan :

• Prioritas berdasarkan pendeknya sisa proses
• Diperhatikan saat proses tiba atau saat proses selesai
• Menghitung lama sisa proses dari semua proses yang ada
• Jika proses dengan sisa proses yang lebih pendek dari proses yang sedang dikerjakan, maka atas dasar prempsi proses yang sedang dikerjakan akan dikeluarkan dari prosesor.

contoh :

Nama Proses    Saat Tiba       Lama Proses

         A                           0                        7

         B                           2                        3

         C                           4                        9

         D                           5                        4

 

Barisan Proses :

                           A                B                  C           D

 

 Sisa                           A=5           A=5              A=5

 

                                    B=2           B=1              B=0

                                                       C=9              C=9

                                                       D=4

 

 

 

 

Tabel PTPD

 

 

 

 4. Algoritma Penjadwalan Ratio Pinalti Tertinggi Dipertamakan (RPTD/HPRN)

Penjadwalan dengan prioritas tanpa prempsi

ketentuan :

Prioritas berdasarkan besarnya nilai ratio pinalti

rumus ratio pinalti = Rp = (s + t)/t

    s = waktu sia-sia (saat selesai - saat tiba)

    t = lama proses

Tetap mendahulukan proses terpendek, namun prioritas proses panjang akan turut meningkat melalui peningkatan ratio pinaltinya.

 

contoh :

  

Step  1

 

PENJELASAN STEP 1

Pada saat 0 : hanya ada A, A diolah

Pada saat 4 : A rampung B,C,D,E telat tiba

 

Perhitungan Rasio Penalti  

       Proses         Tiba Selama          Rasio Penalti

           B                  4 - 1 = 3                 (3 + 2)/2 = 2,5

           C                  4 - 2 = 2                 (2 + 5)/5 = 1,2

           D                  4 - 3 = 1                 (1 + 8)/8 = 1.125

           E                  4 - 4 = 0                  (0 + 4)/4 = 1

 

 Ratio penalti tertinggi pada B, B diolah

Step 2

PENJELASAN STEP 2

Pada saat 6  :  A dan B telah rampung 

Perhitungan rasio penalti

           Proses        Tiba selama        Rasio penalti

     C              6 - 2 = 4            (4 + 5)/5 = 1,8

     D              6 - 3 = 3            (3 + 8)/8 = 1,375

     E              6 - 4 = 2            (2 + 4)/4 = 1,5

         

Rasio penalti tertinggi pada C, C diolah

Step 3

 

PENJELASAN STEP 3

 

Pada saat 11 :  A, B, dan C telah rampung

Perhitungan rasio penalti

     Proses          Tiba selama             Rasio penalti

          D               11 - 3 = 8               (8 + 8)/8 = 2

          E               11 - 4 = 7               (7 + 4)/4 = 2,75

          

Raio penalti tertinggi pada E, E diolah

Pada saat  15 : A, B, C, dan E telah rampung D diolah

Tabel RPTD/HPRN 

 

Barisan proses

 

   

 

5. Algoritma Penjadwalan Putar Gelang (Roun Robin/Time Slice)

Penjadwalan tanpa prioritas dengan prempsi

Beberapa ketentuan :

• Kuantum waktu, waktu yang digunakan oleh prosesor untuk melengkapi setiap proses
• Prosesor akan melayani setiap proses berdasarkan antrian
• Prosesor akan melayani sesuai dengan kuantum waktu yang sudah ditentukan.

contoh :

Tabel proses putar gelang

Kuantum 3

Penyelesaian Algoritma Roun Robin/Time Slice

 

 

Tabel putar gelang