Семафоры с тестом и набором (возможна ошибка при реализации кода) - PullRequest
Новая
       97

Семафоры с тестом и набором (возможна ошибка при реализации кода)

0 голосов
/ 26 апреля 2020

Я изучал семафоры и искал реализацию семафоров на сайте (http://faculty.salina.k-state.edu/tim/ossg/IPC_sync/ts.html), однако, я не понимаю реализацию, чтобы никто не заходил на сайт, код показано ниже. 

struct semaphore {
    int value = <initial value>;
    boolean mutex = FALSE;
    boolean hold = TRUE;
    queue m, h;
};

shared struct semaphore s;

/* P() */
acquire_semaphore(struct semaphore s) {
    while(TS(s.mutex)) WAIT(s.m);    /* wait for intertal mutex */
    s.value--;
    if(s.value < 0) {
        s.mutex = FALSE;
        SIGNAL(s.m);
        while(TS(s.hold)) WAIT(s.h); /* wait - too many out */
    }
    else
        s.mutex = FALSE;
        SIGNAL(s.m);
}

/* V() */
release_semaphore(struct semaphore s) {
    while(TS(s.mutex)) WAIT(s.m);   /* wait for intertal mutex */
    s.value++;
    if(s.value >= 0) {
        s.hold = FALSE;
        SIGNAL(s.h);
    }
    s.mutex = FALSE;
    SIGNAL(s.m);
}

boolean Test_and_Set( boolean memory[m] )
{ [
    if( memory[m] )        // lock denied
        return True;
    else {                 // lock granted
        memory[m] = True;
        return False;
    }
  ]
}

Метод TS, который я предположил, это TestandSet (), который также показан выше, скопированный с того же веб-сайта, моя проблема заключается в том, что если 3 процесса приходят вместе и вызывают acqu_semaphore с семафором, инициализированным значением 1, тогда значение семафора станет равным -2, а процессы p2 и p3 будут go в очередь h и никогда не будут сигнализироваться на пробуждение, это кажется неправильным, поэтому я предполагаю, что есть ошибка в коде? Мое предположение, чтобы исправить это, состояло бы в том, что строка "if (s.value> = 0) {" в семафоре релиза должна быть "if (s.value <= 0) {", так как это будет вызывать следующий процесс в удерживаемом (з) очередь. Ниже показана таблица, где я работаю над кодом вручную с 3 процессами с именами p1, p2 и p3. Спасибо за любую помощь. </p> 

Action            | Value | Mutex | Hold | m  | h       | Comments
init              | 1     | FALSE | TRUE | [] | []      | 
P1 aquire lock    | 0     | FALSE | TRUE | [] | []      | P1 now has the semaphore
P2 aquire lock    | -1    | FALSE | TRUE | [] | [P2]    | P2 added to the h queue
P3 aquire lock    | -2    | FALSE | TRUE | [] | [P2,P3] | p3 added to the h queue
P1 release lock   | -1    | FALSE | TRUE | [] | [P2,P3] | lock released but since s.value is <= 0 signal not set to wake s.h queue

1 Ответ

1 голос
/ 27 апреля 2020

Первый: 

acquire_semaphore(struct semaphore s)

Когда это вызывается, семафор предоставляется значением и почти наверняка должно быть ссылкой . Когда оно равно значению , любые изменения, сделанные при приобретении, вообще не отражаются в s [см. Примечание 1]. Итак, что бы ни делало приобретение, оно не обеспечивает семантику получения семафора. То же самое, скорее всего, относится к ссылкам на неопределенные типы очередей (s-> m, s-> h).

Это еще один класс c: 

}
else
    s.mutex = FALSE;
    SIGNAL(s.m);

Что на самом деле понимается компилятором как: 

} else {
    s.mutex = FALSE;
}
SIGNAL(s.m);

Что не кажется правильным, но многое кажется неправильным. Так что, если это вообще что-то делает, это случайно (может быть, неудача?). Игнорируйте его, если только вам не назначено его исправить.

Во-вторых, он пытается реализовать семафоры поверх WAIT & SIGNAL, которые эквивалентны семафору; Вполне вероятно, что его можно исправить следующим образом: 

struct semaphore {
    queue s;
};
acquire_semaphore(struct semaphore *s) {
    WAIT(&s->s);
}
release_semaphore(struct semaphore *s) {
    SIGNAL(&s->s);
}

и покончить с ним.

[примечание]: разумно расположить семафор следующим образом: 

struct semaphore {
     struct _semaphore *p;
};
struct _semaphore {
     /* actual bits to make a semaphore here */
};

Который имеет приятный эффект разрешения семантики копирования в семафоре, поэтому, если кто-то делает что-то вроде перераспределения структуры, содержащей семафор, он ведет себя, как и ожидалось. Это не делается в этом примере, но это хорошо запомнить.

...