18. Что представляет из себя примитив синхронизации “монитор”? опишите его интерфейс (набор операций) и приведите простой пример использования.

Мониторы были придуманы Хоаром (C. A. R. Hoare) как более безопасный примитив синхронизации. Они проще в использовании, так как не требуют столь высокого внимания, как семафоры.

Монитор представляет собой объект, содержащий один или несколько методов. Примечательной особенностью является то, что в один конкретный момент времени только одна нить может находиться в мониторе, то есть исполнять один из его методов. Ещё одним важным свойством является то, что нити могут на время лишаться эксклюзивного доступа в ожидании некоего события (это реализуется с помощью условных переменных — conditional variables).

Некоторые языки (например, Java) имеют встроенные реализации мониторов. Впрочем, их несложно реализовать и самим, используя, например, библиотеку POSIX Threads (pthread) с её эксклюзивными замќами (mutal lock, mutex — тип pthread_mutex_t) и условными переменными (тип pthread_cond_t).

Интерфейс монитора содержит две операции:

1. Осуществить блокировку доступа к коду

2. Освободить блокировку

Действие монитора аналогично действию одноместного семафора

19. КАКИЕ ИНСТРУКЦИИ АППАРАТНОЙ СИНХРОНИЗАЦИИ ВЫ ЗНАЕТЕ? СРАВНИТЕ ИХ. ПРИВЕДИТЕ НЕСКОЛЬКО ПРИМЕРОВ, КАК НА ИХ ОСНОВЕ МОЖНО ПОСТРОИТЬ РАЗЛИЧНЫЕ ПРИМИТИВЫ СИНХРОНИЗАЦИИ (УСЛОВНЫЕ ПЕРЕМЕННЫЕ, СЕМАФОРЫ, ...).

In computer science, read-modify-write is a class of atomic operations such as test-and-set, fetch-and-add, and compare-and-swap which both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent race conditions in multi-threaded applications. Typically they are used to implement mutexes or semaphores. These atomic operations are also heavily used in non-blocking synchronization.

test-and-set instruction is an instruction used to write to a memory location and return its old value as a single atomic (i.e. non-interruptible) operation. If multiple processes may access the same memory, and if a process is currently performing a test-and-set, no other process may begin another test-and-set until the first process is done. CPUs may use test-and-set instructions offered by other electronic components, such as Dual-Port RAM; CPUs may also offer a test-and-set instruction themselves.

A lock can be built using an atomic test-and-set instruction as follows:

function Lock(boolean *lock) {

while (test_and_set (lock) == 1)

;

}

The calling process obtains the lock if the old value was 0. It spins writing 1 to the variable until this occurs.

fetch-and-add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement mutual exclusion and concurrent algorithms in multiprocessor systems, a generalization of semaphores.

In uniprocessor systems, it is sufficient to disable interrupts before accessing a critical section. However, in multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time[citation needed]; and even with interrupts disabled two or more processors could be attempting to access the same memory at the same time. The fetch-and-add instruction allows any processor to atomically increment a value in memory location, preventing such multiple processor collisions.

Maurice Herlihy (1991) proved that fetch-and-add has a finite consensus number, in contrast to the compare-and-swap operation. The fetch-and-add operation can solve the wait-free consensus problem for no more than two concurrent processes[1].

compare-and-swap CPU instruction ("CAS") (or the Compare & Exchange - CMPXCHG instruction in the x86 and Itanium architectures) is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value. This guarantees that the new value is calculated based on up-to-date information; if the value had been updated by another thread in the meantime, the write would fail. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple Boolean response (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).

int compare_and_swap ( int* reg, int oldval, int newval)

{

int old_reg_val = *reg;

if (old_reg_val == oldval)

*reg = newval;

return old_reg_val;

}

Implementing mutual exclusion with test-and-set

One way to implement Mutual exclusion uses test-and-set in the following way:

boolean lock = false

function Critical(){

while TestAndSet(lock)

skip //spin until lock is acquired

critical section //only one process can be in this section at a time

lock = false //release lock when finished with the critical section

}

With fetch-and-add primitive a mutual exclusion lock can be implemented as:

record locktype {

int ticketnumber

int turn

}

procedure LockInit( locktype* lock ) {

lock.ticketnumber := 0

lock.turn := 0

}

procedure Lock( locktype* lock ) {

int myturn := FetchAndAdd( &lock.ticketnumber )

while lock.turn ≠ myturn

skip // spin until lock is acquired

}

procedure UnLock( locktype* lock) {

FetchAndAdd( &lock.turn )

}

These routines provide a mutual-exclusion lock when following conditions are met:

Locktype data structure is initialized with function LockInit before use

Number of tasks waiting for the lock does not exceed INT_MAX at any time

Integer datatype used in lock values can 'wrap around' when continuously incremented