Асинхронные исключения
Ваша задача — симулировать работу машины под названием 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, выведите информацию обо всех потоках, которые завершились до превышения емкости, а затем выведите "<>". Если нет, и если есть один или более потоков, не завершившихся к концу симуляции, выведите информацию обо всех завершившихся потоках, а затем выведите "<>". В противном случае (т.е. когда все потоки завершаются в течение времени), просто выведите информацию обо всех потоках. Все кавычки даны для ясности.
Информация о потоках должна быть записана в порядке возрастания идентификатора потока, по одной на строку. Информация об одном потоке обозначается двумя целыми числами, идентификатором потока и временем его завершения, разделенными одним пробелом.