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 240!
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!
In your CS 240 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 Eunice on Monday, Feb. 21 at 11:00am.
The recording can be found at https://mediaspace.illinois.edu/media/t/1_szt6gloj.
The slide can be found at https://courses.grainger.illinois.edu/cs240/sp2022/static/mp-overviews/MP4 Overview Session.pdf.
There is no
starttest suite this week but be sure to take a look at this MP before the session!
You will implement the “wallet library”, which has only a few basic requirements:
- Your wallet initially starts empty, with 0 of all resources.
- Your wallet can accept any resource (identified by any string). The user of your library will call
wallet_change_resourceand supply a
deltato change your resource by a certain
- You must NEVER let your wallet go negative. You must not return from
wallet_change_resourceuntil you can satisfy the request (another thread must add to your wallet).
- You may have multiple wallets at once. All state of your wallet must be maintained in your
- 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.
In your solution, you must only modify the following files. Modifications of other files may break things:
You will find your four functions –
wallet_destroy – in
lib/wallet.c. Additionally, the
wallet_t struct is defined in
Running Sample Implementations
A simple implementation using a wallet is provided for you as
hedgehog-simple.c and compiles into
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.
make testto compile and build the test suite.
./test "[part=1]"to test the correctness of your solution.
./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
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.
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 master
You can verify your code was successfully submitted by viewing your git repo on github.com