Državno natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred)/ prvi dan - 3. zadatak

Dretva (eng. thread) je slijed instrukcija koje izvodi procesor kako bi izvršio određeni zadatak.

Današnji operacijski sustavi podržavaju višedretvenost (eng. multithreading), tj. omogućuju “paralelno” izvođenje više različitih dretvi.

Iako se čini da se izvršavanje različitih dretvi izvodi istovremeno, jednojezgreni procesor u svakom trenutku može izvoditi instrukcije samo jedne dretve, ali neprestano mijenja dretvu koju obrađuje dajući svakoj dretvi malo vremensko razdoblje u kojem se ona izvršava.

Pretpostavimo da imamo jedan takav operacijski sustav koji radi na jednojezgrenom procesoru.

Rad procesora se odvija u ciklusima koji su označeni prirodnim brojevima od 1 na dalje.

U sustavu će se tijekom vremena pojaviti n dretvi označenih brojevima od 1 do n.

Za svaku dretvu j je unaprijed poznat ciklus dj u kojem se ona raspoređuje na procesor te ukupan broj instrukcija tj od kojih se dretva sastoji.

Operacijski sustav u svojoj jezgri održava listu L koja sadrži sve dretve čije je izvršavanje započelo i još nije završilo, a na početku je ta lista prazna.

Dodatno, operacijski sustav održava pokazivač P koji pokazuje na dretvu u listi L koja je sljedeća na redu za izvršavanje (kada god je lista L prazna, pokazivač P ne pokazuje ni na koju dretvu).

Operacijski sustav u svakom ciklusu c ponavlja redom sljedeće korake:

1. Ako postoji dretva i koja se raspoređuje na procesor u trenutnom ciklusu (di = c) onda se i stavlja na kraj liste L.
2. Ako lista L nije prazna: (a) Izvršava se točno jedna instrukcija dretve j na koju trenutno pokazuje pokazivač P. (b) Pokazivač P se pomiče na sljedeću dretvu u listi, a ako je dretva j bila zadnja u listi, pokazivač se postavlja na prvu dretvu u listi. (c) Ako je izvršeno svih tj instrukcija dretve j onda se ona briše iz liste L.

U gornjim koracima svaki puta kada se u praznu listu L doda nova dretva, onda se pokazivač P namjesti tako da pokazuje na upravo dodanu dretvu.

Slično, kada nakon izbacivanja neke dretve lista ostane prazna, onda se P namjesti tako da ne pokazuje ni na koju dretvu.

Za svaku zadanu dretvu odredite ciklus u kojemu se izvršava njena zadnja instrukcija.

Možete pretpostaviti da je raspored takav da se nikada više dretvi ne raspoređuje na procesor u istom ciklusu (svi dj su različiti).

Ulazni​ podaci

U prvom redu nalazi se prirodni broj n (1 ≤ n ≤ 100 000) — broj dretvi.

U j-tom od sljedećih n redova nalaze se dva prirodna broja dj i tj (1 ≤ dj ≤ 2 · 109, 1 ≤ tj ≤ 109) — redom ciklus u kojem se dretva j raspoređuje na procesor te broj instrukcija dretve j.

Dretve su poredane redoslijedom kojim se raspoređuju na procesor, odnosno vrijedi d1 < d2 < . . . < dn.

Izlazni podaci

Ispišite n redova. U j-ti red ispišite ciklus u kojem se izvrši posljednja instrukcija dretve j.

Primjeri test​ podataka

Ulaz

5
1 1
2 2
3 3
4 3
5 2

Izlaz

1
3
10
11
9

Objašnjenje

Pojašnjenje prvog primjera: Sljedeća tablica sadrži stanje liste L neposredno nakon što je izvršen korak 1. odnosno korak 2. u svakom ciklusu.

U paru (a, b) prvi element je oznaka dretve, a drugi element broj instrukcija te dretve koje je još potrebno izvršiti.

Osjenčana je ona dretva na koju pokazuje pokazivač P. Primijetite da je moguće da se dretva rasporedi na procesor te da završi i bude brisana iz liste u jednom ciklusu.

Ulaz

4
1 4
3 2
5 8
7 6

Izlaz

5
6
20
18

Ulaz

5
2 2
3 1
6 3
7 2
9 2

Izlaz

3
4
9
10
12