Scheduling

Scheduling adalah Penjadwalan. dimna Penjadwalan yang dimaksud disini adalah proses yang sudah diatur dengan ketentuannya di sebuah sistem operasi agar tidak terjadi suatu tabrakan dengan proses yang lain. Dengan adanya penjadwalan dapat ditentukan proses itu mulai bekerja kapan dan harus berhenti kapan. Sasaran utamanya:

• Adil

dimana semua proses dapat melakukan eksekusi mendapat kesempatan yang sama.

• Efisiensi

waktu yang digunakan untuk mengeksekusi suatu proses harus seminimal mungkin, agar tidak terjadi interrupt atau critical
section

• Response Time

Waktu yang dibutuhkan untuk mengeksekusi dibagi menjadi dua interaktif dan real time. Interaktif adalah waktu dimana sampai karakter pertama tampil di terminal. sedangkan real time adalah dimana waktu yang dibutuhkan dari intruksi pertama di eksekusi.

• Turn Around Time

Waktu yang digunakan dari awal proses dieksekusi samapai akhir. Turn arround time = waktu eksekusi + waktu menunggu

• Throughput adalah jumlah proses yang dapat dikerjakan dalam satu waktu.

Dari pengertian diatas dapat disimpulkan bahwa real time scheduling adalah penjadwalan yang digunakan untuk mengeksekusi suatu proses dari proses pertama dieksekusi sampai akhir. agar semua proses dapat dieksekusi.

Algoritma yang sering digunakan di real time scheduling ada 3:

1. CLOCK DRIVEN

            Diutamakan untuk sistem hard real time dimana semua proses diketahui adalah design time sehinnga scheduling offline dapat digunakan. oleh karena itu, kita harus memikirkan proses mana yang harus dikerjakn terlebih dahulu agar tidak terjadi intrerrupt. Dengan cara proses yang tidak memerlukan waktu yang banyak dipilih terlebih dahulu, sebelum dieksekusi.

Tipe Clock Driven :

• semua proses real time sudah tetap dan diketahui
• jadwal yang dihitung secara offline disimpan dan digunakan pada saat runtime

       2.  Weighted round-robin

Digunakan pada saat real- time traffic dimana terjadi proses dengan kecepatan tinggi,  oleh karena itu diaktifkan jaringan. Proses dibatasi oleh time quantum. setelah 1 time quantum proses akan diinterupt.

Keuntungan algoritma Round Robin :
pembagian penanganan proses lebih merata
Kerugian algoritma Round Robin :
waiting time maksimum untuk tiap proses :
(n-1) * q
n = jumlah proses dalam queue
q = time quantum
n Pengaruh besar-kecilnya time quantum
n Menentukan besar time quantum yang ideal
80 % proses memiliki CPU-burst time < time quantum

      3.   Priority-driven

Diutamakan pada dinamis rea time dimana sistem harus cepat beradaptasi dengan perubahan yang terjadi.

Mengutamakan proses yang memiliki prioritas lebih tinggi ,karakteristik untuk menentukan prioritas :

• Time limit
•  Memory requirement
• Akses file
• Perbandingan antara I/O burst dengan CPU burst
• Tingkat kepentingan proses
• Preemptive dan Non-preemptive

Algoritma Scheduling yang digunakan di non real-time :
1. berdasarkan release time

• First-In-First-Out
• Last-In-First-Out

2. Berdasarkan waktu eksekusi
-  Shortest-Execution-Time-First
– Longest-Execution-Time-First

Algoritma yang berdasarkan prioritas saat deadline
– Earliest deadline first
– Least slack time first

Thread

CHAPTER 4 : THREAD

Definisi Thread
Thread adalah sebuah pengontrol aliran program pelaksanaan program dengan menggunakan kendali tunggal. Operasi yang paling Modern saat ini adalah sistem yang banyak sekali menyediakan berbagai cara, dan memungkinkan suatu proses terkendali dengan baik.

Pendekatan tradisional sebuah thread eksekusi per-proses, dimana konsep thread tidak dikenal.

Multithreaded Process

Benefits/manfaat
· Kemampuan reaksi
· Sumber daya berbagi
· Ekonomi
· Scalabilas
Thread bermanfaat untuk Multithreading yang berguna untuk Multiprocessor dan Singleprocessor. Kegunaan untuk system Multiprocessor, adalah :
a) Sebagai unit pararel atau tingkat granularitas pararelisme.
b) Peningkatan kinerja disbanding berbasis proses.
Kegunaan Multithreading pada singleprocessor, adalah :
a) Kerja foreground dan background sekaligus di satu aplikasi.
b) Penanganan asynchronous processing menjadi lebih baik.
c) Mempercepat eksekusi program.
d) Pengorganisasian program menjadi lebih baik.

Multicore Programming
Multicore systems mendesak/memaksa para programmer untuk melewati tantangan yang meliputi :
a) pembagian aktivitas
b) Saldo/Timbangan
c) Data yang telah hancur
d) Ketergantungan Data
e) Pengujian dan debugging

Arsitektur Server Multithreaded

ketika client mengajukan suatu permintaan, pada saat itu juga server akan menuliskan suatu thread yang baru untuk pelayanan atas permintaan yang diajukan oleh client. Selain itu server juga menyimpulkan atau mendengarkan atas permintaan client sehingga permintaan client dapat terpenuhi.

Pelaksanaan Eksekusi Pada Saat Yang Bersaman Pada Suatu Sistem Berinti Tunggal
Single CoreGambar dibawah ini merupakan suatu gambar yang menunjukkan sebuah program yang melakukan dua remote procedure calls (RPC) ke dua host yang berbeda untuk memperoleh hasil gabungannya.

Pada sebuah program single-core, untuk memperoleh suatu hasil proses dilakukan secara berurutan. Penulisan ulang program dengan menggunakan thread-thread yang terpisah bagi setiap RPC-nya menghasilkan kecepatan yang cukup berarti. Apabila program ini beroperasi pada sebuah uniprosesor, maka request harus dibuat secara seri dan hasil beroperasi secara seri, namun program akan menunggu dua jawaban pada waktu yang bersamaan.
Pelaksanaan Paralel Pada Suatu Multicore Sistem

User Threads
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

Kernel Threads
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


Multithreading Models
1. Many-to-One : banyaknya User-Level thread yang dipetakan ke kernel thread tunggal, akan tetapi dari beberapa user thread dapat menggunakan satu kernel thread saja.
Contoh :
· Solaries Green Thread
· GNU Portable Thread
2. One-to-One : setiap user-level thread memetakan ke kernel thread, akan tetapi user thread hanya dapat menggunakan satu kernel thread.
Contoh :
· Windows NT/XP/2000
· Linux
· Solaris 9 and later
3. Many-to-Many 
· Mengijinkan beberapa user-level thread memakai beberapa kernel thread.
· Mengijinkan system operasi untuk menciptakan beberapa kernel thread.

Thread Libraries
1. Thread libraries menyediakan pemrogram dengan API untuk menciptakan dan memanage thread.
2. Dalam pengimplementasiannya ada dua cara, diantaranya :
· Keseluruhan library pada ruang pemakai.
· Kernel-support library yang didukung dengan OS.

Pthreads
1. Dapat dianggap sebagai user-level atau kernel-level.
2. Suatu POSIX standar (IEEE 1003.1c) API untuk menciptakan thread dan sinkronisasi.
3. API menetapkan sifat thread library, implementasinya adalah pengembangan library.

Java Threads
1. Java thread diatur oleh JVM.
2. Secara khusus diterapkan untuk menggunakan thread model yang disediakan dengan dasar OS.
3. Java thread diciptakan oleh :
· Memperpanjang thread class.
· Menerapkan runnable interface.

Threading Issues
1. Semantics of fork() and exec() system call.
2. Thread cancellation of target thread
3. Asynchronous atau deffered (penundaan atau ketidak serempakan)
4. Signal handling (isyarat menangani)
5. Thread pools : menciptakan sejumlah thread dalam suatu kolom dimana mereka saling menunggu pekerjaan. Keuntungannya yaitu :
· Pada umumnya sedikit lebih cepat untuk melayani suatu permintaan dengan suatu thread yang sudah ada dibandingkan menciptakan suatu thread baru.
· Mengijinkan sejumlah thread dalam suatu aplikasi menjadi seukuran pool.
6. Thread-specific data
7. Scheduler activation

Thread Cancellation
1. pengakhiran suatu thread sebelum selesai.
2. Dua pendekatan umum :
· Cancellationterminate yang tidak serempak dengan penyusupan target.
· Penundaan Cancellationterminate dengan penyusupan target pada waktu tertentu.

Signal Handling
1. Isyarat digunakan Sistem UNIX untuk memberitahu suatu proses bahwa peristiwa tertentu telah terjadi.
2. Suatu signal handler digunakan untuk proses signal :
· Signal yang dihasilkan oleh peristiwa tertentu.
· Signal yang dikirim untuk suatu proses.
· Signal adalah handler.
· Linux mengacu pada thread sebagai tasksrather disbanding thread.
· Thread muncul ketika dilaksanakannya melalui clone() system call.
· Clone()allows merupakan sebuah child untuk membagi dalam pengalokasian ruang alamat yang menjadi tugas parent pada proses.

Windows XP Threads
Pengimplementasian one-to-one menentukan, kernel-level.
Setiap threads meliputi :
· Id thread : suatu nilai unik yang mengindentifikasikan sebuah thread apabila thread itu memanggil server.
· Register set : nilai-nilai register tingkat pengguna yang disimpan.
· Separate user dan kernel stack.
· Private data storage area.
Dari hasil pemahaman diatas, secara garis besar dapat diketahui bahwa…
Thread sering disebut Light Weight Process (LWP), yaitu unit dasar utilisasi pemroses dan berisi program counter, register set dan stack space. Thread-thread di satu proses berbagi (memekai bersama) bagian code, data dan sumber daya system operasi seperti file dan signal. Pemakaian ektensif menyebabkan alih pemroses antara thread-thread di satu proses tidak mahal disbanding alih konteks antar proses. Meski alih thread masih memerlukan alih himpunan register, namun tidak ada keterlibatan manajemen memori.
Multithreading merupakan upaya untuk menigkatkan kinerja system computer, disebabkan :
1. Penciptaan thread baru lebih cepat dibandingkan penciptaan proses baru.
2. Terminasi thread lebih cepat dibandingkan pengakhiran proses.
3. Alih ke thread lain di suatu proses lebih cepat disbanding dari satu proses ke proses lain.
4. Thread-thred di satu proses dapat berbagi kode, data dan sumber daya lain secara nyaman dan efisiensi disbanding proses-proses terpisah.

Kegunaan Thread
Multithreading berguna untuk multiprocessor dan singleprocessor.
Kegunaan untuk system multiprocessor adalah :
· Sebagai unit pararel atau tingkat granularitas pararelisme.
· Peningkatan kinerja disbanding berbasis proses.
Kegunaan multithreading pada singleprocessor, adalah :
· Kerja foreground dan background sekaligus di satu aplikasi.
· Penanganan asynchronous proseccing menjadi baik.
· Mempercepat eksekusi program.
· Pengorganisasian program menjadi lebih baik.
Manfaat utama banyak thread di satu proses adalah memaksimumkan derajat kongkurensi antara operasi-operasi yang terkait erat. Aplikasi jauh lebih efisien dikerjakan sebagai sekumpulan thread disbanding sekumpulan proses.

Karakteristik Thread
Proses merupakan lingkungan eksekusi bagi thread-thread yang dimilikinya. Thread-thread di satu proses memakai bersama sumber daya yang dimiliki proses, yaitu :
· Ruang alamat.
· Himpunan berkas yang dibuka.
· Proses-proses anak.
· Timer-timer.
· Snyal-sinyal.
· Sumber daya-sumber daya lain milik proses.
Tiap thread mempunyai property independen berikut seperti :
· Keadaan (state) eksekusi thread (running, ready dan sebagainya).
· Konteks pemroses. Thread dapat dipandang sebagai satu PC (program counter) tersendiri independen di satu proses.
· Beberapa penyimpan static per-thread untuk variable-variabel local.

Paket Bahasan Perancangan Paket Thread
Paket thread adalah sekumpulan primitive (misalnya library calls) untuk pemrogram berhubungan dengan thread di program aplikasi. Pertimbangan penting pembuatab paket thread adalah :
· Waktu penciptaan thread.
· Penanganan critical region di tingkat thread.
· Penanganan private global variables.
· Implementasi paket thread.

Jenis-jenis Thread Berdasarkan Waktu Penciptaannya
Kategori thread berdasarkan waktu penciptaan :
1. Static threads
Jumlah thread yang akan dibuat ditentukan saat penulisan dan kompilasi program. Tiap thread langsung dialokasikan stack tetap.
Keunggulan à sederhana.
Kelemahan à tidak fleksibel.
2. Dynamic threads
Penciptaan dan penghancuran thread “on-the-fly” saat eksekusi. Penciptaan thread biasanya menspesifikasikan fungsi utama thread (seperti pointer ke procedure) dan ukuran stack, dapat juga ditambah parameter-parameter lan seperti prioritas panjadwalan.
Keunggulan à fleksibel.
Kelemahan à lebih rumit.

Implementasi Paket Thread
Implementasi paket thread :
1. Thread level kernel.
> Keunggulan :
· Memudahkan koordinasi multithread seperti proses server.
· Tidak seboros kumpulan proses tradisional.
> Kelemahan :
· Operasi manajemen thread sangat lebih boros.
· Kernel harus menyediakan semua feature.
2. Thread level pemakai.
> Keunggulan :
Kinerja luar biasa bagus disbanding thread level kernel.
· Tidak diperlukan modifikasi kernel.
· Fleksibelitas tinggi.
> Kelemahan :
· Tidak manfaatkan multiprocessor.
· Untuk aplikasi dengan keterlibatan kernel yang kecil.
· Mengharuskan nonblocking system call.

Struktur Sistem Operasi Multiprocessor
System operasi serupa multiprogrammed uniprocessor. System operasi multiprocessor lebih kompleks karena terdapat banyak pemroses yang mengeksekusi task-task secara kongkuren. System operasi multiprocessor harus dapat mendukung eksekusi banyak task dan mengeksploitasi banyak pemroses untuk meningkatkan kinerja.
Struktur system operasi multiprocessing, antara lain :
1. Separate supervisor
Semua pemroses mempunyai kopian kernel, supervisor dan struktur data sendiri, menanggapi interupsi-interupsi pemakai yang berjalan di pemroses itu. Terdapat struktur data bersama untuk interaksi di antara pemroses-pemroses. Pengaksesan diproteksi menggunakan mekanisme sinkronisasi :
· Tiap pemroses mempunyai perangkat I/O dan system file sendiri.
· Terdapat sedikit coupling diantara pemroses-pemroses.
· Tiap pemroses bertindak sebagai system otonom dan independen.
> Keunggulan :
· Dapat degradasi secara perlahan dalam menghadapi kegagalan pemroses karena hanya terdapat sedikit coupling diantara pemroses-pemroses.
> Kelemahan :
· System sulit melakukan eksekusi pararel satu task tunggal (yang dipecah menjadi subtask-subtask dan menjadwalkan subtask-subtask di banyak pemroses secra kongkuren).
· Tidak efisien karena supervisor, kernel dan struktur data direplikasi di tiap pemroses.
2. Master-slave
Satu pemroses disebut master, bertugas memonitor status dan memberikan kerja ke pemroses-pemroses lain, slave. Slave-slave dipandang sebagai pool sumber daya yang dijadwalkan master. Pemroses-pemrose slave mengeksekusi program-program aplikasi.
> Keungulan :
· Efisien.
· Implementasi (sinkronisasi pengaksesan variable, dan sebagainya) mudah karena system operasi dieksekusi di satu pemroses tunggal.
> Kelemahan :
· Sangat bergantung pada pemroses master.
· Master dapat mengalami botlencek dan berkonsekuensi tidak menggunakan pemroses-pemroses slave secara penuh.
3. Symmetric
Semua proses otonom dan dipandang identik. Terdapt satu kopian supervisor atau kernel yang dapat dieksekusi semua pemroses secara kongkuren.
> Masalah :
· Pengaksesan kongkuren struktur data bersama perlu dikendalikan agar terjaga intergritasnya.
> Solusi :
· Cara paling sederhana adalah memandang seluruh system operasi sebagai satu critical section dan hanya memungkinkan satu pemroses mengeksekusi system operasi di satu waktu. Metode ini disebut floating master karena dapat dipandang sebagai konfigurasi master-slave dimana master di-apungkan/diangkat dari satu pemroses ke pemroses lain.
> Keunggulan :
· Paling fleksibel dan berdaya tahan tinggi.
· Memungkinkan eksekusi satu task tunggal secara pararel.
· Dapat mendegradasi secara perlahan dalam menghadapi kegagalan.
· Penggunaan sumberdaya sangat efisien.
> Kelemahan :
· Perancangan dan implementasi paling sulit.

Pertemuan 3

Multi Processor

Pengertian Multicore computer, Multicore computer sering kita dengar, terutama yang membahas tentang spesifikasi komputer, jadi Multicore computer adalah Komputer yang prosesornya mempunyai banyak core, core-core tersebut beroperasi seolah olah merupakan suatu prosesor dengan single chip.
Multicore mempunyai keuntungan yaitu dapat meningkatkan performa tanpa meningkatkan clock speed dari prosesor jadi lebih menghemat listrik dan space.

Pengertian Multi Prosesor, Multi Prosesor berbeda dengan Multi core computer, perbedaan nya adalah dalam satu komputer, terdapat banyak Prosesor, bukan satu prosesor dengan banyak core, terkadang kedua teknologi tersebut digabungkan.

Multicore vs MultiProsesor

• Hemat Energi :

untuk masalah hemat energi , multi-core computer  mempunyai efisiensi energi lebih tinggi daripada multi Prosesor, ini dikeranakan tidak ada circuit yang berulang dan karena antar chip hubungan nya sangat dekat jadi lebih hemat energi.

• Hemat Tempat :

Multi core computer lebih hemat tempat dari Multi Prosesor, karena banyak chip berada dalam satu tempat, jika multi prosesor, chip – chip diletakkan secara terpisah.

•  Performa :

Multi prosesor dalam hal performa lebih baik, karena dapat menghandle banyak request secara terpisah, sedangkan multicore computer menjalankan request secara bergantian.

• Kesimpulan Multi Core vs Multi Prosesor:

Untuk masalah energi dan space, multi core lebih unggul, karena jarak antar chip sangat dekat, sedangkan untuk masalah performa, Multi Prosesor lebih unggul karena pemrosesan request tidak bergantian, melainkan antar chip melakukan tugas masing – masing dengan berbarengan.

• Multiple Processor System
  • Shared Memory Multi-Processor
  • Massage Passing Multicomputer
  • Wide area distributed system

•  UMA Multiprocessor with BUS -Based Architectures

pada gambar A diatas, merupakan architecture tanpa caching, jadi tanpa ada memori sementara, gambar B diatas, architecture nya menggunakan sistem caching, cache diletakkan pada masing – masing CPU, jadi untuk menuju CPU yang lain, CPU harus melalui Cache terlebih dahulu, sedangkan pada gambar C, yaitu caching dengan private memory, private memory hanya bisa diakses CPU yang bersangkutan.

• Architecture

System Multiprosesor dibagi menjadi dua berdasarkan cara berhubungan antar CPU dan memory yaitu UMA , NUMA dan NORMA

• UMA(Uniform Memory Form) :

UMA memorynya seragam , juga bisa disebut SMP (Symetrical MultiProsesor), yaitu sistemnya simetris atau satu jalur hanya ada satu conversation yg bisa lewat. karakteristik SMP yang lain adalah

1. Antrian tidak jelas (Unpredictable) , namun dengan menggunakan crossbar switch, bisa diatur delaynya sehingga jadi predictable.

2.Kelemahan yaitu BottleNeck atau leher botol, dimana outputnya lebih kecil.

• NUMA Architecture

gambar diatas merupakan Arsitekur dari NUMA (Non Unified Memory Access)

Karakteristik dari NUMA :

1. Terdapat single address space yang diketahui oleh semua CPU
2. Akses ke remote memory melalui instruksi LOAD dan STORE.
3. Akses ke remote memory lebih lambat daripada akses ke memory lokal

• UMA(also known as SMP) vs NUMA

Persamaan :

1. Single memory space

Perbedaan :

1. Waktu akses
2. jumlah prosesor
3. Bus vs network implementation

• Classification of parallel system
  • SISD (Single Instruction single data)
    • Uniprocessor
  • MISD(Multiple Instruction Single Data)
    • Stream based processing
  • SIMD(Single Instruction Multiple Data = DLP)
  • MIMD(Multiple Instruction Multiple Data)

Time Sharing

Menggunakan single data structure untuk scheduling suatu multiprosesor, time sharing digunakan untuk penschedulan CPU, supaya tidak terjadi tabrakan.

gambar diatas meruapakan proses Time Sharing. selain time sharing juga terdpar space sharing, gambarnya adalah sebagai berikut :

Gang Scheduling

Merupakan komunikasi diantara 2 thread.

Terdapat 3 bagian dari Gang Scheduling

1. Thread yang sejenis dijadikan 1 thread
2. semua member dari gang berjalan secara simultan
3. semua member start dan end berbarengan

Pengertian Multiprocessing,Multitasking, dan Distributed Processing

Pengertian Multiprocessing :

Multipengolahan (Bahasa Inggris:Multiprocessing) adalah istilah teknologi informasi yang merujuk kepada kemampuan pemrosesan komputer yang dilakukan secara serentak. Hal ini dimungkinkan dengan menggunakan dua CPU atau lebih dalam sebuah sistem komputer. Istilah ini juga dapat merujuk kepada dukungan sebuah sistem untuk mendukung lebih dari satu prosesor dan mengalokasikan tugas kepada prosesor-prosesor tersebut.

Multipengolahan' juga kadang merujuk kepada kemampuan eksekusi terhadap beberapa proses perangkat lunak dalam sebuah sistem secara serentak, jika dibandingkan dengan sebuah proses dalam satu waktu, meski istilah multiprogramming lebih sesuai untuk konsep ini. Multiprocessing sering diimplementasikan dalam perangkat keras (dengan menggunakan beberapa CPU sekaligus), sementara multiprogramming sering digunakan dalam perangkat lunak. Sebuah sistem mungkin dapat memiliki dua kemampuan tersebut, salah satu di antaranya, atau tidak sama sekali.

Pengertian Multitasking :

Banyak tugas atau tugas ganda (Bahasa Inggris :Multitasking) adalah istilah teknologi informasi yang mengacu kepada sebuah metode dimana banyak pekerjaan atau dikenal juga sebagai proses diolah dengan menggunakan sumberdaya CPU yang sama. Dalam kasus sebuah komputer dengan prosesor tunggal, hanya satu instruksi yang dapat bekerja dalam satu waktu, berarti bahwa CPU tersebut secara aktif mengolah instruksi untuk satu pekerjaan tersebut. Multitasking memecahkan masalah ini dengan memjadwalkan pekerjaan mana yang dapat berjalan dalam satu waktu, dan kapan pekerjaan yang lain menunggu untuk diolah dapat dikerjakan. Kondisi mengalokasikan CPU dari pekerjaan satu ke pekerjaan yang lain disebut context switch. Ketika context switch terjadi dengan sangat cepat -- kondisi ini cukup untuk memberikan ilusi pengolahan-paralel. Bahkan dalam komputer yang memiliki lebih dari satu CPU (disebut multi-prosesor), multitasking memperbolehkan lebih banyak pekerjaan dijalankan dibanding dengan jumlah CPU yang tersedia.

Pengertian Distributed Processing : 

Mengerjakan semua proses pengolahan data secara bersama antara komputer pusat dengan beberapa komputer yang lebih kecil dan saling dihubungkan melalui jalur komunikasi. Setiap komputer tersebut memiliki prosesor mandiri sehingga mampu mengolah sebagian data secara terpisah, kemudian hasil pengolahan tadi digabungkan menjadi satu penyelesaian total. Jika salah satu prosesor mengalami kegagalan atau masalah yang lain akan mengambil alih tugasnya.

Sumber : www.wikipedia.org