LAB4B. Barijera++

Obična barijera (primjer) ima sučelja:

1. bar_init(B, N) koja inicijalizira barijeru B za N dretvi
2. bar_wait(B) koju poziva dretva
   1. poziv blokira dretvu ako to nije zadnja N-ta koja je došla na barijeru
   2. ne blokira dretvu ako je to zadnja N-ta koja je došla na barijer, ali pritom odblokira svih N-1 dretvi koje su već blokirane; također "resetira" barijeru za idući korak

Uobičajeno korištenje takve barijere od skupa N-dretvi:

početna dretva prije stvaranja novih:
	bar_init(B, N)
	inicijaliziraj sve ostalo
	stvori dretve

radna dretva (I):
	petlja
		x = uzmi_dio_problema(I)
		y = generiraj_rješenje(x)
		bar_wait(B)

Ideja proširenja jest da se proširi semantika bar_wait() na način da on ne blokira uvijek. Naime, ako ostale dretve još nisu gotove i ova bi možda mogla iskoristiti još vremena za pronalazak boljeg rješenja.

	petlja
		x = uzmi_dio_problema(I)
		(y, k) = generiraj_početno_rješenje(x)
		//k=0 nije još optimalno, k=1 optimalno je
		dok je (bar_wait(B, k) != 0)
			(y, k) = optimiraj(x, y, k)

Poziv bar_wait(B, k):

• jednak prethodnom ako je k = 1 (i vrati 0 nakon odblokiranja)
• kada je k = 0:
  • ako je na barijeri već N-1 dretva (sve čekaju!), onda je korak gotovo, sve pusti i vrati 0
  • ako je do barijere već došlo već N-1 dretvi (sve su izračunale bar početno rješenje, ali neke možda još optimiraju svoje), onda blokiraj ovu dretvu i pri odblokiranju vrati joj 0
  • ako do barijere nisu došle sve dretve, onda zapamti da je ova izračunala početno rješenje, ali ne blokiraj ovu dretvu već vrati 1

Osmisliti i ostvariti algoritam barijere prema opisanome. Novi mehanizam ostvariti postojećima, npr. monitorom (mutex_lock, cond_wait, ...).

Primjerima pokazati rad programa. Koristiti prave dretve, ne simulirati.