How does the ideal gas law relate to real gases?

ideal gas law states that there are no inter molecular attractions between gas molecules and that ideal gas does not occupy space therefore having no volume.
however, a real gas does have intermolecular attractions and does have a volume.

ECE302 Spring 2006 HW5 Solutions February 21, 2006 1

ECE302 Spring 2006 HW5 Solutions February 21, 2006 1
Solutions to HW5
Note: Most of these solutions were generated by R. D. Yates and D. J. Goodman, the
authors of our textbook. I have added comments in italics where I thought more detail was
appropriate. I have made corrections where needed. The solution to problem 3.9.2 is my
own.
Problem 3.1.1 • The cumulative distribution function of random variable X is
FX (x) =


0 x < −1,
(x + 1)/2 −1 x < 1,
1 x 1.
(a) What is P[X > 1/2]?
(b) What is P[−1/2 < X 3/4]?
(c) What is P[|X| 1/2]?
(d) What is the value of a such that P[X a] = 0.8?
Problem 3.1.1 Solution
The CDF of X is
FX (x) =


0 x < −1
(x + 1)/2 −1 x < 1
1 x 1
(1)
Each question can be answered by expressing the requested probability in terms of FX(x).
(a)
P [X > 1/2] = 1 − P [X 1/2] = 1 − FX (1/2) = 1 − 3/4 = 1/4 (2)
(b) This is a little trickier than it should be. Being careful, we can write
P [−1/2 X < 3/4] = P [−1/2 < X 3/4] + P [X = −1/2] − P [X = 3/4] (3)
Since the CDF of X is a continuous function, the probability that X takes on any
specific value is zero. This implies P[X = 3/4] = 0 and P[X = −1/2] = 0. (If this is
not clear at this point, it will become clear in Section 3.6.) Thus,
P [−1/2 X < 3/4] = P [−1/2 < X 3/4] = FX (3/4) − FX (−1/2) = 5/8 (4)
(c)
P [|X| 1/2] = P [−1/2 X 1/2] = P [X 1/2] − P [X < −1/2] (5)
Note that P[X 1/2] = FX(1/2) = 3/4. Since the probability that P[X = −1/2] = 0,
P[X < −1/2] = P[X 1/2]. Hence P[X < −1/2] = FX(−1/2) = 1/4. This implies
P [|X| 1/2] = P [X 1/2] − P [X < −1/2] = 3/4 − 1/4 = 1/2 (6)
ECE302 Spring 2006 HW5 Solutions February 21, 2006 2
(d) Since FX(1) = 1, we must have a 1. For a 1, we need to satisfy
P [X a] = FX (a) =
a + 1
2
= 0.8 (7)
Thus a = 0.6.
Problem 3.1.2 • The cumulative distribution function of the continuous random variable V is
FV (v) =


0 v < −5,
c(v + 5)2 −5 v < 7,
1 v 7.
(a) What is c?
(b) What is P[V > 4]?
(c) P[−3 < V 0]?
(d) What is the value of a such that P[V > a] = 2/3?
Problem 3.1.2 Solution
The CDF of V was given to be
FV (v) =


0 v < −5
c(v + 5)2 −5 v < 7
1 v 7
(1)
(a) For V to be a continuous random variable, FV (v) must be a continuous function. This
occurs if we choose c such that FV (v) doesn’t have a discontinuity at v = 7. We meet
this requirement if c(7 + 5)2 = 1. This implies c = 1/144.
(b)
P [V > 4] = 1 − P [V 4] = 1 − FV (4) = 1 − 81/144 = 63/144 = 7/16 (2)
(c)
P [−3 < V 0] = FV (0) − FV (−3) = 25/144 − 4/144 = 21/144 = 7/48 (3)
(d) Since 0 FV (v) 1 and since FV (v) is a nondecreasing function, it must be that
−5 a 7. In this range,
P [V > a] = 1 − FV (a) = 1 − (a + 5)2/144 = 2/3 (4)
The unique solution in the range −5 a 7 is a = 4p3 − 5 = 1.928.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 3
Problem 3.2.1 • The random variable X has probability density function
fX (x) =

cx 0 x 2,
0 otherwise.
Use the PDF to find
(a) the constant c,
(b) P[0 X 1],
(c) P[−1/2 X 1/2],
(d) the CDF FX(x).
Problem 3.2.1 Solution
fX (x) =

cx 0 x 2
0 otherwise
(1)
(a) From the above PDF we can determine the value of c by integrating the PDF and
setting it equal to 1. Z 2
0
cx dx = 2c = 1 (2)
Therefore c = 1/2.
(b) P[0 X 1] =
R 1
0
x
2 dx = 1/4
(c) P[−1/2 X 1/2] =
R 1/2
0
x
2 dx = 1/16
(d) The CDF of X is found by integrating the PDF from 0 to x.
FX (x) =
Z x
0
fX
􀀀
x′

dx′ =


0 x < 0
x2/4 0 x 2
1 x > 2
(3)
Problem 3.2.2 • The cumulative distribution function of random variable X is
FX (x) =


0 x < −1,
(x + 1)/2 −1 x < 1,
1 x 1.
Find the PDF fX(x) of X.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 4
Problem 3.2.2 Solution
From the CDF, we can find the PDF by direct differentiation. The CDF and correponding
PDF are
FX (x) =


0 x < −1
(x + 1)/2 −1 x < 1
1 x 1
fX (x) =

1/2 −1 x < 1
0 otherwise
(1)
Problem 3.3.3 • Random variable X has CDF
FX (x) =


0 x < 0,
x/2 0 x 2,
1 x > 2.
(a) What is E[X]?
(b) What is Var[X]?
Problem 3.3.3 Solution
The CDF of X is
FX (x) =


0 x < 0
x/2 0 x < 2
1 x 2
(1)
(a) To find E[X], we first find the PDF by differentiating the above CDF.
fX (x) =

1/2 0 x 2
0 otherwise
(2)
The expected value is then
E [X] =
Z 2
0
x
2
dx = 1 (3)
(b)
E

X2
=
Z 2
0
x2
2
dx = 8/6 = 4/3 (4)
Var[X] = E

X2
− E [X]2 = 4/3 − 1 = 1/3 (5)
Problem 3.3.4 • The probability density function of random variable Y is
fY (y) =

y/2 0 y < 2,
0 otherwise.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 5
What are E[Y ] and Var[Y ]?
Problem 3.3.4 Solution
We can find the expected value of X by direct integration of the given PDF.
fY (y) =

y/2 0 y 2
0 otherwise
(1)
The expectation is
E [Y ] =
Z
∞
−∞
yfY (y)dy =
Z 2
0
y2
2
dy = 4/3 (2)
To find the variance, we first find the second moment
E

Y 2
=
Z
∞
−∞
y2fY (y)dy =
Z 2
0
y3
2
dy = 2. (3)
The variance is then Var[Y ] = E[Y 2] − E[Y ]2 = 2 − (4/3)2 = 2/9.
Problem 3.4.2 • Y is an exponential random variable with variance Var[Y ] = 25.
(a) What is the PDF of Y ?
(b) What is E[Y 2]?
(c) What is P[Y > 5]?
Problem 3.4.2 Solution
(a) From Appendix A, we observe that an exponential PDF Y with parameter > 0 has
PDF
fY (y) =

e− y y 0
0 otherwise
(1)
In addition, the mean and variance of Y are
E [Y ] =
1

Var[Y ] =
1
2 (2)
Since Var[Y ] = 25, we must have = 1/5.
(b) The expected value of Y is E[Y ] = 1/ = 5, so
E

Y 2
= Var[Y ] + (E [Y ])2 = 50 (3)
(c)
P [Y > 5] =
Z
∞
5
fY (y) dy = −e−y/5

∞
5
= e−1 (4)
ECE302 Spring 2006 HW5 Solutions February 21, 2006 6
Problem 3.4.3 • X is an Erlang (n, ) random variable with parameter = 1/3 and expected value E[X] =
15.
(a) What is the value of the parameter n?
(b) What is the PDF of X?
(c) What is Var[X]?
Problem 3.4.3 Solution
From Appendix A, an Erlang random variable X with parameters > 0 a postive real
number and n a positive integer has PDF
fX (x) =

nxn−1e− x/(n − 1)! x 0
0 otherwise
(1)
In addition, the mean and variance of X are
E [X] =
n

Var[X] =
n
2 (2)
(a) Since = 1/3 and E[X] = n/ = 15, we must have n = 5.
(b) Substituting the parameters n = 5 and = 1/3 into the given PDF, we obtain
fX (x) =

(1/3)5x4e−x/3/24 x 0
0 otherwise
(3)
(c) From above, we know that Var[X] = n/ 2 = 45.
Note: we need not use the definitions in Appendix A to solve these problems. We can
obtain the expressions for the expected value and the variance by applying the definitions.
This will require using integration by parts and induction, but is not otherwise difficult.
Problem 3.5.1 • The peak temperature T, as measured in degrees Fahrenheit, on a July day in New Jersey is
the Gaussian (85, 10) random variable. What is P[T > 100], P[T < 60], and P[70 T 100]?
Problem 3.5.1 Solution
Given that the peak temperature, T, is a Gaussian random variable with mean 85 and
standard deviation 10 we can use the fact that FT (t) = ((t − μT )/ T ) and Table 3.1 on
ECE302 Spring 2006 HW5 Solutions February 21, 2006 7
page 123 to evaluate the following
P [T > 100] = 1 − P [T 100] = 1 − FT (100) = 1 −

100 − 85
10

= 1 − (1.5) = 1 − 0.9332 = 0.0668 (1)
P [T < 60] =

60 − 85
10

= (−2.5)
= 1 − (2.5) = 1 − .9938 = 0.0062 (2)
P [70 T 100] = FT (100) − FT (70)
= (1.5) − (−1.5) = 2 (1.5) − 1 = .8664 (3)
Problem 3.5.3 • X is a Gaussian random variable with E[X] = 0 and P[|X| 10] = 0.1. What is the
standard deviation X?
Problem 3.5.3 Solution
X is a Gaussian random variable with zero mean but unknown variance. We do know,
however, that
P [|X| 10] = 0.1 (1)
We can find the variance Var[X] by expanding the above probability in terms of the (·)
function.
P [−10 X 10] = FX (10) − FX (−10) =

10
X

−

1 −

10
X

= 2

10
X

− 1
(2)
This implies (10/ X) = 0.55. Using Table 3.1 for the Gaussian CDF, we find that 10/ X
0.125 or X 80.
Problem 3.6.2 • Let X be a random variable with CDF
FX (x) =


0 x < −1,
x/4 + 1/2 −1 x < 1,
1 1 x.
Sketch the CDF and find
(a) P[X < −1] and P[X −1],
(b) P[X < 0] and P[X 0],
(c) P[X > 1] and P[X 1].
ECE302 Spring 2006 HW5 Solutions February 21, 2006 8
Problem 3.6.2 Solution
Here the authors use the notation
FX
􀀀
a−

:= lim
x→a−
FX (a) (1)
FX
􀀀
a+
:= lim
x→a+
FX (a) (2)
where a is any value in the range of the CDF.
[As in] the previous problem we find
(a)
P [X < −1] = FX
􀀀
−1−

= 0 P [X −1] = FX (−1) = 1/4 (3)
Here we notice the discontinuity of value 1/4 at x = −1.
(b)
P [X < 0] = FX
􀀀
0−

= 1/2 P [X 0] = FX (0) = 1/2 (4)
Since there is no discontinuity at x = 0, FX(0−) = FX(0+) = FX(0).
(c)
P [X > 1] = 1 − P [X 1] = 1 − FX (1) = 0 (5)
P [X 1] = 1 − P [X < 1] = 1 − FX
􀀀
1−

= 1 − 3/4 = 1/4 (6)
Again we notice a discontinuity of size 1/4, here occurring at x = 1.
Problem 3.6.3 • For random variable X of Problem 3.6.2, find
(a) fX(x)
(b) E[X]
(c) Var[X]
Problem 3.6.3 Solution
(a) By taking the derivative of the CDF FX(x) given in Problem 3.6.2, we obtain the
PDF
fX (x) =
(x+1)
4 + 1/4 + (x−1)
4 −1 x 1
0 otherwise
(1)
The reason for the factor of 1/4 multiplying the impulses can be seen by graphing
the CDF and determining the magnitude of the jumps in the CDF that occur at ±1.
(You can calculate this without drawing the graph but it can be helpful to visualize the
behavior of the function.)
ECE302 Spring 2006 HW5 Solutions February 21, 2006 9
(b) The first moment of X is
E [X] =
Z
∞
−∞
xfX (x) dx (2)
= x/4|x=−1 + x2/8

1
−1 + x/4|x=1 = −1/4 + 0 + 1/4 = 0. (3)
(c) The second moment of X is
E

X2
=
Z
∞
−∞
x2fX (x) dx (4)
= x2/4

x=−1 + x3/12

1
−1 + x2/4

x=1 = 1/4 + 1/6 + 1/4 = 2/3. (5)
Since E[X] = 0, Var[X] = E[X2] = 2/3.
Problem 3.7.2 • Let X have an exponential ( ) PDF. Find the CDF and PDF of Y = pX. Show that Y
is a Rayleigh random variable (see Appendix A.2). Express the Rayleigh parameter a in
terms of the exponential parameter .
Problem 3.7.2 Solution
Since Y = pX, the fact that X is nonegative and that we asume the square root is always
positive implies FY (y) = 0 for y < 0. In addition, for y 0, we can find the CDF of Y by
writing
FY (y) = P [Y y] = P
hpX y
i
= P

X y2
= FX
􀀀
y2
(1)
For x 0, FX(x) = 1 − e− x. Thus,
FY (y) =

1 − e− y2
y 0
0 otherwise
(2)
By taking the derivative with respect to y, it follows that the PDF of Y is
fY (y) =

2 ye− y2
y 0
0 otherwise
(3)
In comparing this result to the Rayleigh PDF given in Appendix A, we observe that Y is a
Rayleigh (a) random variable with a = p2 .
ECE302 Spring 2006 HW5 Solutions February 21, 2006 10
Problem 3.7.3 • If X has an exponential ( ) PDF, what is the PDF of W = X2?
Problem 3.7.3 Solution
Since X is non-negative, W = X2 is also non-negative. Hence for w < 0, fW(w) = 0. For
w 0,
FW (w) = P [W w] = P

X2 w

(1)
= P [X w] (2)
= 1 − e− √w (3)
Taking the derivative with respect to w yields, for w 0, fW(w) = e− √w/(2pw). The
complete expression for the PDF is
fW (w) =
(
e−
pw
2√w w > 0
0 otherwise
(4)
where we note that we cannot allow w = 0 to be part of the first case when we have pw in
the denominator.
Problem 3.8.1 • X is a uniform random variable with parameters −5 and 5. Given the event B = {|X| 3},
(a) Find the conditional PDF, fX|B(x).
(b) Find the conditional expected value, E[X|B].
(c) What is the conditional variance, Var[X|B]?
Problem 3.8.1 Solution
The PDF of X is
fX (x) =

1/10 −5 x 5
0 otherwise
(1)
(a) The event B has probability
P [B] = P [−3 X 3] =
Z 3
−3
1
10
dx =
3
5
(2)
From Definition 3.15, the conditional PDF of X given B is
fX|B (x) =

fX (x) /P [B] x 2 B
0 otherwise
=

1/6 |x| 3
0 otherwise
(3)
(b) Given B, we see that X has a uniform PDF over [a, b] with a = −3 and b = 3. From
Theorem 3.6, the conditional expected value of X is E[X|B] = (a + b)/2 = 0.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 11
(c) From Theorem 3.6, the conditional variance of X is Var[X|B] = (b − a)2/12 = 3. Of
course we do not have to use Theorem 3.6. We can instead use the definitions and
write
Var[X|B] = E

X2|B

− (E [X|B])2 =
Z 3
−3
x2

1
6

dx − 02 = · · · = 3. (4)
Problem 3.8.2 • Y is an exponential random variable with parameter = 0.2. Given the event A = {Y < 2},
(a) What is the conditional PDF, fY |A(y)?
(b) Find the conditional expected value, E[Y |A].
Problem 3.8.2 Solution
From Definition 3.6, the PDF of Y is
fY (y) =

(1/5)e−y/5 y 0
0 otherwise
(1)
(a) The event A has probability
P [A] = P [Y < 2] =
Z 2
0
(1/5)e−y/5 dy = −e−y/5

2
0
= 1 − e−2/5 (2)
From Definition 3.15, the conditional PDF of Y given A is
fY |A (y) =

fY (y) /P [A] x 2 A
0 otherwise
(3)
=

(1/5)e−y/5/(1 − e−2/5) 0 y < 2
0 otherwise
(4)
(b) The conditional expected value of Y given A is
E [Y |A] =
Z
∞
−∞
yfY |A (y) dy =
1/5
1 − e−2/5
Z 2
0
ye−y/5 dy (5)
Using the integration by parts formula
R
u dv = uv −
R
v du with u = y and dv =
e−y/5 dy yields
E [Y |A] =
1/5
1 − e−2/5

−5ye−y/5

2
0
+
Z 2
0
5e−y/5 dy

(6)
=
1/5
1 − e−2/5

−10e−2/5 − 25e−y/5

2
0

(7)
=
5 − 7e−2/5
1 − e−2/5
(8)
ECE302 Spring 2006 HW5 Solutions February 21, 2006 12
Problem 3.9.2 • For the modem receiver voltage X with PDF given in Example 3.32, use Matlab to plot
the PDF and CDF of random variable X. Write a Matlab function x=modemrv(m) that
produces m samples of the modem voltage X.
Problem 3.9.2 Solution
I generated the PDF and CDF using the Matlab commands normpdf and normcdf. I
generated a histogram of the random samples from the PDF generated by my Matlab
function modemrv. The code for generating the required plots is given below.
%
% Yates and Goodman 3.9.2 2/14/06 --sk
%
x1 = (normpdf([-30:.01:30],-5,2)+normpdf([-30:0.01:30],5,2))/2;
figure(1)
plot([-30:.01:30],x1)
title(’PDF for Example 3.32, p. 139’);
xlabel(’x’);
ylabel(’f_X(x)’);
print -deps pdf_3_9_2
figure(2)
x2 = (normcdf([-30:.01:30],-5,2)+normcdf([-30:0.01:30],5,2))/2;
plot([-30:.01:30],x2)
title(’CDF for Example 3.32, p. 139’);
xlabel(’x’);
ylabel(’F_X(x)’);
print -deps cdf_3_9_2
% some checks:
% height of local minimum of PDF at x = 0
disp(’height of local minimum of PDF at x = 0’)
fx0 = 2*exp(-25/8)/sqrt(32*pi)
% height of local maximum of PDF at x = +/- 5
disp(’height of local maximum of PDF at x = +/- 5’)
fx5 = (exp(-100/8)+1)/sqrt(32*pi)
x = modemrv(10000);
figure(3)
hist(x,100);
title(’Histogram of samples from the PDF of Example 3.32’)
xlabel(’x (Volts)’)
print -deps hist_3_9_2
ECE302 Spring 2006 HW5 Solutions February 21, 2006 13
Here is the plot of the PDF.
−30 −20 −10 0 10 20 30
0
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
0.1
PDF for Example 3.32, p. 139
x
fX(x)
Note that in order to verify that I was using the function normpdf correctly I plugged in
the values of 0 and 5 to see what the local maxima and minima should be. The results were
>> p3_9_2
height of local minimum of PDF at x = 0
fx0 =
0.0088
height of local maximum of PDF at x = +/- 5
fx5 =
0.0997
which match the values seen in the plot of the PDF.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 14
Here is the plot of the CDF.
−30 −20 −10 0 10 20 30
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
CDF for Example 3.32, p. 139
x
FX(x)
Without doing any calculations, we know that the CDF should have value FX(0) = 1/2 and
that FX(x) should approach 1 as x becomes large. Our plot meets both of these criteria.
Finally, here is the function modemrv,
function x=modemrv(m);
%Usage: x=modemrv(m)
%generates m samples of X, the modem
%receiver voltage in Exampe 3.32.
%X=+-5 + N where N is Gaussian (0,2)
sb=[-5; 5]; pb=[0.5; 0.5];
b=finiterv(sb,pb,m);
noise=gaussrv(0,2,m);
x=b+noise;
and the histogram of the data generated by the function modemrv. The shape of the his-
togram matches the shape of the PDF as it should.
ECE302 Spring 2006 HW5 Solutions February 21, 2006 15
−15 −10 −5 0 5 10 15
0
50
100
150
200
250
300
Histogram of samples from the PDF of Example 3.32
x (Volts)

Adfly ads reduced *

Now, there should only be one adfly ad on site load. You should be able to browse the blog now without ads reoccuring.

5 Tips to Help You on Your Finals

Here are some tips to help out with those finals!

1. Don't freak out about tests. Yes, they are long, and comprehensive, and require a lot of preparation, but it is all stuff you've learned over the semester, and you can get through most of the material in 24 hours of studying. When you think your life is nearly over, imagine yourself a week from now; finals done, summer in session. It's less than 7 days away.

2. Block sites like Facebook, Twitter, YouTube, Google Plus. Social networking will drain your time away slowly, even though it doesn't feel like it. Visiting Facebook 5 times in 2 hours at 6 minutes a  visit is 30 minutes of time lost to Facebook, accounting for 25% of your overall productivity in those two hours. It adds up! Try Chrome application "StayFocusd" to block websites.

3. Don't spend so much on pizza and fast food. Save that for when you're done or when you realllly need some motivation. Stick to simple meals that can be easily prepared, so you can have as much time to study as you can get.



4. The library is not your friend during finals week. Every nook and booth you find will have people in it already. You'll waste a bunch of time finding parking too, let alone finding a table with an outlet for your laptop. Try another campus building; classrooms are usually empty, and offer you the secluded study environment you need to focus.

5. Plan out your week accordingly. Final on Friday? Maybe partying on Thursday night with your friends isn't the best idea. I like to allocate one day ahead of each final to specifically focus on that final, and I turn down most social activities unless they are before that one day buffer (you are already going to be distracted by the internet, roommates, your phone, etc. You don't need to have any more with social activities that take up hours of precious study time).

In the end, remember, by 4pm on Friday you'll be feeling awesome and free with a great outlook on the summer ahead. Thats when you can relax. As for now, you got work to put in.

15-441: Computer Networks Homework 2 Solution

DOWNLOAD THE PDF FILE

15-441: Computer Networks
Homework 2 Solution
Assigned: September 25, 2002.
Due: October 7, 2002 in class.
In this homework you will test your understanding of the TCP concepts taught in class including flow control,
congestion control, and reliability.
You must solve the homework individually. Make sure you provide all your answers in the space provided
in the end. For full credit, show your work in clearly readable writing. Points will be deducted for unreadable
answers. The following notation should be used for all the calculations.
Parameter Description Units
􀀀 Maximum Segment Size bytes/packet
Window Size packets
􀀀 Window Size bytes
Round trip time seconds
or
Throughput bits/sec
Utilization dimensionless percentage
Loss rate dimensionless proportion/probability
Table 1: Notation of parameters to be used throughout the assignment
1 TCP Basics
1. True or False?
(a) Host A is sending a large file to host B over a TCP connection. Assume host B has no data to send to host A.
Host B will not send acknowledgments to host A because host B cannot piggyback the acknowledgments
on data.
Answer: FALSE. Piggybacking is an optimization that is used when both sides have to send data to each
other so that the receiver, instead of sending two packets i.e., an ACK and a data packet, it just sends one.
When the receiver (B) does not have any data to send, it will still send an ACK with the sequence number
field containing the next sequence of data it is supposed to send.
(b) The size of the TCP RcvWindow never changes throughout the duration of the connection.
Answer: FALSE. RcvWindow is used to give the sender an idea of how much free buffer space is available
at the receiver. Thus as the amount of unacknowledged TCP data varies the RcvWindow also changes.
(c) Suppose host A is sending a large file to host B over a TCP connection. The number of unacknowledged
bytes that A sends cannot exceed the size of the advertised receiver buffer.
Answer: TRUE. TCP is not permitted to overflow the allocated receiver buffer. Hence when the sender
can not send any more data RcvWindow would be 0 and hence all the buffer would have unacknowledged
data.
(d) Suppose that the last SampleRTT in a TCP connection is equal to 1sec. Then the current value of TimeoutInterval
for the connection will necessarily be
􀀀
sec.
Answer: FALSE. Depending on the value of

or EstimatedRTT it may or may not be greater than 1.
2. Suppose host A is sending a large file to host B over a TCP connection. The two end hosts are 10msec apart
(20msec RTT) connected by a 1Gbps link. Assume that they are using a packet size of 1000 bytes to transmit
the file. Also assume for simplicity that ACK packets are extremely small and can be ignored.
(a) At least how big would the window size (in packets) have to be for the channel utilization to be greater
than 80%.
Answer: Bandwidth-delay product of A to B




!
.
For 80% utilization, it will be

" #

%$&' ( "$)
* + , !
.
Number of packets
.-+/0213-54
6
7 18-94:4;4 < =8> ? @ A !
.
(b) Assuming infinite initial threshold, no losses and competing traffic, approximately how long (in seconds)
would it take for the normal slow start mechanism to achieve 80% utilization?
Answer: Number of RTTs
CBEDGF H"IKJG MLONP Q R
.
Time

S K
* % T 3$ KUM AV?
.
3. TCP waits until it has received three duplicate ACKs before performing a fast retransmit. Why do you think the
TCP designers chose not to perform a fast retransmit after the first duplicate ACK for a segment is received?
Answer: Packets can arrive out of order from the IP layer. So whenever an out of order packet would be
received it would generate a duplicate ACK and if we perform retransmission after the first duplicate ACK it
would lead the sender to introduce too many redundant packets in the network.
2 TCP Security
Consider a misbehaving TCP receiver. The receiver modifies its TCP such that upon receiving a data segment containing
W
bytes, the receiver divides the resulting acknowledgment into 􀀀 , where 􀀀YX W
, separate acknowledgments
each covering one of 􀀀 distinct pieces of the received data segment. For e.g. if it receives data acknowledging bytes
1 to 1000, then the receiver, for 􀀀
<
, will send 2 ACKs for 501 and 1001.
Consider a normal TCP sender sending data to this misbehaving TCP receiver. The sender sends a 1500 byte
packet with sequence number 1. The receiver sends back 􀀀
<Z
ACKs.
1. What packets will the sender send next in response to the 3 ACKs?
Answer: Response will be packets with byte sequence numbers 1501, 3001, 4501 and 6001.
2. Assuming no losses and negligible packet transmission time, derive an expression for the sender window size
during the slow start phase, in terms of
[
(number of RTTs) and 􀀀 .
Answer: For each outgoing packet, the receiver sends back 􀀀 ACKs. The sender will increment the
? \][^
by
􀀀 . So if initially the window was 1, after 1 RTT the window size will be 􀀀
N<
. In the second RTT, the sender
sends 􀀀
NR
packets (the window size) and receives 􀀀

`J
􀀀
N L
ACKs. So now the window will increase
by 􀀀

`J
􀀀
N L
and become 􀀀

`J
􀀀
NR LaN
􀀀
N CJ
􀀀
N LI . After
[
RTTs, the window size will be
J
􀀀
NP VL5b
.
3. Can you think of a simple enhancement to the sender which can prevent the receiver from launching this attack?
Answer: One solution is that the sender should advance the congestion window at byte granularity rather than
packet granularity. Hence
? \][^
will be incremented not by a full MSS but only proportional to the amount of
data acknowledged. Another solution is to increment
? \ [^
by one MSS when a valid ACK arrives covering the
entire data segment sent.
2
3 RED/AQM
Consider a bursty greedy source. Would RED drop more packets for this source or Droptail? Explain briefly your
answer.
Answer: Bursty traffic suffers more losses with drop tail than RED gateways. Consider the case when the queue
gets almost full. In droptail gateways an arrival of a burst would result in several losses as most of the burst will be
lost. In contrast in RED gateways, it drops packets early so as not to allow the queue to grow fully. So when a burst
arrives, it will only drop some of the packets of the burst. The number of packets dropped will be roughly proportional
to their share of the bandwidth. Hence the bursty flow should lose fewer packets in RED.
4 Fast Recovery and TCP Modelling
Note: Remember to use Table 1 for all symbols and units. Points will be lost for incorrect units.
1. Harry Bovik says that when during steady state, achieved TCP throughput should be 75% of the bottleneck
bandwidth. His reasoning is that when the throughput reaches 100% of the bottleneck, there is a packet drop
causing the window to be halved to 50% and then it increases linearly back to 100% repeating the same cycle.
Is he right or wrong? Explain briefly your answer.
Answer: He is wrong. The achieved throughput should be close to 100% because of router buffers. As the TCP
connection starts sending at rates higher than the bottleneck bandwidth the buffers start to fill up until there is
a packet loss. Now the TCP will reduce its rate to 50% of that high rate and so on the average TCP will be
sending at much higher rate than 75% of the bottleneck bandwidth.
2. Let
\
represent the congestion window size in TCP during steady state. The idealized congestion window size
varies from 􀀀I
to during steady state and then a loss occurs. Suppose an additional constraint is added
such that the maximum receiver window size for a connection is set to

. Assuming a loss occurs when the
congestion window has a size of ,
(a) Find the loss rate for this TCP connection in terms of . Hint : Calculate the number of packets sent
per loss cycle
Answer: Solution 1 (correct):
􀀀7
to
Approximate Number of Packets sent = A r􀀀 ea under the graph = rectangular region + trapezium region
=
􀀀7
  􀀀7 N -I J 􀀀7 N 􀀀 L
  􀀀7 - I - 7 I Loss rate
- 􀀀 - I 7 -
􀀀 Solution 2 (accepted with full points): 􀀀I
to
Approximate Number of Packets sent = Area un d􀀀 er the graph = rectangular region + trapezium region
= 􀀀 I
 􀀀 I N I- J 􀀀 I N 􀀀 L
 􀀀 -;I-
I Loss rate
-􀀀 I
-;-
􀀀
W/2
W
3W/4
W/4 RTT W/2 RTT Time sec.
3W/4
Time sec.
3W/8
3W/8 RTT 5W/8 RTT
Figure 1: Answer 4.3 : TCP Window with flow control
(b) Derive an expression for the achieved throughput


in terms of

and 􀀀 .
Answer: Solution 1 (correct):
􀀀7
to
􀀀 From previous answer,


- I 7 -
.
3

  􀀀




􀀀
1

1 7 1
-
􀀀 1

-5421

Replacing with
- I 7 -
and simplifying we get

 
-54 I 1
1

bps
Solution 2 (accepted with full points): 􀀀I
to
􀀀 From previous answer,


I
-:-
.

  􀀀




􀀀
1

1 7 1
-:- 􀀀 1

I 1

Replacing with
I
-:-
and simplifying we get

  I I:I 1

1

bps
5 Congestion Control
Harry Bovik thinks that if the sources in the Internet use additive increase additive decrease (AIAD) the system should
still converge to fairness and efficiency.
C
C
Region I
Region II
Region III
Region IV
Connection 2 throughput
Connection 1 throughput
Figure 2: TCP Phase-plot
Harry decides to use phase-plots (see pg. 269 of the book) to check his intuition for the two-user case. Figure 2
shows a simple phase plot. In the graph, the state of the system is represented by a point (x1, x2), where x1 is stream
1’s current rate and x2 is stream 2’s current rate. The total capacity of the link is C bits/s. Assume that after the packet
loss the window sizes have been reduced according to AIAD and now the system state is in either one of the labelled
regions.
1. On the figure, for each of the labelled regions, I, II, III, and IV, draw vectors indicating the direction in which
the system will move next i.e., after the AIAD response to the packet loss.
Answer: See Figure 3.
2. In each of the following regions, does the response after the packet loss increase, reduce or keep fairness the
same?
Region I: Answer: Increases
Region II: Answer: Decreases
4
C
C
Region I
Region II
Region III
Region IV
Connection 2 throughput
Connection 1 throughput
Figure 3: Answer 5.1 : TCP Phase-plot
Region III: Answer: Decreases
Region IV: Answer: Increases
On the 45 degree line through the origin: Answer: Unchanged
3. Does Harry’s scheme converge to a fair allocation? Explain your answer briefly.
Answer: No it does not. Both the connections will decrease their share equally on a packet loss (additive
decrease) rather than in proportion to their share of C (multiplicative decrease). Similarly both the connections
will attempt to grab bandwidth equally when it is available. So the movement will remain on the 45 degree line
parallel to the fairness line based on their initial starting point.
4. Does Harry’s scheme converge to an efficient allocation? Explain your answer briefly.
Answer: Yes it does. They adaptively increase their share when they are below the efficiency line (Regions I and
IV) to move towards the efficiency line. Similarly they decrease their share on losses and hence move towards
the efficiency line when they are above the efficiency line (Regions II and III).
6 Multimedia
1. Harry Bovik decides that for his video application to recover from losses over the Internet he should set the
video buffer playout time equal to the current RTT to the sender. He runs his multimedia application playing
videos from all around the world. He notices that for larger RTT values his video works fine while for shorter
RTT values his video misses several frames. What is the mistake that Harry is making?
Answer: The buffer playout time should be based on the delay jitter rather than end-to-end delay (RTT) to
ensure smooth playing. In this case what is happening is that for shorter RTTs the jitter is more than the RTT
and these delayed packets result in missed frames while for large RTT values, the jitter is smaller than the RTT
and so fewer packets are missed.
2. Why do you think TCP is not used for streaming multimedia (audio, video) files?
Answer: Providing timely delivery is more crucial in multimedia applications than providing reliability. The
multimedia applications can tolerate occasional losses without any need to retransmit all the lost packets. In
regards to congestion control, multimedia applications usually have their own application level mechanisms to
handle congestion because it often requires understanding of the application data (e.g. B, I and P frames in
mpeg) and TCP is not a suitable layer for providing such congestion control mechanisms.
5
3. Harry Bovik says that since there are negligible losses within the US, the streaming multimedia applications do
not need to have a playback buffer in US. What would be your response?
Answer: The playback buffer is required to smooth out the video. Delay variance causes packets to arrive after
their playout time and hence are missed. The playback buffer is needed even if there are no losses.
7 Reliability
For all parts of this question, refer to figure 4. The graph shows the packets sent and ACKs received by a TCP Reno
sender. The x-axis shows the time in seconds and the y-axis shows the sequence number of the packet (or ACK) being
sent (or received). Assume that all packets that are not lost will arrive in order at both the sender and receiver. Also
assume that receiver keeps all the out of order received packets.
Sender view of packets and ACKs in TCP Reno
Packets
ACKs
Seqno
Time
0.0000
5.0000
10.0000
15.0000
20.0000
25.0000
30.0000
35.0000
40.0000
45.0000
50.0000
0.0000 1.0000 2.0000 3.0000 4.0000
Figure 4: Reno : Fast Retransmission
1. Mark on the x-axis of the graph, the time interval when the connection is in slow-start.
Answer: Slow start is approximately from time 0 to 1.4sec, 2.2 to 3.1 sec, and 3.5 to 3.7 (though it is fine if you
missed this last one).
2. Mark the packets (if any) with


that are lost.
Answer: Packet Numbers: 25, 26, 27, 29, 32, 36, 41, 46, 47, 48, 49
6
3. Mark the duplicate packets received by the receiver (if any) with a
􀀀
.
Answer: Packet Numbers: 28(2nd), 30(2nd), 31(2nd), 33(2nd), 34(2nd), 35(2nd), 36(3rd), 37(2nd), 38(2nd),
39(2nd), 40(2nd), 41(3rd), 42(2nd), 43(2nd), 44(2nd), 45(2nd), 46(3rd), 50(2nd)
4. Mark the timed out packet (if any) with a T.
Answer: Packet Number: 26
5. Draw on the graph an approximate curve showing how a Tahoe TCP Sender would behave.
Answer: Tahoe will behave the same as Reno for the first 1.5sec. Then while Reno would wait for a timeout,
Tahoe will start slow start around 1.5sec and continue roughly parallel to Reno but being about 1sec earlier
than Reno.
7

Final Exam: Comp. Sys. Org. II

 Final Exam: Comp. Sys. Org. II

Friday, May 9, 2003 Note: I will send mail to the class list when the exam and course grades are ready -- probably Monday or Tuesday next week. Send me email if you want to know your grades. Solutions to the exam will be posted on the Web some time next week.

Problem 1

(10 points)
Suppose that a disk read from file F completes; that process P is currently running; and that process Q has been blocked waiting for this read to complete. Some of the following events occur; others do not. State which events occur, and in which order they occur.

• A. An assembly-language routine saves the current value of the registers.
• B. Control returns to process P.
• C. P is blocked.
• D. P traps to the kernel, invoking the top of the disk driver.
• E. Process Q is unblocked.
• F. The data is copied from the buffer in the disk controller into Q's user space.
• G. The hardware saves the current value of the program counter.
• H. The interrupt controller issues an interrupt.
• I. There is a context switch from P to Q.
• J. Using the interrupt vector, control jumps to the bottom of the disk driver.

Answer: This problem was a little more ambiguous than I intended, because I forgot to specify the scheduler. With some schedulers and in some states, such as round robin, P will resume as the active process once the interruption has been dealt with. With other schedulers and in other states, P will be preempted for Q; for instance, this will happen if the scheduler is "Shortest remaining time next" and the next CPU burst for Q is shorter than the remainder of P's current CPU burst. So either B or I can occur, though, of course, not both. Also, E and F can occur in either order, and, if I occurs, it can occur in any order relative to E and F. Finally, it is barely possible, though very unlikely, that A could occur before J. That being said: The first two events must be H and G, in that order. These are followed by J and A -- almost certainly in that order, but possibly in order A,J. If control returns to P, then the next events are E and F, in either order, followed by B. If control is passed to Q, then E, F, and I occur in any order.
C and D do not occur. A very common error was to include C, but P is not blocked. It is interrupted by the kernel, and it may be preempted in favor of Q.

Problem 2

(10 points)
Suppose that a computer uses a paging system, with a page size of 4K Bytes, and that the current machine instruction references virtual address V. Suppose that the page containing V is currently in memory but not in the TLB. How is V translated into a physical address? Explain the translation at the level of bit manipulation. Answer: The twelve low-order bits are the offset O; the higher-order bits are the page number P. The value of PageTable[P] is the frame number F. The physical address PA has F has its high-order bits set to F and its low-order bits set to O.

Problem 3

(15 points)

• A. The least recently used (LRU) page replacement algorithm tends to yield fewer page faults than the not recently used (NRU) algorithm. Explain why. Answer: Both algorithms are based on the assumption that pages that have not been recently referenced are likely not to be referenced again soon. The LRU measures the time of the most recent reference exactly. The NRU measures the time of the most recent reference only crudely, dividing it into two categories: since the last clock tick and before the last clock tick. Thus, much less information is available for choosing a page to replace, so the quality of choice is inferior.
• B. Nonetheless, the LRU algorithm is rarely if ever implemented for paging systems. Why not? Answer: Implementing LRU requires that the page be time-stamped at each memory reference (i.e. two such time-stamps per machine instruction.) The hardware to support this is certainly expensive and probably non-existent.
• C. The optimal algorithm cannot be implemented, since it involves predicting the future. What, then, is the significance of this algorithm? Answer: It can be used, after the fact, to establish a lower bound on the minimum number of page faults, which can be used to gauge how well the actual page replacement algorithm is working.
  Almost everyone got part (C) correct, which surprised me a little, as it is a comparatively abstract and minor point.

Problem 4

(16 points)
The problem of starvation is a potential danger at many different points in an operating system. Explain how the problem arises:

• A. In the process scheduling algorithm. Answer: If the choice of the next process to run is based strictly on the properties of the process, such as assigned priority or expected running time, then a steady stream of high-priority/short jobs may prevent a low-priority/long job from ever being chosen.
• B. In the disk arm scheduling algorithm. Answer: If the ``shortest seek time'' algorithm is used, then a steady stream of requests close to the disk arm may prevent a request far from the disk arm from ever being serviced.
• C. In choosing a process to unblock when a semaphor is released. Answer: Much the same as part (A). If there are several processes waiting for a given semaphore, then the OS must choose among them one to run. If the choice is on the basis of priority, and there is a steady stream of high-priority processes being blocked for this semaphor, then a low-priority process may never be chosen.
• D. In the readers/writers problem. Answer: In the standard solution to the readers/writers problem, if the resource is currently being read, then new readers are allowed to enter, but writers are not. Therefore, if there is a steady stream of readers, no writer will ever get access to the resource.

Mostly, errors on this problem were of two types. One was to confuse starvation with deadlock. The other was to confuse starvation with long waits, of one kind or another. Long waits are sometimes inevitable. Starvation is different; starvation is the situation, such as those above, in which logically the system could eventually run process P (unlike deadlock) but it never does run P because it always prefers to run something else.
Answer:

Problem 5

(4 points)
Suppose that a block is 1K Byte and that a disk address is 4 bytes. Suppose that files are implemented using i-nodes, and that an i-node has the following structure: the last address in the inode is a third-level indirect block; the second-to-last address is a second-level indirect block; the third-to-last address is an indirect block; and the remaining addresses are data blocks. Approximately how large a file can this system support? You do not have to give an exact answer; just give a range between two consecutive powers of 2. (That is, the form of your answer should be "Between 2^K and 2^K+1 bytes," for some particular value of K). Answer: Each block holds 2⁸ = 256 addresses (= 1K Bytes / 4 Bytes). Therefore the third-level indirect block points to 2⁸ second-level indirect blocks. Each of these points to 2⁸ indirect blocks. Each of these points to 2⁸ data blocks. Each of these holds 2¹⁰ bytes. So the total size of the data indexed under the third-level indirect block is 2⁸ * 2⁸ * 2⁸ * 2¹⁰ = 2³⁴ bytes = 16 GBytes. The total size of all the other blocks is comparatively negligible (about 1/256 the size). So the answer is "Between 2³⁴ and 2³⁵ bytes."
Only one student got this correct, though three or four other students were within a factor of 100 or so.

Problem 6

(10 points)
Explain briefly (3 or 4 sentences) the difference between a hard link and a symbolic link, as implementations of shared files. Answer: If one creates a hard link from the path name "/B/Y" to the file /A/X, then the directory B holds, under the name Y, the actual disk address of this same file. That is, the relation between the directory B and the file is exactly the same as the relation between the directory A and the file. If the file is deleted under the name /A/X it is still linked under the name /B/Y.
By contrast, if one creates a symbolic link from path name "/B/Y" to file /A/X, all this does is create a new file /B/Y which holds the name of the path "/A/X" plus some flag that this is a symbolic link. If file /A/X is now deleted, this link fails to refer. If a new file /A/X is created, this link now points to the new file.

Problem 7

(15 points)
Amy is running the following experiment to study the effectiveness of multiprogramming in her operating system: She has chosen a fixed, fairly large, program P. The experiment involves concurrently running N processes, each executing P on the identical inputs (so the behavior should be identical) for values of N ranging from 1 to 100, and making a variety of measurements. One of the quantities that Amy is measuring is the number of blocks read from disk. When N=1, the process reads M blocks from disk. Amy expects, therefore, that in general N processes will read N*M blocks.
What she finds is quite different. For small values of N, the number of blocks read is much smaller than N*M; in fact, it's barely larger then M, regardless of N. For large value of N, the number of blocks read is much larger than N*M.
Explain these findings. (2 or 3 sentences is fine; in fact, I'm basically looking for two key words.)
Answer: The two keywords are "cache" and "thrash". Since all the processes are executing the same code at pretty much the same time, they will end up reading the same blocks of the same files at the same time. Hence, after the block has been first read by one process, it will almost certainly be available in the cache for all the other processes, so each block read done for a single process suffices for all the processes, as long as there are few processes.
However, if there are so many processes that the working sets for the processes exceed the size of physical memory, then the system will have to do a large amount of paging in and out (or swapping) to run the processes. This involves a large number of disk reads that were not needed when a single instance of the process was running.

Problem 8

(10 points)
Consider a color display controlled by 24-bit video RAM running in bitmap mode.

• A. What does video RAM "look like" from the point of view of the CPU? Answer: Video RAM, though physically separate, from the point of view of the CPU is just part of the same physical address space as ordinary RAM. That is, there is a fixed range of physical addresses that refers to video RAM.
• B. How does the content of video RAM correspond to the display? Answer: For each pixel in the display there is a corresponding set of 3 (or 4) bytes in video RAM. These hold 3 8-bit integers between 0 and 255, expressing the intensity of the three colors red, blue, and green.

Problem 9

(10 points)
Briefly (2 or 3 sentences) describe the difference between the download/upload model and the remote access model in implementing a distributed file system. State one advantage of each technique. Answer: In a download/upload model, the entire file is downloaded from server to client when the file is opened. When the file is closed, if it has been modified, it is uploaded from client to server. In a remote access model, blocks are downloaded as needed from server to client and uploaded when modified from client to server.
Advantages of download/upload: (1) Easier to implement. (2) More efficient if the client is actually going to read the entire file. (3) The client can continue to read the file if the server or the network connection subsequently crashes.
Advantages of remote access: (1) More efficient if the client is only going to read a small fraction of the file. (2) Much easier to maintain reasonable consistency if several clients are simultaneously working on the same file.

Solutions to sample questions

 Solutions to sample questions

Short problems

Problem 1:

An OS uses the elevator algorithm to schedule the disk-arm. I/O requests are currently pending for blocks on tracks 1, 3, 8, 11, 15, and 16. The disk arm is currently at track 9 and moving upwards. In what order will these requests be handled? Answer: 11, 15, 16, 8, 3, 1

Problem 2:

An OS uses a paging system with 1Kbyte pages. A given process uses a virtual address space of 128K and is assigned 16K of physical memory. How many entries does its page table contain? Answer: 128

Problem 3:

Consider a file system that uses an FAT. The state of the directory is

 
File name | First block | Size in bytes 
---------------------------------------
  AA               5           1350
  BB               7           2200

(The other information in the directory is omitted.) The current state of the FAT is

 0  -- FREE
 1  -- FREE
 2 --  -1
 3 --   4
 4 --  -1
 5 --   2
 6 --  FREE
 7 --   3 
 8 --  FREE

The system uses a block size of 1 Kbyte. What is the last block of file BB? How many bytes of that block are used? (Useful fact: 1K=1024). Answer: The blocks of BB are 7, 3, 4. Since BB has length 2200 and blocks 7 and 3 hold 2048 bytes, there are 152 bytes used in block 4.

Problem 4:

A particular system uses a page size of 1K bytes. A page table for a particular process begins as follows: [ 3, 4, *, 1, *, 8 ...]

• A. What physical address corresponds to the virtual address of 50?
• B. Name a virtual address that will generate a page fault.

(Note: everything uses 0-based indexing.) Answer:
A. 3*1024+50 = 3122.
B. Any virtual address between 2048 and 3071 or between 4096 and 5119.

Problem 5:

Consider a Web browser and Web server that are communicating in HTTP layered over TCP layered over IP. For each of the following functionalities, state whether it is (i) implemented at the level of HTTP (ii) implemented at the level of TCP, (iii) implemented at the level of IP; (iv) carried out by the DNS; or (v) none of the above.

• A. Forwarding packets from one router to another. Answer: IP.
• B. Requesting retransmittal of a packet whose data is garbled. Answer: TCP.
• C. Maintaining a cache of web pages. Answer: HTTP.
• D. Assembling and disassembling a large file into packets. Answer: TCP.
• E. Translating URL's into IP addresses. Answer: DNS.
• F. Assembling the HTML file and the imbedded images into a display. Answer: none of the above (it's up to the browser.)

Long Problems

Problem 6

What is swapping? Why is it used in systems with variable-length partitions? Why is it used in systems with paging? Answer: In swapping, a process is entirely removed from main memory and its state is stored on disk. Swapping is used in an OS that uses variable-length partitions in the case there are active processes that are ready to run but do not fit into any free segment of main memory (either because the total memory requirements of the active processes is too large, or because space has been wasted in external fragmentation.)
In an OS that uses pages, swapping may be used when the sum of the working set sizes for the processes currently in memory is greater than the size of physical memory. When this happens, thrashing -- frequent page faults -- is almost inevitable, as the processes are competing for a resource (frames) that is inadequate to their combined needs. The only solution in such a case is to swap out (suspend) one or more of the processes.

Problem 7:

A user program has opened a file for reading and been reading sequentially through the program for some while. It now attempts to read the next byte, and finds that this byte belongs to a new block, and that this block is not in memory. Describe the major steps that are involved in the passage of control from the user program, which wants to read the byte, to the disk, which must carry out the read, and in the passage of information from the disk to the user program. In particular, your answer should discuss the operations of the device driver, the device-independent software, the actual disk, and the disk controller, in both directions. You may assume that the program is running on a single-process system. At any point, if there are different options for implementation, you can pick one to describe; you need not describe all the options. Answer: (Note: this is a lot more detail than I would expect on an exam answer. Also, the exact steps and the division of the steps among components of the system can vary a lot from one system to another.)
The device-independent software passes to the device driver the number of bytes to be read, the address in user space to read them into, and the file pointer. It then traps to the kernel. The kernel blocks the process and calls the device driver from the top. The device driver determines that the next byte is on a block B not in memory. It finds the address of B from the i-node (presumably in memory). It issues a request to the device controller to read B into memory. The device controller translate the block number of B into a set of consecutive sectors on a track, and instructs the actual disk to read those sectors. The disk moves the arm to the correct track, waits for the disk to rotate to the proper sectors, and reads the information, putting the output into the disk controller's buffer. The disk controller issues a interrupt. The interrupt handler in the kernel sends control to the bottom of the disk driver. The disk driver transfers the block of data from the disk contoller's buffer to the file cache, and transfers the byte of data to the specified address in user space. The kernel unblocks the process and schedules it to run. The device-independent software finds its data where it expects, and returns control to the user process.

Problem 8

On CD-ROM, each file occupies a physically contiguous section of memory.

• A. Name two advantages of this arrangement over the use of i-nodes.
• B. Name two reasons that this system is not used on hard disks.

Answer:

• A. First, it minimizes seek time. If a file is read sequentially (the usual case) then seek time is kept to an absolute minimum. Even if the file is read out of sequence, with contiguous storage, the blocks of the file are at least all in the same part of the disk whereas with non-contiguous storage they are (in general) scattered randomly around the disk. Second, it requires less space, because the i-node need not be kept. An i-node based system generally requires an extra block for the i-node; if there are a lot of small files, this is a substantial cost.
• B. Contiguous storage can only be used for files that are unchanging. If a file is expanded, then it will no longer fit into its place, and, at best, has to be copied in its entirety to some other part of the disk, leaving a large hole. If a file is deleted or reduced in size, then a hole opens up in memory. Unless this hole happens to be filled exactly, you end up with wasted space due to external fragmentation.

Problem 9

A. Explain in 1 or 2 sentences the difference between non-preemptive and preemptive scheduling.
Answer: In a non-preemptive scheduler, a process stops running only when it blocks; it never transitions from "running" to "ready". In a preemptive scheduler, the scheduler may preempt a running process and put it on the ready queue, B. Name one preemptive scheduling algorithm and one non-preemptive scheduling algorithm. (Just the names; you do not have to describe them.)
Answer: Of the scheduling algorithms we have discussed, shortest remaining time first, round robin, selfish round robin are preemptive; first come first served and shortest job first are non-preemptive.
C. Even if all jobs are CPU-bound, a preemptive scheduler may give a better average turnaround time than a non-preemptive scheduler. Give an example that illustrates this.
Answer: Suppose that process P, with one CPU burst of 100 sec, enters at time 0, and the process Q, with one CPU burst of 1 sec, enters at time 1. Then a non-preemptive scheduler will run first P from time 0-100 and then process Q from time 100-101 for an average turnaound time of 100. By contrast, assuming a small quantum and ignoring time lost to context switches, a preemptive scheduler will complete process Q at time 3 and process P at time 101, for an average turnaround time of 52.

Problem 10:

Consider a paging system that uses the "Not Recently Used" (NRU) page replacement algorithm.

• What is the significance of the "R bit" and the "M bit"?
• When are the R bit and M bit set and reset?
• How is a page chosen for replacement?

Answer: The R bit is 1 if the page has been referenced since the last clock tick. The M bit is 1 if the page has been modified since it was read in. At each machine instruction, the R bit for any page of any virtual address referenced is set to 1. The M bit is set to 1 if the process writes to that page. The R bit is reset to 0 at each clock tick. The M bit is reset to 0 when the page is written out to disk. In the NRU algorithm, pages are divided into 4 categories:

• 1. R=M=0.
• 2. R=0, M=1.
• 3. R=1, M=0.
• 4. R=M=1.

A page is chosen for replacement from the lowest of these categories. If there is more than one page in that categories, one is chosen at random.    

What is total charge in an atom?

The total or net charge of an atom is equal to: (the number of protons) - (the number of electrons).

The charge of a proton and electron are equal but opposite -- the proton is positive and the electron is negative. If protons and electrons are found in an atom in equal numbers, the net or total charge of the atom is 0 and thus, the atom is neutral. If there are more protons than electrons (positive charged) or if there are more electrons than protons(negative charged), then the atom is charged (and called an ion).

For example, an ion with 20 protons and 18 electrons has a charge of 20 - 18 = +2. This is the Ca⁺² ion.

a positive quark has a charge of 2/3, a negative quark has a charge of -1/3.
a proton has +1 positive, with 2 positive and 1 negative quark.

www.collegesubs.org Search engine is live!

http://www.collegesubs.org/ is now live. No adfly ads either!!!

Math 501–1, Spring 2006 University of Utah

Solutions to Problem Assignment #5
Math 501–1, Spring 2006
University of Utah
Problems:
1. A gambling book recommends the following “winnin strategy” for the game of roulette:
It recommends that the gambler bet $1 on red. If red appears (this has probability
18/38), then the gambler should take her $1 profit and quit. Else, she should make
additional $1 bets on red on each of the next two spins of the roulette wheel, and then
quit. Let X denote the gambler’s winnings when she quits.
(a) Find P{X > 0}.
Solution. Let Ri denote the event, “red on the ith trial.” Because P(Ri) = 18/38 and
P(Rc
i ) = 20/38,
P{X = 1} = P(R1) + P(Rc1
\ R2 \ R3) =
18
38
+

20
38 ·
18
38 ·
18
38

= 0.591¯7.
On the other hand,
P{X = −1} = P(Rc1
\ R2 \ Rc3
) + P(Rc1
\ Rc2\ R3)
=

20
38 ·
18
38 ·
20
38

+

20
38 ·
20
38 ·
18
38

0.2624,
P{X = −3} = P(Rc1
\ Rc2
\ Rc3
) =

20
38
3
0.1458.
In particular, P{X > 0} = P{X = 1} = 0.591¯7.
(b) Are you convinced that the strategy is indeed a “winning” strategy? Explain your
answer.
Solution. One may think at first that this is a winning strategy because P{win} > 0.5.
But it is the expectation that counts, and we will see next that EX < 0. This
means that the strategy is a losing strategy.
(c) Compute EX.
Solution. We have
EX = 0.591¯7 − 0.2624 − (3 × 0.1458) −0.108.
Therefore, every time we play we expect to lose about 10 cents.
2. One of the numbers 1 through 10 is chosen at random. You are to try and guess
the number chosen by asking questions with “yes-no” answers. Compute the expected
number of questions that you need to ask in each of the following two cases:
(a) Your ith question is to be, “Is it i?”, for i = 1, . . . , 10.
Solution. Let Q denote the number of questions asked. It follows that P{Q = i} = 1/10.
Therefore,
E(Q) =
1
10
+
2
10
+ · · · +
10
10
= 5.5
(b) With each question you try to eliminate one-half of the remaining numbers, as
nearly as possible.
Solution. Consider the following strategy: Divide what you have in halves and ask, “is it
greater than or equal to x?” where x is the middle of the numbers. For instance,
your first question is, “is it greater than or equal to 5.5?”. [All other strategies of
this type are similar. But you need to be consistent.] Let X denote the random
number, so that P{X = i} = 1/10 for i = 1, . . . , 10. If X = 1, 2, 3, 6, 7, 8, then
Q = 3. If X = 4, 5, 9, 10 then Q = 4 (check!). Therefore, P{Q = 3} = P{X =
1} + P{X = 2} + P{X = 3} + P{X = 6} + P{X = 7} + P{X = 8} = 0.6, and
P{Q = 4} = 0.4. Thus, E(Q) = (3 × 0.6) + (4 × 0.4) = 3.4.
3. A person tosses a fair coin until a tail appears for the first time. If “tail” appears
on the nth flip, then the person wins 2n dollars. Let X denote the person’s winnings.
Show that EX = 1. This is known as the “St.-Petersbourg paradox.”
Solution. For all n 1,
P{X = n} = P(H1 \ · · · \ Hn−1 \ Tn) =
1
2n .
Else, P{X = n} = 0. Therefore,
EX =
1X
n=1

2n ×
1
2n

= 1.
4. A box contains 5 red and 5 blue marbles. Two marbles are withdrawn randomly. If
they are the same color, then you win $1.10; if they are different colors, then you win
−$1.00 (i.e., you lose one dollar). Compute:
(a) the expected value of the amount you win;
Solution. Let Ri denote the event, “red on ith draw.” Then, P(R1 \ R2) = (5/10)(4/9)
and P(Rc1
\ Rc2
) = (5/10)(4/9). Let X denote the win, where X < 0 means loss.
Then, P{X = 1.10} = 2×(5/10)(4/9) = 4/9, and P{X = −1} = 5/9. Therefore,
EX = (1.1 × 4
9 ) − 5
9 = −0.0¯6.
(b) the variance of the amount you win.
Solution. Evidently, E[X2] = (1.1× 4
9 )+ 5
9 = 1.0¯4. Therefore, Var(X) = 1.0¯4 −(−0.0¯6)2 =
1.04.
Theoretical Problems:
1. Let X be such that P{X = 1} = p and P{X = −1} = 1 − p. Find a constant c 6= 1
such that E[cX] = 1.
Solution. First, for all real c,
E[cX] = cp + c−1(1 − p).
Set this equal to one to find that cp + (1 − p)/c = 1. I.e., pc2 − c + (1 − p) = 0.
This is a quadratic equation (in c) and has two roots:
c =
1 ±
p
1 − 4p(1 − p)
2p
.
But 1 − 4p(1 − p) = 1 − 4p + 4p2 = (1 − 2p)2. Therefore,
c =
1 ± (1 − 2p)
2p
= 1 and
1 − p
p
.
So the answer is c = (1 − p)/p.
2. Prove that if X is a Poisson random variable with parameter , then for all n 1,
E[Xn] = E[(X + 1)n−1]. (1)
Use this to compute EX, E[X2], VarX, and E[X3].
Solution. We calculate directly:
E[Xn] =
1X
k=0
knP{X = k}
=
1X
k=0
kn e− k
k!
=
1X
k=1
kn e− k
k!
=
1X
k=1
kn−1 e− k−1
(k − 1)!
=
1X
j=0
(j + 1)n−1 e− j
j!
= E[(X + 1)n−1].
Therefore,
EX = E[(1 + X)0] = ,
E[X2] = E[(1 + X)] = (1 + ) = + 2,
VarX = E[X2] − (EX)2 = ,
E[X3] = E[(1 + X)2] =

E

1 + 2X + X2
=

1 + 2 + + 2
= + 3 2 + 3.

Download pdf

Math 678. Homework 3 Solutions.

Math 678. Homework 3 Solutions.
http://math.gmu.edu/~memelian/teaching/Fall11/math678/hw/hw3sol.pdf
#1
We need to derive the formula for the solution of the IVP
ut 􀀀 u + cu = f: in Rn (0;1)
u = g; on Rn ft = 0g
Some observations: (1) the solution to the non-homogeneous problem can be
obtained from the solution to the homogeneous problem via Duhamel's principle;
(2) if the term cu is not present, we know the exact solution to this IVP, (3)
ut + cu = 0 is equivalent to ectut + cectu = 0 which converts to (ectu)t = 0 and
leads to u = Ce􀀀ct as a solution (should remind you of an integrating factor
technique).
From the above observations, we see that a good way to proceed is to mul-
tiply both sides by the function ect. This gives us:
ectut + cectu 􀀀 ect u = ectf
Since (ectu) = ect u, the above can be written as
(ectu)t 􀀀 (ectu) = ectf
and hence this converts into a regular heat equation formulation in terms of ectu,
with non-homogeneous right hand side. The initial condition is unchanged, since
(ectu)(x; 0) = u(x; 0) = g(x). So now we can use Duhamel's principle and write
the exact solution for this modi ed IVP as:
ectu(x; t) =
Z
Rn
(x 􀀀 y; t)g(y)dy +
Z t
0
Z
Rn
(x 􀀀 y; t 􀀀 s)ecsf(y; s)dyds
The solution to the original IVP then follows:
u(x; t) = e􀀀ct
h Z
Rn
(x 􀀀 y; t)g(y)dy +
Z t
0
Z
Rn
(x 􀀀 y; t 􀀀 s)ecsf(y; s)dyds
i
#2
Now let us consider the usual heat equation ut = uxx in 1d with u(x; t) being a
solution.
(a) Take v(x; t) = u(x􀀀y; t). How does one show this is also a solution? The
easiest way is to plug it into the equation. First we need to use chain rule and
compute partial derivatives: vt = (u(x􀀀y; t))t = ut(x􀀀y; t), vx = ux(x􀀀y; t),
relying on the fact that (x 􀀀 y)x = 1. Since ut(x; t) = uxx(x; t) for any x 2 R,
we have vt = vxx. Notice that if we had an IVP originally with u(x; 0) = g(x),
the initial condition for v would be hy(x) = g(x 􀀀 y), and the formula for the
solution using fundamental function (x; t) would give us:
u(x 􀀀 y; t) =
Z
R
(x 􀀀 y 􀀀 s; t)hy(s)ds
1
where s0 = y + s
(b) For any derivative D , where is a multiindex, and the derivative is
taken either in t or in x, we have (D u)t = D ut = D uxx = (D u)xx since
derivatives commute. it follows that any derivative of the solution of the heat
equation is again a solution.
(c) (au + bv)t = aut + bvt = auxx + bvxx = (au + bv)xx, hence au + bv is
again a solution, if u; v are solutions.
(d) This follows from the fact that the operations of integration and di er-
entiation are commutative:
@
@t
Z x
0
u(y; t)dy

=
Z x
0
ut(y; t)dy =
Z x
0
uxx(y; t)dy = @2
@x2
Z x
0
u(y; t)dy

(e) Let v(x; t) = u(
p
ax; at). Then vt(x; t) = av(x; t); vx(x; t) =
p
av(x; t); vxx =
av(x; t). It follows that vt = vxx.
#3
The easiest example of a Dirichlet problem with no solution can be constructed
as follows. Let UT = U (0; T) and = U
T 􀀀 UT be the boundary of this
cylinder including the top, bottom and the sides, while denoting 􀀀T to be the
parabolic boundary comprised of the bottom and vertical sides only. Consider
ut 􀀀 u = 0; in UT
u = f; on
Suppose u 2 C2
1 (UT ) \ C( U
T ) solves this IVP. Then it should satisfy the
weak maximum principle, namely
max
U
T
u(x; t) = max
􀀀T
u(x; t)
Since u(x; t) = f(x) on 􀀀T , we need the solution to satisfy max
U
T
u = max
􀀀T
f.
In particular, f(x; t = T) < max
􀀀T
f, which does not hold for all continuous
functions.
If we allow t = T to be part of the cylinder UT = U (0; T], we need to
construct a more elaborate example of a Dirichlet problem with no solution.
One such example is a ball in R3 with deformable surface. We can push in a
sharp spike at some point on this surface and assume that near the tip of the
spike the surface takes the form of a conical surface obtained by rotating the
curve
y =

e􀀀1=x: for x > 0
0: for x = 0
about the x-axis. Then we can consider heat conduction on the interior of the
deformed ball de ned this way, called
. If the temperature distribution on @

is given by a continuous function f which is equal to zero at points of the spike
2
and is equal to a large positive constant temperature T at points away from the
spike, the seady state temperature u(x) should be close to T for all x in
. But
this is impossible, since u(x) won't be able to approach the zero temperature
as x approaches the spike from within of
. Basically, the spike doe not have
enough surface area to keep the temperature at surrounding points close to zero,
hence the solution fails to be continuous in the closure
. More details about
the subject are available in Helms "Introduction to potential theory" (1975).
#4
Consider v(x; t) = k(x; t)u(x=t;􀀀1=t); t > 0. To see that this solved the heat
equation, let us compute its partial derivatives, using chain rule and product
rule:
vt(x; t) = kt(x; t)u(x
t
;􀀀
1
t
) + k(x; t)(
1
t2 )ut(x
t
;􀀀
1
t
) 􀀀 k(x; t)( x
t2 )ux(x
t
;􀀀
1
t
)
vx(x; t) = kx(x; t)u(x
t
;􀀀
1
t
) + k(x; t)(
1
t
)ux(x
t
;􀀀
1
t
)
vxx(x; t) = kxx(x; t)u(x
t
;􀀀
1
t
) + 2kx(x; t)(
1
t
)ux(x
t
;􀀀
1
t
) + k(x; t)(
1
t2 )uxx(x
t
;􀀀
1
t
)
Now using the fact that kt = kxx; ut = uxx, we can simplify this to
vt 􀀀 vxx = 􀀀
1
t
xk(x; t)
t
+ 2kx(x; t))

ux(x
t
;􀀀
1
t
)
Using the de nition of k(x; t), we can easily see that kx(x; t) = 􀀀(x=2t)k(x; t),
so that xk(x; t) + 2tkx(x; t) = 0. This con rms the claim that v(x; t) solves
the heat equation. Since u(x; t) was de ned for all t < 0, s = 􀀀1=t covers the
domain (0;1). In other words, v(x; t) is a solution for all t > 0.
3

IASTATE Math 266 Exams Solutions

Example:

Exams 1, 2 , 3

Download:
http://www.mediafire.com/?9as3igcjm7idxff

Acct 387 Q1A-IC (Chap. 15 -16)

Acct 387                                           Q1A-IC (Chap. 15 -16)     

Part I. Multiple Choice (Circle the Best Answer) 2 points each

1. Presented below is information related to Getty Corporation:

     Subscriptions Receivable, Common Stock                                $   120,000

     Common Stock, $1 par                                                                     3,600,000

     Common Stock Subscribed                                                                240,000

     Paid-in Capital in Excess of Par—Common Stock                         210,000

     Preferred 8 1/2% Stock, $50 par                                                     1,200,000

     Paid-in Capital in Excess of Par—Preferred Stock                        240,000

     Retained Earnings                                                                               900,000

     Treasury Common Stock (at cost)                                                        90,000

The total stockholders' equity of Getty Corporation is (Note: Assume Subscriptions receivable is treated as contr-equity)

    

     a. $6,180,000.      b. $6,270,000.           c. $6,300,000.           d. $6,390,000.

2. When a corporation issues shares of its own stock in payment for services, the least appropriate basis for recording this transaction would be

a. the fair market  value of the services received

b. the par or stated value of the shares issued.

c. the fair market value of the shares issued

d. All of the above are equally appropriate basis for recording the transaction

3. Nelsen Co. was organized on January 2, 2001, with 100,000 authorized shares of $10 par value common stock.  During 2001 Nelsen had the following capital transactions:

                  January 5—issued 75,000 shares at $14 per share.

                  July 27—purchased 5,000 shares at $11 per share.

                  November 25—sold 4,000 shares of treasury stock at $13 per share.

Nelsen used the cost method to record the purchase of the treasury shares. What would be the balance in the Paid-in Capital from Treasury Stock account at December 31, 2001?

a.  $0.                     b.  $4,000.                  c.  $8,000.                 d.  $12,000.

4. An entry is not made on the

           

a.   date of declaration.

b.   date of record.

c.   date of payment.

d.   An entry is made on all of these dates.

-Continued on Back Side-

5. A retained earnings appropriation always means the company is

    a. setting aside cash for a specific purpose.

   b. disclosing managerial policy.

    c. preventing unusual losses.

    d. improving the debt-equity ratio.

6. Stine Co. had outstanding 2,000 shares of $100 par value 8% cumulative preferred stock and 30,000 shares of $5 par value common stock on December 31, 1998.  At December 31, 1998, dividends in arrears on the preferred stock were $20,000.  Cash dividends declared in 1999 totaled $60,000.  The amounts paid to each class of stock were

                                              Preferred Stock        Common Stock

a.                                                $16,000                      $44,000

b.                                                $20,000                      $40,000

c.                                                $36,000                      $24,000

d.                                                $40,000                      $20,000

Part II. Fill in the blank  (1/2 point each)

Indicate the effect of each of the following transactions on total stockholders' equity by placing an "X" in the appropriate column.

                                      Increase  Decrease   No Effect

1. The sale of treasury stock for

less than its cost.                ___X___    _______    _______

2. Not declaring this year's dividend

On cumulative preferred stock      _______    _______    ___X___

3. Declaration of a stock dividend.   _______    _______    ___X___

4. Payment of a stock dividend.       _______    _______    ___X___

5. Acquiring land by issuing

common stock                       ___X___    _______    _______

6. Declaration of cash dividend.      _______    ___X___    _______ 

7. Payment of cash dividend.          _______    _______    ___X___

8. Conversion of bonds payable

into preferred stock               ___X___    _______    _______