Test 2 Review Sheet

CSCI 480 Autumn, 2018

Test 2 Review Sheet

Note: These are just key points. Please read the related sections in

the textbook to get a full understanding of the topics that were

discussed during lecture.

We have been looking at material from assignments 3, 4 and 5 and chapters 8 to 12 in the textbook. We have not by any means covered all of the material in those chapters.

The test includes a few true-false questions, some short answers and

some (longer) written answers.

There is one coding question which is related to Assignment 3, the microshell.

You will probably need a calculator when you take the test.

------

Main Memory

The concept of a logical address space which is mapped to a separate physical address space is central to proper memory management.

An essential task is not to lose track of any memory (as in "memory

leak").

In contiguous allocation, methods of dynamic allocation include first fit, best fit and worst fit. The first two strategies are generally faster and utilize storage better.

Paging: Allows a program to occupy non-contiguous locations in physical memory, that appear logically contiguous. Requires hardware address translation.

Scheme of paging: an address consists of a page number and a page

offset. The page number is used to index into a page table where

the physical page address is found, then added to the page offset to

produce the real physical address.

If given a logical address, how to translate to the corresponding

physical address (page table contents will be provided)?

Drawback of paging: internal fragmentation can result if page

frames are large, since last page of every process is probably

partially empty.

Paging is sped up by use of an associative TLB.

How to calculate effective access time of paging using TLB?

Segmentation: partition of the user's view of memory into a segment

for each purpose, e.g, subroutine, stack, heap, etc. Hence a logical

address is segment number + offset.

------

Virtual Memory

Demand paging is the most common virtual memory system.

Demand paging achieves a virtual memory that is larger than physical

memory. It requires some hardware, and needs to check for presence

of page before making reference. When a page fault occurs, the state

of the faulting process has to be saved for restarting.

Page Allocation Problem: how to divide N available frames among

K processes.

Page Replacement Algorithms:

--- FIFO: easy, but constantly used pages periodically get flushed

anyway

--- Optimal (but impractical): replace the page which won't be

needed for the longest time

--- Least Recently Used

--- Global vs. Local replacement: whether a frame is selected from

those in use by all processes, or only by the faulting process.

Thrashing: Cause/Examples/Prevention.

Prepaging: we might want to bring a set of pages into memory when a

process starts up, rather than let it fault in: fewer I/O operations.

Page size selection:

--- Factors favoring small pages: less internal fragmentation, less

I/O per fault

--- Factors favoring large pages: smaller table size, less overall

I/O time, fewer faults

--- Other factors may affect paging performance: e.g., program

structure.

Hard Disks and File Systems

Hard Disk vocabulary: We have platters, tracks, cylinders, sectors,

clusters, read/write heads, etc.

Hard disk speed: average seek time, track-to-next-track movement time, data transfer rate, rotational latency, etc.

Access: sequential access and direct access. Direct access is generally harder to support, requiring pre-allocation of a contiguous area, or some method of making the file appear logically like an array of records.

Allocation: File management is storage management of a very large space, with timing considerations. Going for a disk block is much more expensive than reading core memory, so try to minimize the disk operationsnecessary to fetch or write the desired location.

Contiguous Allocation: each file resides in a set of contiguous locations on disk. (Nice if we can manage it, not always possible.)

Linked Allocation: basically, a linked list of data blocks.

Tabular Allocation: we have a file allocation table (FAT). The

number of bits used to number the clusters is an essential parameter.

Indexed Allocation: one or more index blocks contain pointers to data blocks and perhaps to more index blocks

What are the advantages and disadvantage of the above allocation methods? E.g.: For Indexed Allocation, the advantage is that it allows effective storage use and direct access. Disadvantages are that it requires most pointer space overhead and requires more indirection than contiguous allocation, especially for large files.

Disk Scheduling: We want to minimize the total seek time required to

fulfill I/O requests involving various tracks on disk.

Disk scheduling algorithms:

--- First-Come-First-Serve (a queue, easy to code, may not be fast)

--- Shortest-Seek-Time-First (the next request to fulfill is the one

requiring the least read/write head movement from the current

location; some requests may wait a long time)

--- SCAN (move from one end to the other and back, doing all requests

along the way)

--- LOOK (similar to SCAN but does not go all the way to the end if

there are no more requests needed in that direction)

--- C-SCAN (move from one end to the other, doing all requests along

the way, return at once to the beginning and start over)

--- C-LOOK (combines LOOK and C-SCAN)

File organization:

We have directories and we may have sub-directories. A directory

entry contains various kinds of data. With indexed allocation, some

of this data may be in the index block instead.

------

A few practice problems

1. Suppose we are using virtual memory. Here is part of the page

table:

Page Frame

0 3

1 5

2 2

Assume the page size is 2 KB = 2048 bytes. For each of these

logical addresses,find the page number, the offset and the

physical address.

Logical address = 3319

Logical address = 2642

2. Suppose we are managing memory with segments. Here is part of

the segment table:

Segment Base Length

0 2060 458

1 2518 96

2 1200 860

3 800 400

For each of these logical addresses, determine whether the

addressis valid, and if it is valid, find the physical address.

Logical address = 2,392

Logical address = 0,524

Logical address = 1,34

3. If you use FAT-8 as your file system, how large is the File

Allocation Table (in bytes)? If the disk is 80 MB in size,

how large is each cluster?

4. Suppose we are using virtual memory. A process is made up of

6 pages (0 to 5) and is allowed to use 3 frames (0 to 2).

Suppose it wants to use its pages in this order:

0 4 1 0 3 2 1 2

(a) Using the First-in-First-Out algorithm, fill out this

chart to show which pages are in which frames at each point.

Also indicate whether a page fault occurred. When we start,

all frames are empty.

Page Used Frame 0 Frame 1 Frame 2 Page Fault?

(b) Now redo it with the Least-Recently-Used algorithm.

Page Used Frame 0 Frame 1 Frame 2 Page Fault?

5. Suppose your C++ program contains these (consecutive) lines:

int * P = new int[200];

P = new int[250];

What problem do we have here?

6. What is "thrashing"?

7. Suppose we are managing virtual memory. We presently have

72 frames available and 7 processes. What are several

different approaches to allocating frames?

8. A directory entry or an index node may contain various

kinds of information about a file. Name four such kinds of

information.

9. In your C++ code, what is likely to cause a page fault?

10.Suppose I want to store files in contiguous space if at all

possible, even if it is slow. What would be a good strategy?

11.A problem of some file systems is that it is hard to undelete a

file. Suppose we are designing our file system and we want to

guarantee that a user can recover a file up to 1 full day after

deleting it. (Users can be so silly!) After 1 day, the file

should disappear. You may assume all the files involved are

fairly small. What would be a way to manage this?

12. Suppose we are scheduling the operation of a hard disk. At the

moment, there are 4 processes requesting Read operations. These

involve tracks 31, 6, 42, 18. Assume the disk has 50 tracks (0

to 49) and that the time to move track-to-next-track is 0.6

millisecond. The Read/Write heads are presently at track 36 and

has recently been at track 35.

For each of these algorithms, what is the order in which we will

access the tracks, and how much total time will we spend moving

the Read/Write heads?

(a) First-Come-First-Served

(b) LOOK

13. What is the Translation Look-Aside Buffer? Where is it found?

14. What is the Page Table? Where is it found?

15. At one time, it was common to partition all of memory into

some number of fixed-size parts and run one process in each.

What would be a disadvantage of this method?

16. What are the most important duties of the Memory Management Unit?

17. A directory entry may contain “metadata” about a file. What

would be an example of metadata?

18. Suppose a hard disk has a data transfer rate of 150 million bits

per second and a seek time of 18 milliseconds. We want to

rewrite all of an existing file which is 27.0 million bytes long.

It is stored on 18 consecutive tracks. The time to move track-

to-next-track is 0.6 millisecond. How long will it take to

rewrite this file?

19. Where is each of these structures stored?

(a) the TLB

(b) the page table

20. Suppose I have a hard disk of 50 GB and a cluster size of 4096

bytes.

(a) How many clusters do I have?

(b) If I use a bit table to keep track of whether clusters

are free or in use, how large is the bit table (in bytes)?

21. How can we add output redirection to our microshell (as in

Assignment 3)? Assume we have:

prompt> OurProgram *> outfile.txt

where we are using "*>" as our symbol for output redirection.

What code do we need? Think in terms of fork, dup, execv, etc.