В вычислительных системах с одним центральным процессором в каждый момент времени центральный процессор может осуществлять вычисления только одного из процессов. Многозадачные операционные системы, поддерживающие одновременно несколько процессов, разделяют ресурс центрального процессора между процессами, поочередно предоставляя каждому из процессов определенное время использования центрального процессора, тем самым реализуя 9 «псевдопараллельное» выполнение этих процессов. Правило, по которому ресурс распределяет время между несколькими потребителями, называется дисциплиной обслуживания.
Одной из распространенных дисциплин обслуживания для управления ресурсом центрального процессора в операционных системах является круговая очередь (Round Robin). Каждому процессу, находящемуся в этой очереди, присвоен порядковый номер. Операционная система сначала дает процессу с минимальным номером использовать центральный процессор в течение заданного периода времени, называемого квантом непрерывного выполнения. По истечении этого кванта, операционная система предоставляет такой же по продолжительности квант непрерывного выполнения процессу со следующим по возрастанию номером. Если закончился квант непрерывного выполнения процесса с максимальным номером из этой очереди, следующий квант предоставляется опять процессу с минимальным номером и так далее. Если процесс завершил вычисления, он выбывает из очереди. При этом если он не использовал полностью последний квант непрерывного выполнения, операционная система не дожидается окончания кванта и предоставляет новый квант непрерывного выполнения следующему по круговой очереди процессу.
Продолжительность кванта непрерывного выполнения и продолжительность вычислений на центральном процессоре, необходимую каждому процессу, можно измерять в условных единицах – тактах. Например, если процессу P0 нужно до завершения периода вычислений 12 тактов, а квант непрерывного выполнения составляет 5 тактов, то в общей сложности квант непрерывного выполнения должен быть предоставлен такому процессу 3 раза, причем в последний раз он завершит вычисления до окончания выделенного кванта. Для передачи кванта непрерывного выполнения следующему процессу операционная система должна выполнить ряд служебных операций, затрачивая на них фиксированное количество тактов. Это количество тактов одинаково при любой операции передачи кванта непрерывного исполнения другому процессу, в том числе, если предыдущий процесс завершился, не использовав полностью свой квант непрерывного выполнения. Если передача кванта непрерывного выполнения происходит тому же процессу, который перед этим выполнялся, поскольку в очереди не осталось других процессов, операционная система не затрачивает на такую передачу дополнительных тактов и очередной квант непрерывного выполнения этого процесса начинается сразу же после окончания предыдущего.
Для оценки производительности часто используется показатель среднее время выполнения процессов. Для каждого процесса определяется полное время выполнения процесса – время от его появления в очереди до завершения его вычисления в последнем предоставленном ему кванте непрерывного выполнения. Это время включает в себя как такты, на протяжении которых он вычислялся на центральном процессоре, так и такты, которые он ожидал своей очереди на вычисление. Времена полного выполнения всех процессов суммируются и делятся на количество процессов. В результате получается среднее время выполнения процессов. Этот показатель зависит от выбранной продолжительности кванта непрерывного выполнения.
Задача. В начальный момент времени очередь образовали одновременно появившиеся три процесса, которым присвоены номера P0, P1 и P2. При этом процессу P0 требуется до завершения периода вычислений 59 тактов, процессу P1 – 29 тактов, а процессу P2 – 11 тактов.
Время, необходимое операционной системе на передачу кванта непрерывного выполнения очередному процессу составляет 2 такта. В начальный момент времени операционная система сразу же предоставляет квант непрерывного выполнения процессу P0, не затрачивая дополнительных тактов на передачу кванта непрерывного выполнения.
Определите, при какой продолжительности кванта непрерывного выполнения, среднее время выполнения этих процессов окажется минимальным. В ответе укажите целое число – количество тактов в этом кванте непрерывного выполнения.