Алгоритм Хаффмена

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

Код Хаффмена

Вход: n – количество букв, P: array [1..n] of real – массив вероятностей букв, упорядоченный по убыванию.

Выход: C: array [1..n,1..L] of 0..1 – массив элементарных кодов, l: array [1..n] of 1..L – массив длин элементарных кодов схемы оптимального префиксного кодирования.

If n=2 then

C[1,1]:=0; l[1]:=1; (первый элемент)

C[2,1]:=1: l[2]:=1; (второй элемент)

else

q:=P[n-1]+ P[n]; (сумма двух последних вероятностей)

j:=Up(n,q); (поиск места и вставка суммы)

haff(P,n-1); (рекурс вызов)

Dawn(n,j); (достраивание кодов)

End;

Функция Up находит в массиве Р место, в котором должно находиться число q и вставляет это число, сдвигая вниз остальные элементы.

Вход: n – длинна обрабатываемой части массива, P, q – вставляемая сумма.

Выход: измеренный массив P.

For i from n-1 downto 2 do

If P[i-1] <=q then

P[i]:=P[i-1]; (сдвиг элемента массива)

Else

j:=i-1; (определение места вставляемого элемента)

exit for i (все сделано цикл не нужно продолжать)

end;

end;

p[j]:=q (запись восстанавливаемого элемента)

return j

Процедура Dawn строит оптимальный код для n букв на основе построенного оптимального кода для n-1 буквы. Для этого код буквы с номером j временно исключается из массива С путем сдвига вверх кодов букв с номерами, большими j, а затем в конец обрабатываемой части массива С добавляется пара кодов, полученных из кода буквы с номером j удлинением на 0 и 1, соответственно. Здесь C[i,*] означает вырезку из массива, т.е. i-ю строку массива С.

Вход: n – длинна обрабатываемой части массива, P, j – номер «разделяемой» буквы.

Выход: оптимальные коды в первых n элементах массивов C и l.

c:=C[j,*]; (запоминание кода буквы j)

l:=l[j]; (и длинны этого кода)

for i from j to n-2 do

C[i,*]:=C[i+1,*]; (сдвиг кода)

l[i]:=l[i+1]; (и его длинны)

end;

C[n-1,*]:=c; C[n,*]:=c; (копирование кода буквы j)

C[n-1,l+1]:=0; C[n,l+1]:=1; (наращивание кодов)

l[n-1]:=l+1; l[n]:=l+1; (и увеличение длин)

9. Процессы и потоки. Мультипрограммирование, планирование процессов и потоков.

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

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

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

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

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

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

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

Мультипрограммирование, или многозадачность - это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько программ.

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

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

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

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