Реализация семафора в C - PullRequest
       42

Реализация семафора в C

0 голосов
/ 27 февраля 2019

Я работаю над простой реализацией семафора в C, и хотя моя реализация работает (как двоичный семафор), у меня есть вопрос относительно его действительности.

Моя проблема связана с моим определениеммоя функция ожидания:

void Wait(int semid) {
    char *shmPtr;

    shmPtr = shmat(semid, NULL, 0);

    if(shmPtr == (void *) -1){
        printf("Could not attach to semaphore...\n");
        exit(1);
    } 

    //Wait for the value in shared memory to 
    //equal 0, then set it equal to 1,
    //detach and return
    while( (*shmPtr) != 0);

    (*shmPtr) = 1;

    if(shmdt(shmPtr) < 0) {
        printf("Cannot detach from semaphore...");
    }

    return;

}

Мой вопрос связан с циклом while ((* shmPtr)! = 0).Допустим, у нас есть 2 процесса, которые ожидают.Третий процесс изменяет значение семафора на равное 0 (игнорируя тот факт, что это двоичная реализация семафора).

Меня беспокоит то, что если процесс 1 оценивает условие цикла while как ложное, а затем контекст ЦП переключается на процесс 2, прежде чем установить значение семафора равным 1, оба процесса войдут в критическую секцию.

Есть ли лучший способ реализовать функцию ожидания?Я видел много людей, использующих pthread_cond_wait, но в нем используется мьютекс, который по существу отрицает цель реализации семафора.

Спасибо

РЕДАКТИРОВАТЬ: добавление реализации TestAndSet в C из Википедии в C дляссылка в комментариях

#define LOCKED 1

int TestAndSet(int* lockPtr) {
    int oldValue;

    oldValue = *lockPtr;
    *lockPtr = LOCKED;
    // -- End of atomic segment --

    return oldValue;
}

Ответы [ 2 ]

0 голосов
/ 28 февраля 2019

Я не знаю, как это сделать на ПК (если вы узнаете, вернитесь и напишите свой собственный ответ), но вам нужно то, что я называю " атомная защита доступа «.Другими словами, вам нужен механизм для принудительного атомарного доступа к данной переменной в течение заданного промежутка времени.Это означает, что вы, по сути, заставляете все потоки / процессы на мгновение приостанавливаться, в то время как 1 и только 1 поток получает доступ к переменной.Затем он выполняет свою функцию с переменной (например, читает, изменяет, записывает в нее), а затем повторно включает другие потоки, когда это сделано.Таким образом, вы гарантируете атомарный доступ к этой переменной этим потоком во время этих операций.Теперь все условия гонки решены.

Я полагаю, что в C это сильно зависит от архитектуры и опирается на функции C, написанные на встроенном коде сборки через что-то вроде ключевого слова __asm, и / или полагается на установку битов в определенных аппаратных регистрах наопределенные значения для обеспечения определенного поведения.Пример использования ключевого слова __asm: http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.100748_0606_00_en/ddx1471430827125.html.

Пример встроенного кода сборки, заключенного в функцию C:

int add(int i, int j)
{
  int res = 0;
  __asm ("ADD %[result], %[input_i], %[input_j]"
    : [result] "=r" (res)
    : [input_i] "r" (i), [input_j] "r" (j)
  );
  return res;
}

После того, как у вас есть "функции atomic access guard", чтобы предоставить вам атомарный доступ, вы можете сделать что-то вроде следующего:

// atomic access guard ON

// Do whatever you want here: it's all atomic now!
// Read, modify, write, etc.
// - CAUTION: NO OTHER THREADS CAN RUN DURING THIS TIME, SO GET OUT OF THIS QUICKLY

// atomic access guard OFF

В одноядерных системах, таких как микроконтроллеры, с которыми я знаком (STM32 и AVR/ Arduino), атомарный доступ обеспечивается простым отключением всех прерываний.Пример: на микроконтроллерах STM32 с ядром ARM выполните следующие действия, используя необходимые функции CMSIS (предоставляемые ARM):

// Read PRIMASK register, check interrupt status before you disable them 
// Returns 0 if they are enabled, or non-zero if disabled 
uint32_t prim = __get_PRIMASK();

// Disable interrupts 
__disable_irq();

// Do some stuff here which can not be interrupted 

// Enable interrupts back, but only if they were previously enabled (prevents nesting problems)
if (!prim) 
{
    __enable_irq();
}

Источник: https://stm32f4 -discovery.net / 2015/06/ how-to-правильно-enableisable-interrupts-in-arm-cortex-m /

При использовании FreeRTOS (бесплатная операционная система реального времени) , выполните следующие действия:

taskENTER_CRITICAL() // This supports nested calls, and ends up calling `portDISABLE_INTERRUPTS()` anyway.

// do your atomic access here

taskEXIT_CRITICAL() 

См .: https://www.freertos.org/taskENTER_CRITICAL_taskEXIT_CRITICAL.html

При использовании микроконтроллеров с ядром AVR, таких как ATmega328 (базовый процессор Arduino Uno), выполните следующие действия:

uint8_t SREG_bak = SREG; //save global interrupt state
cli(); //clear (disable) interrupts

//atomic variable access guaranteed here

SREG = SREG_bak; //restore interrupt state

См. Мой ответ здесь: https://stackoverflow.com/a/39693278/4561887

Так что теперь вам нужно провести некоторое исследование (и, пожалуйста, отправьте ответ), о том, как применить такой принцип в C в вашей операционной системе и / или архитектуре.и / или через некоторые специальные вызовы вашего ядра или что-то в этом роде.Это может даже потребовать, чтобы вы написали собственную встроенную сборку, чтобы выполнить эту работу, а затем обернули ее в функцию C для вызова.

Я с нетерпением жду, когда вы добьетесь этого.

Обновление : Я просто покопался в исходном коде FreeRTOS, чтобы посмотреть, как они отключают прерывания, и вот чтоЯ нашел для процессора ARM Cortex M3, такого как микроконтроллеры STM32, при использовании компилятора GCC:

Из "FreeRTOSv9.0.0 / FreeRTOS / Source / portable / GCC / ARM_CM3 / portmacro.h":

#define portDISABLE_INTERRUPTS() vPortRaiseBASEPRI()

portFORCE_INLINE static void vPortRaiseBASEPRI( void )
{
uint32_t ulNewBASEPRI;

    __asm volatile
    (
        "   mov %0, %1                                              \n" \
        "   msr basepri, %0                                         \n" \
        "   isb                                                     \n" \
        "   dsb                                                     \n" \
        :"=r" (ulNewBASEPRI) : "i" ( configMAX_SYSCALL_INTERRUPT_PRIORITY )
    );
}
0 голосов
/ 27 февраля 2019

Как прокомментировал Том, чтобы семафоры были верны, вам нужно атомарный тест-и-набор или сравнение-и-своп (сравнение-обмен).

Но это еще не все.Поскольку вы используете разделяемую память (т. Е. Несколькими процессами), элементарных операций, предоставляемых C11 ( Link ), недостаточно.

Поскольку вы все равно вызываете функции Posix, я полагаю, чтоу вас есть доступ к семафорам Posix.

"Семафоры POSIX позволяют процессам и потокам синхронизировать свои действия." ( Link )

...