Overview

The purpose of this assignment is to become familiar with the methods used to enable processes to create and access shared memory. The UNIX IPC package will be investigated as the mechanism for implementing a multiple process project that communicates via shared memory. Of course, any time executing entities share data, it poses an instance of the Critical Section problem. The programming assignment suggests a simple synchronization method to solve the potential race conditions that may occur when shared data are accessed concurrently by several parties.

Activities

• Work your way through the following exercises, demonstrating your knowledge of the material by answering the numbered questions.

• Submit a detailed lab report (may be completed in a group of 2 students). Include the answers to the numbered questions and all of your source code. Be prepared to demo your solution.

• Write a short program that utilizes shared memory.

  TIP

  Note: the solution is dynamic, therefore you do not need to submit hardcopy sample output for this programming assignment.

POSIX Inter Process Communication

In a previous lab, you learned how to use Unix pipe to enable communication between parent and child processes. Unfortunately, communication via pipes have several drawbacks:

• pipes cannot be used by two arbitrary processes which do not have parent/child relationship.
• pipes are destroyed once the parent and child terminate
• data in pipes can only be accesses in FIFO order

When your application requires a persistent communication medium that can be accessed by two arbitrary processes (not necessarily parent/child), a different technique is required.

POSIX compliant operating systems (Linux included) provide the following IPC facilities:

• Message Queues (similar to pipes except message queues have longer lifetime)
• Shared Memory Segments (similar to shared data accessible to multiple threads except shared mem segments have longer lifetime)
• Semaphores (explored in a later lab)

To see a list of these objects on your current EOS workstation, type the following command

# Check IPC status
ipcs

A typical ipcs output looks like the following (to protect privacy of the owner, the actual EOS userids under the "owner" column have been redacted)

------ Message Queues --------
key        msqid      owner      perms      used-bytes   messages
0x00000000 166233     xxxxxxx    600        3511            2
0x00000000 6332       yyyyyyy    600        7162            5

------ Shared Memory Segments --------
key        shmid      owner      perms      bytes      nattch     status
0x00000000 1048576    xxxxxxx    600        393216     2          dest
0x00000000 425985     yyyyyyy    600        2097152    2          dest
0x00000000 425986     zzzzzzz    600        393216     2          dest

----- Semaphore Arrays --------
key        semid      owner      perms      nsems

For this exercise, we will focus on the "Shared Memory Segments" section.

• Each segment is automatically assigned a unique (integer) ID for identification. This unique identifier (shmid) is similar to a file descriptor.

  • After a file is opened/created, all operations to the file are carried out through the descriptor
  • After a shared memory segment is "opened"/created, all operations to the segment are carried out through the "segment descriptor/shmid"

• The perms (permission) column should remind you the permission flags of Unix files (and directories). For instance, the octal code 600 is a numeric code for rw-------, which equivalent to read/write permission by the user owner.

• nattch shows how many processes are currently attached to the segment

• The sample output under the status column shows that the segment is currently marked as "destroyed"

In fact, these IPC facilities are managed similarly to files/directories, except accessing any of these IPC facilities does not incur expensive (slow) I/O costs. A file/directory will persist on the system until its owner (manually) deletes it, likewise these IPC objects will persist on the system until their owner deletes them or the system reboots.

Shared Memory Segments

In a previous lab you experimented with multiple threads that share common global variables. The IPC shared memory segments (SHM) above are conceptually different from global variables in a multi-threaded process.

• Global variables live inside either the data section or the heap section of your process image, and therefore their lifetime are constrained by the process lifetime
• SHMs live outside your process image and have extended lifetime beyond the lifetime of the process who created them

Because of its speed of access (as opposed to say, files or sockets), it is a useful tool for application programmers. This is why shared memory is commonly provided in modern operating systems. However, shared data presents users with an instance of what is called the Critical Section problem (more on this in a future lab).

Normally, each process has its own unique address space. The purpose of shared memory is to allow processes to communicate by sharing the same data area. Each process still has its own data segment, but with an additional shared segment mapped into its virtual address space. Processes may access this shared segment only via pointers; this is known as anonymous memory. The reading and modifying of memory, and hence process communication, occurs in the usual manner but with pointers.

This lab is concerned with the access mechanism itself: learning to use the system calls that implement and manage shared memory. Since shared memory is a kernel resource, programs that use it should adhere to the common resource REQUEST-USE-RELEASE pattern. A few examples are shown below:

	File	Heap	Directory
Request	open()	malloc()	opendir()
Use	read()/write()	via C/C++ pointers	readdir()
Release	close()	free()	closedir()

For IPC shared memory, the "request" step is broken down into the first two steps below and the "release" step is broken down into the last two steps below:

• [REQUEST a] allocate a shared memory region and a kernel data structure
• [REQUEST b] attach the shared memory region into pointer in your code
• use the shared memory (via C/C++ pointers)
• [RELEASE a] detach the shared memory region from the pointer in your code
• [RELEASE b] de-allocate the memory region and the associated kernel data structure

TIP

"Attachment" in this context means mapping the physical location of a shared memory segment (which is external to your process) into an address (a pointer) within your process image.

Each of the above steps (except the third bullet point in italics) is associated with a distinct system call described below:

shmget() : this function creates a shared memory segment. It initializes a kernel data structure to manage the resource and returns a resource ID to the user. This ID, or handle, is used by any process wishing to access the shared segment.

TIP

shmget() can be used for at least two purposes

• create a new shared memory block (call with IPC_CREAT flag)
• access an existing shared memory block (call without IPC_CREAT)

shmat() : attaches the specified shared memory region to the address space of the calling process.

shmdt() : detaches the specified shared memory region.

shmctl() : used for controlling the resource. This function has different uses that range from returning information about the shared memory segment to locking the memory. It can also be used to "free" the resource; removing the shared memory segment and its associated data structures from the system.

TIP

Recall that malloc() essentially performs the following two actions:

• Allocate a (new) block of memory from the HEAP
• Return the address of the memory block

int *heap_arr;
heap_arr = (int *) malloc(1000 * sizeof(int));

In SHM parlance, the above two actions require two separate system calls:

• shmget() is handling the allocation
• shmat() is handling the address assignment

int mem_id;
int *shm_arr;

mem_id = shmget(IPC_PRIVATE,
                 1000 * sizeof(int),
                 IPC_CREAT | S_IRUSR | S_IWUSR);
shm_arr = shmat(mem_id, NULL, 0);

Refer to the man pages for additional details on these functions. You may also find the include files bits/ipc.h and bits/shm.h useful to reference.

TIP

To locate these header files in your compiler installation path, compile your code using the "verbose" option and inspect its "include search directories":

# -v for verbose option
clang -v your_file_name.c
gcc -v your_file_name.c

The sample code below demonstrates the use of these system calls. Note that this program doesn't really do anything useful - because it doesn't make sense for a single process to use shared memory.

Sample Program 1

[Gist]

API rate limit exceeded for 54.209.88.255. (But here's the good news: Authenticated requests get a higher rate limit. Check out the documentation for more details.)

Perform the following operations and answer the questions:

• compile and run Sample Program 1

1. what exactly is being output by Sample Program 1 (what is the meaning of the output values)?

   Hint

   The meaning for "b" is NOT some address plus 4096.

2. read the man pages; then describe the meaning / purpose of each argument used by the shmget() function call.

3. describe two specific uses of the shmctl() function call

4. read the man pages, then use shmctl() to modify Sample Program 1 so that it prints out the size of the shared memory segment

Sharing Multiple Data Items

Let's say your program needs to allocate several data items in the system shared memory: a float and an array of 50 integers. You have two options to allocate them:

• Allocate each data item individually (less preferred)

  float *my_float;   // a pointer
  int *my_arr;       // a pointer
  
  int shm_float_id, shm_arr_id;
  
  // Allocate enough space for ONE float
  shm_float_id = shmget(IPC_PRIVATE, sizeof(float), IPC_CREAT | S_IRUSR | S_IWUSR);
  my_float = (float *) shmat(shm_float_id, NULL, 0);
  
  // Allocate enough space for 50 ints
  shm_arr_id = shmget(IPC_PRIVATE, 50 * sizeof(int), IPC_CREAT | S_IRUSR | S_IWUSR);
  my_arr = (int *) shmat(shm_arr_id, NULL, 0);
  
  // Place values into the variables
  *my_float = 6.02e+23;
  my_arr[3] = -517;

• Place all the data items in a C struct and allocate memory space for the entire struct (more preferred)

  struct MyData {
    float my_float;   // Not a pointer
    int my_arr[50];   // Not a pointer
  }
  
  int shm_id;
  struct MyData *my_shared; // a pointer
  
  shm_id = shmget(IPC_PRIVATE, sizeof(struct MyData), IPC_CREAT | S_IRUSR | S_IWUSR);
  my_shared = (struct MyData *) shmat(shm_id, NULL, 0);
  
  // Place values into the variables (via a pointer to struct)
  my_shared->my_float = 6.02e+23;
  my_shared->my_arr[3] = -517;

DANGER

Never mix system shared memory with heap space

struct MyData {
  float my_float;   // Not a pointer
  int *my_arr;      // A pointer
}

int shm_id;
struct MyData *my_shared;

shm_id = shmget(IPC_PRIVATE, sizeof(struct MyData), _____);
my_shared = (struct MyData *) shmat(shm_id, NULL, 0);

// The following code won't work: the structure is allocated in the system shared memory
// but the array is allocated in THIS PROCESS heap space
my_shared->my_arr = calloc (50, sizeof(int));

Using ipcs and ipcrm

Use the man pages to familiarize yourself with these utilities.

Since shared memory is a kernel resource, it is persistent (i.e. it may remain in the system even after the creating process has terminated). Shared memory is normally de-allocated via theshmctl() function, but the system utility ipcrm (IPC remove) can also be used from your command line when necessary. Use this utility in the event of programming errors. For example, if your program terminates before cleaning up, this utility can be used to free the resources.

ipcrm -m XXXXXX     # Replace XXXXXX with the shmid of your resource

Perform the following operations:

• modify the print statement in Sample Program 1 to determine the ID of the shared memory segment
• in the program insert a pause() after the print statement, recompile and run
• terminate the Sample Program (^C) and run the ipcs utility
• take a screenshot of your terminal
• use the ipcrm utility to remove the shared memory segment
• re-run the ipcs utility to verify that it worked
• take another screenshot

5. Include the screenshots, they should demonstrate that you use the ipcrm command correctly

WARNING

Important: in your C program don't lose your shared memory pointer! Otherwise, you will not be able to properly detach.

Using ftok()

The sample C program creates a shared memory segment using IPC_PRIVATE as key. This is why you see 0x00000000 under the key column of ipcs output. Instead of using zero-value keys, you can supply your own key to shmget():

// "Beef to Go"
int shm_id = shmget(0xBEEF260, ____. ____);

Using this technique, you can use the "passcode" 0xBEEF260 across two (or more) programs so they all access a common shared segment. However, if other users on the same machine already used the same passcode, your program will fail to create/access the memory segment. The library function ftok() ("File to Key") is provided to avoid this issue. The function generates a unique integer key from a pair of filename and an integer you supply as the first and second arguments. You can view the integer returned by ftok() as the hash value of the file.

// Replace xxxxy with the path (absolute or relative) to a file name of your choice
// Replace yyyyy with an integer value of your choice
key_t my_key = ftok("xxxxx", yyyyy);
int shm_id = shmget(my_key, ____. ____);

To understand ftok() better, it is recommended that you write a short program that calls ftok() several times, supply different file name and integer pairs and print the resulting key.

6. Repeat step (5) above after replacing IPC_PRIVATE with a key generated by ftok()

Programming Assignment (Readers and Writer)

Process communication using shared memory involves at least two processes by definition, often referred to as a Reader and a Writer. The programming assignment for this lab is to implement a Writer program that creates a shared memory segment, then repeatedly accepts an arbitrary user input string from the terminal and writes it into shared memory. You must also implement a corresponding Reader program; two instances of reader will attach to the same shared memory segment, repeatedly read each new string from the shared memory and display the string to the screen.

Write two separate programs for each process type and then run each process in its own terminal window. This clearly demonstrates the communication mechanism involved in using shared memory.

Program Requirements

1. You are expected to solve this problem without using sophisticated synchronization mechanisms such as Dekker/Peterson algorithm or semaphores.
2. It is acceptable for your program to use busy wait loops to synchronize the work among the three processes. However, your code should not call any form of sleep: sleep() or usleep() or other possible variants.
3. Use ftok() to generate a unique key for the Writer and both Readers.

The Writer

• The writer is responsible for creating the shared memory (be sure to include the IPC_CREAT flag in your shmget() call)
• the writer should not overwrite the text until both readers completes printing the text
• When the writer accepts a "quit" input string, your programs (the writer and two readers) should conclude with a graceful shutdown, releasing all system resources before terminating.

The Reader

• The reader should not create the shared memory, call shmget() without passing the IPC_CREAT flag.
• You may supply one command line argument to the reader to tell it whether it is running as the first or second reader.
• The Readers should busy wait until a new text is available on the shared memory, so that they can display it (otherwise they would re-display the current string).

TIP

1. The main objective of this exercise to prevent race conditions, your solution should avoid any code that cross updates the shared variables among the three processes (other than the shared text itself).

   • The writer should not update the readers' variables
   • The readers should not update the writer's variables
   • Each reader should not update the other reader's variables

2. You should be able to synchronize for the desired behavior with simple elements such as flag(s) and other variable(s), which must also be stored in shared memory so that all processes can access them.

3. Note that the functionality of this system constitutes "lockstep" synchronization, which is acceptable in this case since that is the desired behavior of the programs (writer goes, then readers go, then writer goes, etc.). However, the reader actions should not be in lockstep, i.e. your code should not force the two readers to run in a specific order.

To test your programs:

• Open three terminal windows
• Run one instance of the "Writer" program in the first window
• Run one instance of the "Reader" program in each of the other two windows
• Type your text input in the first window

DANGER

When checking the correctness of your programs, be aware of the following:

• You are running three concurrent processes sharing a common memory area
• While accessing the shared memory area, any of these three processes may be interrupted anytime and anywhere and this may lead to an unexpected race condition
• Any counter-based synchronization techniques are very likely to FAIL

Because the race condition may happen only on a few sequences of concurrent execution (out of hundreds of possible concurrent sequences) of the three processes, a buggy solution may appear to work correctly. Showing correct output does not automatically guarantee that your writer/reader programs implement the correct logic!

A few possible race conditions:

• One of the readers missed the message due to incorrect action by the other reader or the writer
• Both readers get only part of the message
• Writer overwrites the message before both readers get it, You should consider that case when the writer puts a series of text input at high speed (as opposed to your typing speed on the keyboard)
• ...

Extra Credits

You have two options to earn more points on this lab as decribed below:

Option 1: Multi Threading (lower credits)

Implement the reader/writer logic as two separate functions. Lauch one instance of the writer and two instances of the reader threads. Notice that this approach does not require use of the shm___() system calls.

Option 2: Chat Server (higher credits)

Extend your program to function as a Chat Server, albeit one that functions on a single machine.

The basic ideas:

• instead of writing two separate programs (one for reader and one for writer), you would write one program that runs as both a writer and a reader
• The reader and the writer should run on two separate threads

In a "chat room" of N users you will see N instances of this program running concurrently.

Anything a user types into any process in any terminal window gets echoed to all other processes. Note: this is an OS project. Your solution must use shared memory for IPC (not sockets).

Reminder: all extra credit is in addition to the regular assignment, not in place of it.

Grading Rubrics

Grading Item	Point
Shared memory created by writer	1
Use ftok() to generate key in writer	1
Use ftok() to generate key in reader	1
Shared memory cleanup	1
No race condition in writing the message	1
No race condition in reading the message	2
No race condition in updating supporting data	1
Message is printed correctly by both readers	2
Graceful writer shutdown on "quit"	1
Graceful reader shutdown on "quit"	1
>>> Use one program with two threads
Correct implementation of the Reader thread	2
Correct implementation of the Writer thread	2
>>> Chat Server (Extra Credit)
Correct implementation of Reader thread	3
Correct implementation of Writer thread	3

WARNING

Penalty points similar to previous assignments will be applicable to this assignment. The table of penalty points will not be replicated here.