Jan Kończak

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
===== Shared memory =====

It is possible for two processes to use the same physical address range of the
main memory.
\\
Obviously any modification to such memory done by one process is visible to the
other processes that access the memory.
\\
Such memory is called [[https://en.wikipedia.org/wiki/Shared_memory#In_software|shared memory]].

Keep in mind that although two processes use the same physical addresses, the
virtual addresses are usually different.
\\
So do not store any pointers in the shared memory - they will not be valid for
other processes sharing the memory. Storing offsets (differences between
addresses) within a continuous shared memory address range is fine.
\\
There is an exception to this – when two processes share memory as a result of
a ''fork'', then the addresses naturally match.

To use shared memory, a program must explicitly request the kernel to set up a
(possibly shared) memory address range, and tell the kernel what memory should
be associated with the address range.
\\
This is done using the ''**[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/mmap.html|mmap(…)]]**''
<html><span style="float:right"><small>Needs header: <code>sys/mman.h</code></small></span></html>
function with ''**MAP_SHARED**'' flag.
\\
On success, ''mmap'' returns an address to the start of the newly created
address range.

To tell what memory should back the address rage, one must either pass a file
descriptor to ''mmap'' or ask it to allocate some memory.
\\
The latter can be shared only by this process and its newly created child
processes, and is done by adding the ''**MAP_ANONYMOUS**'' flag, passing the
file descriptor of ''-1'' and passing the offset of ''0''.

When the file descriptor passed to ''mmap'' refers to an ordinary file, the
file is automatically copied by the operating system from disk to memory
<small>(a memory page is fetched upon first access within the page)</small>.
Writing the changes back to the file must be done manually by calling the
''**[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/msync.html|msync]]**''
function.

The file descriptor passed to ''mmap'' can also refer to a shared memory object.
Such descriptors are returned by the ''**[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/shm_open.html|shm_open]]**''
function, which has identical arguments as the ''open'' function, but the
returned descriptor refers to a region of main memory associated with a given
name (rather then with a disk file associated with a path). \\
<small>(In portable code, the name shall be one word starting with a slash.)</small>

In ''mmap'' one has to specify the size of the memory range. If this size is
larger than the backing file, then ''mmap'' succeeds, but any accesses to
the mapped addresses beyond the file result in a ''SIGBUS'' signal.
\\
To ensure that the file is large enough, one can use the following functions:
  * ''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/ftruncate.html|ftruncate]]'' <html><span style="float:right"><small>Needs header: <code>unistd.h</code></small></span></html> resizes file to a given size. \\ Whenever the file is larger it is truncated.
  * ''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/posix_fallocate.html|posix_fallocate]]'' <html><span style="float:right"><small>Needs header: <code>fcntl.h</code></small></span></html> ensures that the file at least of a given size. \\ Whenever the file is larger it is left unchanged. \\ <small>Warning: ''posix_fallocate'' is guaranteed to work for ordinary files. The result of using ''posix_fallocate'' on a shared memory object is undefined.</small>

To clean up the memory mapping, one has to use the
''[[https://pubs.opengroup.org/onlinepubs/9799919799/functions/munmap.html|munmap]]''
function. (Provided one wishes to flush data to a backing ordinary file, one
must call ''msync'' before ''munmap''.)

The ''shm_open'', ''mmap'', ''msync'' and ''munmap'' functions need **''#include <sys/mman.h>''**
(__m__emory __man__agement).
\\
The ''shm_open'' function needs also ''#include <fcntl.h>'' for the file open mode flags (such as ''O_RDWR'').

<html><p style="text-align: center"><object id="svg-object" data="/jkonczak/_media/os_cp:mmap.svg" type="image/svg+xml"></object></p></html>

**To compile programs that use ''shm_open'' with older glibc versions, one must add ''-lrt'' to compile options.**

~~Exercise.#~~
Test the following program that uses shared memory. Run it concurrently in multiple terminals.
\\
Answer the following questions:
\\       • what is the size of the shared memory object?
\\       • how does a ''struct'' help in laying out memory of the shared object?
\\ <small>Try to modify the following:
</small>\\       • <small>print the address of the shared memory
</small>\\       • <small>add a new field called ''counter'' in the ''struct myData'' and implement ''i num'' and ''d num'' commands to increment/decrement the counter
</small>\\       • <small>change the ''prot'' argument of mmap to PROT_READ (without PROT_WRITE) and check how the program works
</small>\\       • <small>change the ''size'' argument of mmap to ''1024*1024'' and try to access an address:
</small>\\               · <small>within mapping, but outside shared memory object (e.g., ''%%putchar(*((char*)data+1025*1024));%%'')
</small>\\               · <small>outside mapping (e.g., ''%%putchar(*((char*)data-1));%%'').
</small>\\         <small>what is the difference in handling those two accesses by the OS?
</small>

<code c simple_cli.c>
#include <fcntl.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <unistd.h>

#define CHECK(result, textOnFail)                                              \
  if (((long int)result) == -1) {                                              \
    perror(textOnFail);                                                        \
    exit(1);                                                                   \
  }

struct myData {
  int version;
  char text[1020];
};

int main() {
  int fd = shm_open("/os_cp", O_RDWR | O_CREAT, 0600);
  CHECK(fd, "shm_open failed");
  int r = ftruncate(fd, sizeof(struct myData));
  CHECK(r, "ftruncate failed");
  struct myData *data = mmap(NULL, sizeof(struct myData),
                             PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
  CHECK(data, "mmap failed");
  close(fd);

  printf("commands:\n"
         "  r           - reads the text\n"
         "  w <text>    - writes new text\n"
         "  q           - quits\n");

  while (1) {
    printf("> ");
    fflush(stdout);

    char c, text[1022] = {0};
    scanf("%1021[^\n]", text);
    do { // this reads all remaining characters in this line including '\n'
      c = getchar();
      CHECK(c, "getchar EOF'ed");
    } while (c != '\n');

    if (!strlen(text)) // empty line
      continue;

    switch (text[0]) {
    case 'r':
      printf("version: %d\n   text: %s\n", data->version, data->text);
      break;
    case 'w':
      data->version++;
      strcpy(data->text, text + 2);
      break;
    case 'q':
      munmap(data, sizeof(struct myData));
      exit(0);
      break;
    }
  }
}
</code>

~~Exercise.#~~
The following program uses the same shared memory object named ''/os_cp''.
Run it in one terminal, and run in parallel the program from the previous exercise.
Try to read the text.

<code c writer.c>
#include <fcntl.h>
#include <signal.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>

#define CHECK(result, textOnFail)                                              \
  if (((long int)result) == -1) {                                              \
    perror(textOnFail);                                                        \
    exit(1);                                                                   \
  }

struct myData {
  int version;
  char text[1020];
};

volatile sig_atomic_t stopFlag = 0;
void ctrlC(int num) { stopFlag = 1; }

int main() {
  int fd = shm_open("/os_cp", O_RDWR | O_CREAT, 0600);
  CHECK(fd, "shm_open failed");
  int r = ftruncate(fd, sizeof(struct myData));
  CHECK(r, "ftruncate failed");
  struct myData *data = mmap(NULL, sizeof(struct myData),
                             PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
  CHECK(data, "mmap failed");
  close(fd);

  signal(SIGINT, ctrlC);
  while (!stopFlag) {
    for (char letter = 'a'; letter <= 'z'; ++letter) {
      data->version++;
      for (int i = 0; i < 1020 - 1; ++i) {
        data->text[i] = letter;
      }
      if (stopFlag)
        break;
    }
  }
  munmap(data, sizeof(struct myData));
  return 0;
}
</code>

===== Semaphores =====

==== What is a semaphore ====

A semaphore is a mechanism to control concurrency. It has an associated number
that can be concurrently incremented and decremented by multiple processes / threads.
Incrementing a semaphore is instantaneous, and so is decrementing a semaphore which value is positive.
\\
**Decrementing a semaphore which value is zero waits until the value becomes
nonzero, that is until another process / thread increments the semaphore.**

Semaphore is an important theoretical primitive for synchronizing processes
or threads. Semaphores are either considered //binary// or //counting//: the
former may have value of 0 or 1, and the latter may have any non-negative value.
\\
The real-world programming libraries usually build semaphores on top of other
synchronization primitives, offer only counting semaphores, and have multiple
undefined behaviours whenever semaphores are used incorrectly.

POSIX standardizes two implementations of semaphores:
[[https://pubs.opengroup.org/onlinepubs/9799919799/basedefs/semaphore.h.html|POSIX semaphores]]
and <small>[[https://pubs.opengroup.org/onlinepubs/9799919799/basedefs/sys_sem.h.html|System V semaphores]]</small>.
While the standard %%C++%% libraries include [[https://en.cppreference.com/w/cpp/header/semaphore|semaphores]],
there are no plans to include them in the standard C library (unlike other
synchronisation primitives, that became already part of
[[https://en.cppreference.com/w/c/thread|C11]]). %%C++%% semaphore semantic is
defined with respect to threads only.

^ \\ Semantic of the operation ^  Name of the operation in:  ^^^^
^:::^  theory  ^^  POSIX  ^  <small>%%C++%%/Java</small>  ^
|increment|''V''|//verhogen//|''sem_post''|<small>''release''</small>|
|wait until nonzero and decrement|''P''|//proberen//|''sem_wait''|<small>''acquire''</small>|
|read the value|—|—|''sem_getvalue''|<small>—/''availablePermits''</small>|

==== Binary semaphore vs mutex ====

There are two vital differences between mutexes and semaphores:
<html><div style="margin-top:-1.4em"></div></html>
  - A mutex locked by some thread //belongs// to it and only the thread is allowed to unlock it.\\ A semaphore can be decremented/incremented by distinct threads/processes.
  - A mutex can be configured recursive, and then it can be locked multiple times by the same thread and will be unlocked only after corresponding number of unlocks.
==== POSIX semaphore API====

There are two ways of creating a POSIX semaphore:
  * __Named semaphore:__ create / open a semaphore associated with an identifier using: \\ <html><span style="float:right"><small>Needs headers:<br><code>semaphore.h</code> and <code>fcntl.h</code></small></span><a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/sem_open.html"></html>''sem_t %%*%%**sem_open**(const char *//name//, int //oflag//)'' \\  ''sem_t %%*%%**sem_open**(const char *//name//, int //oflag//, mode_t //mode//, unsigned int //value//)''<html></a></html> \\ These functions work just like opening a file / opening a shared memory object. \\ The extra **//''value''//** argument is the initial value of the semaphore.
  * __Unnamed semaphore:__ create a variable of the ''sem_t'' type in (usually shared) memory and initialize it using: \\ <html><span style="float:right"><small>Needs header: <code>semaphore.h</code></small></span><a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/sem_init.html"></html>''int **sem_init**(sem_t *//sem//, int //pshared//, unsigned //value//);''<html></a></html> \\ If ''//pshared//'' is logically false (and so equal 0), the semaphore is only guaranteed to work among threads of this process. Else, if ''//pshared//'' is logically true (that is, has a nonzero value) the semaphore is guaranteed to work for threads of distinct processes as well. Again, **//''value''//** sets the initial value of the semaphore.

To decrement a semaphore (possibly waiting thereby), one shall call: \\
<html><span style="float:right"><small>Needs header: <code>semaphore.h</code></small></span>
<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/sem_wait.html"></html>
''int **sem_wait**(sem_t *//sem//);''
<html></a></html> \\
The POSIX semaphores offer also non-blocking (''sem_trywait'') and time-restricted 
(''sem_timedwait'') variants of the ''sem_wait'' function. 

To increment a semaphore, one shall call: \\
<html><span style="float:right"><small>Needs header: <code>semaphore.h</code></small></span>
<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/sem_post.html"></html>
''int **sem_post**(sem_t *//sem//);''
<html></a></html>

It is possible to read the current value of a semaphore (this is useful for
logging and debugging purposes) using:\\
<html><span style="float:right"><small>Needs header: <code>semaphore.h</code></small></span>
<a href="https://pubs.opengroup.org/onlinepubs/9799919799/functions/sem_post.html"></html>
''int **sem_getvalue**(sem_t *//sem//, int *//sval//);''
<html></a></html> \\
Notice that the value is written to ''//sval//'' (and the function returns, like most
POSIX functions, 0 on success and -1 on error).

Once an unnamed semaphore is no longer needed by __any__ process, it shall be destroyed by ''sem_destroy''.\\
Once an named semaphore is no longer needed by __this__ process, it shall be closed with ''sem_close''.\\
Once the name of a named semaphore is no longer needed, it shall be removed by
''sem_unlink''((The semaphore itself remains intact, and will be automatically
destroyed as soon as no process has the semaphore open.)).

**To compile programs that use semaphores with older glibc versions, one must
add ''-pthread'' to compile options.**
  
~~Exercise.#~~ Write a program that creates a named semaphore with value of ''0'' and
waits on it, and a program that opens the named semaphore and posts it.

~~Exercise.#~~ Write a program that allows adding or retrieving data to/from
a [[https://en.wikipedia.org/wiki/Circular_buffer|ring buffer]] located in
shared memory and synchronizes processes accessing the buffer by means of
named semaphores.
\\
<small>
A non-concurrent ring buffer code is provided below:
<html><div style="line-height:1em"></html>
<code c non_concurrent_ring_buffer.c>
#include <signal.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_ELEMENTS_PLUS_ONE 4
typedef char item_t[256];

struct ring_buffer {
  item_t data[MAX_ELEMENTS_PLUS_ONE];
  size_t first;
  size_t last;
};

void initBuffer(struct ring_buffer *buffer) {
  memset(buffer, 0, sizeof(*buffer));
}

void put(struct ring_buffer *buffer, const item_t *item) {
  if ((buffer->last + 1) % MAX_ELEMENTS_PLUS_ONE == buffer->first)
    // the buffer is full, now what?
    raise(SIGUSR1);
  memcpy(&buffer->data[buffer->last], item, sizeof(*item));
  buffer->last = (buffer->last + 1) % MAX_ELEMENTS_PLUS_ONE;
}

void get(struct ring_buffer *buffer, item_t *item) {
  if (buffer->last == buffer->first)
    // the buffer is empty, what now?
    raise(SIGUSR2);
  memcpy(item, &buffer->data[buffer->first], sizeof(*item));
  buffer->first = (buffer->first + 1) % MAX_ELEMENTS_PLUS_ONE;
}

int main() {
  struct ring_buffer *buffer = malloc(sizeof(struct ring_buffer));
  initBuffer(buffer);
  printf("g             gets data from buffer\n"
         "ptext...      puts 'text...' to buffer\n");
  while (1) {
    printf("> ");
    fflush(stdout);
    char cmd[2], c;
    item_t item = {0};
    scanf("%1[^\n]%255[^\n]", cmd, item);
    do { // this reads all remaining characters in this line including '\n'
      c = getchar();
      if (c == -1)
        return 0;
    } while (c != '\n');
    switch (cmd[0]) {
    case 'p':
      put(buffer, &item);
      break;
    case 'g':
      get(buffer, &item);
      printf("%s\n", item);
      break;
    }
  }
  return 0;
}
</code>
<html></div></html>
</small>

~~Exercise.#~~ Analyze the program below. The program is not correct – when run
concurrently multiple times, one of its instances can block forever.
Add a ''sleep'' function (or run the program in a debugger) so that the problem
manifests.
<html><div style="line-height:1em"></html>
<small>
<code c bad_idea.c>
#include <fcntl.h>
#include <semaphore.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <unistd.h>

struct data {
  sem_t sem;
} *data;

int main() {
  int fd = shm_open("/myData", O_RDWR | O_CREAT | O_EXCL, 0666);
  char createSucceeded = (fd != -1);
  if (fd == -1) fd = shm_open("/myData", O_RDWR, 0666);
  if (fd == -1) { perror("shm_open"); exit(1); }

  ftruncate(fd, sizeof(struct data));
  data = mmap(NULL, sizeof(struct data), PROT_WRITE | PROT_READ, MAP_SHARED, fd, 0);

  if (createSucceeded)
    sem_init(&data->sem, 1, 1);

  sem_wait(&data->sem);
  printf("I'm alone here!\n");
  sem_post(&data->sem);

  return 0;
}
</code>
</small>
<html></div></html>



~~META:
language = en
~~