CS463 - Homework 9 - Game of Functional Thrones

Quick Overview

The Task: Musical Chairs

• Requirements
  
  • the number of players is the first command-line argument to the whole program. When not present, your code must default to N = 10. (See our class example, Args.hs, for handling command line arguments).
  • The emcee is a separate thread, which exists for the duration of the game. (it is okay to use the main thread for the emcee).
  • Each player is a separate thread. Each player has a 'name', from P1 through PN. These player threads must exist for the duration of the game, they are not recreated each round. (It's okay for these threads to die when they lose - no need to hang around afterwards).
  • Each chair is a separate resource (e.g., an object). The chairs are named C1 through C(N-1). It must be possible for multiple players to obtain different chairs at the same time.
    • If you have any sort of a single lock on all chairs (meaning that only one player at a time can access them) then you are not fulfilling the requirements of this assignment. A common example violation of this goal would be that the chairs are not just in an array, but that the only way to find a chair to sit on is through some method call that 'controls' the array, or if the entire array is synchronized/locked while an individual is looking for a chair. Instead, each item in the array would need to be separately lockable on their own.
  • each round, whichever player did not manage to obtain a chair is out. The remaining player threads get to play in the next round, and the highest-numbered chair is removed. This means that we always have chairs C1 through C(k-1), but not necessarily players P1 through Pk. For example, in the last round, it's always chair C1, but it could/should be any two of the original players vying for the win.
  • it's entirely up to you to decide what algorithm your players use to find chairs, and it does not need to be fancy (start simple, enhance it later perhaps?). They may rely upon the numbering system of the chairs and their own numbers, or any other strategy that you can design. As long as each player is able to find each open chair eventually, it is fine. Writing up this approach is part of the required (short) document at the end.
  • What can I Import? - the only limitation on what you may import from standard libraries is any randomization library; the variability between runs we see needs to be from threading, not from a random number generator. Other than that, any concurrency libraries or data structure libraries can all be used if you have explored and learned about things in your language beyond what we see in class. Since it has to be a standard library, we won't see anything like import com.somewebsite.musicalChairLib.solution; it's still gotta be your work solving the actual task.
• Notes and Suggestions
  
  • It is okay to include some extra coordination points as necessary between the emcee and players, as long as the find-a-seat phase is initiated by changing the music and the players are able to access different chairs at the same time. In a real game of musical chairs, the emcee would somehow have to inspect all the chairs and identify the person who isn't sitting, so there's a bit of a linear computation to be done here and there.
  • Though not required by your assignment, I added a second command-line argument for an output file name. When omitted, everything is printed to standard out, but when present, I save the contents to that file. This was occasionally helpful to further inspect outputs from various runs of the program and not need to keep scrolling back in the terminal.
    • printing interleaved messages can be difficult in various languages, because multiple threads are competing for the standard output. If you are having any issues with interlaced characters from multiple messages, then you need to introduce something to coordinate the message printing. I tend to have only one resource (or thread) in charge of actual printing, and everyone else sends messages they'd like to print to that resource whenever they'd like. This was the purpose of our announcer threads in our class examples.
      • because most of our program ends up printing things, it's entirely possible that printing may be the bottleneck of our program. Don't worry about that, but if you have details to share in your writeup, be sure to mention it.
  • It's not just expected that each run will produce varied outcomes and varied orders of sitting, but keep in mind that the two separate actions of find-chair and print-sat-message also may be further apart in time than you expect. A later sat-message doesn't mean that's when they sat, only that that's when the message got printed! Be careful not to assume too much from the order of printed messages when debugging. This can trick us into some dead-end debugging sessions.
  • Much more so than in single-threaded programming, if you have a ton of debug-style print statements, they will affect the timing of your program. Removing them can absolutely uncover some nasty race condition bugs.
    • I highly recommend regularly running your code with no debugging statements to avoid finding race conditions at the last minute.
• Required outputs
  

  In order to facilitate grading, you need to print these messages (and only these messages) to standard output, in the indicated ordering. Each one is printed on a line by itself. You may introduce blank lines as desired; they will be ignored.

  • the emcee indicates the game is beginning with BEGIN N players. This is always the first message of the whole game, with the actual positive integer value replacing N, e.g. BEGIN 5 players.
  • each round, the following happens:
    • the emcee prints "round X", e.g. round 1, round 13, etc. The music turns on at this point (no printed message about turning the music on exists - that's implied by the round starting).
    • after the "round" message has printed and all players are ready to begin, the emcee thread prints music off and then immediately turns off the music. Players must notice the music is not playing in order to know that they may begin searching for a seat.
    • as players find and take ownership of available chairs, messages of the form "P1 sat in C1" must be generated and printed. Of course the correct player and chair numbers must be used.
    • the last player realizes they have lost (perhaps by the emcee telling them), and the last message of the round prints, e.g.: P1 lost.
  • when there is only one player left, instead of printing round X again, the emcee announces the winner with a message, e.g.: P1 wins!.
  • the emcee indicates the game is over with END. This is always the last message of the whole game.

Sample Runs

We can both interpret our code, or compile and run our code.

• to interpret it, we use the runhaskell executable. Example:

  runhaskell Homework9 3
  

• to compile it, we create an executable like this example:

  ghc -threaded -main-is Homework9 -o h9 Homework9.hs
  

  • we explicitly ask to have an executable that can do multithreading (-threaded)
  • we indicate which module has the main::IO() function that should be the program with -main-is Homework9
  • we name the output using -o h9
• to run our compiled code utilizing a specific number of cores:

  ./h9 10 +RTS -N4 -RTS
  

  • ./h9 is the executable
  • 10 is a plain old command line argument (number of players)
  • We sandwich any arguments to the runtime system between +RTS and -RTS. We include -N4 to request four HECs ("Haskell Executable Contexts", roughly meaning number of cores).

Here are some sample runs. Of course you're not expected to exactly match the order of who sits, or match who loses each round.

demo$ runhaskell Homework9 3
BEGIN 3 players

round 1
music off
P3 sat in C2
P2 sat in C1
P1 lost

round 2
music off
P3 sat in C1
P2 lost

P3 wins!
END

demo$ runhaskell Homework9 3
BEGIN 3 players

round 1
music off
P3 sat in C2
P2 sat in C1
P1 lost

round 2
music off
P2 sat in C1
P3 lost

P2 wins!
END

demo$ ghc -threaded -main-is Homework9 -o h9 Homework9.hs
Loaded package environment from <...>
[1 of 2] Compiling Homework9        ( Homework9.hs, Homework9.o ) [Source file changed]
[2 of 2] Linking h9 [Objects changed]
<...>
demo$ ./h9 3 +RTS -N4 -RTS
BEGIN 3 players

round 1
music off
P1 sat in C1
P2 sat in C2
P3 lost

round 2
music off
P2 sat in C1
P1 lost

P2 wins!
END

demo$ runhaskell Homework9 6
BEGIN 6 players

round 1
music off
P6 sat in C2
P4 sat in C1
P1 sat in C4
P3 sat in C5
P5 sat in C3
P2 lost

round 2
music off
P3 sat in C2
P4 sat in C4
P6 sat in C3
P1 sat in C1
P5 lost

round 3
music off
P3 sat in C1
P1 sat in C2
P4 sat in C3
P6 lost

round 4
music off
P3 sat in C2
P1 sat in C1
P4 lost

round 5
music off
P3 sat in C1
P1 lost

P3 wins!
END
demo$

Testing It

I've provided a consistency checker file: chairs_checker.py

If you correctly generate output, this code will consume the output and confirm that it is valid or not; this allows for the expected variance in who wins each time but checks for things like players staying out of the game once they lose, correct number of rounds, and so on.

It's written in python 3; you need to give it a single command line argument that is either a filename (containing all the output from a program run), or give it "stdin" indicating it'll receive all the output (likely piped to it).

demo$ java H7 5 > 5.txt
demo$ python3 chairs_checker.py 5.txt
Everything looks good!


demo$ java H7 10 | python3 chairs_checker.py stdin
Everything looks good!
demo$

It's important that you do not print out extra output when your work is turned in, as this will trash the consistency check.

Required Components

You must have a file named Homework9.hs, and it must contain a function main of type IO(). There are some suggested imports in the file stub below, which are safely ignored when not needed.

{-

Name: ________________
Partner: _____________
G#:   ________________
(other header-comments you'd like to add)

-}

module Homework9 where

import Control.Monad        -- many useful functions
import Control.Concurrent   -- threadDelay, forkIO, MVar..., Chan...
import Data.IORef           -- newIORef, readIORef, writeIORef
import System.Environment   -- getArgs

import Debug.Trace

{-
-- download BoundedChan from hackage if you want to use this one.
-- You'll get: BC.BoundedChan, BC.newBoundedChan, BC.readChan, BC.writeChan, etc.

-- import qualified Control.Concurrent.BoundedChan as BC
-}


main :: IO ()
main = do
  ...

Now that we have a main function, you can run your file from the command line as follows without having to compile. This example also supplies N = 10 as a command line argument.

runhaskell Homework9.hs 10

Write-up

As a last step, you will write up a brief summary of what you experienced, in a README.txt file (README.pdf is also acceptable). I'd anticipate around a page at most; as long as you've answered all questions adequately, there's no minimum limit. Here are the questions to address:

1. Structure Notes:
   • what is the shared resource that represents the music? And specifically, where (file/line numbers) does the emcee turn on/off the music?
   • where (file/line) do you create the threads for each player?
   • what value do you use to represent each chair? Where (file/line) are they all created?
2. What was your strategy for players to find empty chairs? How does this ensure all chairs are eventually found?
3. For our programming task, what were the challenges that you faced? Where was there competition for resources, and where was there a need for cooperation?
4. What aspects of the task were straightforward, and which ones felt difficult or laborious?
5. What kinds of bugs did you run into – deadlock? Ordering issues? How did you attempt to inspect what was going wrong with the code? For example, did you try Debug.trace? (Did you use any debuggers or anything? Not required, I'm just curious how your experience went with various languages, and I want you to debrief on it).
6. Any extra thoughts or comments?

Turning it in

Grading

Programming Hints

Multicore usage in Haskell

 ghc -threaded -main-is Homework9 -o h9 Homework9.hs
./h9 10 +RTS -N4 -RTS