What do I need to know to solve this problem?
 

This is not for homework - it is for entry to a computer science club. I have three days to do it. I am not looking for anyone to do this problem for me, but since I don't know where to start, I am looking for advice on what I need to study and learn in order to do it myself. What is the problem about? What do the creators expect me to know in order to do it??

I am a beginning C programmer, and have written maybe three or four average-length school projects in C. They were all console applications, mostly games.

Here is the problem:

A dorm in a university wants to show off how progressive it is and ends its long standing practice of gender-segregated bathrooms on campus. However, as a concession to tradition, it makes a policy that when a woman is in the bathroom only other women may enter, but not men, and vice versa. On the door of every bathroom there will be a sign with a sliding marker that will indicate one of three possible states it is currently in:

Empty
Women Present
Men Present

The project will have two parts:

1. Using pseudocode, outline the following procedures: woman_wants_to_enter, man_wants_to_enter, woman_leaves, man_leaves.

2. In C, write an application that implements the pseudocode and uses the above procedures.

You may use whatever counters and synchronization techniques you like.

**This problem is adapted from the book, Modern Operating Systems, by Tanenbaum.

Any advice would be appreciated. Thank you.

Edit After Responses: The program must have a queue where patrons will wait if they are unable to enter the bathroom, and everyone will stay in the bathroom for a set period of time. The program will execute for 15 or more cycles. (A cycle is defined as one iteration of a person entering a queue if unable to enter the bathroom, and/or entering the bathroom if eligible and/or exiting the bathroom.)

The program must display the following during execution:

The number of the cycle
the state of the bathroom (empty, or occupied by n men or n women)
how many people are in the queue, and what their genders are.

**Problem must be solved using synchronization techniques.

You model the problem as a finite state machine. They are described with state diagrams. The states are states and the procedures are state transitions.

When you're translating your state diagram to code, just use constants for the states, and switch statements for the logic.

Like this? (Attachment.) And then for the program, just do some random choosing of which procedure gets executed, and then say

sign_on_door = {whatever the result of the procedure is, depending on the logic and the current state}?

Is it that simple? Then what are those "counters and synchronization techniques" it is talking about?

Thanks!

Yes, exactly!

No idea what "counters" are referring to. And you wouldn't use "synchronization" because you're not using multiple threads.

Counters is probably referring to how _many_ people of the same sex are currently in the bathroom.

Woman enters; marker becomes "women"; woman leaves; marker becomes "empty".

Woman enters; marker becomes "women"; woman enters; woman leaves; marker better not become "empty".

To track that you need a counter. Or a stack, with bathroom marker state derived via a "spy on the top item" function. And that can be simulated with a pop/push operation.

Perhaps only one counter is needed.
Adopt this convention:
the count of male occupants is positive integers;
the count of female occupants is negative integers.

A man may enter when the counter is not negative.
When a man enters, the counter is incremented.
When a man leaves, the counter is decremented.

A woman may enter when the counter is not positive.
When a woman enters, the counter is decremented.
When a woman leaves, the counter is incremented.

Daniel B. Martin

That's quite neat (provided that we don't have to cope with transsexuals having an identity crisis)!

As a general observation, the situation (in the modelled 'real world', rather than any aspect of the algorithm) is not very robust; it only takes one (modelled) real person to go in and forget to set the marker and a 'Carry on' film breaks out...

That makes sense about the counters. Thanks everyone.

Hmm . . . threads. Now that you mention it, I did overhear some people discussing threads. However, I did not remember the term because it was the first time I had heard it. But the way they were talking, it sounded like that was the way we should solve it. That mysterious conversation was one of the reasons I thought I needed to find out what I was missing here in this forum instead of just starting on the problem.

Would it make any sense to do this with threads?

That is pretty neat.

Simplicity is a virtue. Don't make the job any harder than it has to be.

Daniel B. Martin

Ach, I'm sorry. I just realized there was another page to the specifications. I was looking at it in an unfamiliar email system and it seems you have to press some right/left arrows to get from page to page, and not just scroll down. I didn't know that.

Anyway, I'm really sorry. I didn't mean to waste anyone's time. I just edited my original post to reflect what I know now. This new information does make it more difficult, and I am not quite sure how to approach it. I guess this is what the talk about synchronization was about. So I guess I should just toss the program I just wrote and go learn about threads, then?

The bolded bit needs clarifying for me. Does "set period of time" mean a pre-determined number of cycles for each toilet occupant? How many cycles does a person stay in the toilet? Is there a new arrival every cycle?

It seems that need two queues: one for people outside the toilet and one for inside the toilet with the inside queue including a counter per person for the time left before exiting the toilet.

Is this supposed to be a simulation? If this is the case then you would need to know the probability of a new arrival each cycle and the probability that this new arrival would be a man or a woman.

I suppose all of these variables could be user enterable.

Finally, is it reasonable to assume that a man would spend the same amount of time in the toilet as a woman? ;)

Since the instructions say that we can use any type of counters we want, I believe the amount of time the people stay in the bathroom (and what the measure of time time should be) would be left up to me. I was thinking that everyone should stay in for one cycle, since I am already keeping track of cycles.

As for whether it is a simulation, since that was not specified either I think that would be left up to me as well. Maybe I could just generate a random number from 0 to 2 each cycle to represent who wants to go in, with 0 meaning no one and 1 and 2 meaning man and woman, respectively.

I guess I could have the women stay in for two cycles and the men for one, but if I go that far, I might as well go all the way and have the women go in together in groups of two and three, and that would just be too complicated. ;)

Actually, all those little details I think I can figure along the way. What I'm trying to understand now is just the synchronization part of it. I have been reading about threads, but I still haven't learned enough to see really how they fit into this. The way I am thinking of it, it doesn't seem like they would be necessary (even though I still don't understand quite how they work or how to implement them). However, I did clarify from someone else in the club that the project is supposed to be implemented with "synchronization."

Maybe every person should be their own thread? Then the entire cycle-counter scheme I was thinking of would be wrong, I think. I still need to read more and try to understand how it would work.

I got the impression from the problem that once the toilet was emptied, the entire queue could enter (since everybody is in the queue is the same sex). So it would just be a different cycle counter for each occupant depending on their sex.

I don't understand that bit either. It seems like just a loop counter problem to me (although you could synchronize it to a keypress or have a fixed amount of time between cycles to make the simulation run slow enough to visualize it).

Come to think of it, I don't see why you have to break it down into woman_wants_to_enter, man_wants_to_enter, woman_leaves, man_leaves procedures. The occupants of the toilet will be the opposite sex to those in the queue so all you need is a simple test like:

Yes, you are right about that. Once they are in the queue, they can all go in together as soon as someone of the opposite gender comes out. I was talking about a situation where the women would walk up to the queue together. The way I was thinking of it, only one person of either gender is generated on each cycle. :)

Yes, I see what you mean. That's another reason I just think there is something here I'm not getting. I'm thinking that if I read enough about threads it will make sense, but so far it hasn't happened.