Q4 of the "2017" Paper

I'll try stepping this out. Please criticise! (Now is not a good time for polite unanimity).

0010 0011 0064 0099 0043 0170 0089 0111 0133 0049 0239 0150

12 of them so far.

We only use page numbers, not the entire (decimal, here) memory reference. With a page size of 50 anything up to 0050 is on Page-0

I think I'll try to get those first.

0 0 0064 0099 0 0170 0089 0111 0133 0 0239 0150

Then 50 - 99 is on Page-1

0 0 1 1 0 0170 1 0111 0133 0 0239 0150

100 - 149 = Page-2

0 0 1 1 0 0170 1 2 2 0 0239 0150

Page-3

0 0 1 1 0 3 1 2 2 0 0239 3

And then that 239 is on Page-5.

So the end of the first part of the Reduced String calc gives:

0 0 1 1 0 3 1 2 2 0 5 3

(Every address is now just a page number)

The next part is to take advantage of the fact that if page p comes straight after page p, it's not going to fault. (You know for sure it's already in M).

So the string finally reduces to 0 1 0 3 1 2 0 5 3

Now the question I'm left with is Do we calculate fault rate according to the total number of references we had to begin with? (Doesn't really match the description that follows on page 373, but it makes some kind of sense? Or not?)

Fault rate formula is simple enough FAULTS/LEN (of string) (or FAULT/NRWORDS?)

It's just this last little bit I have any strong doubts about.

==== EDIT ====
I've caught my own first error. To have 50 words on Page-0, Page-1 must start at address 51. So the page boundaries fall on nice round numbers. 0 -50 , 51 - 100, and so on...

Of course that's going to move some of those words to different pages, so the strings are all wrong from then on.

Another thing that I'm doubting here is : Do we start from Page-0? Or do we count from 1, in the natural manner?

Page 0, as specified in TL 102.
Look at example given.

Hi, this is my attempt to Q4:

Memory Address. Page Number
0-49. 0
50-99. 1
100-149. 2
Keep this going till
400-449. 9

Unreduced reference string: (get from table)
0. 0. 1. 1. 0. 3. 1. 2. 2. 0. 4. 3

Reduced reference string:
0. 1. 0. 3. 1. 2. 0. 4. 3.

And well the page faults part is straight forward.

The question I don't like and also don't know the answer to, is the one on the semaphor

Thanks!

OK my error wasn't an error then. First address is 0, so last is 49 (in any block).

TL 102 was on the back burner. I assumed it to be answers to the assignment I did OK in! Phew!

Ew! Yes, I haven't been brave enough to tackle the double semaphore yet. I suppose you treat it as a mapping/ function ... I don't know. Maybe some kind of matrix solution?

====Edit====

OK. Page Fault Rate is calculated ITO the Reduced String.

FAULTS/ LEN (where that's the reduced length). Yes, simple. "Do not divide by 12", in this case.

>TL 102 was on the back burner.

Make sure you go through the TLs 201 and 202 as well.
Important points have been added about the exam.

Checked, but for me those assignments are already "OK". What happened was I got 201 and 102 somehow muddled. Just saw "Ass2" and not something extra. The "something extra" has been quite a help.

How about the "double semaphores"? We have two condition variables, somehow...

Sorry was busy writing under "exam conditions."
You're going to kick yourself its so simple:

Wait(S,R):
while(S<=0 or R<= 0); //do no-op
S--;
R--;

Signal(S,R):
S++;
R++;

Questions:

1.What values did you get for the pf rates?
Both of mine are 7/9.

2.Was your values for SJF = 32/5 and Non-preemption = 35/5?

3.What was your safety sequence?

4.For question 3.4 do they expect us to determine if the request leaves the system in a safe state again? for 4 marks?

Am not yet out of the starting blocks. Was largely just recalling the "outstandings" of this thread, and Tazz had mentioned this problem.

You're right about the kicking myself, though.

OK. I must now try and do my fair share here, eh? I shall get to it, now I have the start needed, and see if that takes me anywhere near the unsolved mysteries still to come.

==== I'll just edit them in as they slowly arrive.... ===

2. Same result as you.

Ok, both my page fault rates were 7/9 and I even got the same answer as you for SJF and non preemptive priority.

My safe sequence was <P1, P3, P0, P2, P4> and I did think that for 3.4 they wanted us to check if the system is in a safe state.

@Tazz please remove the brackets around your safety sequence, otherwise it won't be displayed.
My sequence was P1, P3, P0, P2, P4

> I did think that for 3.4 they wanted us to check if the system is in a safe state.
I would have then done this last as its only worth 4 marks and it takes a long time to do this.

Oops sorry Ben, I did get the same safe sequence . Thanks for the input with the Semaphor question, I don't think I would have figured it tonite!

The file control block question I got
Cont: 50reads + 1 write of new block + 50writes =101
Linked: 52= 50 reads + 1 write of new block + 1 change of block 50's pointer
Indexed: 1

You're welcome.
Cool got the same for file control block question.

Safety sequence the same here. Work had the value (17,8,4) at the end FWIW.

=====

I get a "yes" for 3.4, which doesn't match the marks.

0 < 7 , 2 < 4 , 0 < 3

So the request does not exceed maximum claim (Need).

0 < 2 , 2 < 3, 0 = 0

Request does not exceed what's Available.

So that means we go to the final step, which is to apply the Banker's Safety Algorithm to see if there's a safe sequence ... in an ideal world. In the real world, if that's really what's required, it's probably safer to abandon the 2 marks it's now worth, and go on to something else.

Have I got the two tests of the Request Algo wrong?

slow_eddy Wrote:
-------------------------------------------------------
> Safety sequence the same here. Work had the value
> (17,8,4) at the end FWIW.

I had 10,5,7 for work at the end.
And what's FWIW stand for?

Eddy, were u refering to question 3.1 cos my work had the value of 10, 5, 7 same as my maximum resource vector

Sorry Eddy I meant 3.2 for the work value

For What it's Worth...

2 votes say that although I also lucked out and got the correct answer, I'd better sharpen my pencil, and go and examine my calcs. You are adding Alloc_i, right?

Um.. 3.2 .. Safety sequence.
And then in both 3.3 and 3.4 you go on to test requests made, given that safe state the system is found to be in after working through 3.2.

3.3 is a case of Max Claim Exceeded Error.

I was expecting 3.4 to be a case of "Not Yet Available, so Wait"
but it turns out to not to be so. (If I'm doing it right, that is).

Let me pare down what I did to Work.

(2,3,0)
+(3,0,2) -- adding the allocation of P1.
=(5,3,2)
+(2,1,1) -- adding alloc 3.
= (7,4,3)
+ (0,1,0) --- adding alloc 0.
= (7,5,3)
+(3,0,2)-- alloc 2
=(10, 5, 5)
+(0,0,2)-- alloc 4
=(10,5,7)

I lost it on the last two. Went to (13,5,3) somehow. And then went inexplicably ballistic.

Re: Thrashing essay

How system deals with it:
1. give a process enough frames
2. use a local replacement algorithm

Or should we mention
Model set mode and
Page fault frequency?

pages 386 - 390

As far as Page Faults go, I get the same denominator, at least. The scurvy little bits of paper I've been working on seem to have vanished, so I still can't find my numerators for the pf.

Maybe I'll just do it over.


0. 1. 0. 3. 1. 2. 0. 4. 3.
0. 0. _. 0. _. 2. 2. 2. 2.
0. 1. _. 1. _. 1. 1. 1. 3.
0. 0. _. 3. _. 3. 0. 4. 4

So that would be 7/9 for LRU

Messed this up, and had ideas about leaving it as is for the sake of revealing the correction. Unfortunately I messed that up, too, so we just have my version of LRU-corrected to make use of now.

Wrong answers are often far more revealing than right ones. Pity I messed up my mess.

As far as File disk space allocation goes(gibberish edited out), I was working on the question they have on that in the S2 assignment. They cover more ground, get more complicated, but I figured if I've waded through that I'll manage just part (a) fine. Can't recall having gotten really far before they rang the dinner bell.

We're doing Insert, right? And we're accessing that file at block level, rather than putting the whole thing in M. (So we're using Virtual Memory ... FWIW).

Block for block, the rest of the file has to be shifted right, and the new block then inserted in the middle?

I get:
Contiguous.
Read last block (one op because it's contiguous)
Write last 50 blocks (one space ahead)
Write the block to insert.

Total 52.
<< correction. Each "write" is an "r w", so we get 102>>
<< corrected correction. That first read is the first part of the first r-w pair , so 101. Consensus!!>>

Linked.
Write the insert block somewhere. Keep address in M, so no need for IO for that.
Seek to block 50. That's 50 reads.
Write to FCB for block 50 (??? = better do some revision here), editing pointer to point at the new address. Write to FCB for new block to point to block 51.

Until corrected, then, that's 53. (w + 50 + w + w).

I'd better go track the mistake. Think I'll be lazy and start with the answer kindly supplied by Tazz.

<< OK. The new block starts off in M, so everything we do to it is IO free (apart from writing it somewhere).
And this "FCB" talk is pure gibberish. The pointer is "in the block" ... somewhere.

So before writing the block to a free space, seek to Block 50. Load Block 50 into M.
Now write the new block to free space after setting its pointer (while in M) to point to block 51.
In M, Block 50's pointer gets updated to point to the address of the new block, we write it back to its old space, and we're done.

So that's 50 + r + w + w = 53 ... OK my self-correction is not working so well here, so I'll leave that as is and see if the next one doesn't help. >>

<< I think my problem is with that FCB. It's already in M, so does not have to be fetched. ... Ah! It is an inode. So obviously the OS has an FCB in M at all times for each filesystem object. There's no read to account for. And whether one accounts for the write ... ? Probably not. So 50 + w = 51? But then what about this story of the pointer being "in the block"?>>

LAST EDIT, I promise! (Sorry about this). Double checked and it's definitely so that the pointers are scattered about the blocks. The "FCB" in this case simply has a pointer to "First" and a pointer to "Last", so it's not of any use in saving reads and writes in this particular case. Only the OS can see the internal pointers, but I can't see how it would see them without loading the required block (like Block 50 in our case). So we need an r + w for the pointer. I have a horrible feeling my original answer is right. (Not because I hate being right, just because I hate having to write lots in an exam).

===
In the Indexed case, the Index Block is already in M, so that is simply updated to change the pointers, and the block to insert is written to disk. Number of IO operations = 1. So at least we agree there, too. Sort of. One could get nitpicketty and say that the job's not done until the updated Index Block is written to disk, so that actually (even if it takes a while) we have 2 writes here.
====
OK so I lied about that "last edit" thing. It gets more complicated. How do you know where the middle of a linked list is? ...

Look, I think I'm going to pretend not to have considered that if the question arises... For 3 marks, one does not go counting the list, modulo dividing by 2, counting to this new number ... etc. I'm pretty sure that's pure "Data Structures" stuff, never intended to be part of this exam.

Thrashing = more time paging than exe.

Cause = not enough frames, basically. Combined with global page replacement.

Last-straw process arrives, faults, is given pages that other processes need to finish their jobs.

So now those fault. Because there's global replacement, they are handed the necessary pages of yet other processes. Which fault.

Beyond a certain point all any process is doing is grabbing the frames its neighbours need, while its neighbours rob it in turn. This means there's not much processing going on in the CPU. The processes are too busy robbing each other to get on with doing an honest days' work ...

OK, and if I push that too far it'll turn into an Allegory or some such thing...

The level of processing goes down, so the Scheduler steps in to "fix" this. It brings in new jobs from the queue, and things get even worse.

The short version of the cure would be either "Monitor the working set of each process" (p389, just up from half way); or monitor page fault frequency. p390.

The details of the working set can wait ...

@slow_eddy
@Tazz

Thanks for all you help / input.
You really have made this thread come alive.

By working through this 'past' exam paper and knowing that my answers are right, makes me feel a whole lot better for tomorrow.
Now I just need to get a good night's rest and hope for the best.

Good Luck you two!

Regards
Benjamin

And the same to you two. Good luck! Thanks for all the help.

Hey goodluck to you too guys. I always hit the sack early the night before exams so I was out by 10pm.