1 concurrency part 1
Post on 08-Dec-2015
46 Views
Preview:
DESCRIPTION
TRANSCRIPT
SISTEM OPERASI
CONCURRENCY: MUTUAL EXCLUSION AND SYNCHRONIZATION
Oleh :Kelompok : 2
NADIA RAHMILUTHFAN MAULANARIFAL PRATAMAM. REZA PRATAMAANISSA YOLANDA PUTRY
ROADMAP
Semaphores
Monitors
Message Passing
Readers/Writers Problem
Principals of Concurrency
Mutual Exclusion: Hardware Support
CONCURRENCY
Concurrency merupakan landasan umum perancangan sistem operasi. Proses-proses disebut concurrensy jika proses-proses (lebih dari satu proses) berada pada saat yang sama.
Concurrency muncul pada 3 konteks yang berbeda:
• Multiple Application Waktu sharing
• Aplikasi terstruktur Ekstensi dari rancangan modular
• Struktur sistem operasi SO sendiri diimplementasikan
sebagai sekumpulan proses atau thread
• Atomic operationSebuah fungsi yang diimplementasikan sebagai urutan
satu atau lebih instruksi secara atomic (tanpa interrupt).
• Deadlock suatu keadaan dimana sistem seperti terhenti dikarenakan setiap proses memiliki sumber daya yang tidak bisa dibagi dan menunggu untuk mendapatkan sumber daya yang sedang dimiliki oleh proses lain.
• Livelocksituasi dimana dua atau lebih proses secara kontinu
merubah state sebagai respon tanpa melakukan suatu pekerjaan.
• Critical sectionbagian kode dalam proses yang membutuhkan akses
menuju sumberdaya dan tidak boleh dijalankan ketika proses lain berada pada bagian kode yang terhubung
Beberapa istilah yang berhubungan dengan concurrency
• Mutial ExclusionSebuah ketentuan dimana ketika hanya ada satu proses pada critical section yang boleh memakai sumber daya, dan proses lain yang ingin memakai sumber daya tersebut harus menunggu hingga sumber daya tadi dilepaskan atau tidak ada proses yang memakai sumber daya tersebut
• Race conditionSituasi dimana beberapa proses mengakses dan memanipulasi sebuah pada saat besamaan dan nilai akhir dari data tersebut tergantung pada proses yang terakhir selesai
• StarvationSituasi dimana sebuah proses yang runnable diabaikan oleh scheduler;meskipun mampu melanjutkan, tetapi tidak pernah dipilih
• Telah diketahui bahwa proses dapat diinterleave pada uniprocessor
P r o s e s I n t e r l e a v i n g & O v e r l a p p i n g
1. Sharing sumber daya global– Penulisan suatu shared variable: urutan penulisan sangat penting
2. Pengelolaan alokasi sumber daya secara Optimal.
− OS kesulitan dalam pengelolaan alokasi sumber daya secara optimal
3. Sulit menemukan error pemrograman
Kesulitan Concurrency
Contoh pada Multiprocessor
Process P1
chin = getchar();
chout = chin;
putchar(chout);
Process P2
chin = getchar();chout = chin;
putchar(chout);
Jika diterapkan suatu aturan yang hanya satu proses dapat memasuki fungsi tersebut pada suatu waktu, maka:
• P1 & P2 berjalan pada processor berbeda• P1 memasukkan echo lebih dahulu,
– P2 mencoba masuk tetapi diblok – P2 suspend
• P1 melengkapi eksekusi– P2 me-resume & mengeksekusi echo
Menerapkan Akses Tunggal
• Race condition terjadi ketika: Banyak proses atau thread
membaca & menulis item data Hasil akhir dari aktifitas baca &
tulis tersebut tergantung pada urutan eksekusi dari proses yang terlibat.
• Output tergantung pada siapa yang terakhir menyelesaikan race.
Kondisi Race
Isu perancangan dan pengelolaan apa yang muncul karena adanya concurrency?• SO harus:
Menjaga track dari berbagai prosesMeng-alokasi-kan dan men-dealokasi-kan
sumber dayaMelindungi data & resource dari
gangguan proses lain Memastikan proses & output terbebas
dari kecepatan pemrosesan
Operating System Concern
Tingkat Kesadaran
HubunganPengaruh Satu Proses
Dengan Proses Lainnya
MasalahPengendalian yang
Perlu Dilakukan
Proses tak peduli Persaingan
• Hasil satu proses independen terhadap aksi proses lain• Pewaktuan proses dapat
berpengaruh
Mutual exclusion Deadlock Starvation
Proses secara taklangsung peduli terhadap proses lain (yaitu objek yang dipakai bersama)
Kerjasama dgpemakaianbersama
• Hasil-hasil suatu proses dapat bergantung
pada informasi yg diperoleh dari proses lain• Pewaktuan proses dapat
berpengaruh
Mutual exclusion Deadlock Starvation Koherensi Data
Proses secara langsung peduli terhadap proseslain
Kerjasama dgkomunikasi
• Hasil-hasil suatu proses dapat bergantung
pada informasi yg diperoleh dari proses lain• Pewaktuan proses dapat
berpengaruh
Deadlock Starvation
Ada tiga permasalahan:
• Pada Mutual Exclusion– Critical section (bagian kritis dari
proses)• Deadlock• Starvation
Kompetisi Antar Proses (Resources)
Syarat Mutual Exclusion (1)
• Hanya satu proses pada satu waktu yangdibolehkan ada dalam critical section bagisuatu resource• Proses yang berhenti pada noncriticalsection-nya harus berlanjut tanpa gangguan proses lain• Tidak ada deadlock atau starvation
Syarat Mutual Exclusion (2)
• Proses tidak harus ditunda untuk masuk ke critical section saat tidak ada proses lain yang menggunakannya
• Tidak ada asumsi mengenai kecepatan relatif proses atau jumlah proses
• Proses berada di dalam critical section-nya hanya dalam batas waktu tertentu (finite)
• Uniprocessor hanya membolehkan
interleaving
• Interrupt Disabling− Proses berjalan sampai ia
memanggil suatu layanan SO atau sampai ia diinterupsi
− Disabling interrupts menjamin terwujudnya mutual exclusion
− Tidak akan bekerja pada arsitektur multiprocessor
1. (Disabling Interrupts)
2. Instruksi Mesin Khusus
Instruksi Compare & Swap Intruksi exchange( Juga disebut “compare
and exchange instruction”)
COMPARE & SWAP INSTRUCTION
int compare_and_swap (int *word,
int testval, int newval)
{
int oldval;
oldval = *word;
if (oldval == testval) *word = newval;
return oldval;
}
EXCHANGE INSTRUCTION
void exchange (int register, int memory)
{
int temp;
temp = memory;
memory = register;
register = temp;
}
Keuntungan instruksi mesin khusus
• Dapat diterapkan terhadap beberapa proses pada uniproccessor atau multi processor yang berbagi (sharing) main memory
• Simple, karena itu mudah untuk diperiksa
• Dapat digunakan untuk mendukung banyak critical section
Keuntungan Special machine Instruction
• Busy-waiting : menghabiskan waktu processor
• memungkinkan terjadinya Starvation : ketika suatu proses meninggalkan critical section dan lebih dari satu proses menunggu (waiting).
− Beberapa proses dapat ditolak aksesnya dalam waktu tak terbatas.
• Memungkinkan terjadinya Deadlock
Kerugian Special machine Instruction
top related