Pengertian Spinlock dan Implementasinya

Multitasking adalah tantangan baru bagi programmer sistem operasi. Ada banyak macam resource yang harus digunakan oleh semua thread, namun jumlahnya terbatas, dan tidak mungkin diakses bersamaan. Untuk itu, masing-masing thread harus dapat diatur agar dapat mengaksesnya secara bergiliran secara sinkron.

Dalam hal ini, synchronization primitives adalah metode yang perlu diimplementasikan dalam sebuah sistem operasi. Synchronization primitives yaitu sebutan untuk metode yang dapat menjamin seluruh task dalam sistem multitasking agar dapat berjalan secara sinkron dalam pengaksesan sebuah resource.
 
void putchar(int chr){
   ...
}

void print(char * str){
   while (* str){
      putchar(*str);
      str++;
   }
}

Kode di atas adalah contoh sederhana, dimana programmer harus mulai mempertimbangkan untuk mengimplementasikansynchronization primitive. Bayangkan jika dua task mengakses print() secara hampir bersamaan dalam sistem multitasking. Belum sempat salah satu task mencetak satu per satu karakter dari string, tiba-tiba terjadi task switch ke task lain yang juga ingin menggunakan fungsi print().

task 1:
print (“hello”);
task 2:
print (“world”);

Tanpa sinkronisasi, bisa jadi yang akan tampil di layar terlihat kacau. Misalnya saja, apabila setiap baru saja mencetak sebuah karakter, terburu terjadi task switch, mungkin akan tampil seperti ini.

hweolrllod

Spinlock adalah salah satu metode sinkronisasi dengan menerapkan lock. Contohnya pada fungsi print() yang sudah dimodifikasi di bawah ini. Selama fungsi print() diakses oleh salah satu task, print_lock akan tetap bernilai 1. Task lain yang perlu mengakses print() wajib menunggu hingga task sebelumnya menyelesaikan print dan mengembalikan print_lock sehingga bernilai 0.

char print_lock;
void print(char * str){
   acquire_spinlock(&print_lock);
   while (* str){
      putchar(*str);
      str++;
   }
   release_spinlock(&print_lock);
}

Task yang lebih dahulu memanggil print() akan memanggilacquire_spinlock(). Fungsi ini akan meng-set variabel print_lock = 1 apabila print_lock masih bernilai 0, lalu segera melanjutkan eksekusi. Task lain yang berjalan bersamaan namun sedikit tertinggal, akan mengalami peristiwa busy-waiting ketika memanggil acquire_spinlock(), karena print_lock masih di-set bernilai 1 oleh task sebelumnya. Busy-waiting akan terus berlangsung hingga task sebelumnya memanggil release_spinlock(), sehingga meng-set print_lock = 0.

Algoritma
Acquire Spinlock:
1. Tunggu hingga lock bernilai 0.
2. Jika lock sudah 0, set lock = 1.

Release Spinlock:
1. Set lock = 0.

Implementasi
Sederhananya, acquire_spinlock() bisa saja ditulis dengan kode C semacam ini:
void acquire_spinlock(char * lock ){
   while (* lock != 0){
      //do nothing
      //busy-waiting
   }
   * lock = 1;
}

Akan tetapi, dalam dunia nyata, kode di atas jauh kurang efektif. Apalagi dalam keadaan thread yang cukup padat. Ini karena jika diuraikan, kode while() akan diterjemahkan compiler menjadi serangkaian instruksi assembly yang rumit.

tes:
cmp BYTE PTR [print_lock], 0
jne tes
mov BYTE PTR [print_lock], 1

Misalnya, katakanlah terdapat 3 task yang sama-sama melakukan acquire. Task 1 baru saja melepas print_lock. Sayangnya, setelah itu task 2 dan task 3 secara bersamaan baru saja selesai melakukan instruksi CMP yang memberikan sinyal bahwa print_lock sudah terlepas, namun sama-sama pula terjadi task switch sebelum menjalankan instruksi JNE. Akhirnya, task 2 dan task 3 lolos dari lock lalu mengakses fungsi print() secara bersamaan.
Kondisi seperti itu dapat dihindari dengan memanfaatkan atomic operation, yaitu dengan memanfaatkan instruksi assembly yang dapat melakukan acquire tanpa harus melakukan instruksi pembandingan (CMP) ataupun testing terlebih dahulu. Dalam arsitektur intel, ini bisa dilakukan dengan instruksi XCHG yang diinputkan melalui inline assembly.

tes:
mov al, 1
xchg BYTE PTR [print_lock], al
cmp al,1
je tes

Selama XCHG menghasilkan nilai 1, sudah diketahui bahwa print_lock masih dikuasai task lain, namun jika 0, artinya task sudah berhasil mengambil alih lock. Meskipun terjadi task switch antar banyak task, semuanya tidak akan dapat melewati taktik XCHG.

inline unsigned char _atomic_xchg8(unsigned char* lock, unsigned char x ){
   asm volatile("xchg %1, %0":"=r" (x):"m"(*(volatile unsigned char *)lock),"0" (x):"memory");
   return x;
}

inline void acquire_spinlock(unsigned char *lock){
   while ( 1){
      if ( _atomic_xchg8(lock, 1)== 0) return ;
      while (* lock != 0){
         asm("pause");
      }
   }
}

inline void release_spinlock(unsigned char *lock){
   * lock = 0;
}