Differences

This shows you the differences between two versions of the page.

@@ Line 1: / Line 1: @@
+===== 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/9699919799/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''.
+\\
+<small>
+''MAP_ANONYMOUS'' is not part of the POSIX standard. However, virtually any
+UNIX-like system supports it.
+</small>
+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/9699919799/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/9699919799/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/9699919799/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/9699919799/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/9699919799/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/9699919799/basedefs/semaphore.h.html|POSIX semaphores]]
+and <small>[[https://pubs.opengroup.org/onlinepubs/9699919799/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>|
+==== 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/9699919799/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/9699919799/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/9699919799/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/9699919799/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/9699919799/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>
+#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;
+  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
+~~

Jan Kończak

User Tools

Site Tools

Differences

Page Tools