Lab: Worm!

Assigned:

Tuesday, Feb 7, 2017

Due:

Monday, Feb 13, 2017 by 10:30pm

Collaboration:

Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted. If you do not know whether it is acceptable use a specific resource you should ask.

Lab: Worm!

Assigned:

Tuesday, Feb 7, 2017

Due:

Monday, Feb 13, 2017 by 10:30pm

Collaboration:

Work with your assigned partner for this lab. You may use your classmates and their code as a resource, but please cite them. Sharing of complete or nearly-complete answers is not permitted. If you do not know whether it is acceptable use a specific resource you should ask.

Groups

• Marcel, Rachel, and Yazan
• Saung and Matt
• Alex M. and Kathryn
• Chiara and Connor
• Niko and David
• JaeEun and Black
• Jonah and Clara
• Mattori and Zachary
• Ajuna and Mari
• Anna and Yuxi
• Alex F. and Gemma
• Larry and Uzo
• Giang and Maddie
• Seth and Adam

Overview

For this lab, you will implement a scheduling system for a simple console-based game, Worm!, based on the classic game Snake. The game looks like this when it’s fully implemented:

The game logic is already written and provided, but the game does not yet have a scheduler or job queue. Your job for this lab is to implement a simple job queue and scheduler that runs a set of periodic tasks at the approprate intervals.

The starter code for this lab is available at github.com/grinnell-cs/213-worm.

Part A: Scaffolding

Before you can even build the worm game, you will need to create a file called scheduler.c that implements all of the functions declared in scheduler.h. The makefile system provided will handle this new file automatically, so there’s no need to update the build system.

Look over the declarations in scheduler.h and make sure you understand what they are asking for. A key idea behind this game’s design is the notion of a periodic job, which is a function that should run at a precise interval (no sooner, and no later if at all possible). This is very similar to your implementation of every from the warm-up lab. If the purpose of a scheduler function is unclear, make sure to ask!

Write stub versions (empty functions) of these functions in scheduler.c so you can build and run the program (which should just start and quit immediately). As you add to your implementation, get in the habit of building the program regularly and watching for warning messages; these are usually a sign of an error!

Part B: A Simple Job Queue

It will be easier to write an “intelligent” scheduling policy if you start from something that works (though not very well). You should implement a linked list to keep track of all the jobs added to the system. Once you have the jobs in a list, write a basic implementation for run_scheduler that walks through these jobs in order and runs the next one every 50 milliseconds. There is an implementation of sleep_ms() in util.c that you can use by including util.h.

This simple scheduler won’t respect the requested intervals for the jobs, but it will let you see whether your job queue really works. You should see the following things happen:

1. The worm should move forward
2. If you push an arrow key while the worm is moving, it should turn
3. The “apples” should “spin”
4. New apples should appear periodically (much too fast)
5. The board should update (you wouldn’t see anything else if this wasn’t happening)
6. When your worm runs into a wall, the game should quit

Odds are the game will freeze up as the screen fills with apples. You’ll have to improve the scheduler before you can actually play the game.

Part C: Improving the Scheduler

Extend your job queue implementation to respect the requested job intervals. That means you should not run a job with an interval of 2000ms more than once every two seconds (on average). The time_ms() and sleep_ms() functions in util.h will likely be useful for running these tasks on schedule. It is up to you to figure out how to store and order jobs to satisfy the requested schedule. However, before you try anything too complex take a look at part D.

Now that you are respecting the game’s deadlines, implement the remove_job, update_job_interval, and stop_scheduler functions. The easiest way to update a job’s interval will be to remove the job and re-insert it. Make sure you free memory when you remove nodes from your list of jobs!

Part D: A “Real” Real-Time Scheduler

Odds are your game runs pretty well at this point. Now that you have all the mechanics for a basic scheduler, we’ll use this as a simple exercise to implement one of two real-time scheduling policies. You can choose either the Earliest Deadline First or Rate-Monotonic policy. Given that your game spends most of its time waiting, the exact scheduler policy won’t change the game behavior much (if at all).

A key step in implementing either scheduling policy is sorting the job queue. Regardless of the policy you choose, the run_scheduler function is unlikely to change much. You may have found that sorting your job queue simplified part C. If so, think carefully about what you implemented; can you adapt this to EDF or rate-monotonic scheduling?

Extra Credit: Fancy Features

Can you make the game multiplayer? Should there be obstacles in the game board? What about levels? How about fancy animations when the game ends or when you reach a final score? Extend the game in a meaningful way and I will give you extra credit. Any extra credit-worthy addition should—at bare minimum—create one additional job for the scheduler to run.