CIS 415 - Operating systems

 (InstaQuack: A Better Instagram for Ducks!)

CIS 415 - Operating systems

Fall 2019 - Prof. Allen Malony

Due date: 11:59 pm, Sunday, June 7th, 2020

Introduction:

Today, social networking is the name of the game if you want to reach out and interact with

others online. Puddles, the Oregon Duck and quite the avid socialite, if he does say so himself,

was browsing the University of Oregon's AroundtheO webpage and got a thought about how to

make his interactions with fans hit that next level. Puddles’ idea was to create a social

networking platform that would appeal to the UO undergraduates that make up his fan base.

After consulting his “branding" manager, Puddles decided to call his new social media service

InstaQuack! The ultimate goal is to give the UO student community a way to communicate

what they are doing with realtime photos, sort of like a cross between Twitter and Instagram.

After pitching his idea to the university, Puddles settled on a proprietary server technology for

InstaQuack! called Quacker that can connect photo bombers (like Puddles) with the photosphere

(where his Fan Club hangs out), but with the added twist that new photos will always be more

accessible than old photos. Now, all he needs is to recruit skilled OS developers from Prof.

Malony's CIS 415 class to build app.

Project Details:

At the heart of many systems that share information between users is the

publish/subscribe (Pub/Sub) model. The central idea of the Pub/Sub model is that publishers of

information on different topics want to share that information (articles, pictures, etc.) with

subscribers to those topics. The Pub/Sub model makes this possible by allowing publishers and

subscribers to be created and operate in the following manner: publishers send their data to a

broker which stores it under a given topic (specified by the publisher). From here, any number of

subscribers can receive data from the broker for those topics that they are subscribed to. The

relationship between publishers and subscribers is many-to-many (i.e. there can be multiple

publishers and subscribers and they all may be interested in different topics).

In the case of InstaQuack!, what is being published are only photos with a very brief

caption. Puddles, being the photophile that he is, wants the topics to be associated whatever best

describes the photo, like birds, mountains, parties, people, and so on. Because he has a limited

attention span, Puddles also wants to see only the most recent photos. Thus InstaQuack! must be

responsive, scalable, and rival anything that can be found at other Pac-12 schools. With the

extraordinary skillset that you are learning in CIS 415, for this project you will be implementing

the heart of InstaQuack! - the Quacker pub/sub server architecture (shown in Fig. 1 below).

There are 5 parts to the project, each building on the other. The objective is to get

experience with a combination of OS techniques in your solution, mainly threading,

synchronization, and file I/O.

Fig. 1: InstaQuack! Architectural Diagram

Step 1: The Quacker Topic Store

The Quacker Topic Store is at the heart of InstaQuack! Software stack. It is where recently

published photos are stored. Each topic has a bounded queue (buffer) where publishers enqueue

and subscribers dequeue. The central objective of Part 1 is to build a bounded queue that can be

used by multiple publisher threads and multiple subscriber threads. If this is implemented

successfully, then all that is needed to create the Quacker topic store is to replicate the queues.

Program Requirements:

1. Implement a circular ring buffer (a queue) capable of holding length topic entries,

where each topic entry consists of the struct shown in Fig. 2 below. There will be

MAXTOPICS total topic queues.

Fig.2: Topic entry C structure

2. Each topic queue needs to have a head and a tail pointer (an int). The tail of the topic

queue points to the newest (most recent) entry in the topic queue. The head of the topic

queue points to the oldest entry put in the queue.

3. Write an enqueue() routine to enqueue a topic entry. Each topic entry enqueued will

be assigned a monotonically increasing entry number starting at 1. The topic queue itself

will have an entry counter. Because multiple threads are accessing the topic queue,

enqueue() must synchronize its access to the topic queue. Once a thread has gained

access, the enqueue() routine will read the counter, increment it, and save it back in

the topic entry. A timestamp will be also taken using gettimeofday() and saved in

the topic entry. See: http://man7.org/linux/man-pages/man2/gettimeofday.2.html

4. Write a getEntry() routine to get a topic entry from the topic queue. The routine will

take two arguments: A) An integer argument lastEntry which is the number of the

last entry read by the calling thread on this topic, and B) A reference to an empty

topicEntry struct. The routine will attempt to get the lastEntry+1 entry if it is in

the topic queue. (Note: Because multiple (subscriber) threads can call getentry(), it

must gain synchronized access to the topic queue.) There are possible 3 cases to consider:

a. Case 1: topic queue is empty - getEntry() will return 0.

b. Case 2: lastEntry+1 entry is in the queue - getEntry() will scan the

queue entries, starting with the oldest entry in the queue, until it finds the

lastentry+1 entry, then it copies the entry into the empty topicEntry

structure passed to our routine and return 1.

c. Case 3: topic queue is not empty and lastentry+1 entry is not the queue - For

this case, there are 2 possible sub-cases:

i. getEntry() will scan the queue entries, starting with the oldest entry in

the queue. If all entries in the queue are less than or equal to

lastentry+1, that entry has yet to be put into the queue and

getEntry() will return 0. (Note, this is like the queue is empty.)

ii. getEntry() will scan the queue entries, starting with the oldest entry in

the queue. If the first entry encountered has an entry number greater than

lastEntry+1, copy that entry into our empty topicEntry struct and

return the entryNum of that entry. (Note: This case occurs because the

lastEntry+1 entry was dequeued by the cleanup thread (see below).

The calling thread should update its lastEntry to the entryNum. If

you think about this case, the first entry that is greater than

lastentry+1 will be the oldest entry in the queue.)

5. Topic entries can get too old to keep in the topic queues. If a topic entry ages DELTA

beyond when it was inserted into the queue, it should be dequeued. Write a dequeue()

routine that dequeues old topic entries. This routine will be executed by a special thread

called the topic cleanup thread. It should periodically call dequeue() on every topic

queue. After checking each queue, it should yield. Because there are multiple threads

trying to access the topic queue, dequeue() must synchronize its access.

Remarks:

In Fig. 3 below, we show a high-level view of the topic entry queue. There is one of these

queues for each topic. It has a fixed size and should be implemented as a circular ring buffer.

You should be able to retrofit the simple topic queue code that you will be working on in lab 8,

or write your own from scratch.

Fig. 3: Topic entry queue and operations

Part 1 is trickier than it seems. Let's start with the publishers. Any topic can have multiple

publishers. As such, enqueueing must be synchronized, but it is possible for a topic queue to

become full. If a publisher wants to enqueue an entry to a full topic queue, it has to wait until

there is space to do so. The simplest way to do this is to just yield the CPU and test again when

the thread is rescheduled. (If you want to get fancier, you could consider using a blocking

semaphore to implement this.) Eventually, a dequeue operation will come along and free up

queue space.

Now consider the subscribers. All subscribers for a topic must read topic entries in order

using the getentry() method to get newer feed every time.

 However, once a topic entry has reached a certain age, it might be dequeued instead of

being read by a subscriber. Who does the dequeuing? A thread will be created dedicated to

routinely clean up entries from each Queue which has reached a certain age.

Be sure to test your implementation of the topic queue to see that it is working before

moving on to the next part of the project.

1. Start with a single queue and spawn the following:

a. A single thread to push entries to the queue (i.e. a publisher thread).

b. A single thread to get entries from the queue (ie. a subscriber thread).

c. A single thread to dequeue old entries from the queue (i.e. a cleanup

thread).

2. Try to test out different scenarios, for instance:

a. Have the publisher fill up the queue before letting the subscriber get

entries.

b. Subscriber attempts to get an entry from the queue when it is empty.

c. The subscriber attempts to get an entry that was dequeued.

d. Etc.

Add more publisher/subscriber threads, then redo the tests. When it is working, create more

queues and do more testing. Doing comprehensive testing here will save a lot of debugging

later.

Your program must use Pthreads to implement the threading. Be careful to make

the code you develop thread-safe. You can use sched_yield() to have a thread yield the CPU

and have itself placed at the end of the ready-to-run scheduler queue (see sched_yield(2):

http://man7.org/linux/man-pages/man2/sched_yield.2.html)

Step 2: Constructing the Quacker Server

Now that you have the Quacker topic store working, Part 2 looks to build the rest of our Pub/Sub

broker (Quacker), the Pub/Sub Server and proxy pools. First, we will make it multithreaded. The

idea is that when an InstaQuack! publisher or subscriber “connects" to the Quacker server, a

“proxy" thread (of the appropriate type) is assigned to do their requested actions in the server.

Because publishers and subscribers may come and go, instead of creating a new proxy thread

each time, the Quacker server is initialized with two thread pools: one containing

NUMPROXIES/2 publisher proxy threads and another with NUMPROXIES/2 subscriber proxy

threads. A “free" proxy thread (of the appropriate type) is used by either a publisher or a

subscriber and then returned to the pool when they complete. In part 2, you will implement a

module for InstaQuack! that creates publisher and subscriber proxy thread pools, connects them

to the Quacker topic store, and tests their functionality.

Program Requirements:

1. Create a program that will be the skeleton of the Pub/Sub server. It will create the

Quacker topic store and initialize it, it will create the proxy thread pools (see below), and

then it will run experiments to test that things are working.

2. Create NUMPROXIES/2 publisher proxy threads, initialize them, and put them in a table

representing the publisher proxy thread pool. Each proxy thread is assigned a table entry,

where each table entry has a flag to indicate whether the thread is free and the thread's id.

(Note: Each thread in the pool is initially free. Note 2: The easiest way to do this is with

an array of structs, where we have one struct for each thread and in that struct you have

everything the struct needs.)

3. Create NUMPROXIES/2 subscriber proxy threads, initialize them, and put them in a

table representing the subscriber proxy thread pool. Each proxy thread is assigned a table

entry, where each table entry has a flag to indicate whether the thread is free and the

thread's id. (Note: Each thread in the pool is initially free. Note 2: The easiest way to do

this is with an array of structs, where we have one struct for each thread and in that struct

you have everything the struct needs.)

4. Write tests that allocate publisher proxy threads and provide the threads with topic entries

(could be a list of entries) to publish. When there are no more entries for a particular

publisher proxy thread, it is returned to the pool.

5. Write tests that allocate subscriber proxy threads and provide the threads with topics to

read entries from (could be a list of topics). When there are no more topics to read for a

particular subscriber proxy thread, it is returned to the pool.

6. Run the tests concurrently as best you can. You should try to mix things up to get the

various proxy threads to overlap in their execution.

Remarks:

This is where you should pay attention to synchronization, create test cases for yourself where

more than 2 threads are pushing and more than 2 threads are reading at the same time, you

should expect the output on the terminal to be different every time you test the same commands

without corrupted entries.

Some of the testing harnesses and scenarios that you used in part 1 might be useful to you here.

Your program must use Pthreads to implement the threading. Be careful to make the code you

develop thread-safe.

Step 3: Creating InstaQuack (Pseudo) Publishers/Subscribers

For part 3 of this project, we want to make it possible for InstaQuack publishers and subscribers

to “connect” to our Pub/Sub broker (Quacker). To do this we need to create an interface for this

to happen. To not make it overly complicated, the idea is to represent the publisher and

subscriber behaviors in a set of files that the Quacker server reads after initialization. Each file is

a set of commands that a publisher or subscriber wants to do. To begin, we need to have a set of

commands to create the publishers and subscribers. These will come in on standard input and be

interpreted by the Quacker broker using the following methods:

● create topic ""

Create a topic with ID (integer) and length. This allocates a topic queue.

● query topics

Print out all topic IDs and their lengths.

● add publisher ""

Adds a job to the publisher threads workload. A free thread is allocated to be the “proxy"

for the publisher. When the publisher is started (see below), the thread reads its

commands from the file.

● add subscriber ""

Adds a job to the subscriber threads workload A free thread is allocated to be the “proxy"

for the subscriber. When the subscriber is started (see below), the thread reads its

commands from the file.

● delta

Set DELTA to the value specified.

● start

Start all of the publishers and subscribers. Just before this happens, the cleanup thread is

started. You may use the pause() function to have your threads wait until "start" have

been processed. Then use pthread_kill() with SIGCONT to wake them up.

After these commands have been processed by the main program (master thread), the

publisher and subscriber proxy threads start to read from their command files in part 4. For part

3, they should just start up and print the following before exiting:

“Proxy thread - type: ”

Each publisher and subscriber file will be handled by a thread, if there is no thread

available at the time, then the publisher/subscriber (file) should wait until a thread becomes

available to be processed.

Step 4: Publisher/Subscriber Command Files

As mentioned in part 3, for this project, we will emulate our publishers and subscribers using text

files (i.e. command file) containing their behaviours. For part 4 of the project, you will

implement a method for our proxy threads to execute the commands contained in these files.

This occurs once the publishers and subscribers are started. They will first read the commands

contained in their respective command file and process them. The commands are as follows:

● put "" ""

The publisher thread will attempt to put a topic entry with this information into the topic

ID queue. If the queue is full the publisher will wait.

● get

The subscriber will attempt to get a topic entry from the topic ID queue. Use the

getentry() method multiple times until all the newer entries are given to the subscriber and the

end of the queue has been reached. Write all fetched entries to an output file named "SUB:

● sleep

The publisher or subscriber will sleep for this number of milliseconds.

● stop

The publisher or subscriber thread stops reading commands and the thread is returned to

the respective pool.

You will need to implement methods to execute these commands. Note: The “stop” command

will always be last. We won’t be testing the corner cases where the stop command is not last or

not present.

Remarks:

Once the publishers and subscribers are up and running, they start reading their command files

until they stop. Make sure to check that the topic ID is correct. When all publishers and

subscribers have stopped, the cleanup thread is also stopped. Note: how to handle the subscriber

is a little tricky. For example, you need to decide what to do when a subscriber tries to get an

entry for a topic and there is nothing there. You could decide to try a certain number of times

before giving up. Do not keep trying indefinitely! Also, when there are multiple entries, you

might decide to just get them all. When a publisher/subscriber executes a command it should

print the following:

“Proxy thread - type: - Executed command: ” Step 5: InstaQuack Topic Web Pages

Part 4 did not say what the subscriber does with the topic entry data it gets. For part 5 of the

project, you will adapt the provided HTML file (See Canvas attached files, provided after lab 7)

to be used by our subscribers. This file creates tables for every topic the user is subscribed to

with entries consisting of the photo and caption.

In this way, you will be able to open each of these files in a web browser and see what

each subscriber was able to get from the topics. The main program can be responsible for setting

up the files before starting the publishers and subscribers, or they can do it themselves.

Project Remarks:

One of the more creative aspects of projects of this sort is coming up with the test files that you

can use to evaluate your implementation. For any test run of the system, you need command files

to create publishers/subscribers that the master thread reads, and then more command files for

publishers and subscribers. Of course, there are many different ways to come up with these files

for testing edge cases. Another thing regards the actual photos and captions to be used. With this

in mind, we are allowing students to share their command files photos on the pinned post (Share

your command files and pictures here) on Canvas.

Project Structure Requirements:

For a project to be accepted, the project must contain the following files and meet the following

requirements: (The naming conventions listed below must be followed. Additionally you must

use the C programming language with the pthread library for this assignment. No projects

written in another programming language will be accepted.)

quacker.c: This is the main program. The quacker server is implemented here.

Makefile: Your project must include a standard make file. It must produce exe’s with the

following names: server

Report: Write a 1-2 page report on your project using the sample report collection format given.

Feel free to go over the limit if you wish. Report format and content suggestions are given in the

report collection template.

Note: Additionally, you are allowed to add any other *.h and *.c files you wish. However, when

we run your code we will only be running the server file. Make sure your code runs in the VM

before submission.

Submission Requirements:

Once your project is done, do the following:

Your executable should be able to run with the following command "./InstaQuack input.txt"

1. Open a terminal and navigate to the project folder. Compile your code in the VM with the

-g, -pthread, and - lpthread flag.

2. Run your code and take screenshots of the output as necessary (of each part).

3. Create valgrind logs of each respective part:

a. “valgrind --leak-check=full --tool=memcheck ./a.out > log*.txt 2>&1 ”

4. Tar the project folder with the following content and submit it onto Canvas.

a. quacker.c

b. Any additional header file and their corresponding ".c" file

c. makefile

d. A complete set of your test cases

e. valgrind log

f. Report

Valgrind can help you spot memory leaks in your code. As a general rule any time you allocate

memory you must free it. Points will be deducted in both the labs and the project for memory

leaks so it is important that you learn how to use and read Valgrind’s output. See

(https://valgrind.org/) for more details.

Grading Rubric:

Note: Some sections may have more detail points than the total points, meaning there are more

than 1 way you can get a 0 in that section.

1. 0/100 if your program does not compile.

2. 10 points deduction if your makefile does not work.

Late Homework Policy:

● 10% penalty (1 day late)

● 20% penalty (2 days late)

● 30% penalty (3 days late)

● 100% penalty (>3 days late) (i.e. no points will be given to homework received after 3

days)

Parts Points Description Circular ring buffer 15 A working circular ring buffer with properly working , dequeue(), getEntry() Synchronized circular ring buffer 20 A working synchronized circular ring buffer with synchronization control implemented Correct usage of pthread_create 20 Using thread to process each publisher/subscriber file Correct output file for subscriber 20 Correct output with readable format Valgrind 10 No memory leak/errors Report 10 1 - 2 page report HTML output instead of text 5 Implement step 4 subscriber output to HTML output with given format