Three Spells for Hogwarts

The summer is over and it is time for Hogwarts students to return to the school. But, because of a traffic jam on the way to the King's Cross railway station, a number of Hogwarts students miss the Hogwarts Express. Realizing the situation, the Hogwarts authorities arrange for a number of flying cars to bring these students to Hogwarts.
One car can hold exactly four students; it will not leave with more or fewer. To guarantee the safety of the passengers, it is not permissible to put one Gryffindor in the car with more than one Slytherins, or to put one Slytherin with more than one Gryffindors. Any other combination is safe.

So, Hogwarts needs three spells – one for Gryffindor students, one for Slytherin students and one for Ravenclaw/Hufflepuff students. Each student must perform the assigned spell in order to get into a car.
Prof. Dumbledore can of course write these spells in no time but unfortunately he is in Azkaban trying to capture a few Death Eaters who recently escaped from the prison. Since your company is one of the very few that have a good reputation for solving tricky problems, Prof Snape has sent you an urgent owl to write these spells. Please help Hogwarts and write these spells!
It is OK if last few students never manage to get in a car because they violate the given constraints.
Your company’s wizards should write these spells without any external help. To check if the spells work as intended, they should be implemented as C/C++ functions using POSIX unnamed semaphores and their behavior should be observed using POSIX pthreads to simulate individual Hogwarts students performing these spells.

Solution Approach:
Each student is represented by a pthread. The pthread calls the right spell (based on the house to which the student belongs). The thread terminates when the spell is over (because coming out of the spell call means that the student is placed in a car and is already flying to Hogwarts). So, you could simply have the student pthreads execute the spell functions.
We can have three semaphores - griffindorQueue, slytherinQueue, ravenpuffQueue - with initial values zero to represent three queues where student pthreads wait before they get in a car. We can have three shared ints - griffs, slyths, ravenpuffs - to represent the current number of students currently waiting in each queue. We can have another semaphore - mutex with initial value 1 - to control access to these three shared ints.

The pthreads would join the queue by calling wait() on the semaphore. Before a pthread joins a queue, it will increment the value of the right shared int (of course after acquiring the mutex) and then check if 4 students are available (including itself) that meet the specified constraints (in terms of who all can ride in the same car). If yes, the thread would send right number of signals to each queue (to allow right number of threads to get out of the queues). The thread should ensure that the released threads (including itself) get into a car and leave before some other thread releases another set of 4 threads from their queues (so that the released threads dont get mixed up in undesirable combinations before getting in the cars). This can be ensured by not releasing the mutex until all released threads (including itself) have called and returned from the boardCar() function, which implements a reusable barrier and will not allow a thread to cross the barrier (and hence return from the function call) until 4 threads have arrived at the barrier. So, all released threads call the boardCar() function and the thread who did all this work (for which we can call it the Captain thread) releases the mutex after returning from boardCar(). This also marks the end of the spell function.
See the "River Crossing Problem" in the the Little Book for additional help. This problem is an adaptation of the River Crossing problem.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <signal.h>

#define TRUE 1
#define FALSE 0

sem_t griffindorQueue;
sem_t slytherinQueue;
sem_t ravenpuffQueue;
int griffs = 0, slyths = 0, ravenpuffs = 0;
sem_t mutex;

pthread_barrier_t barrier;

void boardCar(void * param);
void * gSpell(void * param);
void * sSpell(void * param);
void * rhSpell(void * param);

int getSudentNum(char * message);

int main(int argc, char** argv) {

    // initialize all semaphore to 0
    int pshared = 0; // share among threads
    int init_value = 0;

    // initialize all semaphores
    if (sem_init(&griffindorQueue, pshared, init_value) == -1) {
       perror("Griffindor semaphore open");
    if (sem_init(&slytherinQueue, pshared, init_value) == -1) {
       perror("Slytherin semaphore open");...

By purchasing this solution you'll be able to access the following files:

for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Operating Systems Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats