this assignment is an implementation of a cellular automaton that uses OpenGL + glut for its front end. This program implements several rules, including the classical rule of Conway’s original Game of Life.

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

CSC 412 – Operating Systems

 Spring 2020 Cellular Automata 

 

1 What this Assignment is About

1.1 In memoriam John Horton Conway [1917-2020]

This project is sadly topical: I changed my when I read the announcement of the death of Dr. John Horton Conway on April 11th, from complications from COVID-19. John Conway was a British mathematician who did significant contributions to fields of math such as number theory, knot theory, game theory, but his most famous creation is the “Game of Life” (probably in 1970 or shortly earlier), one of the earliest examples of Cellular Automaton, and still the most popular.

 

1.2 Objectives

This assignment is somewhat similar to Prog 05 in the sense that you get a complete working program to work with and need to add functionality. The objectives of Prog 05 are for you to

1. Get further practice at modifying an existing code base, and in particular develop a “feel” for how much of the existing code base you must understand in detail and how much only requires very superficial global understanding;

2. Use external libraries in a C project;

3. Use named pipes to establish communications between a bash script and processes running a C++

4. Implement different forms of multithreaded;

5. Synchronize access to shared resources using either a single, global mutex lock or multiple mutex

(1 and 2: Yes, this is definitely very much part of my devious plan to use this course to also serve as a sort of “applied Software Engineering” course, the often-discussed and never implemented CSC306).

 

1.3 Handout

The main handout for this assignment is an implementation of a cellular automaton that uses OpenGL + glut for its front end. This program implements several rules, including the classical rule of Conway’s original Game of Life.

 

1.4  For a full-fledged implementation

My simple handout is only a quick & dirty implementation (in fact,  it is based on a demo I did  in class a couple of years ago), using the same basic OpenGL + glut framework as my other assignments. For a full implementation and some cool examples of cellular automata, download and run Golly.

 

2 Part II: Cellular Automaton

2.1   Build and run the handout

To build the handout to produce an executable named, say, cell, you would need to do

gcc main.cpp gl frontEnd.cpp -lGL -lglut -o cell

Once you start adding threading code to the handout, you will need to link with the pthread library.

So, the build command will become

gcc main.cpp gl frontEnd.cpp -lpthread -lGL -lglut -o cell

You may also include headers that are part of the math library. In that case you would execute

gcc main.cpp gl frontEnd.cpp -lm -lGL -lglut -lpthread -o cell Just keep in mind that if you need to link with the math library, then you should load it first, and that OpenGL should be loaded before glut.

 

2.2 Now look at the code

Generally, you should understand well all that is going on in main.cpp, but you only need to have a general idea of what is going on in gl frontEnd.cpp. You shouldn’t have to change much in gl frontEnd.cpp, except in the keyboard event-handling callback function, and later on when you need to synchronize some calls.

 

2.3 What to do. Version 1: Multithreaded with a single mutex lock

2.3.1 Modify the main function to take arguments

In the handout, the number of rows and columns of the grid are defined as constants. You should modify the code so that they now come as arguments of the program. You should verity that your program indeed received two arguments, and that these are positive integers larger than 3.

Style-wise, this means that the constants NUM ROWS and NUM COLS won’t be constants any- more and should be renamed, from the current all-caps-separated-by-underscores forms to lower- case with internal capitalization, since they are going to become regular variables.

 

2.3.2  Modify the main function to take arguments

In the handout, the number of rows and columns of the grid are defined as constants. You should modify the code so that the program now takes three arguments: the width (number of columns) and height (number of rows) of the grid, as well as the desired number of computation threads of the program. You should verity that your program indeed received three arguments, that these are strictly positive integers, with the width and height larger than 5, and than the number of threads is not larger than the height of the grid.

Style-wise, this means that the constants NUM ROWS , NUM COLS, and MAX NUM THREADS won’t be constants anymore and should be renamed, from the current all-caps-separated-by-underscores forms to lowercase with internal capitalization, since they are going to become regular variables.

 

2.3.3 Multithread the program

The simplest way to do this is to assign a horizontal band of the grid to each process. Of course, depending on the number of threads and the height of your grid, the last computing thread may not have the same number of rows to process as the other threads.

Because we read the data into the “current” version of the grid and write the results into the “next” copy of the grid, and no two threads ever write at the same location in the “next” grid, there is no synchronization problem between computation threads.

On the other hand, there is a problem with the rendering thread (which is the main thread of the process, once it engages in the call to glutMainLoop()). In theory, there could be a race condition on the nextGrid and nextGrid2D variables.

So, you are going to synchronize access to these variables by adding a mutex lock that will protect critical section regarding the two variables.

 

2.3.4 How to split the work?

We did something like that in a post-plague lab: Each thread should work on a separate range of grid rows. Just make sure that you split the work as evenly as possible. So, for example, if you want to split 13 rows between 4 threads, 4-3-3-3 is a good split, but 4-4-4-1 is not.

As we discussed in a lab, the way to do that is to assign to each thread a start row and an end row indices. Of course, what better place to keep this information than the thread struct that you now—hopefully—automatically define whenever you want to implement a multithreaded solution.

 

2.3.5 One last thing: speedup and slowdown

Finally, for this version to be complete, you need to figure out a way to enable the speedup and slowdown key controls. This does not mean adjusting the delay of the callback to the timer function (which should be set to a value around 10 to 30 milliseconds. Rather, you want to adjust the sleep time between generations.

 

2.4 What you should be aware of (and careful about)

2.4.1 The glut thread must be the main thread

I remind you that glut was created as a minimalist, very simple library for providing some OS services to OpenGL:

• create and resize windows;

• handle keyboard events;

• handle mouse events;

• handle timer events;

• create drop

In order to keep glut simple, its designer imposed some restrictions. The most important for us is that the glut thread (the thread that makes the call to glutMainLoop(), and thereafter surrenders control of calls to glut, must be the main thread, that is, the thread that got created when the process was launched. It cannot be a thread created by pthread create (or a C++ thread or task object created in your program).

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of