/Teaching/System Level Programming/Assignments/A4

Pull from upstream before solving this task.

Task: Interprocess Communication (IPC)

This exercise should teach you what interprocess communication is for and how you can realize it.

Main Idea

Everybody of us has used interprocess communication already. Mostly unintentionally at this point in your studies. This is why we wanted to take this specific topic into this semester’s course.

To understand the concept of IPC, some major concepts must be learned and understood beforehand.

  • Virtual Memory
  • Process vs. Thread
  • Shared Resources
  • Locking

Some of those terms are already familiar to you, others not. I will not entirely go into details for this assignment, but it’s always useful looking up information based on those keywords.

Implementation details: Treasure Hunt Game

You MUST NOT change predefined function signatures, sequences of checks or similar. Exploits will automatically result in deductions! Do not remove or add any usleep or assert statements!

For this assignment you will have to implement a simple adventure game, which consists of two processes communicating with each other using shared memory. The game approximately follows the mechanics of a simplified version of the popular game “Minesweeper”. The game logic functionality is already provided, so it is not necessary to be familiar with the game. The Adventurer reads commands from STDIN (terminal input) and sends them to the TreasureKeeper. The TreasureKeeper handles those commands (sets the adventure state e.g. quest map) and responds accordingly. A adventure consists of an arbritrary amount of quests, that can either be won (by discovering a Treasure) or lost (by getting caught in a Trap). You start the Adventurer-process, which then has to start the TreasureKeeper-process.

Adventurer.c:

  • ”initSharedMemoriesAdventurer()”
    • Initialize the shared memory objects.
    • Make sure to only set the permissions the process needs!
  • ”initMmapingsAdventurer()”
    • Map those objects to virtual memory.
    • The permissions need to match the ones you used for the SHM objects!
    • Make sure not to use this function to do anything else (like initializations).
  • ”initLocks()”
    • Initialize any locks you might need.
  • ”initProcess()”
    • Launch the TreasureKeeper process.
    • Ensure you launch a new process.
    • Ensure you execute the right executable.
  • has to be synchronized properly
  • has to be cleaned up properly (also stop and clean up everything after getCommand() returns 0)

The Adventurer asks for the input, publishes it on the shared memory, and makes it available for the TreasureKeeper process.
For initializing the shared memory, CAREFULLY take a look at the defines!
The names of those objects are predefined and can be found in the list of defines in util.h:.

DO NOT remove or relocate code for checking your approach. Otherwise, we will deduce points.

TreasureKeeper.c:

  • ”initSharedMemoriesTreasureKeeper()”
    • Open the shared memory objects.
    • Make sure to only set the permissions the process needs!
  • ”initMmapingsTreasureKeeper()”
    • Map those objects to virtual memory.
    • The permissions need to match the ones you used for the SHM objects!
  • ”cmdHandler()”
    • Handle the commands received in the request object and return the appropriate answer in the response object.
    • Set the game state (map, quest_active) accordingly.
    • Check out the provided functions in this file. You should not find yourself implementing larger parts of the game logic.
  • Has to be synchronized properly as well.
  • Has to be cleaned up properly.
  • Make sure to use the provided functions.

Command handling:

  • start quest: Set the quest_active variable in the shmadventurestate struct to 1 and initialize a new quest. The map (map) should be shuffled and all of the fields have to be unexplored. Don’t forget to consider the quest being active for the following explore and mark command.
  • explore [1-12]: Explore the field at the passed index (1-12). If the field is already explored, it can’t be explored again. Respond accordingly. If the quest is not active, also respond accordingly. If the field is not in 1-12, the command is not recognized. If the explored field contains either a Treasure or a Trap, the current quest ends. Otherwise, the explored field displays the number of surrounding Traps as hint. Respond accordingly for all cases.
  • mark [1-12]: Mark a unexplored field at the passed index (1-12). The field will be marked in the map. Respond accordingly. The mark command can be used by the Adventurer to follow a certian strategy (e.g. marking suspected traps), but it does not have any further implications for the game.
  • exit: Ends the game. The TreasureKeeper responds with “Until the next adventure awaits!” and both processes are terminated.
  • any other input or questions without predefined answers should be answered with “I don’t understand…”.

DO NOT remove or relocate code for checking your approach. Otherwise, we will deduce points.

util.c:

  • You can add checks in the functions provided, but when tested, all changes made will be ignored.

util.h:

  • The only change allowed in this file is adding synchronization primitives to the shmlocks struct. All other changes made in this file will make your program not testable. Do not change anything but carefully look at the extern variables, defines, and structs.

IPC in a (way too oversimplified) nutshell

Those simplified explanations should not replace your attendance and attention in the lecture nor serve you the detailed solution to this assignment. It should help you to understand the central concept briefly to make research more accessible.

Virtual Memory Virtual memory is part of the concept of modern operating systems. As you may suspect, there is a difference between physical and virtual memory. The physical memory provided by, e.g. (SO-)DIMMs has to be managed by the operating system that uses virtual addresses for locating data. So there has to be a sort of translation between the physical and virtual memory addresses. If you are interested in this topic, you can look up this and related articles [1].

Process vs. Threads As many of you already know from previous assignments, processes are treated differently in contrast to threads – well, kind of. As you discovered, a thread can operate on the whole memory the program has mapped. This means, e.g., the heap-allocated by one thread can be used with any other thread the program launches. It is possible since they share the same virtual address space, as they are all used in one program launched before. So we can deduce that each process has its own virtual memory space. Those virtual memory spaces are strictly separated from each other.
Thus, sharing resources ”between” two processes are realized differently from sharing resources ”in” a process. So we have to share memory between two processes. This memory is surprisingly called shared memory, and it is a central part of IPC [2].

Shared resources Shared resources are “saved” in files, as the file system (FS) is accessible in both processes – well, kind of again. But besides some exceptions, all files saved on the FS can be accessed depending on the rights a user has. But some of you may wonder, how to access this data? Do we have to use ”read()” and ”write()” for sharing information? Well, this is possible with one big limitation. This limitation is that we cannot use virtual addresses to access data easily and fast. Well, there is a solution called ”mmap()”, which takes a file descriptor (fd) that maps the file (full size) to our virtual memory space of the program. That’s it, well, kind of. How this mapping works in the kernel will be taught in the following course called operating systems.

Locking When we use IPC, mostly, some locking mechanisms have to be used. In our case, semaphores and mutexes are the way to go [3].

Holding a lock while going to sleep will lead to point deductions.

Some further hints

What to do before you start?

  • Pull from upstream!
  • Try to understand the program structure.
  • Carefully read the Manpages and/or the POSIX standard on the needed functions.
  • Only begin, if you understand the basic concept of processes, virtual memory, shared resources as well as mapping them. Bruteforcing will lead to a severe amount of wasted time.
  • Adventurer.h and TreasureKeeper.h MUST NOT be changed,
  • You are allowed to add new functions everywhere in the program and extend structs as you like. But don’t remove or move around existing code ever (this would lead to point deductions).
  • Do not add any synchronization mechanisms outside of the game loop. Do not use any calls to wait, waitpid or similar.
  • Do not push binary files or any other junk files.
  • Carefully read the TODOs. Some contain crucial information!

Submission

Modify the files in your git repository. You can find this file in directory A4. Tag the submission with A4 and push it to the server.

[1] https://wiki.osdev.org/Memory_management

[2] https://wiki.osdev.org/Processes_and_Threads

[3] https://wiki.osdev.org/Semaphores#Semaphores

as well as the slides

Assignment Tutor

If you have any questions regarding this assignment, go to Discord and read through the SLP channels. The probability that your question was already answered or some discussions will lead you in the right direction is quite high. If not so, just ask in the corresponding channel.
If you have a more direct question regarding your specific solution, you can also ask the tutor who organizes this assignment.

Linda Pirker, linda.pirker@student.tugraz.at