cs341 Lecture Notes
Spring 2002
Week 8, Thursday

For today you should have:

1) finished the semaphore problem

2) finished homework 5

3) made a high-level pass through chapter 13


For next time you should:

1) start homework 6

2) read Chapter 13 and answer the preparation questions below

3) read the solution of the last semaphore problem and
   start thinking about the next one


Topics for today:

1) multi-level page tables (continued)

2) homework 5 debriefing

3) homework 6 introduction

4) the producers-consumers problem


Multi-level page tables
-----------------------

64-bit address:

1) 14 bits of offset

2) 12 bits of page address

3) 12 bits of book (outer-level page) address

4) 12 bits of next level

5) 12 bits of next level

6) 2 bits last level

How big is a page?


How many pages per book?


How many books?


How big is an inner page table?
Assume that each entry in the table is 4 bytes.



How big is the outer page table?
Again, assume that each entry in the table is 4 bytes.


Roughly how big is the total space for the page table
of a process that is using 1 MB of memory?



Reading notes and preparation questions for Chapter 13
------------------------------------------------------

What is the fundamental abstration provided by the file system?






What are the basic file operations?






The model of a program as a filter is a fundamental idea in
UNIX, although it is a little dated, for reasons we will discuss.


What is stream-block translation?




What is record-stream translation?




What is the difference between a low-level file system and
a structured file-system?




Stream model: sequence of bytes plus and index that records
       file position.

Block model: ordered set of blocks containing contiguous chunks
      of data


API for the stream model:

1) open
2) close
3) read
4) write
5) seek


Open creates a file descriptor, which is an object in the
OS that records

1) the fact that this process is reading this file

2) the file position for this process in this file

3) possibly buffered data, for example, a block that
   has been read from disk but only partially read by
   the application

These file descriptors are not the same thing as an inode,
which is an object on disk that records meta-information
about the file like:

1) name
2) state
3) owner
4) permissions
5) locks
6) accounting information (length, access times, etc)

etc.


Section 13.1.2 Structured Files

What are:

1) record-oriented files




2) indexed files




3) inverted files



Section 13.2 Low level implementation

Open

1) find the inode for this file

2) check permissions (can this process access this file?) 

3) create a file descriptor (and allocate buffers)


Close

1) flush pending operations

2) deallocate the file descriptor


Section 13.2.2

Name one advantage and one disadvantage of the following
block management schemes

1) contiguous allocation




2) linked allocation




3) indexed allocation




Name one advantage and one disadvantage of the following
block allocation schemes

1) free list




2) block status map