КДП/К 2022
Колоквијум 2022. године за РТИ одржан је 26. новембра. Поставка овог рока није доступна на страници предмета. Проблем је био да се направи недвосмислена поставка другог задатка. Решења су имала рекордан број мртвих и живих блокирања.[1]
1. задатак
Поставка
Користећи мониторе са Signal and wait дисциплином решити проблем берберина који спава (The Sleeping Barber Problem). Берберница се сатоји од чекационице са n=5 столица и берберске столице на којој се људи брију. Уколико нема муштерија, брица спава. Уколико муштерија уђе у бербеницу и све столице су заузете, муштерија не чека, већ одмах излази. Уколико је берберин заузет, а има слободних столица, муштерија седа и чека да дође на ред. Уколико берберин спава, муштерија га буди. Обезбедити да се муштерије опслужују по редоследу доласка. Условне променљиве нису FIFO нити имају приоритетне редове чекања.
Решење
Видети презентације са предавања.
2. задатак
Поставка
Посматра се један узак и релативно кратак пут кроз кањон, којим пролазе каубоји и Индијанци. Ако њиме пролазе само каубоји или само Индијанци, они ће бити фини и проћи ће једни поред других. Ако кроз клисуру желе да прођу и каубоји и Индијанци, примењује се "закон јачег", тј. оних којих има више имају првенство пролаза кроз кањон. Треба обезбедити да једном добијено првенство не важи заувек - када се однос снага промени, треба забранити долазак нових особа које су до тада биле бројније, како би они други (сада бројнији[2]) могли да добију првенство проласка кроз кањон. Коритећи условне критичне регионе написати програм који решава овај проблем. [3]
Решење
Напомене
- ↑ За блокирања која се јављају у само одређеним сутацијама скидано је шест и по поена, а за потпуна блокирања десет поена. За изгладњивање је у просеку скидано осам поена.
- ↑ Гледа се збира броја који чека и оних који су у кањону
- ↑ На увиду је асистенткиња објаснила да је било замишљено (мада се и сама сложила не нужно написано) да уколико је дошло до промене првенства, сви који су до тада чекали треба да прођу пре обртања права првенства, без обзира на бројно стање.