Sistem Operasi Proses Sinkronisasi

Riva Kurnia Affandi
A11.2014.08185
A11.54507
Sinkronisasi adalah Akses bersama untuk berbagi dua bersama dapat mengakibatkan inkosistensi data. Pemeliharaan konsistensi data memerlukan mekanisme untuk memastikan eksekusi dari proses kerjasama.
capture
Masalah Sinkronisasi 
  • Race Conditon adalah situasi di mana beberapa proses mengakses dan memanipulasi data bersama pada saat besamaan.
  • Critical Section adalah sebuah segmen kode di mana sebuah proses yang mana sumber daya bersama diakses.
Critical Section mempunyai beberapa kode :
  • Entry Section : kode yang digunakan untuk masuk ke dalam critical section
  • Critical Section : Kode di mana hanya ada satu proses yang dapat dieksekusi pada satu waktu.
  • Exit Section: akhir dari critical section, mengizinkan proses lain.
  • Remainder Section : kode istirahat setelah masuk ke critical section.

Mengatasi masalah Critical Section, yaitu:

  •  Mutual exclutionJika proses sedang mengeksekusi critical section-nya maka tidak ada proses lain yang dapat mengeksekusi dalam critical section mereka.
  •  ProgressJika tidak ada proses yang sedang dieksekusi dalam critical section  dan ada beberapa proses yang ingin masuk ke critical section mereka, maka pemilihan proses yang akan masuk ke critical section berikutnya tidak bisa ditunda.
  • Bounded Waiting :Suatu keterikatan harus ada pada sejumlah proses yang diijinkan masuk ke critical section mereka, setelah adanya proses yang meminta masuk ke critical section dan sebelum  permintaan itu diterima.

Sistem Operasi Deadlock

Riva Kurnia Affandi
A11.2014.08185
A11.54507

Deadlock adalah suatu kondisi dimana 2 proses atau lebih tidak dapat meneruskan eksekusinya disebut juga seperti “hang”, karena proses tersebut saling memperebutkan resource dan saling menunggu pesan dan proses lain untuk waktu yang tidak terbatas lamanya.

deadlock

Penyebab Deadlock

– Mutual Exclusion

yaitu keadaan dimana hanya ada satu proses saja yang boleh memakai resource, proses yang lain harus menunggu sampai proses selesai. contoh buffering video.

– Hold and Wait

yaitu keadaan dimana suatu proses menunggu suatu resource dalam waktu yang lama hingga resource tersebut tidak terpakai oleh proses lainnya.

– No Pre-emption,

yaitu keadaan dimana suatu resource tidak boleh diambil begitu saja/secara paksa oleh proses yang lainnya sehingga suatu proses harus menunggu hingga proses yang sedang memakai resource telah selesai.

– Circular Wait,

yaitu suatu keadaan dimana proses yang lain membutuhkan resource yang sedang dipakai oleh suatu proses sehingga timbul antrian melingkar seperti halnya rantai.

Model Proses

Setiap proses yang menggunakan resource sumber Daya menjalankan urutan operasi.

Meminta Resource (Request) -> Menggunakan Resource (Use) ->Melepaskan Resource Release

 Mencegah Deadlock

Untuk mencegah deadlock dilakukan dengan meniadakan salah satu dari syarat perlu sebagai berikut :

– Mencegah Mutual Exclusion

Mutual exclusion benar-benar tidak dapat dihindari. Hal ini dikarenakan tidak ada resource yang dapat digunakan bersama-sama, jadi sistem harus membawa resource yang tidak dapat digunakan bersama-sama.

– Mencegah Hold and Wait

Mencegah hold and wait, sistem harus menjamin bila suatu proses meminta resource, maka proses tersebut tidak sedang memegang resource yang lain. Proses harus meminta dan dialokasikan semua resource yang diperlukan sebelum proses memulai eksekusi atau mengijinkan proses meminta resource hanya jika proses tidak membawa resource lain.

– Mencegah Non Preemption

Cara mencegah kondisi non preemption :

o Proses yang membawa beberapa resource meminta resource lain yang tidak dapat segera dipenuhi untuk dialokasikan pada proses tersebut, maka semua resource yang sedang dibawa proses tersebut harus dibebaskan.

o Proses yang sedang dalam keadaan menunggu, resource yang dibawanya ditunda dan ditambahkan pada daftar resource.

o Proses akan di restart jika dapat memperoleh resource yang lama dan resource baru yang diminta.

– Mencegah Kondisi Menunggu Sirkular

Sistem mempunyai total permintaan global untuk semua tipe resource. Proses dapat meminta proses kapanpun menginginkan, tapi permintaan harus dibuat terurut secara numerik. Setiap proses yang membutuhkan resource dan memintanya maka nomor urut akan dinaikkan. Cara ini tidak akan menimbulkan siklus. Masalah yang timbul adalah tidak ada cara pengurutan nomor sumber daya yang memuaskan semua pihak.

 

 

Mengganti Elemen List Menjadi 0 Jika Genap

Judul :
gantinol (L)
Definisi dan Spesifikasi :
gantinol : list of integer → list integer
{ gantinol(L) mengganti elemen List menjadi 0 jika genap }
Ralisasi :
Basis : jika list kosong nil
Rekurens: if (FirstElment L) genap, then konso 0 gantinol (Tail L)
else konso (FirstElment L)gantinol (Tail L)
Aplikasi:
(gantinol ‘(1 2 3 4 5 6 7 8 9))
(1 0 3 0 5 0 7 0 9)


(defun gantinol (L)
(cond ((null L) nil)
((evenp (car L))(cons 0 (gantinol (cdr L))))
(t (cons(car L)(gantinol (cdr L))))
)
)

gantinolgenap

Elemen Ganjil List

Judul :
ganjil (L)
Definisi dan Spesifikasi :
ganjil : list of integer → integer
{ ganjil(L) menghitung banyaknya angka ganjil dalam List }
Ralisasi :
Basis : jika list kosong 0
Rekurens: if (FirstElment L) ganjil, then + 1 ganjil (Tail L)
else ganjil (Tail L)
Aplikasi:
(ganjil ‘(1 2 3 4 5 6 7 8 9))
5


(defun ganjil (L)
(cond ((null L)0)
((oddp(car L))(+ 1 (ganjil(cdr l))))
(t(ganjil(cdr L)))
)
)

ganjil

Elemen Genap List

Judul :
genap (L)
Definisi dan Spesifikasi :
genap : list of integer → integer
{ genap(L) menghitung banyaknya angka genap dalam List }
Ralisasi :
Basis : jika list kosong 0
Rekurens: if (FirstElment L) genap, then + 1 genap (Tail L)
else genap (Tail L)
Aplikasi:
(genap ‘(1 2 3 4 5 6 7 8 9))
4


(defun genap (L)
(cond ((null L)0)
((evenp(car L))(+ 1 (genap(cdr l))))
(t(genap(cdr L)))
)
)

genaph

List Of List LISP

List Of List

Definisi :
List of list adalah list yang :
• mungkin kosong,
• mungkin terdiri dari sebuah elemen yang disebut atom dan sisanya adalah list of list,
• mungkin terdiri dari sebuah elemen berupa list dan sisanya adalah list of list
Jadi List of List adalah list S yang elemennya adalah list dan atom
Untuk membedakan antara list dengan atom: List dituliskan di antara tanda kurung (),
sedangkan Atom dituliskan tanpa tanda kurung
Contoh List :
[ ] adalah list kosong
[ad , a , b ] adalah list dengan elemen berupa 3 atom
[ [ ], [a ,b ,c] ,[ d ,e] ,f ] adalah :
list dengan elemen list kosong, L1, L2 dan sebuah atom
L1 adalah list dengan elemen 3 buah atom a, b, c
L2 adalah list dengan elemen 2 buah atom d,e
Untuk list khusus ini, nama Konstruktor dan Selektor tidak dibedakan dengan list yang
hanya mengandung elemen dasar, namun diperlukan predikat tambahan sebagai berikut:
yaitu untuk mengetahui apakah sebuah ekspresi adalah Atom atau List.
Atom dapat berupa:
– atom numerik (yang dapat dipakai sebagai operan dalam ekspresi aritmatik)
– atom simbolik

TYPE LIST-OF-LIST
Definisi dan Spesifikasi Predikat Khusus Untuk List Of List:
IsEmpty : list of list → boolean
{IsEmpty(S) benar jika S adalah list of list kosong}
IsAtom : list of list → boolean
{IsAtom(S) menghasilkan true jika list adalah atom, yaitu terdiri dari sebuah atom }
IsList : list of list → boolean
{ IsList(S) menghasilkan true jika S adalah sebuah list (bukan atom)}
Definisi dan Spesifikasi Konstruktor :
KonsLo : List, List of list → List of list
{ KonsLo(L,S) diberikan sebuah List L dan sebuah List of List S, membentuk list baru
dengan List yang diberikan sebagai elemen pertama List of list: L o S → S’}
KonsL• : List of list , List → List of list
{KonsL• (S,L) diberikan sebuah List of list S dan sebuah list L, membentuk list baru
dengan List yang diberikan sebagai elemen terakhir list of List: S • L → S’}
Definisi dan Spesifikasi Selektor :
FirstList: List of list tidak kosong → List
{FirstList(S) Menghasilkan elemen pertama list, mungkin sebuah list atau atom }
TailList : List of list tidak kosong → List of list
{TailList(S) Menghasilkan “sisa” list of list S tanpa elemen pertama list S }
LastList : List of list tidak kosong → List of list
{LastList(S) : Menghasilkan elemen terakhir list of list S, mungkin list atau atom }
HeadList : List of list tidak kosong → List of list
{HeadList(S) Menghasilkan “sisa” list of list tanpa elemen terakhir list }

;Predikat
(defun IsEmpty (S) ;benar jika S adalah list of list kosong
(null S)
)
(defun IsOneElmt (S) ;benar jika S adalah list of list yang terdiri dari 1 elemen
(and (not (isEmpty S)) (null (cdr S)))
)
(defun IsAtom (S) ;benar jika S terdiri dari sebuah atom
(atom S)
)
(defun IsList (S) ;benar jika S menghasilkan sebuah List
(listp S)
)
;konstruktor
(defun KonsLo (L S) ;menambahkan List L kedalam List of List S, dan List L menjadi elemen pertama List of list
(cons L S)
)
(defun KonsL. (S L) ;menambahkan List L kedalam List of List S, dan List L menjadi elemen Terakhir List of List
(append S L)
)
;selektor
(defun firstList (S) ;menghasilkan elemen pertama list yang mungkin sebuah list atau atom
(car S)
)
(defun TailList (S) ;menghasilkan “sisa” list of list tanpa elemen pertama list S
(cdr S)
)
(defun LastList (S) ;menghasilkan elemen terakhir list yang mungkin sebuah list atau atom
(car (reverse S))
)
(defun HeadList (S) ;menghasilkan “sisa” list of list tanpa elemen terakhir list S
(reverse (cdr (reverse S)))
)

lol1
lol2

Himpunan (Set) LISP

Himpunan(set)

Definisi :
Himpunan (set) adalah sebuah list yang setiap elemennya hanya muncul sekali (unik). List
“kosong” adalah himpunan kosong.
Contoh :
[apel, jeruk, pisang] adalah himpunan
[jeruk, jeruk, mangga, jeruk, pisang, apel] bukan himpunan

TYPE SET (HIMPUNAN)
Definisi dan Spesifikasi Type :
{Set adalah List dengan tambahan syarat bahwa tidak ada elemen yang sama }
{ Semua konstruktor, selektor dan fungsi pada List berlaku untuk Himpunan }
Definisi dan Spesifikasi Konstruktor Himpunan dari List :
{ Himpunan dibentuk dari list }
MakeSet (L) : list → set
{ membuat sebuah set dari sebuah list }
{ yaitu membuang semua kemunculan yang lebih dari satu kali}
{ List kosong tetap menjadi list kosong }
Definisi dan Spesifikasi Predikat:
IsSet : list → boolean
{ IsSet(L) true jika L adalah set }
IsSubSet : 2 set → boolean
{ IsSubSet (H1,H2) true jika H1 adalah subset dari H2: semua elemen H1 adalah juga
merupakan elemen H2 }
Definisi dan Spesifikasi Operasi Terhadap Himpunan :
MakeIntersect : 2 set → set
{ Intersect (H1,H2) membuat interseksi H1 dengan H2 : yaitu set baru dengan anggota
elemen yang merupakan anggota H1 dan juga anggota H2 }
MakeUnion : 2 set → set
{ Union (H1,H2) membuat union H1 dengan H2 : yaitu set baru dengan semua anggota
elemen H1 dan anggota H2 }
Untuk kasus himpunan berikut, dibutuhkan beberapa fungsi terhadap list sebagai berikut :
IsMember : elemen, list → boolean
{ IsMember(e,L) true jika e adalah elemen list L }
Rember : elemen, list → list
{ Rember (x,L) menghapus sebuah elemen bernilai x dari list }
{ list yang baru berkurang SATU elemennya yaitu yang bernilai e }
{ List kosong tetap menjadi list kosong }
MultiRember : elemen, list → list
{ MultiRember (x,L) menghapus semua elemen bernilai x dari list }
{ list yang baru tidak lagi mempunyai elemen yang bernilai x }
{ List kosong tetap menjadi list kosong }

Realisasi dalam Lisp

;Konstruktor
(defun konso (e L) ;menambahkan satu elemen didepan suatu Liat
(cons e L)
)
(defun kons (e L) ;menambahkan satu elemen dibelakang suatu List
(reverse (cons e (reverse L)))
)
;Selektor
(defun firstElmt (L) ;memanggil elemen pertama dari suatu List
(car L)
)
(defun tail (L) ;memanggil semua elemen yang berada dibelakang elemen pertama
(cdr L)
)
(defun lastElmt (L) ;memanggil elemen terakhir dalam suatu list
(car (reverse L))
)
(defun Head (L) ;memanggil semua elemen sebelum elemen terakhir
(reverse (cdr (reverse L)))
)
(defun IsEmpty (L) ;memastikan apakah L suatu List kosong atau bukan
(null L)
)
(defun Makeset (L) ;membuat suatu set
(cond ((isEmpty L) nil)
((IsMember (firstElmt L) L) (konso (firstElmt L) (Makeset (Multirember (firstElmt L) L))))
(t (konso (firstElmt L) (Makeset (tail L))))
)
)
(defun IsSet (L) ;Benar jika L adalah set
(if (equal (Makeset L) L)
t
nil
)
)
(defun IsSubset (H1 H2) ;benar jika semua elemen H1 sama dengan H2
(cond ((IsEmpty H1) t)
((IsMember (firstElmt H1) H2) (IsSubset (tail H1) H2))
(t nil)
)
)
(defun MakeIntersect (H1 H2) ;membuat set baru dengan anggota elemen yang merupakan anggota H1 dan anggota H2 yang sama
(cond ((isEmpty H1 ) nil)
((IsMember (firstElmt H1) H2) (konso (firstElmt H1) (MakeIntersect (tail H1) H2)))
(t (MakeIntersect (tail H1) H2))
)
)
(defun MakeUnion (H1 H2) ;Membuat set baru dengan semua anggota dari semua anggota H1 dan H2
(cond ((isEmpty H1) H2)
((IsMember (firstElmt H1) H2) (konso (firstElmt H1) (MakeUnion (tail H1) (Multirember (firstElmt H1) H2))))
(t (konso (firstElmt H1) (MakeUnion (tail H1) H2)))
)
)
;Fungsi Bantu
(defun IsMember (x L) ;Bernilai benar jika Nilai x berada di dalam List
(cond ((IsEmpty L) nil)
((equal x (firstElmt L)) t)
(t (IsMember x (tail L)))
)
)
(defun Multirember (x L) ;Menghapus semua elemen bernilai x pada List
(cond ((isEmpty L) nil)
((equal (firstElmt L) x) (Multirember x (tail L)))
(t (konso (firstElmt L) (Multirember x (tail L))))
)
)
(defun rember (x L) ;Menghapus Sebuah elemen bernilai x pada List
(cond ((isEmpty L) nil)
((equal (firstElmt L) x) (tail L))
(t (konso (firstElmt L) (Rember x (tail L))))
)
)

himpunanbro

List Of Integer LISP

List Of Integer

Definisi :
Integer adalah himpunan angka yang tak terhingga
Definisi rekursif list integer
Basis: List kosong adalah list bilangan integer
Rekurens : list bilangan integer dibuat dengan cara menambahkan sebuah integer pada
list bilangan integer.

Definisi dan Spesifikasi Type :
type List of integer
(Definisi: list yang elemennya integer, menambahkan sebuah integer pada list bilangan integer )
Definisi dan Spesifikasi Konstruktor:
Konso : integer, List of integer tidak kosong → List of integer
{Konso(e,L): menghasilkan sebuah list dari e dan L, dengan e sebagai elemen
pertama e : e o L → L’}
Kons• : List of integer tidak kosong, integer → List of integer
{ Kons(L,e): menghasilkan sebuah list dari L dan e, dengan e sebagai elemen terakhir
list : L • e → L’}

Definisi dan Spesifikasi Selektor:
FirstElmt: List of integer tidak kosong → integer
{FirstElmt(L) Menghasilkan elemen pertama list L }
Tail : List of integer tidak kosong → List of integer
{Tail(L) : Menghasilkan list tanpa elemen pertama list L }
LastElmt : List of integer tidak kosong → integer
{LastElmt(L) : Menghasilkan elemen terakhir list L }
Head : List of integer tidak kosong → List of integer
{Head(L) : Menghasilkan list tanpa elemen terakhir list L}

Realisasi dalam Lisp

(defun konso(e L) ;menghasilkan sebuah list dari e dan L, dengan e sebagai elemen pertama
(cons e L)
)
(defun kons(L e) ;menghasilkan sebuah list dari L dan e, dengan e sebagai elemen terakhir
(reverse (cons e (reverse L)))
)
(defun firstelmt(L) ;Menghasilkan karakter pertama Teks L
(car L)
)
(defun tail(L) ;Menghasilkan list tanpa elemen pertama Teks L
(cdr L)
)
(defun lastelmt(L) ;Menghasilkan karakter terakhir Teks L
(car (reverse L))
)
(defun head(L) ;Menghasilkan list tanpa elemen terakhir Teks L
(reverse (cdr (reverse L)))
)

loi
Contoh penggunaan List Of Integer
Judul :
genap (L)
Definisi dan Spesifikasi :
genap : list of integer → integer
{ genap(L) menghitung banyaknya angka genap dalam List }
Ralisasi :
Basis : jika list kosong 0
Rekurens: if (FirstElment L) genap, then + 1 genap (Tail L)
else genap (Tail L)

;mencari banyaknya angka genap dalam list of int
(defun genap ( L)
(cond((null L)0)
((evenp(car L) )(+ 1 (genap (cdr L))))
(t(genap(cdr L)))
)
)

List Of Integer.mp4_snapshot_03.01_[2015.06.23_17.00.33]

List Of Character LISP

List of Character

Definisi :
Teks adalah list yang elemennya terdiri dari karakter. Karakter adalah himpunan terhingga dari ‘a’…’z’, ‘A’…’B’, ‘0’…’9′
Definisi Rekursif terdiri dari Basis dan Rekuren
Basis : Teks Kosong adalah teks
Rekurens : Teks dapat dibentuk dengan menambahkan sebuah karakter pada teks

Definisi dan Spesifikasi Type :
type Teks : List of character
(Definisi Teks : sesuai dengan definisi rekursif di atas )

Definisi dan Spesifikasi Konstruktor:
Konso : character, Teks → Teks
Konso (e,T): menghasilkan sebuah list dari e dan L, dengan e sebagai elemen
pertama e : e o L → L’
Kons : Teks, character → Teks
Kons (L,e): menghasilkan sebuah list dari T dan e, dengan e sebagai elemen terakhir
teks : L • e → L

Definisi dan Spesifikasi Selektor:
FirstChar: Teks tidak kosong → character
FirstElmt(L) Menghasilkan character pertama Teks L
Tail : Teks tidak kosong → Teks
Tail(L) : Menghasilkan list tanpa elemen pertama Teks L
LastChar : Teks tidak kosong → character
LastElmt(L) : Menghasilkan character terakhir Teks L
Head : Teks tidak kosong → Teks
Head(L) : Menghasilkan list tanpa elemen terakhir Teks L

Realisasi dalam Lisp

(defun konso(e L) ;menghasilkan sebuah list dari e dan L, dengan e sebagai elemen pertama
(cons e L)
)
(defun kons(L e) ;menghasilkan sebuah list dari L dan e, dengan e sebagai elemen terakhir
(reverse (cons e (reverse L)))
)
(defun firstelmt(L) ;Menghasilkan karakter pertama Teks L
(car L)
)
(defun tail(L) ;Menghasilkan list tanpa elemen pertama Teks L
(cdr L)
)
(defun lastelmt(L) ;Menghasilkan karakter terakhir Teks L
(car (reverse L))
)
(defun head(L) ;Menghasilkan list tanpa elemen terakhir Teks L
(reverse (cdr (reverse L)))
)

loc 1

Contoh penggunaan List Of Character
Judul :
Hitchar (L)
Definisi dan Spesifikasi :
Hitchar : Teks → integer > 0
{ Hitchar(L) menghasilkan banyaknya kemunculan ‘char1’ dalam List }
Ralisasi :
Basis : jika list kosong 0
Rekurens: if (FirstElment L) = char1, then + 1 Hitchar char1 (Tail L)
else Hitchar char1 (Tail L)

;mencari banyaknya char dalam list of char
(defun hitChar (char1 L)
(cond((null L)0)
((eq(car L) char1)(+ 1 (hitChar char1 (cdr L))))
(t(hitChar char1(cdr L)))
)
)

loc2