SCHEDULING

Scheduling

Behaviour of Process

1. Process-bound : dilihat dari proses itu sendiri
2. I/O bound : dilihat dari input dan output

CPU Scheduler()

• Algoritma  scheduling:  Memilih dari proses-proses yang berada di memori (ready to execute) dan memberikan jatah CPU ke salah satu proses tersebut.
• CPU Scheduler berfungsi untuk menampilkan proses-proses didalam sebuah memori yang sudah siap untuk dieksekusi, dan dialokasikan ke dalam CPU.
• CPU scheduling mempunyai 4 keputusan :

1. berubah dari running ke waiting state
2. berubah dari running ke ready state
3. berubah dari waiting ke ready state
4. terminate/mengakhiri

• Scheduling nomor 1 dan 4 adalah non-preemptive
• Scheduling nomor 2 dan 3 adalah preemptive

Types of Scheduler

• Long-term scheduling -> Menyeleksi proses-proses mana yang harus dimasukkan ke dalam ready queue dan membawanya ke memori untuk dieksekusi .
• Medium-term scheduling -> Menentukan apakah menambah sebagian jumlah proses atau seluruhnya dalam memori utama
• Short-term -> Menentukan proses mana yang selanjutnya akan dieksekusi dan mengalokasikan CPU untuk proses tersebut, dimana pemilihan proses barunya dialokasikan sesering mungkin.
• I/O scheduling -> I/O device yang tersedia akan menghandle proses I/O yang tertunda

Dispatcher

Dispatcher mengatur dan memberikan kontrol CPU kepada proses yang dipilih oleh “short-term scheduler”. Dispatcher melibatkan :

• perubahan konteks
• perubahan ke mode user
• melompat ke lokasi yang salah dalam program user

Dispatcher latency adalah waktu yang dibutuhkan oleh dispatcher untuk menyelesaikan 1 proses dan memulai proses yang lainnya.

Scheduling Criteria :

• CPU utilization :  untuk menjaga agar CPU tetap dalam keadaan sibuk/bekerja (menggunakan CPU semaksimal mungkin).
• Throughput :  maksimalkan jumlah proses yang selesai dijalankan (per satuan waktu).
• Turnaround time : meminimalkan waktu selesai eksekusi suatu proses (sejak di submit sampai selesai).
• Waiting time : meminimalkan waktu tunggu proses  (jumlah waktu yang dihabiskan menunggu di ready queue).
• Response time :  meminimalkan waktu respon dari sistem terhadap user (interaktif, time-sharing system), sehingga interaksi dapat berlangsung dengan cepat.

Optimization Criteria :

• Max CPU utilization : Penggunaan CPU secara maksimal
• Max throughput : Penyelesaian jumlah proses yang maksimal
• Min turnaround time : Waktu yang diperlukan semakin cepat semakin baik
• Min waiting time : Waktu menunggu seminimal mungkin
• Min response time : Waktu untuk merespon secepat mungkin

Goal of Scheduling

1. All system
   – Fairness : mengatur proses dalam penggunaan bersama sumber daya CPU secara adil
   – Policy enforcement :  memastikan kebijakan yang diterapkan berjalan
   – Balance : menjaga semua bagian sistem dalam keadaan sibuk
2. Batch system
   – Throughput : memaksimalkan jumlah job per jam (jobs per hour)
   – Turn around time :  meminimalkan waktu dari mulai (submission) hingga berakhir (termination)
   – CPU utilization : mengupayakan CPU selalu sibuk sepanjang waktu
3. Interactive system
   – Response time : merespon permintaan (request) dengan cepat
   – Proportionallity : memenuhi harapan pengguna (user’s expectation)
4. Real time system
   – Meeting deadlines : menghindari kehilangan data
   – Predictability : menghindari penurunan kualitas dalam sistem multimedia

Batch Scheduling Algorithms

Ada beberapa metode dalam scheduling :

1.  First-Come First-Serve
Proses diassign ke dalam CPU secara urut.

Keuntungan : Mudah dimengerti dan mudah diprogram

Kelemahan  : Pekerjaan yang lebih singkat tetap harus menunggu meskipun ada pekerjaan yang lebih lama berada di depannya

.

2.  Shortest Job First

Pekerjaan yang lebih ringan akan dikerjakan terlebih dahulu.

Shortest Job First mempunyai 2 skema yaitu Preemptive  dan Non Preemptive.

• Non preemptive :  saat CPU diberi proses maka harus menunggu proses tersebut sampai selesai terlebih dahulu.
• Preemptive : Jika ada proses baru yang datang dengan jumlah CPU burst time nya lebih sedikit dibandingkan dengan sisa CPU burst time proses yang sedang berjalan maka proses yang baru datang tersebut dapat dijalankan terlebih dahulu. Skema ini juga dikenal sebagai Shortest-Remaining-Time-First (SRTF).

– Shortest Job First – Non Preemptive

– Shortest Job First – Preemptive

Contoh soal :

Tugas dari Buku Operating Systems: Internals and Design Principles: International Edition,7th Edition Halaman 447 nomor 9.2

Process	Arrival Time	Processsing Time
A	0	3
B	1	5
C	3	2
D	9	5
E	12	5

Jawab :

1. First-Come First-Serve

Seperti yang telah dijelaskan diatas, FCFS menggunakan prinsip FIFO yaitu First In First Out.

Waktu menunggu A = 0 detik karena tidak ada proses yang berjalan sebelumnya pada saat proses A datang oleh karena itu proses A bisa langsung dikerjakan.

Waktu menunggu B = 2 detik karena arrival time proses B=1 sedangkan proses A baru selesai pada detik ke 3. Jadi waktu menunggunya adalah 3-1=2.

Waktu menunggu C = 5 detik karena arrival time proses C=3 sedangkan proses B baru selesai pada detik ke 8. Jadi waktu menunggunya adalah 8-3=5.

Waktu menunggu D = 1 detik karena arrival time proses D=9 sedangkan proses C baru selesai pada detik ke 10. Jadi waktu menunggunya adalah 10-9=1.

Waktu menunggu E = 3 detik karena arrival time proses E=12 sedangkan proses D baru selesai pada detik ke 15. Jadi waktu menunggunya adalah 15-12=3.

Jadi ..

Waktu menunggu untuk A=0, B=2, C=5, D=1, E=3

Rata-rata waktu menunggu = (0+2+5+1+3)/5 = 2,2 detik

2. Shortest Job First – Non Preemptive

Pada Non Preemptive proses yang waktu pengerjaanya lebih cepat bisa dikerjakan terlebih dahulu dengan catatan proses yang sebelumnya harus diselesaikan terlebih dahulu.

Seperti biasa proses A dijalankan terlebih dahulu karena tidak ada proses yang berjalan sebelumnya dan waktu menunggunya adalah 0 detik.

Nah sekarang proses yang dijalankan selanjutnya adalah proses C. kenapa tidak proses B terlebih dahulu? bukannya proses B yang datang lebih dulu dibandingkan proses C? Seperti yang telah dijelaskan sebelumnya proses yang waktu pengerjaannya lebih cepat maka dijalankan terlebih dahulu. Proses C memiliki processing tme = 2 , sedangkan proses B memiliki processing time = 5. Jadi waktu menunggu proses c adalah 0 karena saat datang langsung dikerjakan.

Proses selanjutnya adalah B. Mengapa harus B? padahal proses B,D dan E memiliki processing time yang sama? alasannya adalah karena proses B datang terlebih dahulu, selanjutnya baru proses D dan E yang dijalankan.

Waktu menunggu proses B = 4, karena proses B baru dijalankan pada detik ke 5 sedangkan proses B datang pada detik ke 1. Jadi 5-1=4 detik.

Waktu menunggu proses D = 1, karena proses D baru dijalankan pada detik ke 10 sedangkan proses D datang pada detik ke 9. Jadi 10-9=1 detik

Waktu menunggu proses E = 1, karena proses D baru dijalankan pada detik ke 15 sedangkan proses D datang pada detik ke 12. Jadi 15-12=3 detik

Waktu menunggu untuk A=0, B=4, C=0, D=1, E=3

Rata-rata waktu menunggu = (0+4+0+1+3)/5 = 1,6 detik

3. Shortest Job First – Preemptive

Kebetulan jawaban Preempive pada soal ini sama persis dengan jawaban non-preemptive, namun secara teknik pengerjaan tentu ada yang berbeda. Yang membedakan adalah pada preemptive kita bisa menghentikan proses yang sedang berjalan jika ada proses yang datang pada waktu tersebut dengan processing time yang lebih rendah.

Misalnya pada detik ke 0 datang proses A dengan processing time 4, lalu pada detik ke 2 ada proses C datang dengan processing time 1, yang dilakukan pada preemptive ini adalah menjalankan proses C terlebih dahulu dengan kata lain proses A di delay waktu pengerjaannya. Setelah proses C selesai pada detik ke 3 maka proses A bisa dilanjutkan kembali dengan waktu menunggunya adalah 1 detik (3-2=1). Namun jika ada proses baru lagi yang datang dengan processing time nya lebih rendah dari A , maka proses A bisa tertunda lagi sampai proses tersebut selesai dijalankan. Begitu juga dengan proses-prosess selanjutnya.

Jadi untuk jawaban preemptive adalah :

Waktu menunggu untuk A=0, B=4, C=0, D=1, E=3

Rata-rata waktu menunggu = (0+4+0+1+3)/5 = 1,6 detik

THREAD

THREAD

            Thread merupakan bagian dari proses, dimana proses sendirir adalah program yang sedang dieksekusi, ada dua jenis proses, pertama heavyweight  dan ada lightweight atau dikenal juga sebagai thread.

Thread adalah unit dasar dari utilisasi CPU. Di dalamnya terdapat ID thread, program counter, register, dan stack. Dan saling berbagi dengan thread lain dalam proses yang sama. Dengan banyak kontrol thread proses dapat melakukan lebih dari satu pekerjaan pada waktu yang sama.

THREAD MODEL

 Kolom pertama berisi beberapa item bersama oleh semua thread dalam proses . Yang kedua berisi beberapa item pribadi ke setiap thread .

 

Setiap thread memiliki stack masing masing

KEUNTUNGAN THREAD

1.      Tanggap: Multithreading mengizinkan program untuk berjalan terus walau pun pada bagian program tersebut di block atau sedang dalam keadaan menjalankan operasi yang lama/ panjang. Sebagai contoh, multithread web browser dapat mengizinkan pengguna berinteraksi dengan suatu thread ketika suatu gambar sedang diload oleh thread yang lain.

2.      Pembagian sumber daya: Secara default, thread membagi memori dan sumber daya dari proses. Keuntungan dari pembagian kode adalah aplikasi mempunyai perbedaan aktifitas thread dengan alokasi memori yang sama.

3.      Ekonomis: Mengalokasikan memori dan sumber daya untuk membuat proses adalah sangat mahal. Alternatifnya, karena thread membagi sumber daya dari proses, ini lebih ekonomis untuk membuat threads.

4.      Pemberdayaan arsitektur multiprosesor: Keuntungann dari multithreading dapat ditingkatkan dengan arsitektur multiprosesor, dimana setiap thread dapat jalan secara parallel pada prosesor yang berbeda. Pada arsitektur prosesor tunggal, CPU biasanya berpindah-pindah antara setiap thread dengan cepat, sehingga terdapat ilusi paralelisme, tetapi pada kenyataannya hanya satu thread yang berjalan di setiap waktu.

IMPLEMENTASI THREAD
Implementasi thread terdiri dari 3 jenis:

1.      User

1. Pelaksanaan manajemen thread yang dilakukan oleh user-level thread library. Terdapat dua kelompok besar implementasi thread, yaitu user-level thread dan kernel-level thread. Didalam fasilitas user-level thread yang murni, semua tugas manajemen thread dilakukan oleh aplikasi dan kernel tidak mengetahui keberadaan thread.

2. Tiga kunci thread libraries :

·         POSIX Pthread

·         Win32 thread

·         Java thread

2.      Kernel

1. Suatu proses thread Yyang didukung oleh kernel. Untuk memberitahu kejadian kernel, kernel menciptakan scheduler activatioan baru, memberikan ke pemroses dan melakukan upcall ke ruang pemakai.

2. Contoh :

·         Windows XP/2000

·         Solaris

·         Linux

·          Tru64 UNIX

·         Mac OS X

3.      Hybrid

Merupakan gabungan user dan kernel

Multiplexing user-level threads onto kernel- level threads

HUBUNGAN THREAD DAN PROSES

Secara informal, proses adalah program yang sedang dieksekusi. Ada dua jenis proses, proses berat (heavyweight) atau biasa dikenal dengan proses tradisional, dan proses ringan atau kadang disebut thread.

Thread saling berbagi bagian program, bagian data dan sumber daya sistem operasi dengan thread lain yang mengacu pada proses yang sama. Thread terdiri atas ID thread, program counter, himpunan register, dan stack. Dengan banyak kontrol thread proses dapat melakukan lebih dari satu pekerjaan pada waktu yang sama.

SISTEM OPERASI - PROSES

PROCESS

Proses adalah keadaan ketika sebuah program sedang di eksekusi. Saat komputer berjalan, terdapat banyak proses yang berjalan secara bersamaan. Sebuah proses dibuat melalui system call create-process yang membentuk proses turunan ( child process) yang dilakukan oleh proses induk ( parent process). Proses turunan tersebut juga mampu membuat proses baru sehingga semua proses ini pada akhirnya membentuk pohon proses.

KARAKTERISTIK PROSES

•       Identifier: identifier unik yang berguna untuk membedakan proses satu dan yang lainnya.

•       State: proses yang sedang mengeksekusi berada di state yang berjalan.

•       Priority: tingkat prioritas relative terhadap proses lainya.

•       Program counter: alamat dari instruksi berikutnya ada di program yang dieksekusi.

•       Memory pointers: termasuk pointer ke program code dan data yang berhubungan dengan proses ini dan semua blok memoriyang dibagi dengan proses lain

•       Context data: data yang ada di registry di dalam proses saat eksekusi.

•       I/O status information:  outstanding I/O requests, I/O devices (e.g., disk drives)  ditugaskan untuk proses ini, listdari file yang digunakan oleh proses.

•       Accounting information: jumlah processor time dan clock time yang digunakan, time limits, account numbers, dan lainya.

TERBENTUKNYA PROSES

·         Menentukan identifier yang unik

·         Mengalokasikan space untuk proses

·         Inisialisasi proses control block

·         Mengatur link yang tepat

·         Membuat perluasan strktur data lainya

YANG DAPAT MENGHENTIKAN PROSES

·         Penghentian yang normal

·         Melampau batas waktu

·         Memori tidak tersedia

·         Bounds violation

·         Protection error (ex: write pada file read only)

·         Arithmetic error

·         Time overrun (proses menunggu terlalu lama)

·         I/O failure

·         Instruksi yang salah (terjadi ketika mengeksekusi data)

·         Privileged instruction

·         Penyalahgunaan data

·         Intervensi os (seperti ketika terjadi deadlock)

·         Parent terhenti sehingga child juga

·         Permintaan parent

PROCESS TABLE

·         Diimana lokasi sebuah proses

·         Atribut yang penting untuk managemenproses:

o   Proses ID

o   Proses State

o   Lokasi di memori

PROCESS LOCATION

·         Proses termasuk program yang akan dieksekusi

o   Lokasi data untuk local dan global variable

o   Konstanta didefinisikan

o   Stack

·         Process control block

o   Kumpulan atribut

·         Process image

o   Kumpulan program, data, stack dan atribut

FIVE STATE PROCESS MODEL 

ALASAN PROSES SWITCH

·         Clock interrupt

o   Proses yang dieksekusi mencapai batas maksimum pada suatu waktu

·         I/O interrupt

·         Kesalahan memori

o   Alamat memori ada di virtual memori jadi harus dibawa ke main memori

·         Trap

o   Terdapat error

o   Menyebabkan proses memasuki state “exit”

·         Supervisor call

o   Seperti file yang terbuka

SUSPENDED PROOCESS

·         Proses lebih cepat daripada I/) sehingga semua proses harus menunggu I/O.

·         Menukar proses ke disk  untuk membebaskan memori

·         Blocked state menjadi suspend state ketika swap ke disk

·         Dua state baru

o   Blocked, suspend

o   Ready, suspend

PENYEBAB PROCESS SUSPENSION

MODE EKSEKUSI

·         User mode

o   Less privileged mode

o   User program biasanya di eksekusi di mode ini

·         System mode, control mode, atau kernel mode

o   More privileged mode

o   Kernel of the operating system

SYSTEM CALL

Layanan langsung sistem operasi ke pemrograman, disebut dengan system call. System call adalah tata cara pemanggilan di program aplikasi untuk memperoleh layanan yang disediakan oleh sistem operasi. Contoh yang paling baik untuk melihat bagaimana system call bekerja untuk manajemen proses adalah Fork.

FORK

 Fork adalah satu satunya cara untuk membuat sebuah proses baru pada sistem Unix. Fork membuat duplikasi yang mirip dengan proses aslinya. Setelah perintah Fork, child akan mengeksekusi kode yang berbeda dengan parentnya.

•       Ketika fork()di eksekusi ,ia membuat Salinan  identic dari alamat

•       Kedua proses mulai dieksekusi

•       Parent dan child berjalan secara  independent

SYSTEM

·         Mengeksekusi  perintah dari dalam program

·         Sebanyak jika perintah itu telah diketik ke shell

·         Membuat subproses menjalankan standard bourne shell

·         (/ bin / sh) dan tangan perintah ke shell bahwa untuk

·         eksekusi; tunduk pada fitur, keterbatasan dan keamanan

·         shell; pada kebanyakan sistem GNU / Linux, menunjuk untuk bash

EXEC

·         Memanggil salah satu exec() akan menghentikan program yang sedang berlangsung dan mulai mengeksekusi yang baru:

o   int execl( const char *path, const char *arg, ...);

o   int execv( const char *path, char *const argv[]);

o    int execle( const char *path, const char *arg , ..., char * const envp[]);

o   int execlp( const char *file, const char *arg, ...);

o   int execvp( const char *file, char *const argv[]);

·         Proses ID tidak berubah

OTHER SYSTEM CALL

·         Exit()

o   Menghntikan proses secara normal

o   Unblock waiting parent

·         Wait()

o   Digunakan oleh parent

o   Ditunggu oleh child untuk menyelesaikan eksekusi

·         Getpid()

o   Mengembalikan identifier calling process

·         Getppid()

o   Mengembalikan identifier parent