LinuxQuestions.org
Did you know LQ has a Linux Hardware Compatibility List?
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
Search this Thread
Old 05-01-2013, 01:46 PM   #1
Miranden
Member
 
Registered: May 2012
Posts: 188

Rep: Reputation: 19
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.

Last edited by Miranden; 05-02-2013 at 02:24 PM.
 
Old 05-01-2013, 02:14 PM   #2
dugan
Senior Member
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 4,616

Rep: Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415
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.

Last edited by dugan; 05-01-2013 at 02:33 PM.
 
1 members found this post helpful.
Old 05-01-2013, 03:04 PM   #3
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
Quote:
Originally Posted by dugan View Post
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!
Attached Images
File Type: jpg states2.jpg (66.2 KB, 27 views)
 
Old 05-01-2013, 03:06 PM   #4
dugan
Senior Member
 
Registered: Nov 2003
Location: Canada
Distribution: distro hopper
Posts: 4,616

Rep: Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415Reputation: 1415
Yes, exactly!

No idea what "counters" are referring to. And you wouldn't use "synchronization" because you're not using multiple threads.
 
1 members found this post helpful.
Old 05-01-2013, 04:28 PM   #5
jamesf
Member
 
Registered: Dec 2004
Location: USA
Distribution: Slackware 12 and higher
Posts: 218

Rep: Reputation: 44
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.
 
Old 05-01-2013, 05:17 PM   #6
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Ubuntu
Posts: 1,083

Rep: Reputation: 287Reputation: 287Reputation: 287
Quote:
Originally Posted by jamesf View Post
Counters is probably referring to how _many_ people of the same sex are currently in the bathroom.
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
 
1 members found this post helpful.
Old 05-01-2013, 05:28 PM   #7
salasi
Senior Member
 
Registered: Jul 2007
Location: Directly above centre of the earth, UK
Distribution: SuSE, plus some hopping
Posts: 3,896

Rep: Reputation: 774Reputation: 774Reputation: 774Reputation: 774Reputation: 774Reputation: 774Reputation: 774
Quote:
Originally Posted by danielbmartin View Post
the count of male occupants is positive integers;
the count of female occupants is negative integers.
...
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...
 
Old 05-01-2013, 06:04 PM   #8
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
That makes sense about the counters. Thanks everyone.

Quote:
Originally Posted by dugan View Post

. . . you wouldn't use "synchronization" because you're not using multiple threads.
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?
 
Old 05-01-2013, 06:06 PM   #9
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
Quote:
Originally Posted by danielbmartin View Post
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.
That is pretty neat.
 
Old 05-01-2013, 06:34 PM   #10
danielbmartin
Senior Member
 
Registered: Apr 2010
Location: Apex, NC, USA
Distribution: Ubuntu
Posts: 1,083

Rep: Reputation: 287Reputation: 287Reputation: 287
Quote:
Originally Posted by Miranden View Post
Would it make any sense to do this with threads?
Simplicity is a virtue. Don't make the job any harder than it has to be.

Daniel B. Martin
 
Old 05-01-2013, 11:31 PM   #11
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
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?

Last edited by Miranden; 05-02-2013 at 05:10 PM.
 
Old 05-02-2013, 11:18 AM   #12
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 524
Blog Entries: 2

Rep: Reputation: 68
Quote:
Originally Posted by Miranden View Post
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 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?
 
Old 05-02-2013, 01:11 PM   #13
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
Quote:
Originally Posted by psionl0 View Post
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.

Last edited by Miranden; 05-02-2013 at 02:38 PM.
 
Old 05-02-2013, 02:09 PM   #14
psionl0
Member
 
Registered: Jan 2011
Distribution: slackware_64 14.0
Posts: 524
Blog Entries: 2

Rep: Reputation: 68
Quote:
Originally Posted by Miranden View Post
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.
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.

Quote:
Originally Posted by Miranden View Post
What I'm trying to understand now is just the synchronization part of it.
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:
Code:
IF (arrival.sex = toilet.sex) OR (toilet.sex = nil) THEN
    enterToilet(arrival)
ELSE
    enterQueue(arrival)
ENDIF

Last edited by psionl0; 05-02-2013 at 02:10 PM.
 
Old 05-02-2013, 02:31 PM   #15
Miranden
Member
 
Registered: May 2012
Posts: 188

Original Poster
Rep: Reputation: 19
Quote:
Originally Posted by psionl0 View Post
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.
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.

Quote:
Originally Posted by psionl0 View Post
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:
Code:
IF (arrival.sex = toilet.sex) OR (toilet.sex = nil) THEN
    enterToilet(arrival)
ELSE
    enterQueue(arrival)
ENDIF
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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
how to solve solve broken shell problem prasanth.george Red Hat 1 01-21-2011 09:48 AM
does anyone knows how to solve this problem nikhidet Linux - Software 1 10-14-2010 02:08 AM
could u solve my problem chandu.bezawada Linux - General 3 07-26-2007 06:11 AM
Who can help me to solve this problem? Annie0716 Programming 2 08-09-2004 07:59 PM
No one can solve my problem Sundance Linux - Newbie 5 12-08-2003 01:13 PM


All times are GMT -5. The time now is 04:54 AM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration