загрузка...
загрузка...
На головну

 Моделі життєвого циклу ПЗ |  каскадна модель |  спіральна модель |  підхід RAD |  Базові технології локальних мереж, загальна характеристика протоколів локальних мереж, структура стандартів IEE802.х. |  Технологія Token Ring |  Структура стандартів IEEE 802.x |  Завадостійке кодування, циклічні коди, коди Хеммінга. |  Призначення і функції ОС. Функціональні компоненти ОС Linux. |  Кодування з мінімальною надмірністю, алгоритм Шеннон Фано. |

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

  1.  алгоритм
  2.  АЛГОРИТМ
  3.  алгоритм
  4.  алгоритм
  5.  алгоритм
  6.  алгоритм
  7.  АЛГОРИТМ

Метод Хаффмана: літери алфавіту повідомлень вписуються в стовпець в порядку убування ймовірностей. Дві останні літери об'єднуються в одну допоміжну букву, якої приписується сумарна ймовірність. Ймовірності букв, які не брали участі в об'єднанні, і отримана сумарна ймовірність знову розташовуються в порядку убування ймовірностей в додатковому стовпці, а дві останні букви об'єднуються.

код Хаффмена

Вхід: 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. Процеси та потоки. Мультипрограмування, планування процесів і потоків.

Найважливішою частиною операційної системи, що безпосередньо впливає на функціонування обчислювальної машини, є підсистема управління процесами.

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

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

У мультипрограммной операційній системі одночасно може існувати кілька процесів. Частина процесів породжується з ініціативи користувачів і їх додатків, такі процеси зазвичай називають призначеними для користувача. Інші процеси, звані системними, Не започатковано самою операційною системою для виконання своїх функцій.

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

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

Протягом періоду існування процесу його виконання може бути багаторазово перерване і продовжене. Для того щоб відновити виконання процесу, необхідно відновити стан його операційного середовища. Стан операційного середовища ідентифікується станом регістрів і програмного лічильника, режимом роботи процесора, покажчиками на відкриті файли, інформацією про незавершені операції введення-виведення, кодами помилок виконуваних даним процесом системних викликів і т. Д. Ця інформація називається контекстом процесу. Кажуть, що при зміні процесу відбувається перемикання контекстів.

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

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

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

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

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


 



 Оптимальне кодування. Алгоритм Хаффмана. |  Управління пам'яттю, типи адрес, алгоритми розподілу пам'яттю.
загрузка...
© um.co.ua - учбові матеріали та реферати