Shpori_na_ekzamen_OS

101

16. Мультимедийные операционные системы

Мультимедийные файлы

В большинстве систем обычный текстовый файл состоит из линейной последовательности байтов без какой-либо структуры, о которой знала бы операционная система. В мультимедиа ситуация гораздо более сложная. Во-первых, видеои аудиоданные полностью различны. Они вводятся совершенно разными устройствами, у них различная внутренняя структура, и воспроизводятся они также различными устройствами.

Более того, большинство фильмов сегодня нацелено на всемирную аудиторию, немалая часть которой не говорит по-английски. Последняя проблема решается одним из двух способов. Для некоторых стран производится дополнительная звуковая дорожка, с голосами, дублированными на местном языке. Так же используются субтитры. В результате цифровой фильм может оказаться состоящим из большого количества файлов: видеофайла, нескольких аудиофайлов и нескольких текстовых файлов с субтитрами на различных языках. Таким образом, файловая система должна следить за несколькими «субфайлами». Одна возможная схема заключается в том, что каждый субфайл хранится как обычный файл (например, при помощи i-узла, в котором хранятся номера всех его блоков), а все субфайлы описываются новой структурой. Другой способ состоит в создании новой разновидности двумерного i-узла, в котором в каждой колонке перечисляются блоки каждого субфайла. В общем, организация должна предоставлять зрителю возможность при просмотре фильма динамически выбирать звуковые дорожки и субтитры.

Во всех случаях необходим некий способ синхронизации субфайлов, чтобы любая звуковая дорожка соответствовала изображению. Если изображение и звук хотя бы слегка рассинхронизируются, зритель будет слышать слова актера до или после движения его губ, что легко определяется и довольно сильно раздражает зрителя.

Кодирование звука

Когда акустическая волна воздействует на микрофон, микрофон формирует электрический сигнал, представляющий амплитуду звука в виде функции времени. Человеческое ухо слышит сигналы в диапазоне частот от 20 до 20 000 Гц. Наше ухо слышит логарифмически, поэтому сила звука обычно измеряется в логарифмах отношения амплитуд, например в децибелах (дБ):

дБ = 20 log 10(A/B).

Аудиоволны могут преобразовываться в цифровую форму при помощи аналоговоцифрового преобразователя (АЦП). АЦП принимает на входе электрическое напряжение и формирует двоичное число на выходе. На рис. 7.3, а показан пример синусоидальной волны. Чтобы представить этот сигнал в цифровом виде, мы можем измерять значения сигнала (отсчеты) через равные интервалы времени, как показано на рис. 7.3, б. Если звуковая волна не является чисто синусоидальной, а представляет собой сумму нескольких синусоидальных волн, самая высокая частота составляющих которых равна f, тогда для последующего восстановления сигнала достаточно измерять значения сигнала с частотой дискретизации 2f. Это утверждение было математически доказано Найквистом в 1924 году. Производить измерения сигнала с большей частотой нет смысла, так как более высокие частоты отсутствуют в сигнале.

102

Оцифрованные отсчеты никогда не бывают точными. Трехбитовые отсчеты на рис. 7.3 могут принимать только 8 значений, от -1,00 до +1,00 с шагом 0,25. При 8-битовом квантовании каждый отсчет может принимать одно из 256 различных значений. При 16

битах на отсчет можно кодировать сигнал с еще более высокой точностью, так как каждому значению сигнала можно поставить в соответствие одно из 65 536 различных значений. Ошибка, возникающая в результате неточного соответствия квантованного сигнала исходному сигналу, называют шумом квантования.

Двумя хорошо известными примерами оцифрованного звука являются телефон и аудиокомпакт-диски. Для телефонной системы, используются 7-битовые и 8-битовые отсчеты. Таким образом, получаемая скорость передачи данных составляет 56 000 бит/с или 64 000 бит/с.

Аудиокомпакт-диски содержат звуковой сигнал, оцифрованный с частотой дискретизации 44 100 Гц, в результате чего они могут хранить звуки с частотами до 22 кГц, что достаточно для людей. Каждому отсчету выделяется 16 бит, которые используются как обычное 2-байтовое целое число, пропорциональное амплитуде сигнала. Тем не менее этот формат достаточно хорош.. Алгоритм MPEG, уровень МРЗ позволяет сжимать оцифрованный звук примерно в 10 раз. В последние годы стали популярными переносные плейеры, воспроизводящие музыку в этом формате. Цифровой звук легко обрабатывать на компьютере. Существуют десятки программ для персональных компьютеров, позволяющие пользователям записывать, воспроизводить, редактировать, микшировать и хранить звук. Сегодня вся профессиональная звукозапись и редактирование звука осуществляется в цифровом виде.

Кодирование изображения

Сетчатка глаза человека обладает инерционными свойствами: яркое изображение, быстро появившееся на сетчатке, остается на ней несколько миллисекунд, прежде чем угаснуть. Если последовательность одинаковых или близких изображений появляются и исчезают с достаточно высокой частотой, то

глаз человека не заметит, что он смотрит на дискретные изображения. Частота, при которой глаз перестает замечать мигание яркости источника света (изображения), составляет около 50 Гц.

Черно-белое телевиденье.

Для преобразования двумерного изображения в вид одномерной зависимости напряжения от времени камера быстро сканирует электронным лучом изображение,

104

заключается в последовательности кадров, состоящих из прямоугольной сетки элементов рисунка - пикселами. В цветном телевидении достаточно использовать по 8 бит на каждый из трех цветов RGB, что дает в сумме 24 бита на пиксел.

Для гладкой передачи движения необходимо отображать по меньшей мере 25 кадров в секунду. Однако, поскольку качественные мониторы обычно сами сканируют по нескольку раз хранящиеся в их памяти изображения с частотой 75 и более кадров в секунду, проблема мерцания изображения решается на уровне монитора сама собой, и чередование строк в цифровом видео не требуется. Другими словами, плавность движущегося изображения определяется количеством отличающихся изображений в секунду, тогда как мерцание зависит от частоты перерисовки экрана.

Для показа цифрового видео на XGA-экране при 24 битах на пиксел и 25 кадрах в секунду потребуется поток данных со скоростью 472 Мбит/с. Это очень дорого. Лучшее решение состоит в том, чтобы передавать 25 кадров в секунду и позволить компьютеру самому хранить эти кадры и отображать их с утроенной или учетверенной частотой.

10. Сжатие видеоинформации

Для всех систем сжатия требуется два алгоритма: один для компрессии данных у источника информации, а другой — декомпрессии у ее получателя (алгоритмами кодирования и декодирования).

Во-первых, во многих приложениях фильм, кодируется всего один раз при его создании и помещении на мультимедийный сервер, но декодируется тысячи раз при просмотре пользователями. Эта асимметрия означает, что алгоритм кодирования может быть довольно медленным и требовать дорогого оборудования, тогда как алгоритм декодирования должен быть быстрым и должен работать даже на дешевом оборудовании.

С другой стороны, для мультимедиа реального времени, например видеоконференции, медленное кодирование неприемлемо. Кодирование здесь должно происходить на ходу, в режиме реального времени.

Во-вторых, процесс кодирования/декодирования не обязан быть обратимым, т.е, что при сжатии обычного файла, его передаче и декомпрессии получатель обязан получить точную копию оригинала. При передаче мультимедиа абсолютная точность не требуется. Вполне допустимы небольшие отклонения видеосигнала от оригинала после его кодирования и декодирования. Система, в которой декодированный сигнал не точно соответствует кодированному оригиналу, называется системой с потерями. Все системы сжатия данных, применяемые в мультимедиа, являются системами с потерями, так как они позволяют достичь гораздо большего коэффициента сжатия.

Стандарт JPEG является очень важным для мультимедиа, так как в первом приближении мультимедийный стандарт для движущихся изображений MPEG представляет собой просто кодирование каждого кадра отдельно алгоритмом JPEG плюс некоторые дополнительные процедуры межкадрового сжатия и обнаружения движения.

Первый этап кодирования изображения алгоритмом JPEG представляет собой подготовку блока. Рассмотрим частный случай кодирования 24-битового RGBвидеоизображения размером 640x480 пикселов, как показано на рис. 7.5, а. Поскольку разделение на яркость и цветность позволяют сильнее сжать изображение, сначала из значений RGB вычисляются яркость и два значения цветности (Y, I и Q).

105

Для значений Y, I и Q строятся отдельные матрицы с элементами в диапазоне от 0 до 255. Затем значения цветности / и Q усредняются по квадратным блокам из четырех пикселов, что уменьшает размеры матриц цветности в 4 раза. Это сжатие является преобразованием с потерями, но человеческий глаз его практически не замечает. На этом этапе общий объем данных уменьшается вдвое. Затем из каждого элемента вычитается число 128, чтобы переместить число 0 в середину диапазона. Наконец, каждая матрица разбивается на квадраты по 8x8 пикселов.

На втором этапе кодирования к каждому из квадратных блоков отдельно применяется дискретное косинусное преобразование. На выходе получается 7200 матриц 8x8 коэффициентов дискретного косинусного преобразования (ДКП). Элемент (0, 0) такой матрицы представляет собой среднее значение блока. Остальные элементы содержат информацию о спектральной мощности каждой пространственной частоты.

3 этап: квантование, в котором наименее важные ДКПкоэффициенгы удаляются. Это преобразование (с потерями) выполняется делением всех коэффициентов ДКП-матрицы на табличные весовые коэффициенты. Если все весовые коэффициенты равны 1, то это преобразование ничего не меняет. Однако при резком росте весовых коэффициентов по мере удаления от элемента матрицы (0, 0) более высокие пространственные частоты быстро теряются.

На четвертом этапе значение, содержащееся в элементе (0, 0) каждого блока (в левом верхнем углу квадрата), заменяется его отклонением относительно значения в предыдущем блоке. Так как эти значения представляют собой усредненные величины своих блоков, они должны меняться медленно, следовательно, полученные в результате разности должны быть невелики.

На пятом этапе 64 элемента блока выстраиваются в ряд, к которому применяется кодирование длин серий. Чтобы сконцентрировать нули в конце ряда, сканирование блока выполняется зигзагом.

На последнем, шестом этапе к общему списку чисел применяется код Хаффмана.

Для декодирования сжатого изображения нужно выполнить все те же операции в обратном порядке. В отличие от некоторых других алгоритмов, JPEG примерно симметричен: декодирование занимает столько же времени, сколько и кодирование.

106

Стандарт MPEG

В видеофильмах имеется избыточность двух типов: пространственная и временная. Чтобы использовать пространственную избыточность, можно просто кодировать каждый кадр отдельно алгоритмом JPEG. Дополнительного сжатия можно достичь, используя преимущество того факта, что последовательные кадры часто бывают почти идентичны (временная избыточность). JPEG используют когда картинка мало меняется. Выход MPEG-2 состоит из кадров следующих типов:

1.I (Intracoded — автономные) — независимые неподвижные изображения, кодированные алгоритмом JPEG.

2.Р (Predictive — предсказывающие) — содержащие разностную информацию, относительно предыдущего кадра.

3.В (Bidirectional — двунаправленные) — содержащие изменения относительно предыдущего и последующего кадров.

I-кадры представляют собой обычные неподвижные изображения, кодированные алгоритмом JPEG с использованием полного разрешения яркости и половинного разрешения для обоих сигналов цветности. I-кадры должны периодически появляться в выходном потоке по трем причинам. Во-первых, должна быть возможность просмотра фильма не с самого начала. Зритель, пропустивший первый кадр, не сможет декодировать все последующие кадры, если все кадры будут зависеть от предыдущих, и I-кадры не будут время от времени включаться в поток. Во-вторых, дальнейшее декодирование фильма станет невозможным в случае ошибки при передаче какого-либо кадра. В-третьих, наличие таких кадров существенно упростит индикацию во время быстрой перемотки вперед или назад. По этим причинам I-кадры включаются в выходной поток примерно один-два раза в секунду.

Р-кадры, напротив, представляют собой разность между соседними кадрами. Они основаны на идее макроблоков., покрывающих 16x16 пикселов в пространстве яркости и 8x8 пикселов в пространстве цветности. Не меняем все картинку, меняем только макроблоки, где что-то изменилось.

Макроблок можно искать в предыдущем кадре в текущей позиции с заданными смещениями по горизонтали и вертикали. Для каждой позиции может вычисляться количество совпадений матрицы яркости. Позиция с наибольшим значением совпадений будет объявляться победительницей при условии, что это значение превосходит некое пороговое значение. В противном случае макроблок будет считаться не найденным.

Макроблок, для которого найден похожий на него макроблок в предыдущем кадре, кодируется в виде разности значений яркости и цветности. Затем матрицы разностей подвергаются дискретному косинусному преобразованию, квантованию, кодированию длин серий и кодированию Хаффмана так же, как это делает алгоритм JPEG. В выходном потоке макроблок представляется в виде вектора сдвига (насколько далеко сдвинулся макроблок по горизонтали и вертикали от положения в предыдущем кадре), за которым следует список чисел, кодированных по Хаффману. Если же в предыдущем кадре не нашлось подходящего макроблока, текущее значение кодируется алгоритмом JPEG, как в 1-кадре.

В-кадры подобны Р-кадрам с той разницей, что позволяют привязывать макроблок либо к предыдущему, либо к следующему кадру. Для декодирования В-кадров необходимо удерживать в памяти сразу три кадра: предыдущий, текущий и следующий в порядке зависимостей друг от друга. Это означает, что при передаче видео по сети необходима буферизация данных на машине пользователя, чтобы изменить порядок кадров для их правильного отображения. Поскольку порядок отображения кадров не совпадает с порядком их взаимозависимостей, для воспроизведения фильма задом наперед

107

потребуется значительная буферизация и сложные алгоритмы.

Планирование процессов в мультимедийных системах Планирование однородных процессов

Простейшая разновидность видеосервера может поддерживать отображение фиксированного числа фильмов, использующих одинаковую скорость передачи данных, видеоразрешение, частоту кадров и другие параметры. При таких условиях используется эффективный алгоритм планирования. Для каждого фильма создается отдельный процесс (или поток), чья работа чтении фильма с диска по кадру и передаче этого кадра пользователю. Поскольку все процессы одинаково важны, выполняют одинаковый объем работ на каждый кадр и блокируются, закончив обработку текущего кадра, то для управления этими процессами лучше всего использовать простой алгоритм поочередного планирования.

Один способ достижения правильного временного режима состоит в использовании управляющих часов, тикающих, скажем, 30 раз в секунду. При каждом тике все процессы запускаются последовательно в одном и том же порядке.

Общее планирование реального времени

Количество пользователей меняется со временем, размеры кадров изменяются в широчайших пределах благодаря самой природе видеосжатия, кроме того, в различных фильмах может использоваться различное разрешение. В результате может оказаться, что разным процессам потребуется работа с разной частотой для выполнения различного объема работ и с различными сроками их окончания. Такие соображения приводят к совершенно другой модели: нескольким процессам, соревнующимся за право использования центрального процессора, каждый со своим заданием и графиком его выполнения. Планирование нескольких конкурирующих процессов, у некоторых есть жесткие сроки выполнения работ, называется планированием реального времени. В качестве примера среды, в которой работает мультимедийный планировщик реального времени, рассмотрим три процесса, А, В и С, показанные на рис. 7.10.

Процесс А запускается каждые 30 мс. Для обработки каждого кадра требуется около 10 мс времени центрального процессора. При отсутствии конкуренции он будет запускаться импульсами А1, А2, A3 и т. д., каждый из которых будет начинаться через 30 мс после предыдущего. Каждый 10-миллисекундный интервал работы центрального процессора обрабатывает один кадр и должен завершить работу к определенному моменту времени, то есть прежде, чем начнется обработка следующего кадра.

108

Процесс В работает с частотой 25 кадров в секунду, а процесс С— с частотой 20 кадров в секунду. Время обработки каждого кадра показано на рисунке — 15 мс для процесса В и 5 мс для процесса С.

Проблема планирования состоит в том, как в данной ситуации планировать работу процессов А, В и С так, чтобы гарантировать выполнение ими требуемой работы в срок.

В некоторых системах реального времени процессы являются прерываемыми, тогда как в других системах — нет. В мультимедийных системах процессы, как правило, могут прерываться. Это означает, что процесс, которому угрожает невыполнение задачи в срок, может прервать работающий процесс прежде, чем тот успеет закончить обработку своего кадра. Затем управление может быть возвращено прерванному процессу. Мы рассмотрим алгоритмы планирования реального времени с прерываниями, так как они не противоречат принципам мультимедийных систем и позволяют достичь лучших показателей производительности, чем алгоритмы без прерываний. Единственная забота состоит в том, что при заполнении буфера за короткие интервалы времени буфер должен быть заполнен в срок, чтобы его можно было отправить за одну операцию. В противном случае может возникнуть джиттер.

Алгоритмы реального времени могут быть статическими или динамическими. Статические алгоритмы заранее назначают каждому процессу фиксированный приоритет, после чего выполняют приоритетное планирование с переключениями. У динамических алгоритмов нет фиксированных приоритетов.

Алгоритм планирования RMS

Классическим примером статического алгоритма планирования реального времени для прерываемых, периодических процессов является алгоритм RMS (Rate Monotonic Scheduling — планирование с приоритетом, пропорциональным частоте). Этот алгоритм может использоваться для процессов, удовлетворяющих следующим условиям:

1.Каждый периодический процесс должен быть завершен за время его периода.

2.Ни один процесс не должен зависеть от любого другого процесса.

3.Каждому процессу требуется одинаковое процессорное время на каждом интервале.

4.У непериодических процессов нет жестких сроков.

5.Прерывание процесса происходит мгновенно, без накладных расходов.

Алгоритм RMS работает, назначая каждому процессу фиксированный приоритет, равный частоте возникновения событий процесса. Например, процесс, который должен запускаться каждые 30 мс (3 раза в секунду), получает приоритет 33; процесс, который должен запускаться каждые 40 мс (5 раз в секунду), получает приоритет 25; а процесс, который должен запускаться каждые 50 мс (20 раз в секунду), получает приоритет 20. Во время работы планировщик всегда запускает готовый к работе процесс с наивысшим приоритетом, прерывая при необходимости работающий процесс.

Процессам А, В и С назначены статические приоритеты 33, 25 и 20; это означает, что когда процесс А желает работать, он работает, прерывая любой другой процесс, использующий центральный процессор в данный момент. Процесс В может прервать работу процесса С, но не А. Процесс С вынужден ждать, пока центральный процессор не освободится. Изначально все три процесса готовы к работе (см. рис. 7.11). Выбирается процесс с максимальным приоритетом, то есть процесс А. Ему разрешается работать в течение 15 мс, требующихся процессу, чтобы полностью выполнить работу по передаче одного кадра. Когда процесс А заканчивает свою работу, запускается процесс В, а затем процесс С. Вместе эти процессы потребляют 30 мс процессорного времени, поэтому, когда процесс С заканчивает свою работу, пора снова запускать процесс А. Этот цикл

110

алгоритма EDF может достигать 100 %. Платой за это является использование более сложного алгоритма. Таким образом, на реальном видеосервере при загруженности центрального процессора ниже предела RMS может использоваться алгоритм RMS. В противном случае должен применяться алгоритм EDF.

17.Мультипроцессоры

1.Способы повышения вычислительной мощности компьютерной системы

При системном вызове на центральном процессоре, обратившемся к системе с системным вызовом.

В прошлом решение всегда состояло в том, чтобы увеличить тактовую частоту процессора. К сожалению, сегодня мы приближаемся к некоторым фундаментальным пределам тактовой частоты. В соответствии со специальной теорией относительности Эйнштейна, электрический сигнал не может распространяться быстрее скорости света, равной 30 см/нс в вакууме и около 20 см/нс в медном проводе или оптоволоконном кабеле. Это означает, что в компьютере с тактовой частотой 10 Гц сигналы за один такт не могут распространяться дальше, чем на 2 см. Для 100-гигагерцового компьютера полная длина пути сигнала будет составлять максимум 2 мм. Компьютер с тактовой частотой 1 ТГц должен иметь размеры менее 100 мкм, чтобы сигнал от одного его конца до другого успел пройти за один такт процессора.

Производство компьютеров такого размера может теоретически и возможно, но при этом мы сталкиваемся с другой фундаментальной проблемой: рассеянием тепла. Чем быстрее работает компьютер, тем больше тепловой энергии он производит, а чем меньше компьютер, тем труднее отводить эту тепловую энергию. Уже сейчас на новых системах с процессором Pentium вентилятор для охлаждения центрального процессора больше, чем сам центральный процессор.

Другой способ увеличения вычислительной мощности системы состоит в

использовании параллельных вычислений. Для этого могут использоваться многопроцессорные компьютеры, состоящие из большого количества процессоров, каждый из которых работает с «нормальной» частотой. Однако совместно эти процессоры обладают значительно большей мощностью, чем отдельный центральный процессор.

Высокопараллельные компьютеры часто применяются для сложных вычислений. Для решения этих задач требуются долгие расчеты на большом количестве центральных процессоров одновременно.

Еще один способ увеличения вычислительной мощности системы заключается в использовании параллельных расчетов на большом количестве отдельных

компьютеров, соединенных в локальную или глобальную сеть. В настоящее время продолжается быстрый рост глобальной сети Интернет. Не так давно Интернет получил еще одно применение: поскольку он связывает по всему миру тысячи компьютеров, было решено использовать эту сеть для решения больших научных проблем. С точки зрения вычислительной мощности система, состоящая из 1000 компьютеров по всему миру, не отличается от такой же системы из 1000 компьютеров, стоящих в одном помещении, хотя характеризуется задержкой и имеет некоторые другие технические характеристики. Проблемы начинаются, когда вам требуется соединить эти компьютеры друг с другом для решения одной общей задачи.

Весь обмен информацией между электронными компонентами сводится к отправке и приему сообщений, представляющих собой строго определенные последовательности битов. Различия состоят во временных параметрах, пространственных масштабах и