Паралелізм розподілених застосувань

Паралелізм взаємодії з користувачем

Паралелізм операцій введення-виведення

Види паралелізму

Можна виділити такі основні види паралелізму:

§ паралелізм багатопроцесорних систем;

§ паралелізм операцій введення-виведення;

§ паралелізм взаємодії з користувачем;

§ паралелізм розподілених систем.

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

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

Багатопотокове застосування може реалізувати цей вид паралелізму через створення нових потоків, які виконуватимуться, коли поточний потік очікує опе­рації введення-виведення. Так реалізується асинхронне введення-виведення, ко­ли застосування продовжує своє виконання, не чекаючи на завершення операцій введення-виведення.

Під час інтерактивного сеансу роботи користувач може виконувати різні дії із застосуванням (і очікувати негайної реакції на них) до завершення обробки попе­редніх дій. Наприклад, після запуску команди «друкування документа» він може негайно продовжити введення тексту, не чекаючи завершення друкування.

Щоб розв'язати це завдання, можна виділити окремі потоки для безпосеред­ньої взаємодії із користувачем (наприклад, один потік може очікувати введення з клавіатури, інший — від миші, додаткові потоки — відображати інтерфейс кори­стувача). Основні задачі застосування (розрахунки, взаємодія з базою даних то­що) у цей час виконуватимуть інші потоки.

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

5.

За допомогою потоків вирішуються такі проблеми:

§ потоки дають змогу реалізувати різні види паралелізму і дозволяють застосуванню масштабуватися із ростом кількості процесорів.

§ для підтримки потоків потрібно менше ресурсів, ніж для підтримки процесів (наприклад, немає необхідності виділяти для потоків адресний простір).

§ для обміну даними між потоками може бути використана спільна пам'ять (адресний простір їхнього процесу). Це ефективніше, ніж застосовувати засо­би міжпроцесової взаємодії.

Незважаючи на перелічені переваги, використання потоків не є універсальним засобом розв'язання проблем паралелізму, і пов'язане з деякими труднощами:

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

§ використання потоків може спричинити зниження продуктивності застосувань. Переважно це трапляється в однопроцесорних системах (наприклад, у таких сис­темах спроба виконати складний розрахунок паралельно декількома потоками призводить лише до зайвих витрат на перемикання між потоками, кількість ви­конаних корисних інструкцій залишиться тією ж самою).

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

Лекція №2.

Тема: Способи реалізації моделі процесів і потоків та їх опис.

План:

1.Способи реалізації моделі потоків (Л1. ст.50-51).

2.Стани процесів і потоків (Л1. ст.51-52).

3.Опис процесів і потоків (Л1. ст.52).

4.Керуючі блоки процесів і потоків (Л1. ст.53).

5.Образи процесів і потоків (Л1. ст53-54).

1.

В ОС використовують два типи потоків – потоки користувача і потоки ядра

Потік користувача — це послідовність виконання команд в адресному просторі процесу. Ядро ОС не має інформації про такі потоки, вся робота з ними викону­ється в режимі користувача. Засоби підтримки потоків користувача надають спе­ціальні системні бібліотеки; вони доступні для прикладних програмістів у вигляді бібліотечних функцій. Бібліотеки підтримки потоків у сучасних ОС реалізу­ють набір функцій, визначений стандартом РОSІХ (відповідний розділ стандарту називають POSIX.1b); тут прийнято говорити про підтримку потоків РОSІХ.

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

♦ Процес

Співвідношення між двома видами потоків визначає реалізацію моделі пото­ків. Є кілька варіантів такої реалізації (схем багатопотоковості); розглянемо най­важливіші з них (рис. 3.1).

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

§ Схема М:1 не дає змоги скористатися багатопроцесорними архітектурами, ос­кільки визначити, який саме код виконуватиметься на кожному із процесорів, може тільки ядро ОС. У результаті всі потоки одного процесу завжди викону­ватимуться на одному процесорі.

§ Оскільки системні виклики обробляються на рівні ядра ОС, блокувальний системний виклик (наприклад, виклик, який очікує введення даних користу­вачем) зупинятиме всі потоки процесу, а не лише той, що зробив цей виклик.

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

Схема багатопотоковості М:N. У цій схемі присутні як потоки ядра, так і по­токи користувача, які відображаються на потоки ядра так, що один потік ядра мо­же відповідати декільком потокам користувача. Число потоків ядра може бути змінене програмістом для досягнення максимальної продуктивності. Розподіл по­токів користувача по потоках ядра виконується в режимі користувача, плануван­ня потоків ядра - у режимі ядра. Схема є складною в реалізації і сьогодні здає свої позиції схемі 1:1.

2.

Для потоку дозволені такі стани:

§ створення (new) — потік перебуває у процесі створення;

§ виконання (running) — інструкції потоку виконує процесор (у конкретний мо­мент часу на одному процесорі тільки один потік може бути в такому стані);

§ очікування (waiting) — потік очікує деякої події (наприклад, завершення опе­рації введення-виведення); такий стан називають також заблокованим, а по­тік - припиненим;

§ готовність (ready) — потік очікує, що планувальник перемкне процесор на нього, при цьому він має всі необхідні йому ресурси, крім процесорного часу;

§ завершення (terminated) — потік завершив виконання (якщо при цьому його ресурси не були вилучені з системи, він переходить у додатковий стан — стан зомбі).

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

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

Відносно систем, які реалізують модель процесів, прийнято говорити про ста­ни процесів, а не потоків, і про планування процесів; фактично стани процесу в цьому разі однозначно відповідають станам його єдиного потоку.

У багатопотокових системах також можна виділяти стани процесів. Наприклад, у багатопотоковості, реалізованій за схемою М:1, потоки змінюють свої стани в режимі користувача, а процеси — у режимі ядра.

3.

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

Для керування розподілом ресурсів ОС повинна підтримувати структури да­них, які містять інформацію, що описує процеси, потоки і ресурси. До таких структур даних належать:

§ таблиці розподілу ресурсів: таблиці пам'яті, таблиці введення-виведення, таб­лиці файлів тощо;

§ таблиці процесів і таблиці потоків, де міститься інформація про процеси і по­токи, присутні у системі в конкретний момент.

4.

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

Керуючий блок потоку (Thread Control Block, ТСВ) відповідає активному по­току, тобто тому, який перебуває у стані готовності, очікування або виконання. Цей блок може містити таку інформацію:

§ ідентифікаційні дані потоку (зазвичай його унікальний ідентифікатор);

§ стан процесора потоку: користувацькі регістри процесора, лічильник інструк­цій, покажчик на стек;

§ інформацію для планування потоків.

Таблиця потоків — це зв'язний список або масив керуючих блоків потоку. Во­на розташована в захищеній області пам'яті ОС.

Керуючий блок процесу (Process Control Block, РСВ) відповідає процесу, що присутній у системі. Такий блок може містити:

§ ідентифікаційні дані процесу (унікальний ідентифікатор, інформацію про інші процеси, пов'язані з даним);

§ інформацію про потоки, які виконуються в адресному просторі процесу (на­приклад, покажчики на їхні керуючі блоки);

§ інформацію, на основі якої можна визначити права процесу на використання різних ресурсів (наприклад, ідентифікатор користувача, який створив процес);

§ інформацію з розподілу адресного простору процесу;

§ інформацію про ресурси введення-виведення та файли, які використовує процес.

Зазначимо, що для систем, у яких реалізована модель процесів, у керуючому блоці процесу зберігають не посилання на керуючі блоки його потоків, а інфор­мацію, необхідну безпосередньо для його виконання (лічильник інструкцій, дані для планування тощо).

Таблицю процесів організовують аналогічно до таблиці потоків. Як елементи в ній зберігатимуться керуючі блоки процесів.

5.

Сукупність інформації, що відображає процес у пам'яті, називають образом про­цесу (process image), а всю інформацію про потік - образом потоку (thread image). До образу процесу належать:

§ керуючий блок процесу;

§ програмний код користувача;

§ дані користувача (глобальні дані програми, загальні для всіх потоків);

§ інформація образів потоків процесу.

Програмний код користувача, дані користувача та інформація про потоки за­вантажуються в адресний простір процесу. Образ процесу звичайно не є безпе­рервною ділянкою пам'яті, його частини можуть вивантажуватися на диск. Ці пи­тання будуть розглянуті в розділі 9.

До образу потоку належать:

§ керуючий блок потоку;

§ стек ядра (стек потоку, який використовується під час виконання коду потоку в режимі ядра);

§ стек користувача (стек потоку, доступний у користувацькому режимі).

Схема розташування в пам'яті образів процесу і його потоків зображена нарис. 3.3. Усі потоки конкретного процесу можуть користуватися загальною ін­формацією його образу.

Лекція №3.

Тема: перемикання контексту й обробка переривань.

План:

1.Організація перемикання контексту (Л1. ст.54-55).

2.Обробка переривань (Л1. ст.55).

3.Створення процесів та їхня ієрархія (Л1. ст.56-57).

4.Особливості завершення процесів (Л1. ст.59).

5.Синхронне й асинхронне виконання процесів (Л1. ст.59).

6.Створення і завершення потоків (Л1. ст.60-61).

1.

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

Загальних принципів перемикання контексту дотримуються у більшості систем, але їхня реалізація обумовлена конкретною архітектурою. Для перемикання контексту потрібно ви­конати такі операції:

§ зберегти стан процесора потоку в деякій ділянці пам'яті (області зберігання стану процесора потоку);

§ визначити, який потік слід виконувати наступним;

§ завантажити стан процесора цього потоку із його області зберігання;

§ продовжити виконання коду нового потоку.

Перемикання контексту здійснюється із залученням засобів апарат­ної підтримки. Можуть бути використані спеціальні регістри та ділянки пам'яті, які дають можливість зберігати інформацію про поточну задачу (коли розгляда­ють апаратне забезпечення, аналогом поняття «потік» є поняття «задача»), а також спеціальні інструкції процесора для роботи з цими регістрами та ділянками пам'яті.

В архітектурі ІА-32 для збереження стану процесора кожної задачі (вмісту пов'язаних із нею регістрів процесора) використовують спеціальну ділянку пам'яті - сегмент стану задачі ТSS. Адресу цієї області можна одержати з регістра задачі ТR (це системний ад­ресний регістр).

Для перемикання задач досить завантажити нові дані в регістр ТR. У резуль­таті значення регістрів процесора поточної задачі автоматично збережуться в її сегменті стану, після чого в регістри процесора буде завантажено стан процесора нової (або раніше перерваної) задачі й почнеться виконання її інструкцій.

Наступний потік для виконання вибирають відповідно до принципів плану­вання потоків.

2.

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

Наведемо приклад послідовності дій під час обробки переривання:

§ збереження стану процесора потоку;

§ встановлення стека оброблювача переривання;

§ початок виконання оброблювача переривання (коду операційної системи); для цього з вектора переривання завантажується нове значення лічильника команд;

§ відновлення стану процесора потоку після закінчення виконання оброблюва­ча і продовження виконання потоку.

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

3.

Засоби створення і завершення процесів дають змогу динамічно змінювати в опе­раційній системі набір застосувань, що виконуються. Засоби створення і завер­шення потоків є основою для створення багатопотокових програм.

Процеси можуть створюватися ядром системи під час її ініціалізації. Наприклад, в UNIX-сумісних системах таким процесом може бути процес ініціалізації систе­ми іnit, у Windows ХР - процеси підсистем середовища (Win32 або POSIX). Та­ке створення процесів, однак, є винятком, а не правилом.

Найчастіше процеси створюються під час виконання інших процесів. У цьому разі процес, який створює інший процес, називають предком, а створений ним процес - нащадком.

Нові процеси можуть бути створені під час роботи застосування відповідно до його логіки (компілятор може створювати процеси для кожного етапу компіляції, веб-сервер - для обробки прибулих запитів) або безпосередньо за запитом кори­стувача (наприклад, з командного інтерпретатора, графічної оболонки або файло­вого менеджера).

Розрізняють два типи процесів з погляду їхньої взаємодії із користувачем - інтерактивні та фонові.

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

§ Фонові процеси із користувачем не взаємодіють безпосередньо. Зазвичай вони запускаються під час старту системи і чекають на запити від інших застосу­вань. Деякі з них (системні процеси) підтримують функціонування системи (реалізують фонове друкування, мережні засоби тощо), інші виконують спе­ціалізовані задачі (реалізують веб-сервери, сервери баз даних тощо). Фонові процеси також називають службами (services, у системах лінії Windows ХР) або демонами (daemons, в UNIX).

Ієрархія процесів

Після того як процес-предок створив процес-нащадок, потрібно забезпечити їх­ній взаємозв'язок. Є різні варіанти розв'язання цього завдання.

Можна організувати на рівні ОС однозначний зв'язок «предок-нащадок» так, щоб для кожного процесу завжди можна було визначити його предка. Наприклад, якщо процеси визначені унікальними ідентифікаторами, то для реалізації цього підходу в керуючому блоці процесу-нащадка повинен завжди зберігатися іденти­фікатор процесу-предка або посилання на його керуючий блок.

Таким чином формується ієрархія (дерево) процесів, оскільки нащадки мо­жуть у свою чергу створювати нових нащадків і т. ін. У таких системах існує спеціальний вихідний процес (в UNIX-системах його називають іnit), з яко­го починається побудова дерева процесів (його запускає ядро системи). Якщо предок завершить виконання свого процесу перед своїм нащадком, функції предка бере на себе вихідний процес.

З іншого боку, зв'язок «предок-нащадок» можна не реалізовувати на рівні ОС. При цьому всі процеси виявляються рівноправними. Якщо зв'язок «предок-на­щадок» для конкретної пари процесів все ж таки потрібен, за його підтримку від­повідають самі процеси (процес-предок, наприклад, може сам зберегти свій іден­тифікатор у структурі даних нащадка у разі його створення).

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

4.

Існує три варіанти завершення процесів.

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

Процес аварійно завершується через помилку. Такий вихід може бути перед­бачений програмістом (під час обробки помилки приймається рішення про те, що далі продовжувати виконання програми неможливо), а може бути наслідком гене­рування переривання (ділення на нуль, доступу до захищеної області пам'яті тощо).

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

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

5.

Коли у системі з'являється новий процес, для старого процесу є два основних ва­ріанти дій:

§ продовжити виконання паралельно з новим процесом - такий режим роботи називають асинхронним виконанням;

§ призупинити виконання доти, поки новий процес не буде завершений, — та­кий режим роботи називають синхронним виконанням. (У цьому разі викори­стовують спеціальний системний виклик, який у POSIX-системах назива­ють wait().)

Вибір того чи іншого режиму залежить від конкретної задачі. Так, наприклад, веб-сервер може створювати процеси-нащадки для обробки запитів (якщо наяв­ного набору нащадків недостатньо для такої обробки). У цьому разі обробка має бути асинхронною, бо відразу після створення нащадка предок має бути готовий до отримання наступного запиту. З іншого боку, компілятор С під час запуску процесів, що відповідають етапам компіляції, має чекати завершення кожного етапу, перш ніж перейти до наступного, - у такому разі використовують син­хронну обробку.

6.

Дата добавления: 2014-10-23