---
title: SO Lista 12
tags: SO
author: Mateusz Reis
---
# SO LISTA 12
## Zadanie 1

_thread long myid;
static char **strtab;
void *thread(void *vargp) 
{
    myid = *(long *)vargp;
    static int cnt = 0;
    printf("[%ld]: %s (cnt=%d)\n", myid, strtab[myid], ++cnt);
    return NULL;
}

int main(int argc, char *argv[]) 
{
    strtab = argv;
    while (argc > 0) 
    {
        myid = --argc;
        pthread_create(&tid, NULL, thread, (void *)&myid);
    }
}

Załóżmy że mamy dwa wątki wtedy tabelka naszych zmiennych może wyglądać tak:
|var name|ref from main|ref from thread1|ref from thread2|
|-|-|-|-|
|myid.m|y|y|y|
|myid.t1|n|y|n|
|myid.t2|n|n|y|
|strtab|y|y|y|
|vargp.t1|n|y|n|
|vargp.t2|n|n|y|
|cnt|n|y|y|
|argc|y|n|n|
|argv[0]|n|y|y|

Zmienne współdzielone:
- strtab
- cnt
- argv[0]
- myid.m
Zmienne które mogą doprowadzić do wyścigu
- cnt
- myid.m
- strtab/argv

## Zadanie 2

**sekcja krytyczna** - fragment programu w którym korzysta się z zasobu dzielonego, który może być używany tylko przez jeden wątek naraz.
Rozwiązanie problemu sekcji krytycznej musi zawierać:
- nigdy w sekcji krytycznej nie mogą znaleźć się dwa procesy jednocześnie
- nie możemy zakładać nic o prędkości ani liczbie procesorów
- żaden proces będący poza sekcją krytyczną nie może blokować innych procesów
- żaden proces nie może czekać w nieskończoność na dostęp do sekcji krytycznej

**wyłączenie przerwać** - programy są wywłaszczane i wznawiane przez przerwania zegarowe, jeśli je wyłączymy proces nie może zostać wywłaszczony

Wyłączenie przerwań jest bardzo niebezpieczne (nieskończona pętla w sekcji krytycznej w której wyłączyliśmy przerwania nigdy się nie skończy i nie będzie można jej zabić) natomiast wyłączyć przerwania możemy tylko dla jednego procesora w przypadku komputerów wielo-rdzeniowych wyłączenie przerwań dla jednego rdzenia nic nie da.

Sekcje krytyczne powinny być jak najkrótsze ponieważ nie mogą być wykonywane równolegle więc jest im większa część programu to sekcja krytyczna tym mniejsze przyspieszenie uzyskamy.

## Zadanie 3
**instrukcja atomowa** - instrukcja, która jest niepodzielna. Wykonuje się w całości albo wcale
**blokada wirująca** - blokada która poleda na tym, że wątek, który czeka na jej zwolnienie czeka w pętli

typedef int spin_t;

bool compare_and_swap(int &dest,int val,int new_val)
{
    if(*dest==val)
    {
        *dest=new_val;
        return true;
    }
    return false;
}

void lock(spin_t *lock)
{
    while(!compare_and_swap(lock,0,1));
}

void unlock(spin_t *lock)
{
    *lock=0;
}

Blokada wirująca nie jest sprawiedliwa ponieważ nie daje gwarancji na dostęp do zasobów przez wątek, przez co wątek może wirować w nieskończoność co doprowadza do głodzenia.

Proces w przestrzeni użytkownika może zostać wywłaszczony podczas założonej blokady, wtedy wszystkie pozostałe wątki będą kręcić się w kółko oczekując na zwolnienie i paląc cykle procesora. Jest to szczególnie bolesne gdy mamy dużo procesów i mało rdzeni/wątków procesora.

## Zadanie 4

Warunki konieczne do wystąpienia zakleszczenia:
1. - Mutual-Exclusion - zasoby są przydzialne na wyłączność wybranym procesom lub są wolne
2. - Hold-and-Wait - proces trzyma dostęp do przynajmniej jednego zasobu i żąda kolejnego zasobu
3. - No-Preemption - zasoby mogą być zwalniane tylko przez procesy i nie można im ich zabrać
4. - Circular Wait - istnieje cykl procesów w którym każdy proces przetrzymuje zasób który jest żądany przez kolejny proces w cyklu

**Zapobieganie zakleszczeniom** - zarządzanie zasobami w taki sposób żeby nie wystąpiły zakleszczenia :
- Ad.1 - unikanie przypisywania danych na wyłączność:
- dane tylko do odczytu mogą być przypisane wielu procesom
- zasoby do pisania - spooling (dane wysyłamy do bufora gdzie następnie są wykorzystywane/zapisywane przez urządzenie) lub użycie specjalnego mechanizmu, który nie zakłada blokady

- Ad.2 - procesy żądają zasobów przed rozpoczęciem działania lub zwalniają trzymany zasób jeśli nie mogą otrzymać kolejnego
- Ad.3 - wirtualizacja zasobów, przez co można wywłaszczyć proces w trakcie korzystania z zasobów
- Ad.4 - wprowadzamy zasadę, że procesy mają prawo używać tylko jednego zasobu jednocześnie, jeśli chcą otrzymać kolejny zasób to muszą zwolnić poprzedni

Rozwiązania stosowane w praktyce:
- spooling - Ad.1 - odsyłamy zasoby do bufora i zajmujemy się czymś innym (np. wysyłamy plik do bufora skąd pobiera go drukarka i drukuje go samodzielnie )
- partial lock ordering - Ad.4 - mapowanie pamięci w Linuxie

Rozwiązania kłopotliwe:
- Ad.3 nie wszystkie zasoby da się zwirtualizować
- Ad.1 możliwe przepełnienie bufora lub rozpoczęcie zapisywania tylko cześci zasobów
- Ad.2 musielibyśmy znać wszystkie zasoby od razu i byłyby one nabywane wcześniej niż są potrzebne, zwalniając zasoby można doprowadzić do livelock-a

## Zadanie 5

shared boolean blocked [2] = { false, false };
shared int turn = 0;
void P (int id) 
{
    while (true) 
    {    
        blocked[id] = true;
        while (turn != id) 
        {
            while (blocked[1 - id])continue;
            turn = id;
        }
        /* put code to execute in critical section here */
        blocked[id] = false;
    }
}
void main() { parbegin (P(0), P(1)); }

Kontrprzykład :
- p1 wchodzi do pierwszej pętli
- p1 ustawia blocked[1] na true
- p1 wchodzi do petli while(turn!=id) bo turn na poczatku wynosi 0
- p1 sprawdza blocked[0] i wychodzi z petli while(blocked[1-1])
- p0 wchodzi do pierwszej petli i ustawia blocked[0] na true
- p0 nie wchodzi do drugiej petli while(turn!=id) bo turn na poczatku wynosi 0
- p0 zaczyna wykonywac sekcje krytyczna
- p1 ustawia turn na 1 i wychodzi z petli
- p1 zaczyna wykonywac sekcje krytyczna

## Zadanie 6

**Aktywne czekanie** - stan w którym wątek czeka na zdjęcie blokady ale nie robi nic sensownego tylko marnuje cykle procesora

**yield()** - proces "oddaje procesor" tzn. informuje że chce zmienić swój status z "running" na "ready"

Użycie yield() nie rozwiązuje problemu głodzenia oraz przy dużej liczbie wątków nie jest dużo lepsze niż aktywne czekanie.

**blokady usypiające