CS414 Prelim 2. November 11, 2003

5 questions, 20 points each.  75 minutes (10:10-11:25)

 

1.      T-Bone’s Mutt Home, a dog kennel in Lansing, has hired you to write software.  Each dog in the kennel has a crate, with a door leading to the play area. 

 

When a dog wants to go outside, it presses a big button next to the door and waits for it to open.  Once a dog is outside, a timer starts.  After 15 minutes, dog biscuits are released into the dog’s food bowl (in its crate).  Thus, a dog will play outside for 15 minutes, but then heads back inside, and the door closes and re-latches behind it.  If more than one dog goes out, the timer will be start running when the first dog goes out. 

 

Some dogs are mean.  There is a table nice[0..D-1] such that nice[i] is true if dog i can play with others.  If a dog isn’t nice, it can only go out alone.

 

We’ll model dogs as processes.  Write a monitor with entry points IWantToGoOut(d) and BackInside(d) implementing the door latch. 

 

      Monitor kennel {

              Boolean    nice[0..D-1] = { ….. }; /* Assume this is initialized appropriately */

              Condition  Mean, Nice;

              Int              Ncnt = 0, Mcnt = 0;

 

              Void IWantToGoOut(int id)

              {

                       if(nice[id] == false)

                             MeanDogGoesOut();

                       else

                             NiceDogGoesOut();

 

                       /* INCLUDED JUST FOR CLARITY */

                       UnlatchTheDoor(id);

                       If((NCnt+Mcnt) == 1) StartTheTimer();

               }

 

               Void BackInside(int id)

               {

                       /* ALSO INCLUDED FOR CLARITY */

                       LatchTheDoor(id);

 

                       if(nice[id] == false)

                             MeanDogCameIn();

                       else

                             NiceDogCameIn();

               }

 

                /* The remainder is just readers and writers, unchanged */

               void NiceDogGoesOut()

               {

                       if(Mcnt > 0) {

                              ++Nwait;  Nice.wait();  --Nwait;

                       }

                       ++Ncnt;

                       Nice.signal();

               }

              

               void MeanDogGoesOut()

               {

                       if(Ncnt > 0 || Mcnt > 0)

                              Mean.wait();

                       Mcnt = 1;

               }

 

               void NiceDogComesIn()

               {

                        if(--Ncnt == 0)

                                Mean.signal();

               }

 

               void MeanDogComesIn()

               {

                        Mcnt = 0;

                        If(Nwait > 0)

                                Nice.signal();

                        else

                                Mean.signal();

               }

 

       }

2.      In class we learned how the TCP protocol works.

a.    Suppose that machine A is connected to machine B by a wireless link that runs at 10MB/sec but drop messages now and then.  The communications link is idle.  Now, a process on machine A sends a very large amount of data as fast as it can (“slow start” is not an issue).  Under what conditions might the transfer run MUCH slower than 10MB/sec?  Explain. 

 

As we saw on one of the homework problems, this is a common problem when the link loses messages.  The TCP protocol gets confused and thinks the network is actually overloaded, so it sends less and less data.  Thus even if the capacity of the link was actually close to 10MB, the protocol might slow down to a trickle.

 

b.    Suppose that a machine is sending variable-length records over a TCP connection.  For example, it might write 32 bytes, then 16 bytes, then 100 bytes.  Can the receiver at the other end of the connection tell how many bytes were in each record, or do we need to send a “record length”?  Explain briefly.

 

TCP doesn’t include any indication of record lengths.  So you need to send this information as part of the record.  That way the remote machine can read the length, and then read the record.

 

c.    TCP increases its sending rate linearly (by adding steadily to the rate), but cuts its rate exponentially when a loss is detected (by halving it).  What’s the idea behind this “linear speedup / exponential backoff” rule?

 

TCP does this because there is a time lag between when the network gets overloaded and when it detects the problem.  When it increases its sending rate, the “impact” may not be felt for some time (perhaps 50ms or longer).  By then it may have increased the rate several times.  Thus when a packet loss occurs, it probably occurred a while back.  TCP thus decreases its rate by a lot to compensate for the delay.  The linear increase / exponential decrease policy is a rule of thumb that seems to work well for this purpose.

 

3.      A bird-watching computer network has five cameras controlled by programs P0 … P4 (running on machines M0 … M4) and a sixth server computer running a file server program FS.   When a camera spots a bird, it snaps a picture, compresses it, and then sends the resulting file (the size can vary quite a bit) to the FS program.  The FS program appends the picture to the end of a “bird sightings of the day” file for later review by an expert.

 

a.    Would it be easier (require less code on your part) to use UDP or TCP to send the picture files from the camera programs to the DB system?

 

TCP makes more sense.  Why reinvent the wheel?  If you use UDP, you need to basically reimplement all of TCP by hand, since packets could get lost and you also need to break up each image into smaller UDP sized chunks, then reassemble them.  TCP handles all of this for you.

 

b.    Suppose the cameras have very well synchronized clocks and that the pictures include the time when they were taken.  Is it possible that the pictures in the DB file might end up “out of order”, e.g. a picture taken at 3pm (and sent promptly) might end up listed in the file before a picture taken at 2:27pm (and also sent right away)?

 

Yes, this can easily happen.  TCP needs time to send a file, and anyhow one picture could be much bigger than another.  The case where it definitely won’t happen is if the two pictures were taken by the same camera.  In that case, they should arrive in order.

 

c.    We don’t want to print the “birds of the day” file until we are sure that all the pictures are safely written to it.  What would you do to ensure that the DB program knows when it has all the pictures?  Assume that nothing crashes.

 

At the end of the day, each camera should send a message saying “I don’t have any more data to send”.  Then the file system will know when it has them all.

4.      A CNN web page lists some URLs on archive.cnn.akamai.com.  You run ping from home (road runner) and then at Cornell (campus network). 

 

a.    From home “ping cnn.com” takes 55ms. From Cornell it takes 123ms.   They list identical IP addresses for cnn.com. List some possible reasons for the round-trip time difference.

 

The CNN web site may be reached by very different routes even from machines that are physically near one-another, especially if the machines are connected to different Internet service providers as in this example.  Cornell’s network connection could also be slower or just more heavily loaded.

 

b.    Now you ping archive.cnn.akamai.com.  Both report 18ms, but one gives the IP address of the akamai machine as 124.67.125.111, while the other gives it as 124.67.200.27.    Explain why this can happen.

 

Akamai uses the DNS to map the SAME computer name into DIFFERENT IP addresses corresponding to different servers within its data centers (and it has many of them).  So, in this case, it seems to be directing the requests to rather different machines.  The fact that each turns out to be 18ms away is just a coincidence.

 

c.    You set up your home computer to host a file sharing program and give out your IP address.  But nobody is able to connect. Explain why this might happen.

 

Many network providers use firewalls and/or network address translation.  This can mean that your IP address as seen “in the network” won’t be the same as it is when seen “from at home”.  Either of these can cause the problem – either your external IP address isn’t what you think it is, or the ISP has a firewall blocking incoming connections.

5.      Below is are two memory reference tableaus for the same reference string.  We assume a fixed sized memory partition of size  D = 4 pages. 

a.    Fill in the two tables, one for the least recently used (LRU) policy, and the other for least frequently used (LFU). We filled in the part for t=1 to t=4.

 

LRU

 

R(t)

9

7

1

3

9

5

6

1

2

9

7

8

1

2

1

3

1

4

9

7

1

3

9

1

3

S0

9

7

1

3

9

5

6

1

2

9

7

8

1

2

1

3

1

4

9

7

1

3

9

1

3

S1

Æ

9

7

1

3

9

5

6

1

2

9

7

8

1

2

1

3

1

4

9

7

1

3

9

1

S­2

Æ

Æ

9

7

1

3

9

5

6

1

2

9

7

8

8

2

2

3

1

4

9

7

1

3

9

S3

Æ

Æ

Æ

9

7

1

3

9

5

6

1

2

9

7

7

8

8

2

3

1

4

9

7

7

7

IN(t)

9

7

1

3

Æ

5

6

1

2

9

7

8

1

2

Æ

3

Æ

4

9

7

Æ

3

Æ

Æ

Æ

OUT(t)

Æ

Æ

Æ

Æ

Æ

7

1

3

9

5

6

1

2

9

Æ

7

Æ

8

2

3

Æ

4

Æ

Æ

Æ

 

 

LFU

 

R(t)

9

7

1

3

9

5

6

1

2

9

7

8

1

2

1

3

1

4

9

7

1

3

9

1

3

S0

9

7

1

3

9

9

9

9

9

9

9

9

9

9

9

9

1

1

9

9

1

1

9

1

1

S1

Æ

9

7

1

3

5

6

1

2

2

7

8

1

2

1

1

9

9

1

1

9

9

1

9

9

S­2

Æ

Æ

9

7

1

3

5

6

1

1

2

7

8

1

2

3

3

4

4

7

7

3

3

3

3

S3

Æ

Æ

Æ

9

7

1

3

5

6

6

1

2

7

8

8

2

2

3

3

4

4

7

7

7

7

IN(t)

9

7

1

3

Æ

5

6

1

2

Æ

7

8

1

2

Æ

3

Æ

4

Æ

7

Æ

3

Æ

Æ

Æ

OUT(t)

Æ

Æ

Æ

Æ

Æ

7

1

3

5

Æ

6

1

2

7

Æ

8

Æ

2

Æ

3

Æ

4

Æ

Æ

Æ

 

 

b.    Now compute the hit ratios for the time period t=5…25 (the part you filled in)

 

HitRatio(LRU) =  7/21 (.333)

 

 

HitRatio(LFU) =  9/21 (.429)

 

 

c.    Suppose that when using this sort of table, paging policy X gives a smaller hit ratio than paging policy Y over a wide range of reference strings.  Is it safe to conclude that in a real system, Y would be a better choice?  Explain briefly.

 

No.  When we make these tables, we leave out an important real-world phenomenon: the “stutter” seen when a program references the same page many times in a row, perhaps over a long period of time.  This effect can change the behavior of a program.