2.3.

5 Semaphores
This was the situation in 1965, when E. W. Dijkstra (1965) suggested using an
integer variable to count the number of wakeups saved for future use. In his
proposal, a new variable type, which he called a semaphore, was introduced.
A semaphore could have the value 0, indicating that no wakeups were saved, or
some positive value if one or more wakeups were pending.
Dijkstra proposed having two operations on semaphores, now usually called
down and up (generalizations of sleep and wakeup, respectively). The down
operation on a semaphore checks to see if the value is greater than 0. If so, it
decrements the value (i.e., uses up one stored wakeup) and just continues. If
the value is 0, the process is put to sleep without completing the down for the
moment. Checking the value, changing it, and possibly going to sleep, are all
done as a single, indivisible atomic action. It is guaranteed that once a
semaphore operation has started, no other process can access the semaphore
until the operation has completed or blocked. This atomicity is absolutely
essential to solving synchronization problems and avoiding race conditions.
Atomic actions, in which a group of related operations are either all performed
without interruption or not performed at all, are extremely important in many
other areas of computer science as well.
The up operation increments the value of the semaphore addressed. If one or
more processes were sleeping on that semaphore, unable to complete an
earlier down operation, one of them is chosen by the system (e.g., at random)
and is allowed to complete its down. Thus, after an up on a semaphore with
processes sleeping on it, the semaphore will still be 0, but there will be one
fewer process sleeping on it. The operation of incrementing the semaphore and
waking up one process is also indivisible. No process ever blocks doing an up,
just as no process ev er blocks doing a wakeup in the earlier model.
As an aside, in Dijkstras original paper, he used the names P and V instead of
down and up, respectively. Since these have no mnemonic significance to people
who do not speak Dutch and only marginal significance to those who do
Proberen (try) and Verhogen (raise, make higher)we will use the terms down
and up instead. These were first introduced in the Algol 68 programming
language.
Solving the Producer-Consumer Problem Using Semaphores
Semaphores solve the lost-wakeup problem, as shown in Fig. 2-28. To make
them work correctly, it is essential that they be implemented in an indivisible
way. The normal way is to implement up and down as system calls, with the
operating system briefly disabling all interrupts while it is testing the
semaphore, updating it, and putting the process to sleep, if necessary. As all of
these actions take only a few instructions, no harm is done in disabling
interrupts. If multiple CPUs are being used, each semaphore should be
protected by a lock variable, with the TSL or XCHG instructions used to make sure
that only one CPU at a time examines the semaphore.
Be sure you understand that using TSL or XCHG to prevent several CPUs from
accessing the semaphore at the same time is quite different from the producer
or consumer busy waiting for the other to empty or fill the buffer. The

semaphore operation will take only a few microseconds, whereas the producer
or consumer might take arbitrarily long.
#define N 100

/* number of slots in the buffer */

typedef int semaphore;

/* semaphores are a special kind of int

semaphore mutex = 1;
semaphore empty = N;
semaphore full = 0;

*/
/* controls access to critical region */
/* counts empty buffer slots */
counts full buffer slots
/*
*/

void producer(void)
{ int item;
while (TRUE) {

/*

TRUE is the constant 1

*/

item = produce item( );

/* generate something to put in buffer */

down(&empty);

/*

down(&mutex);

/* enter critical region */

inser t item(item);

/* put new

up(&mutex);
up(&full);
}

decrement empty count

*/

item in buffer

*/
/* leave critical region */
/* increment count of full slots */

void consumer(void)
{ int item;
while (TRUE) {

/* infinite loop */

down(&full);

/*

down(&mutex);

/* enter critical region */

item = remove item( );

/* take

up(&mutex);
up(&empty);
consume item(item);

decrement full count

*/

item from buffer

*/
/* leave critical region */
/* increment count of empty slots */
/* do something with the item */

}
}
Figure 2-28. The producer-consumer problem using semaphores.

This solution uses three semaphores: one called full for counting the number of
slots that are full, one called empty for counting the number of slots that are
empty, and one called mutex to make sure the producer and consumer do not
access the buffer at the same time. Full is initially 0, empty is initially equal to
the number of slots in the buffer, and mutex is initially 1. Semaphores that are
initialized to 1 and used by two or more processes to ensure that only one of
them can enter its critical region at the same time are called binary
semaphores. If each process does a down just before entering its critical region
and an up just after leaving it, mutual exclusion is guaranteed.
Now that we have a good interprocess communication primitive at our disposal,
let us go back and look at the interrupt sequence of Fig. 2-5 again. In a system
using semaphores, the natural way to hide interrupts is to have a semaphore,
initially set to 0, associated with each I/O device. Just after starting an I/O
device, the managing process does a down on the associated semaphore, thus
blocking immediately. When the interrupt comes in, the interrupt handler then
does an up on the associated semaphore, which makes the relevant process
ready to run again. In this model, step 5 in Fig. 2-5 consists of doing an up on
the devices semaphore, so that in step 6 the scheduler will be able to run the
device manager. Of course, if several processes are now ready, the scheduler
may choose to run an even more important process next. We will look at some
of the algorithms used for scheduling later on in this chapter.
In the example of Fig. 2-28, we have actually used semaphores in two different
ways. This difference is important enough to make explicit. The mutex
semaphore is used for mutual exclusion. It is designed to guarantee that only
one process at a time will be reading or writing the buffer and the associated
variables. This mutual exclusion is required to prevent chaos. We will study
mutual exclusion and how to achieve it in the next section.
The other use of semaphores is for synchronization. The full and empty
semaphores are needed to guarantee that certain event sequences do or do not
occur. In this case, they ensure that the producer stops running when the buffer
is full, and that the consumer stops running when it is empty. This use is
different from mutual exclusion.

Ini adalah situasi di tahun 1965, ketika EW Dijkstra (1965) menyarankan

menggunakan variabel integer untuk menghitung jumlah wakeups disimpan
untuk digunakan di masa depan. Dalam proposalnya, variabel jenis baru, yang
disebut semaphore, diperkenalkan. Sebuah semaphore bisa memiliki nilai 0,
menunjukkan bahwa tidak ada wakeups diselamatkan, atau beberapa nilai
positif jika satu atau lebih wakeups yang tertunda.
Dijkstra mengusulkan memiliki dua operasi pada Semaphore, sekarang
biasanya disebut bawah dan atas (generalisasi tidur dan wakeup, masingmasing). Bawah operasi pada pemeriksaan semaphore untuk melihat apakah
nilai lebih besar dari 0. Jika demikian, itu decrements nilai (yaitu, menggunakan
sampai satu wakeup disimpan) dan hanya terus. Jika nilai 0, proses ini
ditidurkan tanpa menyelesaikan turun untuk saat ini. Memeriksa nilai,
mengubahnya, dan mungkin akan tidur, semua dilakukan sebagai single,
tindakan atom terpisahkan. Hal ini dijamin bahwa setelah operasi semaphore
telah dimulai, tidak ada proses lain dapat mengakses semaphore sampai
operasi selesai atau diblokir. Atomicity ini adalah sangat penting untuk
memecahkan masalah sinkronisasi dan menghindari kondisi lomba. Tindakan
atom, di mana sekelompok operasi terkait baik semua dilakukan tanpa
gangguan atau tidak dilakukan sama sekali, sangat penting di banyak daerah
lain ilmu komputer juga.
Operasi up increment nilai semaphore ditangani. Jika satu atau lebih proses
sedang tidur di semaphore itu, tidak dapat menyelesaikan operasi sebelumnya
turun, salah satunya dipilih oleh sistem (misalnya, secara acak) dan
diperbolehkan untuk menyelesaikan yang turun. Dengan demikian, setelah
sampai pada semaphore dengan proses tidur di atasnya, semaphore akan tetap
0, tapi akan ada satu lebih sedikit proses tidur di atasnya. Operasi incrementing
semaphore dan bangun satu proses juga dibagi. Tidak ada proses blok pernah
melakukan up, seperti ada proses ev blok er melakukan wakeup dalam model
sebelumnya.
Sebagai samping, dalam kertas asli Dijkstra, ia menggunakan nama P dan V
bukannya bawah dan atas, masing-masing. Karena ini tidak memiliki
signifikansi mnemonic untuk orang-orang yang tidak berbicara signifikansi
Belanda dan hanya marjinal bagi mereka yang melakukan-proberen (mencoba)
dan Verhogen (menaikkan, membuat lebih tinggi) -kita akan menggunakan
istilah ke bawah dan sebagai gantinya. Ini pertama kali diperkenalkan pada
bahasa pemrograman Algol 68.
Memecahkan Masalah Producer-Consumer Menggunakan Semaphore
Semaphore memecahkan masalah hilang-wakeup, seperti ditunjukkan pada
Gambar. 2-28. Untuk membuat mereka bekerja dengan benar, adalah penting
bahwa mereka dilaksanakan dengan cara yang tak terpisahkan. Cara normal
adalah untuk menerapkan naik turun saat panggilan sistem, dengan sistem
operasi sebentar menonaktifkan semua menyela ketika sedang menguji
semaphore, memperbarui, dan menempatkan proses untuk tidur, jika perlu.
Karena semua tindakan ini mengambil hanya beberapa instruksi, tidak ada
salahnya dilakukan dalam menonaktifkan interupsi. Jika beberapa CPU yang
digunakan, masing-masing semaphore harus dilindungi oleh variabel kunci,

dengan TLS atau XCHG instruksi yang digunakan untuk memastikan bahwa
hanya satu CPU pada suatu waktu memeriksa semaphore.
Pastikan Anda memahami bahwa menggunakan TLS atau XCHG untuk
mencegah beberapa CPU mengakses semaphore pada saat yang sama sangat
berbeda dari produsen atau konsumen yang sibuk menunggu yang lain untuk
mengosongkan atau mengisi buffer. Operasi semaphore akan mengambil hanya
beberapa mikrodetik, sedangkan produsen atau konsumen mungkin mengambil
sewenang-wenang panjang.
Solusi ini menggunakan tiga Semaphore: satu disebut penuh untuk menghitung
jumlah slot yang penuh, yang disebut kosong untuk menghitung jumlah slot
yang kosong, dan satu disebut mutex untuk memastikan produsen dan
konsumen tidak mengakses buffer di waktu yang sama. Penuh awalnya 0,
kosong awalnya sama dengan jumlah slot di buffer, dan mutex awalnya 1.
Semaphore yang telah siap untuk melakukan 1 dan digunakan oleh dua atau
lebih proses untuk memastikan bahwa hanya satu dari mereka dapat memasuki
wilayah critical di waktu yang sama disebut Semaphore biner. Jika setiap proses
tidak turun sebelum memasuki kawasan kritis dan hanya setelah
meninggalkannya, saling pengecualian dijamin.
Sekarang bahwa kita memiliki komunikasi interprocess baik primitif yang kita
miliki, marilah kita kembali dan melihat urutan interrupt Gambar. 2-5 lagi.
Dalam sistem yang menggunakan Semaphore, cara alami untuk
menyembunyikan interupsi adalah memiliki semaphore, awalnya diatur ke 0,
yang terkait dengan setiap I / O device. Hanya setelah memulai perangkat I / O,
proses pengelolaan melakukan di atas semaphore terkait, sehingga
menghalangi segera. Ketika interupsi masuk, interrupt handler kemudian
melakukan up pada semaphore terkait, yang membuat proses yang relevan
siap dijalankan lagi. Dalam model ini, langkah 5 pada Gambar. 2-5 terdiri dari
melakukan pada semaphore perangkat, sehingga pada langkah 6 scheduler
akan dapat menjalankan device manager. Tentu saja, jika beberapa proses
sekarang siap, scheduler dapat memilih untuk menjalankan proses lebih
penting berikutnya. Kita akan melihat beberapa algoritma yang digunakan
untuk penjadwalan nanti dalam bab ini.
Dalam contoh pada Gambar. 2-28, kita telah benar-benar digunakan Semaphore
dalam dua cara yang berbeda. Perbedaan ini cukup penting untuk membuat
eksplisit. Mutex semaphore digunakan untuk saling pengecualian. Hal ini
dirancang untuk menjamin bahwa hanya satu proses pada suatu waktu akan
membaca atau menulis buffer dan variabel terkait. Mutual exclusion ini
diperlukan untuk mencegah kekacauan. Kami akan mempelajari saling
pengecualian dan bagaimana mencapainya pada bagian berikutnya.
Penggunaan lain dari Semaphore adalah untuk sinkronisasi. The Semaphore
penuh dan kosong yang diperlukan untuk menjamin bahwa urutan peristiwa
tertentu melakukan atau tidak terjadi. Dalam hal ini, mereka memastikan
bahwa produsen berhenti berjalan ketika buffer penuh, dan berhenti konsumen
berjalan ketika itu kosong. Penggunaan ini berbeda saling pengecualian.