Transcript SSW01 - Admin

Overview

Assignment 11: hints
 File

systems
Assignment 10: solution
 Deadlocks
& Scheduling
1
UNIX Filesystem

References:
 M.
Bach, The Design of the UNIX Operating System,
Prentice Hall
 http://lxr.linpro.no/

Each file has a unique inode containing:
 ownership
 type
 access
rights
 size
 access/creation/…
time
 location of the data on disk
2
Disk Layout

A disk contains:
 boot
block: bootstrap code
 super block: state of the file system
 inode list: list of file descriptors
 data blocks
boot
block
super
block
inode list
data blocks
3
Inode: Example
owner: corti
group: inf
type: regular file
permissions: rwxr-xr-x
accessed: Jan 08 2004 1:45 P.M.
modified: Jan 08 2004 10:30 A.M.
inode: Jan 08 2004 1:45 P.M.
disk addresses
4
File Structure
data
blocks
inode
direct 0
direct 1
direct 2
direct 3
direct 4
direct 5
direct 6
direct 7
direct …
direct 11
single indirect
double indirect
triple indirect
5
Directories
A directory is a normal file with a list of
names and inodes.
Inode Number File Name
 Example:

83
.
2
..
1798
init
1276
fsck
85
clri
1268
motd
1799
mount
6
Processes, File Table, …
user file descriptor
file table
inode table
0 stdin
1 stdout
count 3 (/a/b)
2 stderr
3
4
count 1, rd
count 1 (local)
… …
count 1, rd-wr
0 stdin
1 stdout
count 1, rd
count 1 (private)
2 stderr
3
count 1, wr
4
… …
count 1, rd
7
Mounting
iso9660
/pictures
ext2
fat
/etc
/mnt
/cdrom
/dos
/home
/proc
/usr
/var
\dos
\windows
ext2
/user1
/user2
/user3
procfs
/meminfo
/cpu
8
A11 Ex1 – File size

Calculate the maximum size of a UNIX file
on a disk with 2KB data blocks
9
A11 Ex2 – File access

Append one byte at the end of a file
Filename ./a/b/c/f
 Size 1G


Which sequence of disk accesses is
necessary (worst case, no caching)
10
A11 Ex3 – Redirection

Used for output  input redirects
 ./cmd
<infile >outfile
 ./cmd | grep keyword
Which mechanisms are used?
 Which data structures are needed?

11
A11 Ex4 – Mounting

Which mechanisms are used to support
different kinds of file systems?
 Hint:
different file system structures
12
Overview

Assignment 11: hints
 File

systems
Assignment 10: solution
 Deadlocks
& Scheduling
13
A10 Ex1 – Deadlocks

Give a real-life example of deadlock. 
 (4)
Cars arriving at an intersection at the
same time

Is it possible to have a deadlock with one
process/thread only? 
 Non-reentrant
locks
14
A10 Ex2 – Synchronization Primitives

Assumption: OS with only a yield() system call
Pseudo-code implementation of lock, unlock,
wait, and notify

Data structures:

a
list of ready threads
 a flag to mark an object as locked
 a per-object lock list (list of threads waiting for the
lock)
 a per-object wait list (list of threads waiting for
notification)
15
lock()
If the object (o) is unlocked we lock it, otherwise
we move the thread to the lock list.
IF o is not locked THEN
mark o as locked;
ELSE
remove the thread from the ready list;
insert the thread in the lock list of the
object;
yield();
END
16
unlock()
We unlock the object and we move one of the
waiting threads to the ready list and call yield().
IF the lock list is not empty THEN
remove a thread from the object’s lock
list and put it on the ready list;
ELSE
mark o as unlocked;
END;
yield();
17
wait()
We have first to unlock the object and then to
move the current thread into the wait list.
unlock(o);
remove the current thread from the
ready list;
put the current thread in the object’s
wait list;
yield();
18
notify()
A thread is awakened and must wait for the
object to be unlocked.
take a thread t from the wait list of
o;
remove t from the wait list;
put t in the object’s lock list;
yield();
19
notifyAll()
All the objects are awakened and they must
wait for the object to be unlocked.
FOR thread t in the wait list of o DO
remove t from the wait list;
put t in the object’s lock list;
END;
yield();
20