Programming Language Concept Session 10

Programming Language Concept Session 10


  • Concurrency dapat terjadi di empat level:
    Machine instruction level (mengeksekusi dua atau lebih instruksi mesin bersamaan)
    High-level language statement level (mengeksekusi dua atau lebih pernyataan bahasa level tinggi bersamaan)
    Unit level (mengeksekusi dua atau lebih unit subprogram bersamaan)
    Program level (mengeksekusi dua atau lebih program bersamaan)
  • Mekanisme control concurrent meningkatkan felixibility programming
  • Algoritma concurrent dikatakan scalable jika kecepatan eksekusinya bertambah ketika lebih banyak processor tersedia
  • Physical concurrency merupakan concurrency, misal ada lebih dari satu processor, yang beberapa unit program dari program yang sama eksekusi bersamaan
  • Ketika programmer dan aplikasi software memisalkan bahwa ada banyak processor menyediakan actual concurrency, ketika faktanya eksekusi sebenarnya dari program berada di sisipan di satu processor dikenal dengan logical concurrency
  • Alasan menggunakan concurrency:
    – Kecepat eksekusi program di mesin dengan banyak processor
    – Bahkan ketika suatu mesin hanya memiliki satu processor, program yang ditulis untuk eksekusi concurrent dapat lebih cepat dari program sama yang ditulis untuk eksekusi beruntun (nonconcurrent)
    Concurrency menyediakan metode berbeda mengkonseptualisasi solusi program ke masalah
    – Untuk aplikasi program yang didistribusikan ke bermacam mesin, secara local ataupun melalui Internet

Subprogram-Level Concurrency


  • Task merupakan unit dari program, mirip dengan subprogram, yang dapat berada di eksekusi concurrent dengan unit lain di program yang sama
  • Task terkadang dikenal dengan process
  • Di beberapa bahasa seperti Java dan C# , metode tertentu bekerja sebagai task, dan dieksekusi di objek yang dikenal dengan thread
  • Heavyweight task mengeksekusi di tempat alamatnya sendiri
  • Lightweight task semua berjalan di tempat alamat yang sama, sehingga dapat lebih efesien dari heavyweight
  • Suatu task dikatakan disjoint ketika tidak berkomunikasi atau berdampak ke eksekusi dari task lain di program tersebut
  • Synchroninzation merupakan mekanisme yang mengkontrol urutan dimana task mengeksekusi
  • Ada dua macam synchronization:
    Cooperation synchronization, dibutuhkan ketika suatu task harus menunggu task lainnya untuk menyelesaikan aktivitasnya sebelum task tadi mulai atau melanjutkan eksekusinya
    Competition synchronization, dibutuhkan ketika ada dua task yang membutuhkan sumber sama yang tak dapat digunakan bersamaan
    – Contoh: jika task A perlu akses data lokasi x ketika task B sedang mengakses x, task A harus menunggu task B menyelesaikan pemrosesan dari x.

Cooperation: task mungkin harus menunggu pemrosesan di tempat yang diperlukan operasi task miliknya tersebut selesai

Competition: task mungkin harus menunggu selesainya pemrosesan lain dari task apapun yang sedang terjadi di data tertentu

  • Competition synchronization diperlukan ketika dua task dapat menghasilkan hasil yang berbeda yang bergantung pada urutannya, seperti:

Task A: TOTAL = TOTAL + 1

Task B: TOTAL = 2 * TOTAL

  • Sistem program run-time yang dikenal dengan scheduler mengatur pembagian processor diantara task
  • Scheduler menyediakan synchronization yang memerlukan mekanisme untuk menghambat waktu eksekusi task
  • Task dapat berada di berbagai keadaan berbeda:
    New: task dikatakan berada di kondisi new ketika telah dibuat namun belum memulai eksekusi
    Ready: task dikatakan siap untuk dijalankan namun sedang belum dijalankan
    Running: task yang sedang mengeksekusi
    Blocked: task yang telah berjalan, namun ekekusinya diganggu oleh event tertenu
    Dead: task yang tidak lagi hidup (eksekusinya sudah selesai atau secara eksplisit dimatikan oleh program)
  • Liveness merupakan suatu karakteristik yang mungkin atau tidak dimiliki oleh suatu unit program
    – Di code sekuensial, artinya unit tersebut akhirnya akan menyelesaikan eksekusinya
  • Jika semua task di lingkungan concurrent kehilangan livenessnya, maka dikenal dengan deadlock

Semaphore


  • Dirancang oleh Edsger Dijkstra pada tahun 1965
  • Semaphore merupakan struktur data yang berisi counter dan queue untuk menyimpan task descriptor
  • Task descriptor merupakan struktur data yang menyimpan semua informasi relevan tentang keadaan eksekusi dari task
  • Semaphore dapat digunakan untuk mengimplementasi guard di code yang mengakses struktur data bersama (shared)
  • Guard merupakan alat lingustik yang memperbolehkan code yang dijaga (guarded) dieksekusi hanya ketika kondisi tertentu bernilai true
  • Semaphore hanya memiliki dua operasi, wait dan release (dikenal P dan V oleh Dijkstra)
  • Semaphore dapat digunakan untuk menyediakan competition dan cooperation synchronization

Cooperation Synchronization dengan Semaphore


Untuk cooperation synchronization, buffer harus memiliki cara mencatat jumlah posisi yang kosong dan yang telah terisi di buffer utnuk menghindari underflow dan overflow. Misal emptyspots dapat digunakan menjadi variable counter untuk menjaga jumlah posisi kosong di shared buffer yang digunakan producer dan consumer, dan fullspot sebagai variable counter untuk menjaga jumlah posisi terisi di shared buffer. Queue emptyspot dapat menyimpan task producer yang menunggu tempat kosong di buffer, sedangkan queue fullspot dapat menyimpan task consumer yang menunggu nilai untuk diletakkkan di buffer.

Misal buffer tersebut didesain sebagai ADT yang semua datanya masuk ke buffer melalui subprogram DEPOSIT, dan semua data yang meninggalkan buffer melalui subprogram FETCH. Subprogram DEPOSIT hanya perlu memeriksa semaphore emptyspot untuk melihat apakah ada tempat kosong. Jika setidaknya ada satu, maka DEPOSIT dapat dieksekusi, yang memiliki side effect mengurangi counter emptyspot. Jika buffer penuh, pemanggil DEPOSIT harus menunggu di emptyspots queue hingga tempat kosong tersedia. Ketika DEPOSIT selesai, subprogram DEPOSIT menambahkan counter semaphore fullspot untuk menandakan kalau ada satu lagi lokasi terisi di buffer.

Subrpogram FETCH memiliki rentetan yang bertolak belakang dengan DEPOSIT. Ia memerika semaphore fullspot untuk meliha apakah buffer memiliki setidaknya satu item. Jika iya, item ditanggalkan dan semaphore emptyspot menambah counternya satu. Jika buffer kosong, pemanggil task diletakkan di queue fullspot untuk menunggu hingga item muncul. Ketika FETCH selesai, ia harus menambahkan counter emptyspots.

Operasi tipe semaphore sering tidak langsung – ia diselesaikan melalui subprogram wait dan release. Maka dari itu, operasi DEPOSIT yang hanya dijelaskan sebenarnya diselesaikan dengan panggilan ke wait dan release. Perlu diingat bahwa wait dan release harus bisa mengakses task-ready queue

Subprogram semaphore wait digunakan untuk menguji counter dari variable semaphore yang diberikan. Jika nilainya lebih dari nol, pemanggil dapat menjalakan operasinya. Dalam kasus ini, nilai counter dari variable semaphore dikurangi untuk menandai bahwa sekarang ada lebih dikit satu dari apapun yang dihitungnya. Jika nilai counter nol, pemanggil tersebut harus diletakkaan di waiting queue variable semaphore, dan processor harus diberikan ke ready task lainnya.

Subprogram semaphore release digunakan oleh task untuk membolehkan task lain untuk memiliki satu dari berapapun counter dari yang dihitung variable semaphore yang ditentukan. Jika queue dari variable semaphore yang ditentukan kosong, yang artinya tak ada task yang menunggu, release menambahkan counternya (untuk menandakan ada satu lagi dari apapun yang sedang dikontrol sekarang tersedia). Jika satu atau lebih task sedang menunggu, release memindahkan satu dari mereka dari queue semaphore ke ready queue.

  • Pseudocode operasi wait dan release

wait(aSemaphore)

if aSemaphore’s counter > 0 then

decrement aSemaphore’s counter

else

put the caller in aSemaphore’s queue

attempt to transfer control to some ready task

(if the task ready queue is empty, deadlock occurs)

end if

release(aSemaphore)

if aSemaphore’s queue is empty (no task is waiting) then

increment aSemaphore’s counter

else

put the calling task in the task-ready queue

transfer control to a task from aSemaphore’s queue

end

  • Pseuodocode task producer dan consumer:

semaphore fullspots, emptyspots;

fullspots.count = 0;

emptyspots.count = BUFLEN;

task producer;

loop

— produce VALUE —

wait(emptyspots); { wait for a space }

DEPOSIT(VALUE);

release(fullspots); { increase filled spaces }

end loop;

end producer;

task consumer;

loop

wait(fullspots); { make sure it is not empty }

FETCH(VALUE);

release(emptyspots); { increase empty spaces }

— consume VALUE —

end loop

end consumer;

Competition Synchronization dengan Semaphore


  • Semaphore ketiga, yang dinamakan access, digunakan untuk mengontrol akses
  • Counter dari access hanya memiliki nilai 0 dan 1
  • Semaphore semacam ini dikenal dengan binary semaphore
  • Contoh:

semaphore access, fullspots, emptyspots;

access.count = 1;

fullspots.count = 0;

emptyspots.count = BUFLEN;

task producer;

loop

— produce VALUE —

wait(emptyspots); { wait for a space }

wait(access); { wait for access }

DEPOSIT(VALUE);

release(access); { relinquish access }

release(fullspots); { increase filled spaces }

end loop;

end producer;

task consumer;

loop

wait(fullspots); { make sure it is not empty }

wait(access); { wait for access }

FETCH(VALUE);

release(access); { relinquish access }

release(emptyspots); { increase empty spaces }

— consume VALUE —

end loop

end consumer;

Monitor


  • Semua operasi sinkronisasi pada shared data dikumpulkan menjadi satu unit program, struktur tersebut dinamakan monitor
  • Competition Synchronization
    Shared data merupakan penghuni di monitor (bukan di unit client)
    – Implementasi monitor menggaransikan akses disinkronisasi dengan memperbolehkan hanya satu akses di suatu waktu
    – Panggilan ke procedure monitor secara implisit di-queue jika monitor tersebut sibuk sewaktu pemanggilan
  • Cooperation Synchronization
    – Kerja sama antar proses masih sebuah task programming
    – Programmer harus menggaransikan kalau shared buffer tak akan underflow atau overflow

Message Passing


  • Message passing merupakan model umum untuk concurrency
    – Dapat meniru semaphore dan monitor
    – Tidak hanya untuk competition synchronization
  • Konsep synchronous message passing: seperti atasan yang meminta sekretarisnya untuk menahan semua telepon masuk hingga aktivitas lainnya karena sedang melakukan obrolan penting. Setelah obrolan tersebut selesai, atas memberitahu sekretaris tersebut kalau ia sekarang sudah bisa berbicara dengan pemanggil yang telah ditunda tadi.
  • Task dapat didesain sehingga ia dapat menunda eksekusinya di titik tertentu, seperti seseorang yang sedang menunggu untuk panggilan penting. Di beberapa kasus, tak dapat melakukan apa-apa selain duduk diam dan menunggu. Namun, jika task A sedang menunggu suatu message saat task b mengirim message, message tersebut dapat ditransmit. Actual transmition message ini dikenal dengan rendezvous

  • Task yang memilik klausa accept, namun code yang lainnya tidak dikenal dengan server task (contoh gambar diatas)
  • Task tanpa klausa accept dikenal dengan actor task


Sumber:

  • Concept of Programming Languages 10th. Ed  / Robert W. Sebesta (Chapter 13)
  • Concurrency / Binus Powerpoint Presentation

This entry was posted in Computer Science, Programming Language Concept and tagged , , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *