Zadania

  1. exclusive.h: Biblioteka dostarczająca funkcję void exclusive(char const* lock), która zapewnia, że tylko jeden program może się wykonywać poprzez następujący mechanizm:

    1. Próbę otwarcia pliku na wyłączność (syscall open)

    2. Jeśli plik istniał i zawiera id innego procesu to zamyka plik i czeka na zakończenie danego procesu (np. sprawdzając czy istnieje katalog /proc/{pid}/, wykorzystując wywołanie stat). Następnie próbuje ponownie otworzyć plik na wyłączność.

    3. Zapisuje swój identyfikator procesu do pliku i zamyka go

  2. shared_queue.c implementacja mechanizmu współdzielonej kolejki pomiędzy procesami, z wykorzystaniem współdzielonej pamięci. Implementacja kolejki tablicowa.

Kod testujący zachowanie kolejki
#include "queue.h"
#include <sched.h> // for sched_yield
#include <assert.h>
#include <stdio.h>

// queue is inside shared memory
void test(struct queue *queue)
{
	int pid = fork();
	if (pid == 0) {
		int i = 0;
		for (unsigned i = 0;; ++i) {
			// TODO: Busy loop is not the best solution
			while (full(*queue))
				sched_yield();
			enqueue(queue, i);
			printf("Produced: %d\n", i);
		}
	} else {
		for (unsigned i = 0;; i++) {
			// TODO: Busy loop is not the best solution
			while (empty(*queue))
				sched_yield();
			int read = dequeue(queue);
			printf("Consumed: %d\n", read);
			assert(i == read);
		}
	}
  // unreachable
}

W przykładzie wykorzystano liczby unsigned jako dane kolejki by nie doprowadzić do niezdefiniowanego zachowania przez przekroczenie zakresu typu.

Dodatkowo wykorzystano funkcję sched_yield() pozwalającą na oddanie czasu procesora - redukuje to ilość czasu spędzoną w pętli, a przez to umożliwia sprawiedliwszy podział czasu procesora.

Pliki i ich deskryptory

Wywołania systemowe:

  • open(2) - pozwala na stworzenie i/lub otwarcie pliku (w tym z ekskluzywnym dostępem), zwraca deskryptor pliku;

  • close(2) - zamyka deskryptor;

  • read(2) - odczytuje maksymalnie n bajtów z danego deskryptora;

  • write(2) - zapisuje maksymalnie n bajtów do danego deskryptora.

Deskryptor pliku to unikalny dla każdego procesu identyfikator do zasobu, takiego jak: plik, pipe czy socket. Każdy proces domyślnie ma 3 podstawowe deskryptory: 0 dla standardowego wejścia, 1 dla standardowego wyjścia, 2 dla standardowego wyjścia błędów.

Hello world z użyciem write
#include <assert.h>
#include <string.h>
#include <unistd.h>

int main()
{
	char const* msg = "hello, world";
	int written;
	written = write(STDOUT_FILENO, msg, strlen(msg));
	assert(written == strlen(msg));
	return 0;
}
Interakcja biblioteki standardowej i deskryptorów
#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>

int main()
{
	int fd = open("example.txt", O_WRONLY|O_CREAT|O_TRUNC);
	assert(fd >= 0);

	char const* msg = "Written using syscalls\n";
	int written = write(fd, msg, strlen(msg));
	assert(written == strlen(msg));


	// Create stream for this file descriptor using C standard library
	FILE *f = fdopen(fd, "w");
	assert(f != NULL);

	fprintf(f, "Written using libc\n");
	fclose(f);
	return 0;
}

Ciekawostka: wykorzystanie biblioteki standardowej do komunikacji sieciowej

Dzięki możliwości adaptacji deskryptorów plików przez bibliotekę C, można łatwo stworzyć prostą bibliotekę, która ułatwia programowanie sieciowe.

Pamięć współdzielona między procesami

Wykorzystywany jest mechanizm przypisanego do pamięci pliku z użyciem funkcji mmap. Ponieważ procesy współdzielą plik do którego przypisana jest pamięć, to stan tej pamięci jest pomiędzy nimi spójny (pomijając możliwe problemy współbieżnego zapisu i odczytu).

Poza otwarciem pliku wykorzystywane jest ftruncate do tego by zapewnić odpowiedni rozmiar pliku - pamięć większa od rozmiaru pliku nie będzie współdzielona między procesami.

#include <stdio.h>
#include <assert.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

int main()
{
    int fd;
    if ((fd = open("example.txt", O_RDWR|O_CREAT)) < 0) {
        perror("błąd");
    }

    ftruncate(fd, sizeof(int)*16);

    int* p = (int*)mmap(
        NULL,
        sizeof(int)*16,
        PROT_READ | PROT_WRITE,
        MAP_SHARED,
        fd,
        0);
    if (p == NULL) {
        close(fd);
        perror("mmap");
        return 1;
    }

    int pid = fork();
    if (pid == 0) {
        for (int i = 0;; ++i) {
            p[0] = i;
        }
    } else {
        int prev = p[0];

        for (;;) {
            int x = p[0];
            if (x != prev) {
                printf("Changed: %d\n", x);
                prev = x;
            }
        }
    }

    munmap(p, sizeof(int)*16);
    close(fd);
    return 0;
}

Inne mechanizmy komunikacji międzyprocesowej (IPC)

Podstawowe mechanizmy IPC w ramach systemu Linux: map sysvipc(7). Omówienie dostępne jest też na Wikipedii.

Tablicowa implementacja kolejki

Do implementacji kolejki wykorzystany zostanie struktura bufora cyklicznego.

Circular Buffer Animation
Rysunek 1. Wizualizacja implementacji bufora cyklicznego (z Wikipedii)

Implementacja kolejki z użyciem bufora cyklicznego zakłada posiadanie tablicy n-elementowej o elementach typu T, indeks odczytu (read) i indeks zapisu (write).

Wspiera następujące operacje dla wybranego typu T:

  • void enqueue(struct queue *queue, T value); - przypisuje do elementu o indeksie write element value, a następnie inkrementuje indeks write modulo rozmiar tablicy n

  • T dequeue(struct queue *queue); - zwraca element o indeksie read, a następnie inkrementuje indeks read modulo rozmiar tablicy n

  • bool empty(struct queue); - kolejka jest pusta jeśli indeksy odczytu i zapisu są sobie równe

  • bool full(struct queue); - kolejka jest pełna jeśli kolejny indeks zapisu ((write+1)%n) jest równy indeksowi odczytu

Operacje enqueue i dequeue powinny być chronione przed odpowiednio zapisem do pełnej kolejki i pobraniem elementu z pustej kolejki.

Przykładowy kod testujący implementację (zakładający, że strutuka queue zawiera już w sobie bufor kolejki przez co nie jest potrzebna dynamiczna alokacja):

#include "queue.h"

int main()
{
  struct queue queue = {};
  int data, i;

  assert(empty(queue));
  enqueue(&queue, 10);
  data = dequeue(&queue);
  assert(data == 10);
  assert(empty(queue));

  for (i = 0; !full(queue); ++i) {
    enqueue(&queue, i);
  }

  for (; !empty(queue); --i) {
    dequeue(&queue);
  }
  assert(i == 0);
  return 0;
}

Ciekawostka: Implementacja bufora cyklicznego z użyciem map pamięci

Artykuł Powerful Page Mapping Techniques omawia możliwość tworzenia bufora cyklicznego z wykorzystaniem wirtualnej pamięci. Zaprezentowany jest przykład dla systemu Windows.

Rozwiązanie dostępne jest również w ramach systemu Linux: Using black magic to make a fast circular buffer.