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

Процес використання семафорів передбачає дві операції: очікування (P) і сигнал (V). Операція очікування зменшує значення семафора, а операція сигналу збільшує значення семафора. Коли значення семафора дорівнює нулю, будь-який процес, який виконує операцію очікування, буде заблоковано, доки інший процес не виконає операцію сигналу.

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

Семафор — це особливий тип даних синхронізації, який можна використовувати лише через певні примітиви синхронізації. Коли процес виконує операцію очікування на семафорі, операція перевіряє, чи значення семафора>0. Якщо так, воно зменшує значення семафора і дозволяє процесу продовжити його виконання; інакше він блокує процес на семафорі. Сигнальна операція на семафорі активує процес, заблокований на семафорі, якщо такий є, або збільшує значення семафора на 1. Через цю семантику семафори також називають семафорами підрахунку. Початкове значення семафора визначає, скільки процесів можуть пройти операцію очікування.

рік на квартали

Семафори бувають двох типів:

1. Бінарний семафор –
   Це також відоме як блокування м'ютексу. Він може мати лише два значення – 0 і 1. Його значення ініціалізується рівним 1. Використовується для реалізації вирішення завдань критичної секції з кількома процесами.
2. Рахунковий семафор –
   Його значення може варіюватися в необмеженому домені. Він використовується для контролю доступу до ресурсу, який має кілька екземплярів.

Тепер давайте подивимося, як це робиться.

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

Деякі моменти щодо роботи P і V:

bfs проти dfs

1. Операція P також називається операцією очікування, сну або вимкнення, а операція V також називається операцією сигналу, пробудження або роботи.
2. Обидві операції є атомарними, і семафор(и) завжди ініціалізується одним. Тут атомарна означає змінну, для якої читання, модифікація та оновлення відбувається в той самий час/момент без випередження, тобто між читанням, модифікацією та оновленням не виконується жодна інша операція, яка може змінити змінну.
3. Критичний розділ оточений обома операціями для реалізації синхронізації процесу. Дивіться зображення нижче. Критична ділянка процесу P знаходиться між операціями P і V.

Тепер давайте подивимося, як він реалізує взаємне виключення. Нехай є два процеси P1 і P2, і семафор s ініціалізовано як 1. Тепер, якщо припустимо, що P1 входить у свою критичну секцію, тоді значення семафора s стає 0. Тепер, якщо P2 хоче увійти у свою критичну секцію, він чекатиме, поки s> 0, це може статися лише тоді, коли P1 завершує свою критичну секцію та викликає операцію V на семафорі s.

Таким чином досягається взаємне виключення. Подивіться на зображення нижче, щоб дізнатися, що таке двійковий семафор.

Реалізація: Бінарні семафори

struct semaphore {    enum value(0, 1);  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(semaphore s) { if (s.value == 1) { s.value = 0;  } else { // додати процес до черги очікування q.push(P) sleep();  } } V(семафор s) { якщо (s.q порожній) { s.value = 1;  } else { // вибрати процес із черги очікування Process p = q.front();  // вилучити процес із очікування, оскільки // він був надісланий для CS q.pop();  пробудження (p);  } } // Цей код змінено Susobhan Akhuli>

#include  #include #include struct semaphore{  Queueq;  int значення; }; void P(struct semaphore s) { if (s.value == 1) { s.value = 0;  } else { s.q.push(P);   сон();  } } void V(semaphore s) { if (s.q порожній) { s.value = 1;  } else { // Отримати процес із черги очікування Process p = q.front();  // Видалити процес з очікування q.pop();  пробудження (p);  } } int main() { printf('Це Хеміш!!');    // Цей код надав Хімеш Сінгх Чаухан return 0; } // Цей код змінено Susobhan Akhuli>

import java.util.*; class Semaphore {  public enum Value { Zero, One }  public Queueq = новий LinkedList();  public Value value = Value.One;  public void P(Semaphore s, Process p) { if (s.value == Value.One) { s.value = Value.Zero;  } else { // додати процес до черги очікування q.add(p);  p.Sleep();  } } public void V(Semaphore s) { if (s.q.size() == 0) { s.value = Value.One;  } else { // вибрати процес із черги очікування Process p = q.peek();  // вилучити процес із очікування, оскільки // його було надіслано для CS q.remove();  p.Wakeup();  } } }>

from enum import Enum from queue import Queue class Semaphore: class Value(Enum): Zero = 0 One = 1 def __init__(self): self.q = Queue() self.value = Semaphore.Value.One def P(self, s, p): if s.value == Semaphore.Value.One: s.value = Semaphore.Value.Zero else: # add the process to the waiting queue s.q.put(p) p.Sleep() def V(self, s): if s.q.qsize() == 0: s.value = Semaphore.Value.One else: # select a process from waiting queue p = s.q.queue[0] # remove the process from waiting as it has # been sent for CS s.q.get() p.Wakeup()>

using System.Collections.Generic; class Semaphore {  public enum value { Zero, One }  public Queueq = нова черга();  public void P(Semaphore s, Process p) { if (s.value == value.One) { s.value = value.Zero;  } else { // додати процес до черги очікування q.Enqueue(p);  p.Sleep();  } } public void V(Semaphore s) { if (s.q.Count == 0) { s.value = value.One;  } else { // вибрати процес із черги очікування Process p = q.Peek();  // видалення процесу з очікування, оскільки // було надіслано для CS q.Dequeue();  p.Wakeup();  } } }>

class Semaphore {  constructor() {  this.value = 0;  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  this.q = [];  }  P() {  if (this.value == 1) {  this.value = 0;  } else {  // add the process to the waiting queue  this.q.push(P);  sleep();  }  }  V() {  if (this.q.length == 0) {  this.value = 1;  } else {  // select a process from waiting queue  let p = this.q.shift();  // remove the process from waiting as it has been  // sent for CS  wakeup(p);  }  } }>

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

java, якщо інше

Тепер припустимо, що є ресурс, кількість екземплярів якого дорівнює 4. Тепер ми ініціалізуємо S = 4, а решта те саме, що і для двійкового семафора. Кожного разу, коли процес хоче отримати цей ресурс, він викликає P або чекає функції, а коли це зроблено, він викликає V або сигнальну функцію. Якщо значення S стає дорівнює нулю, то процес повинен чекати, поки S не стане додатним. Наприклад, припустимо, що є 4 процеси P1, P2, P3, P4, і всі вони викликають операцію очікування на S (ініціалізується 4). Якщо інший процес P5 хоче отримати ресурс, він повинен почекати, поки один із чотирьох процесів не викличе сигнальну функцію, і значення семафора стане додатним.

Обмеження:

1. Одним із найбільших обмежень семафора є інверсія пріоритету.
2. Взаємоблокування, припустімо, що процес намагається розбудити інший процес, який не перебуває в стані сну. Таким чином, взаємоблокування може заблокувати необмежений час.
3. Операційна система повинна відстежувати всі виклики, щоб очікувати і сигналізувати семафору.

Проблема в цій реалізації семафора:

Основна проблема із семафорами полягає в тому, що вони вимагають зайнятого очікування. Якщо процес знаходиться в критичній секції, інші процеси, які намагаються увійти в критичну секцію, чекатимуть, поки критична секція не буде зайнята жодним процесом. Щоразу, коли будь-який процес очікує, він постійно перевіряє значення семафора (погляньте на цей рядок, поки (s==0); в операції P) і витрачає цикл ЦП.

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

довідкові типи java

Реалізація: Рахунковий семафор

struct Semaphore {  int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq; }; P(Семафор s) { s.value = s.value - 1;  якщо (s.value< 0) {  // add process to queue  // here p is a process which is currently executing  q.push(p);  block();  }  else  return; } V(Semaphore s) {  s.value = s.value + 1;  if (s.value <= 0) {  // remove process p from queue  Process p = q.pop();  wakeup(p);  }  else  return; }>

import java.util.LinkedList; import java.util.Queue; // semaphore class  class Semaphore {  // our value  int value;  Queueq;  public Semaphore(int value) { this.value = value;  q = новий LinkedList();  } public void P(Process p) { value--;  якщо (значення< 0) {  q.add(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  Process p = q.remove();  p.wakeup();  }  } }>

import heapq # Global Variable to track the Processes going into Critical Section COUNTER=1 class Semaphore: def __init__(self,value): # Value of the Semaphore passed to the Constructor self.value=value # The Waiting queue which will be using the heapq module of Python self.q=list() def getSemaphore(self):  ''' Function to print the Value of the Semaphore Variable ''' print(f'Semaphore Value: {self.value}') def block(process): print(f'Process {process} Blocked.') def wakeup(process): print(f'Process {process} Waked Up and Completed it's work.') def P(s): global COUNTER s.value=s.value-1 if(s.value<0): heapq.heappush(s.q,COUNTER) block(COUNTER) else: print(f'Process {COUNTER} gone inside the Critical Section.') COUNTER+=1 return def V(s): global COUNTER s.value=s.value+1 if(s.value<=0): p=heapq.heappop(s.q) wakeup(p) COUNTER-=1 else: print(f'Process {COUNTER} completed it's work.') COUNTER-=1 return # Can Pass the Value of the Counting Semaphore to the Class Constructor # Example for Counting Semaphore value as 2 s1=Semaphore(2) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() P(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() V(s1) s1.getSemaphore() # This Code is Contributed by Himesh Singh Chauhan>

using System.Collections.Generic; public class Semaphore {  public int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  Queueq = нова черга();  public void P(Process p) { value--;  якщо (значення< 0) {  // add process to queue  q.Enqueue(p);  p.block();  }  }  public void V()  {  value++;  if (value <= 0) {  // remove process p from queue  Process p = q.Dequeue();  p.wakeup();  }  } }>

// Define a Semaphore object function Semaphore() {  this.value = 0;  this.q = []; // Initialize an array to act as a queue } // Implement the P operation Semaphore.prototype.P = function(p) {  this.value = this.value - 1;  if (this.value < 0) {  // Add process to queue  this.q.push(p);  // Assuming block() and wakeup() functions are defined elsewhere  block();  } }; // Implement the V operation Semaphore.prototype.V = function() {  this.value = this.value + 1;  if (this.value <= 0) {  // Remove process p from queue  var p = this.q.shift();  // Assuming wakeup() function is defined elsewhere  wakeup(p);  } }; // This code is contributed by Susobhan Akhuli>

У цій реалізації кожного разу, коли процес очікує, він додається до черги очікування процесів, пов’язаних із цим семафором. Це робиться через системний виклик block() цього процесу. Коли процес завершено, він викликає функцію сигналу, і один процес у черзі відновлюється. Він використовує системний виклик wakeup().

Переваги семафорів:

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

Недоліки семафорів:

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