Асинхронні винятки
Ваше завдання — симулювати роботу машини під назвою ACM (Асинхронна Обчислювальна Машина), щоб визначити, скільки часу потрібно кожній програмі для завершення своєї роботи. Це допомагає виявляти несподівану поведінку потоків, таку як гонки та взаємоблокування.
ACM має багато обчислювальних блоків і може запускати багато потоків одночасно. Вона використовує глобальний планувальник, який підтримує всі потоки, призначає потік на кожен обчислювальний блок і керує всіма семафорами. Кожен потік має свій власний ідентифікатор і може перебувати в одному з трьох станів: ВИКОНАННЯ, ГОТОВИЙ і ОЧІКУВАННЯ. Глобальний планувальник має одну чергу потоків, яка містить усі потоки в стані ГОТОВИЙ.
Пояснення програми
Програма складається з одного або більше блоків коду. Кожен блок коду містить список операцій ACM, включаючи фактичні обчислення та створення потоків. Кожен потік виконує операції лише в одному з наданих блоків коду, і він виконує операції зверху вниз блоку, якщо не отримує сигнал killThread від інших потоків.
Пояснення операцій
Програма симуляції ACM симулює 9 операцій. Тут я описую їх усі. Зверніть увагу, що слово, укладене в [], повинно мати якусь фактичну назву або значення.
compute [clock]
Витратити [clock] тактів на обчислення. Коли ця операція переривається після витрати T тактів іншими потоками або планувальником і відновлюється пізніше, вона споживає [clock] - T тактів.
[thread-var] <- forkR [code block]
Створити нативний потік, що виконується на [code block] і зберегти його ідентифікатор у змінній потоку [thread-var]. Він може виконуватися одночасно з будь-якими потоками, які створені в іншому обчислювальному блоці. Якщо [thread-var] вже використовувався в потоці, його попереднє значення перезаписується і втрачається. (Це означає, що ми не зможемо звертатися до потоку, хоча він може виконуватися вічно.)
[thread-var] <- forkI [code block]
Створити віртуальний потік, що виконується на [code block] і зберегти його ідентифікатор у змінній потоку [thread-var]. Віртуальний потік ділиться деякими ресурсами ОС зі своїм батьківським потоком, тому вони не можуть виконуватися одночасно, навіть якщо є вільні обчислювальні блоки. Це обмеження застосовується до будь-яких двох потоків, які безпосередньо або опосередковано пов'язані відносинами батько-дитина forkI. Якщо [thread-var] вже використовувався в потоці, його попереднє значення перезаписується і втрачається.
yield
Перевести поточний потік зі стану виконання в стан готовності. Потік переходить в кінець черги потоків.
killThread [thread-var]
Надіслати сигнал завершення потоку [thread-var]. [thread-var] гарантовано використовується в операціях forkR або forkI в тому ж блоці коду до цієї операції. Коли потік отримує сигнал завершення, він негайно скасовує свої запити на ресурси за допомогою блокування, переходить у стан готовності, якщо він знаходиться в стані блокування, і завершує свою операцію, коли він у стані виконання. Ця операція не змінює значення семафорів. Якщо цільовий потік вже завершився, ця операція нічого не робить.
lock [semaphore name] [amount]
Запитати [amount] семафора [semaphore name]. Якщо значення [semaphore name] більше або дорівнює [amount], просто віднімає [amount] із змінної семафора. В іншому випадку операція блокує поточний потік, поки змінна не стане більше або дорівнює [amount]. Як тільки змінна стає більше або дорівнює [amount], потік переходить у стан ГОТОВИЙ і переходить у чергу потоків після віднімання [amount] із змінної. Якщо є більше одного потоку, які запитують той самий семафор, потік, який першим заблокував семафор, завжди отримує стан ГОТОВИЙ першим. Отже, інші потоки не отримають стан ГОТОВИЙ, навіть якщо змінна семафора задовольняє їхні вимоги. Якщо є більше одного потоку, які отримують стан ГОТОВИЙ, потік, який раніше заблокував семафор, переходить у чергу першим.
unlock [semaphore name] [amount]
Додати [amount] до [semaphore name]. Значення семафорів можуть бути більшими за початкові значення. Потік не блокується цією операцією.
loop [loop count]
Виконати фрагмент коду між loop і відповідною командою next [loop count] разів.
next
Це відповідає команді loop у тому ж блоці коду. Фрагмент коду між loop і next повинен бути виконаний.
end
Завершити операцію. Ця команда з'являється лише в кінці блоку коду, і кожен блок коду має цю операцію в кінці.
Кожен параметр повинен бути або назвою, або цифрою. Назва — це алфавітний рядок (чутливий до регістру), і його довжина не перевищує 200. Ось деякі пояснення.
[thread-var]
Це назва. Вона відноситься лише до ідентифікатора в тому ж потоці. Кожен потік має своє значення, навіть якщо воно має ту ж назву.
[clock]
Це невід'ємне ціле число, яке не перевищує 1000.
[semaphore-name]
Це назва.
[amount]
Це невід'ємне ціле число, яке не перевищує 1000.
[loop count]
Це невід'ємне ціле число, яке не перевищує 1000.
Крім того, ви можете припустити наступні обмеження.
Загальна кількість рядків, які всі потоки оцінюють протягом симуляції, ніколи не перевищує 100000.
Розмір вхідного файлу ніколи не перевищує 100KB.
Пояснення симулятора
Потоки призначаються на ЦП, коли
починається симуляція. (Потік призначається на ЦП 1. Його блок коду — це перший блок коду вхідних даних.)
є більше одного потоку, які знаходяться в стані готовності, які можуть бути призначені на ЦП. (Потоки призначаються в порядку черги потоків. Якщо є більше одного ЦП, які можуть бути призначені на потік, вибирається найменший ЦП.)
крок часу є кратним часовому інтервалу. (Якщо на ЦП є потік, який знаходиться в стані виконання, потік переходить у стан готовності в порядку зростання ідентифікатора ЦП. Після цього потоки призначаються на кожен ЦП в порядку зростання ідентифікатора ЦП.)
На кожному кроці симулятор виконує кругове витіснення (коли крок часу є кратним часовому інтервалу), виконує операції кожного поточного потоку і збільшує крок часу. Коли виконується операція обчислення, потік отримує час обчислення. Потік, який має час обчислення більше 0, не може виконувати жодних операцій. Після кожного кроку симулятор зменшує позитивний час обчислення кожного поточного потоку.
Операції, виконані на тому ж кроці часу, виконуються в порядку зростання ідентифікатора ЦП. На тому ж кроці часу ідентифікатор ЦП операції більше або дорівнює ідентифікаторам ЦП операцій, які вже були виконані.
Крок часу починається з 0.
Вхідні дані
Вхід складається з декількох тестових випадків.
Кожен тестовий випадок починається з рядка, що містить два цілі числа, розділені пробілом. Вони означають кількість кроків часу симуляції та максимальну кількість потоків, які здатна обробити ACM, відповідно. Наступний рядок містить одне ціле число, яке вказує кількість доступних ЦП. Наступний рядок має ціле число, що означає часовий інтервал планувальника.
Опис семафорів слідує. Він починається з кількості семафорів, за яким слідує інформація про кожен семафор, по одному на рядок. Інформація про семафор складається з алфавітного рядка (чутливого до регістру) і цілого числа, які вказують назву семафора та його початкове значення, відповідно.
Нарешті, надані блоки коду. Спочатку йде кількість блоків коду, а потім описується кожен блок коду. Перший рядок опису кожного блоку коду — це назва блоку (алфавітний рядок, чутливий до регістру), за яким слідує двокрапка (:). Наступні рядки описують вміст блоку коду. Блок коду — це масив операцій, описаних вище, і одна операція записується в один рядок. Ви можете припустити, що кожен блок коду завжди закінчується операцією 'end'.
Вхід завершується двома нулями, розділеними пробілом.
Обмеження
Є 1 черга потоків.
Ідентифікатор n-го створеного потоку — це n.
Ідентифікатори ЦП — це 1 до кількості ЦП.
Кількість кроків часу не перевищує 1000.
Максимальна кількість потоків не перевищує 1000.
Кількість ЦП не перевищує 100.
Часовий інтервал не перевищує 1000.
Кількість семафорів не перевищує 1000.
Кількість блоків коду не перевищує 1000.
Вихідні дані
Для кожного тестового випадку надрукуйте його номер на першому рядку.
Якщо кількість живих потоків перевищує можливості ACM, вкажіть інформацію про всі потоки, які завершилися до перевищення можливостей, а потім вкажіть "<>". Якщо ні, і якщо є один або більше потоків, які не завершилися в кінці симуляції, вкажіть інформацію про всі завершені потоки, а потім вкажіть "<>". В іншому випадку (тобто коли всі потоки завершуються в межах часу), просто вкажіть інформацію про всі потоки. Усі лапки наведені для ясності.
Інформація про потоки повинна бути записана в порядку зростання ідентифікатора потоку, по одному на рядок. Інформація про один потік позначається двома цілими числами, ідентифікатором потоку та часом його завершення, розділеними одним пробілом.