# Ćwiczenia 5, grupa śr. 10-12, 22 listopada 2023

###### tags: `PRW23` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki | | | | | | | | |
Konrad Kowalczyk | X | X | | X | X | X | X | |
Jakub Krzyżowski | X | | | X | X | X | | |
Łukasz Magnuszewski | | | | | | | | |
Marcin Majchrzyk | X | X | X | X | X | X | | |
Jan Marek | X | | | X | X | X | | |
Marcin Mierzejewski | | | | | | | | |
~~Juan Jose Nieto Ruiz | x | x | x | | x | x | | |
~~Konrad Oleksy | X | X | X | | | | | |
Javier Rábago Montero | X | X | X | X | X | X | X | |
Michał Mękarski | | | | | | | | |
:::

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1
:::success
Autor: Jan Marek
:::


Aby wykazać, że kolejka jest niepoprawna, wystarczy pokazać przykład historii, która nie jest linearyzowalna.


Nie mamy oczekujących wywołań, więć nie musimy rozszerzać H do G (a więc “H=G”).
**G:**

A p.enq(x)
B p.enq(y)
B p: void
B p.deq()
B p: EmptyException
A p: void

**S:**

[...]
B p.enq(y)
B p: void
[...]
B p.deq()
B p: EmptyException
[...]

Aby utworzyć `S`, musimy w któreś `[...]` wstawić

A p.enq()
A p: void

jednak możemy zauważyć, że nie ważne gdzie je wstawimy, to nie otrzymamy legalnej sekwencyjnej historii S (ponieważ nie będziemy spełniać specyfikacji kolejki FIFO - tzn. dostajemy wyjątek 'EmptyException' kiedy kolejka p nie jest pusta), a więc G nie odpowiada żadnej legalnej sekwencyjnej historii S, co oznacza, że H=G nie jest linearyzowalna.

## Zadanie 2
:::success
Autor: Konrad Kowalczyk
:::

public class HWQueue<T> {
	AtomicReference<T>[] items;
	AtomicInteger tail;
	static final int CAPACITY = Integer.MAX_VALUE;
	public HWQueue() {
		items = (AtomicReference<T>[]) Array.newInstance(AtomicReference.class,CAPACITY);
		for (int i = 0; i < items.length; i++) {
			items[i] = new AtomicReference<T>(null);
		}
		tail = new AtomicInteger(0);
	}
	public void enq(T x) {
		int i = tail.getAndIncrement();
		items[i].set(x);
	}
	public T deq() {
		while (true) {
			int range = tail.get();
			for (int i = 0; i < range; i++) {
				T value = items[i].getAndSet(null);
				if (value != null) {
					return value;
				}
			}
		}
	}
}

<h4><b>int i = tail.getAndIncrement();</b></h4>


W zlinearyzowanej w taki sposób historii spodziewalibyśmy się, że w funkcji `deq()` ściągniemy z kolejki x. Jednak w rzeczywistości w momencie wykonania `deq()` w kolejce x się jeszcze nie znalazł, za to znalazł się y. W takim razie w funkcji `deq()` z kolejki wyciągniemy y, co jest niezgodne z naszą linearyzacją.

<h4><b>items[i].set(x);</b></h4>


W zlinearyzowanej w taki sposób historii spodziewalibyśmy się, że w funkcji `deq()` ściągniemy z kolejki y. Jednak w rzeczywistości miejsce, do którego przypiszemy x zostało wybrane wcześniej niż miejsce, do którego przypiszemy y, więc `deq()` ściągnie z kolejki x, co jest niezgodne z naszą linearyzacją.

Zatem w treści metody `enq()` nie ma pojedynczego punktu linearyzacji. Jednak to nie oznacza, że `enq()` nie jest linearyzowalna, ponieważ punkt linearyzacji może być różny dla każdego wykonania funkcji w naszej historii.

## Zadanie 3
:::success
Autor: Konrad Oleksy
:::


* przy próbie włożenia elementu do kolejki mamy pewność, że na danej pozycji tabeli tylko raz zostanie zapisana wartość. zapewania nam to atoma instrukcja: **tail.getAndIncrement()**
* przy próbie wyciągniecia elementu z kolejki mamy pewność, że na wartość zostanie przeczytana tylko raz i usatwiona na null w operacji atomowej: **items[i].getAndSet(null)**
* wszystkie elementy ustawione w tablicy są na pozycjach od 0 do tail

Mamy również pewność, że gdy różne wątki bedą próbować dodać element do kolejki to wartości bedą pożniej wyciągane w tej samej kolejności, ponieważ nawet jeśli wątki ustawią wartość w tablicy(**items[i].set(x)**) to przy wyciągnia ich z koleji sprawdzana jest tablica od pierwszej pozycji.

## Zadanie 4
:::success
Autor: Jakub Krzyżowski
:::

**Nieczekanie:** każde wywołanie metody kończy się w skończonej liczbie kroków.

**Niewstrzymywanie:** zawsze *jakieś* wywołania metody kończą się w skończonej liczbie kroków.

Te własności są **nieblokujące** ponieważ dowolne nieoczekiwane opóźnienie działania jednego wątku nie oznacza, że wątek ten blokuje działanie innych wątków i **niezależne**, bo gwarantują, że program jako całość wykonuje postępy niezależnie od tego które wątki wywołuje planista.

Niezakleszczenie i niezagłodzenie są blokujące, ponieważ nieoczekiwane opóźnienie działania wątku może uniemożliwić postęp innym wątkom i zależne, bo postęp jest możliwy tylko, jeśli system daje pewne gwarancje (np. że każdy wątek wyjdzie z sekcji krytycznej w *rozsądnym czasie*.)

Współbieżna metoda wykorzystująca zamki nie może być nieczekająca.
W takiej metodzie zazwyczaj dochodzi do sytuacji gdzie jeden wątek próbuje zająć zamek, który zajął już inny wątek. W takim wypadku ten wątek musi czekać, aż tamten zwolni zamek. To oczekiwanie tworzy możliwość nieokreślonych opóźnień -> powtarzania kroku sprawdzenia czy zamek został zwolniony nie wiadomo ile razy. Co jest sprzeczne z definicją metod nieblokujących.

Metoda `weird()` jest nieczekająca, bo każde wywołanie kończy się w określonej, skończonej liczbie kroków.
Nie jest za to nieczekająca z limitem kroków, bo $2^i$ nie da się ograniczyć przy $i \rightarrow \infty$.

## Zadanie 5
:::success
Autor: Javier Rábago Montero
:::

public class Reg64 {
    private int reg1; // 32-bit register 1
    private int reg2; // 32-bit register 2
    
    public void write(long value) {
        reg1 = (int) (value & 0xFFFFFFFF); // Write lower 32 bits to reg1
        reg2 = (int) (value >>> 32); // Write upper 32 bits to reg2
    }
    
    public long read() {
        long value = reg2; // Read upper 32 bits from reg2
        value = (value << 32) | (reg1 & 0xFFFFFFFFL); // Combine upper and lower 32 bits
        return value;
    }
}

It is safe because if write doesn’t overlap with read, read will return the last written value, and if they overlap it will return a value within the allowed range of values.
It is not regular because 2 threads can write at the same time (depending on the context this code is being used, like with no lock or queue), meaning that both write registers at the same time and a subsequent read would return something that has never been written.
It is not atomic because it is not regular.

:::

## Zadanie 6
:::success
Autor: Marcin Majchrzyk
:::

public void lock() {
    flag[i] = true;
    victim = i;
    while (flag[j] && victim == i) {};
}

public void unlock() {
    flag[i] = false;
}

Dowód warunku niezagłodzenia nie jest naruszony, ponieważ zależy on od zmiennej victim, która dalej jest atomowa

Dowód warunku wzajemnego wykluczenia mógłby być złamany, gdy oba wątki odczytają z tablicy flag wartości false. Niepewność w odczycie z regularnego rejestru występuje tylko wtedy gdy odczyt i zapis nachodzą na siebie.

                                 write(flag[A]=true)   write(victim=A)
A                                      <------>            <------>

B        <------>          <------>        <------>     <------>
    write(flag[B]=true) write(victim=B) read(flag[A]) read(victim)

- jeżeli wątek B odczyta ```flag[A] == true``` to oczekuje na zmianę zmiennej ```victim```, po czym wchodzi do sekcji krytycznej, a wątek A jest zablokowany
- jeżeli wątek B odczyta ```flag[A] == false``` to wchodzi do sekcji krytycznej, a wątek A jest zablokowany

## Zadanie 7
:::success
Autor: Javier Rábago Montero
:::

public class SRSWRegister {
    private BooleanSRSWRegister[] registers;
    private BooleanSRSWRegister[] registers2;
    private BooleanSRSWRegister switchRegister;

    public SRSWRegister(int size) {
        this.registers = new BooleanSRSWRegister[size];
        this.registers2 = new BooleanSRSWRegister[size];
        this.switchRegister = new BooleanSRSWRegister();
        switchRegister.write(1);
        for (int i = 0; i < size; i++) {
            registers[i] = new BooleanSRSWRegister();
        }
        for (int i = 0; i < size; i++) {
            registers2[i] = new BooleanSRSWRegister();
        }
        registers[0].write(1);
    }

    public void write(int value) {
        String binary = Integer.toBinaryString( (1 << registers.length ) | value ).substring(1); // Padding with 0s
        int index = 1;
        if (switchRegister.read() == 1) {
            for (int i = registers.length - 1; i > 0; i--) {

                int bit = Character.getNumericValue(binary.charAt(i));

                registers[index].write(bit);
                index++;
            }

        }
        if (switchRegister.read() == 0) {
            for (int i = registers2.length - 1; i > 0; i--) {

                int bit = Character.getNumericValue(binary.charAt(i));

                registers2[index].write(bit);
                index++;
            }
        }
        if(switchRegister.read() == 1){
            switchRegister.write(0);
        }
        else{
            switchRegister.write(1);
        }


    }

    public int read() {
        StringBuilder binary = new StringBuilder();
        if (switchRegister.read() == 0) {
            for (int i = registers.length - 1; i > 0; i--) {
                int bit = registers[i].read();
                binary.append(bit);
            }
        }
        if (switchRegister.read() == 1){
            for (int i = registers2.length - 1; i > 0; i--) {
                int bit = registers2[i].read();
                binary.append(bit);
            } 
        }
        return Integer.parseInt(binary.toString(), 2);
    }

    public static class BooleanSRSWRegister {
        private boolean value;

        public void write(int bit) {
            value = (bit == 1);
        }

        public int read() {
            return value ? 1 : 0;
        }

    }

    public static void main(String[] args) {
        int size = 8;
        SRSWRegister register = new SRSWRegister(size); // Specify the size of the register
        register.write(46);
        int value = register.read();
        System.out.println(value); // Output: 46
    }
}

For a sequential operation is trivial that after writing we will get a correct read of what we wrote.
In the case of a concurrent execution, the first bit of one of the arrays will tell method read() if it can be read or not. As this bit changes only when write has finished writing, read(), if executing concurrently will read the registers that are not being written.

## Zadanie 8
:::Success
Autor: Javier Rábago Montero
:::

We have to prove two implications.

1. If the register under consideration is a regular MRSW register then all its access histories satisfy (*) and (**).

𝑅i → 𝑊i: No read call returns a value from the future. It is obvious that a register cant read something that hasn´t been written yet. The only way it can exist Ri is Wi→𝑅i→ 𝑊i→𝑅i, but Wi can only happen once at most.

𝑊i → 𝑊j→ 𝑅i: No read call returns a value from the distant past, that is, one that precedes the most recently written non-overlapping value. After Wj is written, the value Ri reads no longer exist, and Wi cant write again. This means that as j>i, the statement 𝑊i → 𝑊j→ 𝑅i is a contradiction.

2. If the register under consideration is a good MRSW register and all its access histories satisfy (*) and (**) then the register is a regular one.

There are 2 possibilities:

If R ins’t concurrent with W, let’s assume Wi is the last value written, so the value returned by R can’t be the one written by Wj (remember i<j) according to `(*)`. This means that the only values possible for read are W0, W1 … Wi-1, Wi. From `(**)` as we know Wi was the last and has completely finished as it is not concurrent with R, the only possible value to read is Ri.

If R is concurrent with Wi, the value returned, as before, can’t be the one written by Wj `(*)`. From `(**)`, as is single write, R can´t return a value from the distant past, but as we don´t know if Wi has finished yet, the value returned can be either the one written by Wi or Wi-1.