MP 4: Resource Manager

Due Date: Completed and turned in via git before October 4, 2022 at 11:59pm
Points: MP 4 is worth 40 points
Semester-Long Details: Programming Environment and MP Policy

Overview

A classic game of the Internet-era is the game “Cookie Clicker”. Cookie Clicker is the “genre-defining” game of “incremental games”, where you have something that generates a resource in the background. With tasks being done in the background, this sounds like a perfect fit for CS 340!

For this MP, you will program a wallet that will hold a collection of resources. A user will interact with your wallet by adding or subtracting resources from it, except that you must not allow the wallet to ever go negative – debt is not allowed!

We’ll theme this wallet with various different fun theses like building a degree (🎓), but in more complex systems these resources can be CPUs needed for a cluster job, available RAM for a large compute job, or other system resources.

However, it’s both simpler and easier to debug with emojis – so lets get started!

Initial Files

In your CS 340 directory, merge the initial starting files with the following commands:

git fetch release
git merge release/mp4 -m "Merging initial files"

MP Overview Session

An MP Overview was held by Ameya on Thursday, Sept. 29 at 5:00pm. The slides can be found here. The recording of the session can be found here.

MP Requirements

You will implement the “wallet library”, which has only a few basic requirements:

  1. Your wallet initially starts empty, with 0 of all resources.
  2. Your wallet can accept any resource (identified by any string). The user of your library will call wallet_change_resource and supply a delta to change your resource by a certain delta.
  3. You must NEVER let your wallet go negative. You must not return from wallet_change_resource until you can satisfy the request (another thread must add to your wallet).
  4. You may have multiple wallets at once. All state of your wallet must be maintained in your wallet_t.
  5. Finally, and most importantly, many threads will be accessing your wallet(s) at the same time. You must ensure the data in your wallet is correct by ensuring accesses to your wallet are properly synchronized.

Modifiable Files

In your solution, you must only modify the following files. Modifications of other files may break things:

  • wallet.c
  • wallet.h

Implementation

You will find your four functions – wallet_init, wallet_get, wallet_change_resource, and wallet_destroy – in lib/wallet.c. Additionally, the wallet_t struct is defined in lib/wallet.h.

Running Sample Implementations

A simple implementation using a wallet is provided for you as hedgehog-simple.c and compiles into hedgehog-simple.

Simple Case: Hedgehogs

When you run ./hedgehog-simple, you will see two threads run that do the following:

  • A hedgehog food generator that constantly generates 🐛,
  • A hedgehog generator that consumes 🐛 to generate 🦔!

Complex Case: Degree

A more complex implementation (provided in degree.c and can be run with ./degree), builds your degree by a series of worker threads including:

  • A clover field that constantly produces ☘️ (and an occasional 🍀),
  • A workshop that constantly produces 🧰 (and an occasional 💎),
  • An orchard that constantly produces 🍏,
  • A research job that consumes 🧰 and 🧬 to create a 📙,
  • And a bunch of other jobs (you can check out the degree.c) to eventually create just a single 🎓!

Fun Case: Gacha

Gacha is a system where a resource can be spent to open a “loot box” that contains random items. In Genshin Impact, the gacha system allows players to earn three star, four star, or five star items with a pity system that guarantees an item of a certain star-level. *(This sort of gacha system exists in almost all mobile microtransaction-based games, and most include some sort of pity.)

When you run ./gacha (compiled from gacha.c), the program will simulate grinding out earning the currency for 90 draws and the distribution of items – how lucky can you get?

Edge Case: Ping-Pong

When you run ./ping-pong (compiled from ping-pong.c), you will constantly be bouncing resources back and forth. This has proven useful for debugging some edge cases.

Running Tests

  • Run make test to compile and build the test suite.
  • Run ./test "[part=1]" to test the correctness of your solution.
  • Run ./test "[part=2]" to test that your solution does not use busy-waiting and properly synchronizes your threads.

The test cases in the part1 test basic functionalities of the wallet including initial count of any resource should be 0, you cannot let the wallet balance go negative, test whether you can properly build a degree (provided in degree.c) and Hedge-Hogs (provided in hedgehog-simple.c).

The test cases in the part2 test whether your wallet can handle large number of additions and deletion requests from multiple threads in parallel. Also, in part2, we test whether your implementation consumes CPU resources (i.e. busy waiting) or not when waiting for a producer to generate resources.

Memory Correctness

For full credit, your MP must run “valgrind clean”. This means that you must:

  • Compile all test cases on the command line using make test,
  • Run all test cases using valgrind --leak-check=full --show-leak-kinds=all ./test,
  • This must report the following output: All heap blocks were freed -- no leaks are possible

macOS Specific Information

Sadly, valgrind does not work on macOS. However, it does work in Docker running on a Mac:
# Build a light-weight docker:
docker build -t cs340  .

# Run make clean, make, and run valgrind:
docker run --rm -it -v `pwd`:/mp4 cs340 "make clean"
docker run --rm -it -v `pwd`:/mp4 cs340 make
docker run --rm -it -v `pwd`:/mp4 cs340 "valgrind ./test"

Submit

When you have completed your program, double-check your code works and submit it:

git add -A
git commit -m "MP4 submission"
git push origin main

You can verify your code was successfully submitted by viewing your git repo on github.com