Semafory to zwykłe zmienne używane do koordynowania działań wielu procesów w systemie komputerowym. Służą do wymuszania wzajemnego wykluczania, unikania sytuacji wyścigowych i wdrażania synchronizacji między procesami.

Proces korzystania z semaforów zapewnia dwie operacje: oczekiwanie (P) i sygnał (V). Operacja oczekiwania zmniejsza wartość semafora, a operacja sygnału zwiększa wartość semafora. Gdy wartość semafora wynosi zero, każdy proces wykonujący operację oczekiwania zostanie zablokowany do czasu, aż inny proces wykona operację sygnalizacyjną.

Semafory służą do implementowania sekcji krytycznych, czyli obszarów kodu, które muszą być wykonywane tylko przez jeden proces na raz. Używając semaforów, procesy mogą koordynować dostęp do współdzielonych zasobów, takich jak pamięć współdzielona lub urządzenia we/wy.

Semafor to specjalny rodzaj danych synchronizacyjnych, którego można używać wyłącznie za pośrednictwem określonych prymitywów synchronizacji. Gdy proces wykonuje operację oczekiwania na semaforze, operacja ta sprawdza, czy wartość semafora jest> 0. Jeśli tak, zmniejsza wartość semafora i pozwala procesowi kontynuować wykonywanie; w przeciwnym razie blokuje proces na semaforze. Operacja sygnałowa na semaforze aktywuje proces zablokowany na semaforze, jeśli taki istnieje, lub zwiększa wartość semafora o 1. Ze względu na tę semantykę semafory nazywane są również semaforami zliczającymi. Początkowa wartość semafora określa, ile procesów może przejść operację oczekiwania.

Semafory są dwojakiego rodzaju:

1. Semafor binarny –
   Nazywa się to również blokadą mutex. Może mieć tylko dwie wartości – 0 i 1. Jego wartość jest inicjalizowana na 1. Służy do implementacji rozwiązania problemów sekcji krytycznej w wielu procesach.
2. Liczenie semaforów –
   Jego wartość może obejmować dowolną domenę. Służy do kontrolowania dostępu do zasobu, który ma wiele instancji.

Zobaczmy teraz, jak to się dzieje.

char + int w Javie

Najpierw przyjrzyj się dwóm operacjom, których można użyć, aby uzyskać dostęp do zmiennej semafora i ją zmienić.

Kilka punktów dotyczących operacji P i V:

1. Operacja P nazywana jest także operacją oczekiwania, uśpienia lub wyłączenia, a operacja V nazywana jest także operacją sygnalizowania, budzenia lub budzenia.
2. Obie operacje są niepodzielne, a semafory są zawsze inicjowane na jeden. Tutaj atomowy oznacza zmienną, na której odczyt, modyfikacja i aktualizacja odbywają się w tym samym czasie/momencie bez wywłaszczenia, tj. pomiędzy odczytem, ​​modyfikacją i aktualizacją nie jest wykonywana żadna inna operacja, która mogłaby zmienić zmienną.
3. Sekcja krytyczna jest otoczona przez obie operacje mające na celu wdrożenie synchronizacji procesów. Zobacz poniższy obrazek. Krytyczna część procesu P znajduje się pomiędzy operacjami P i V.

Przyjrzyjmy się teraz, jak realizuje wzajemne wykluczenie. Niech będą dwa procesy P1 i P2, a semafor s zostanie zainicjowany jako 1. Załóżmy teraz, że P1 wejdzie do swojej sekcji krytycznej, a wartość semafora s wyniesie 0. Teraz, jeśli P2 będzie chciał wejść do swojej sekcji krytycznej, będzie czekać, aż s> 0, może się to zdarzyć tylko wtedy, gdy P1 zakończy sekcję krytyczną i wywoła operację V na semaforach.

W ten sposób dochodzi do wzajemnego wykluczenia. Spójrz na poniższy obrazek, aby uzyskać szczegółowe informacje, które są semaforem binarnym.

Realizacja: Semafory binarne

dodaj tablicę Java

struct semaphore {    enum value(0, 1);  // q contains all Process Control Blocks (PCBs)  // corresponding to processes got blocked  // while performing down operation.  QueueQ; }; P(semafor s) { if (s.value == 1) { s.value = 0;  } else { // dodaj proces do kolejki oczekującej q.push(P) Sleep();  } } V(semafor s) { if (s.q jest pusty) { s.value = 1;  } else { // wybierz proces z kolejki oczekującej Proces p = q.front();  // usuń proces oczekujący, // wysłany do CS q.pop();  Obudź się);  } } // Ten kod został zmodyfikowany przez Susobhana Akhuli>

#include  #include #include struct semaphore{  QueueQ;  wartość całkowita; }; void P(semafor struktury s) { if (s.value == 1) { s.value = 0;  } else { sq.push(P);   spać();  } } void V(semafor s) { if (s.q jest pusty) { s.value = 1;  } else { // Pobieranie procesu z procesu kolejki oczekującej p = q.front();  // Usuń proces z oczekiwania q.pop();  Obudź się);  } } int main() { printf('To jest Hemish!!');    // Autorem tego kodu jest Himesh Singh Chauhan return 0; } // Ten kod został zmodyfikowany przez Susobhana Akhuli>

import java.util.*; class Semaphore {  public enum Value { Zero, One }  public Queueq = nowa lista połączona();  public Wartość wartości = Wartość.Jeden;  public void P(Semafor s, Proces p) { if (s.value == Value.One) { s.value = Value.Zero;  } else { // dodaj proces do kolejki oczekującej q.add(p);  p.Uśpienie();  } } public void V(Semafor s) { if (s.q.size() == 0) { s.value = Value.One;  } else { // wybierz proces z kolejki oczekującej Proces p = q.peek();  // usuń proces z oczekiwania, // został wysłany do CS q.remove();  p.Pobudka();  } } }>

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 = nowa kolejka();  public void P(Semafor s, Proces p) { if (s.value == wartość.Jeden) { s.value = wartość.Zero;  } else { // dodaj proces do kolejki oczekującej q.Enqueue(p);  p.Uśpienie();  } } public void V(Semafor s) { if (s.q.Count == 0) { s.value = wartość.Jeden;  } else { // wybierz proces z kolejki oczekującej Proces p = q.Peek();  // usuń proces oczekujący, // wysłany do CS q.Dequeue();  p.Pobudka();  } } }>

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);  }  } }>

Powyższy opis dotyczy semafora binarnego, który może przyjmować tylko dwie wartości 0 i 1 i zapewniać wzajemne wykluczanie. Istnieje jeszcze jeden typ semafora, zwany semaforem zliczającym, który może przyjmować wartości większe niż jeden.

Załóżmy teraz, że istnieje zasób, którego liczba instancji wynosi 4. Teraz inicjujemy S = 4, a reszta jest taka sama jak w przypadku semafora binarnego. Ilekroć proces potrzebuje tego zasobu, wywołuje P lub czeka na funkcję, a kiedy to zrobi, wywołuje V lub funkcję sygnałową. Jeśli wartość S osiągnie zero, proces musi poczekać, aż S stanie się dodatnie. Załóżmy na przykład, że istnieją 4 procesy P1, P2, P3, P4 i wszystkie wywołują operację oczekiwania na S (zainicjowaną wartością 4). Jeżeli inny proces P5 potrzebuje zasobu to powinien poczekać aż jeden z czterech procesów wywoła funkcję sygnału i wartość semafora stanie się dodatnia.

Zmienna zmienna Java

Ograniczenia:

1. Jednym z największych ograniczeń semafora jest inwersja priorytetów.
2. Zakleszczenie: załóżmy, że proces próbuje obudzić inny proces, który nie jest w stanie uśpienia. Dlatego zakleszczenie może blokować na czas nieokreślony.
3. System operacyjny musi śledzić wszystkie wywołania oczekiwania i sygnalizować semaforowi.

Problem w tej implementacji semafora:

Główny problem z semaforami polega na tym, że wymagają długiego oczekiwania. Jeśli proces znajduje się w sekcji krytycznej, inne procesy próbujące wejść do sekcji krytycznej będą czekać, aż sekcja krytyczna nie będzie zajęta przez żaden proces. Ilekroć jakiś proces czeka, stale sprawdza wartość semafora (spójrz na tę linię podczas (s==0); w operacji P) i marnuje cykl procesora.

Istnieje również ryzyko wystąpienia blokady, ponieważ procesy wirują w oczekiwaniu na blokadę. Aby tego uniknąć, poniżej przedstawiono inną implementację.

Realizacja: Liczenie semaforów

struct Semaphore {  int value;  // q contains all Process Control Blocks(PCBs)  // corresponding to processes got blocked  // while performing down operation.  QueueQ; }; P(Semafor s) { wartość s = wartość s - 1;  jeśli (s.wartość< 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;  publiczny semafor (wartość int) { this.value = wartość;  q = nowa lista połączona();  } public void P(Proces p) { wartość--;  jeśli (wartość< 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 = nowa kolejka();  public void P(Proces p) { wartość--;  jeśli (wartość< 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>

W tej implementacji, ilekroć proces czeka, jest dodawany do oczekującej kolejki procesów powiązanych z tym semaforem. Odbywa się to poprzez wywołanie systemowe block() tego procesu. Po zakończeniu procesu wywołuje funkcję sygnału i jeden proces w kolejce jest wznawiany. Używa wywołania systemowego wakeup().

Zalety semaforów:

• Prosty i skuteczny mechanizm synchronizacji procesów
• Wspomaga koordynację pomiędzy wieloma procesami
• Zapewnia elastyczny i niezawodny sposób zarządzania udostępnionymi zasobami.
• Można go używać do implementowania sekcji krytycznych w programie.
• Można go użyć, aby uniknąć warunków wyścigowych.

Wady semaforów:

• Może to prowadzić do pogorszenia wydajności z powodu narzutu związanego z operacjami oczekiwania i sygnalizowania.
• Nieprawidłowe użycie może spowodować zakleszczenie.
• Została zaproponowana przez Dijkstrę w 1965 roku i jest bardzo znaczącą techniką zarządzania współbieżnymi procesami za pomocą prostej wartości całkowitej, znanej jako semafor. Semafor to po prostu zmienna całkowita, która jest współdzielona między wątkami. Zmienna ta służy do rozwiązania problemu sekcji krytycznej i osiągnięcia synchronizacji procesów w środowisku wieloprocesorowym.
• Nieprawidłowe użycie może powodować problemy z wydajnością programu.
• Debugowanie i konserwacja może być trudne.
• Może być podatny na warunki wyścigowe i inne problemy z synchronizacją, jeśli nie jest prawidłowo używany.
• Może być podatny na niektóre rodzaje ataków, takie jak ataki typu „odmowa usługi”.