Transcript File

Unit-I
Foundation of Unix Operating Systems
Contents:
•
•
•
•
•
•
•
•
•
•
Kernel
OS Booting Process
Buffer Management in UNIX
Buffer Cache
Internal File Representation
File Management
System Calls for file system
Access Methods
Free Space Management
Disk Management
UNIX System Overview :
User
Shell
The Kernel
System
Hardware
Kernel:
• Core and most important part of the OS
APPLICATION
• Manages the i/p ,o/p from software and
translates them into data processing instructions
for CPU and other components of computer.
• Monolithic Kernel
KERNEL
• Micro Kernel
• ExoKernel
HARDWARE
Kernel Architecture (UNIX) :
User program
User level
Library
kernel level
system call interface
Inter process
communication
File Subsystem
Buffer Cache
character
Process Control
Subsystem
block
Scheduler
Memory
Management
Device driver
Hardware control
hardware
kernel level
User level
Kernel Functions :
Monolithic Kernel :
User Mode
Kernel Mode
Micro Kernel :
User Mode
Kernel Mode
Hybrid Kernel :
User Mode
Kernel Mode
ExoKernel :
GRUB-I
• GRand Unified Bootloader
• Boot loader from GNU project
• Select one of installed OS i.e. kernel configuration
• Loads on startup and allows boot time changes
• Allows network booting, highly portable(FAT/NTFS)
• Can be loaded from external devices.
• GRUB-I or Legacy GRUB
• Cent OS versions below Ubuntu 9.10
Working of GRUB :
• On booting BIOS transfers controls to boot device like CD, hard
disk etc.
• First sector is MBR 512 bytes:• 446 bytes for primary bootloader
• 64 bytes for partition information
• 2 boot signature
• MBR loads boot sector to active partition.
• GRUB replaces MBR with its own code.
Working of GRUB :
• STAGE 1: Located in MBR points to stage 2 memory area as
MBR can’t contain all the code.
• STAGE 2: Points to configuration file. Can be located anywhere
with sufficient memory space.
• STAGE 1.5: Used only if the boot information is small enough
to fit in the area immediately after the MBR.
GRUB-II
•
•
•
•
•
•
•
•
•
•
Latest Version of GNU GRUB.
Replaced GRUB since Ubuntu 9.10 and Fedora 14.
Complete newly written.
Provides flexibility and performance enhancement.
Rescue mode / recovery mode
Custom menus
Themes
Graphical boot menu support
Boot LiveCD ISO images directly from hard drive
New configuration file structure
Kernel Architecture (UNIX) :
User program
User level
Library
kernel level
system call interface
Inter process
communication
File Subsystem
Buffer Cache
character
Process Control
Subsystem
block
Scheduler
Memory
Management
Device driver
Hardware control
hardware
kernel level
User level
Buffer Management :
• When a process wants to access data from a file, the kernel
brings the data into main memory, alters it and then request
to save in the file system.
• To decrease the response time and increase throughput, the
kernel minimizes the frequency of disk access by keeping a
pool of internal data buffer called buffer cache.
• Buffer cache contains the data in recently used disk blocks.
• When reading data from disk, the kernel attempts to read
from buffer cache.
• If data is already in the buffer cache, the kernel does not need
to read from disk.
• If data is not in the buffer cache, the kernel reads the data
from disk and cache it.
Buffer Cache :
• A buffer consists of two parts
• a memory array – contains data from the disk
• buffer header – Identifies the buffer
• Buffer is in memory copy of disk block
• disk block : buffer = 1 : 1
device num
block num
ptr to data area
status
ptr to previous buf on hash queue
ptr to next buf on hash queue
ptr to previous buf on free list
ptr to next buf on free list
Buffer Header
Buffer Header Status Bits :
• #define BH_Uptodate
/*1 if the buffer contains valid
data*/
• #define BH_Dirty
/*1 if the buffer is dirty*/
• #define BH_Lock
/*1 if the buffer is locked*/
• #define BH_Req
/*0 if the buffer has been
invalidated*/
• #define BH_Protected
/*1 if the buffer is protected*/
Structures of the buffer pool :
• Buffer pool according to LRU
• The kernel maintains a free list of buffer
• doubly linked circular list of buffer
• take a buffer from the head of the free list.
• When returning a buffer, attaches the buffer to the tail.
Forward ptrs
free list
head
buf 1
buf 2
buf n
Back ptrs
Free list of Buffers
Structures of the buffer pool :
• When the kernel accesses a disk block
•
•
•
•
Search as (device num,block num) rather than entire buffer pool
separate queue (doubly linked circular list)
hashed as a function of the device and block num
Every disk block exists on one and only on hash queue and only
once on the queue
Hash queue headers
28
4
64
blkno1 mod 4
17
5
97
blkno2 mod 4
98
50
10
blkno3 mod 4
3
35
99
blkno0 mod 4
Buffers on the Hash Queues
Scenarios for retrieval of a
buffer :
• Kernel determine the logical device no. and block no.
• The algorithms for reading and writing disk blocks use the algorithm
getblk
• The kernel finds the block on its hash queue
• The buffer is free.
• The buffer is currently busy.
• The kernel cannot find the block on the hash queue
• The kernel allocates a buffer from the free list.
• In attempting to allocate a buffer from the free list, finds a
buffer on the free list that has been marked “delayed write”.
• The free list of buffers is empty.
Retrieval of a Buffer:1st Scenario (a)
• The kernel finds the block on the hash queue and its buffer is free
Hash queue headers
28
4
64
17
5
97
98
50
10
3
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
Search for block 4
Retrieval of a Buffer:1st Scenario (b)
28
4
64
17
5
97
98
50
10
3
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
24
Remove block 4 from free list
Retrieval of a Buffer: 2nd Scenario (a)
• The kernel cannot find the block on the hash queue, so it allocates a buffer
from free list
Hash queue headers
28
4
64
17
5
97
98
50
10
3
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
freelist header
25
Search for block 18: Not in cache
Retrieval of a Buffer: 2nd Scenario (b)
Hash queue headers
28
4
64
17
5
97
98
50
10
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
18
freelist header
26
Remove 1st block from free list: Assign to 18
Retrieval of a Buffer: 3rd Scenario (a)
• The kernel cannot find the block on the hash queue, and finds delayed
write buffers on hash queue
Hash queue headers
28
4
64
17
5
97
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
delay
98
50
10
3
35
99
delay
freelist header
Search for block 18, Delayed write blocks on free list
27
Retrieval of a Buffer: 3rd Scenario (b)
Hash queue headers
28
64
blkno0 mod 4
blkno1 mod 4
17
5
97
writing
blkno2 mod 4
blkno3 mod 4
98
50
10
3
35
99
18
writing
freelist header
(b) Writing Blocks 3, 5, Reassign 4 to 18
Figure 3.8
28
Retrieval of a Buffer: 4th Scenario
• The kernel cannot find the buffer on the hash queue, and the free list is
empty
Hash queue headers
28
4
64
17
5
97
blkno2 mod 4
98
50
10
blkno3 mod 4
3
35
99
blkno0 mod 4
blkno1 mod 4
freelist header
29
Search for block 18, free list empty
Retrieval of a Buffer: 5th Scenario
• Kernel finds the buffer on hash queue, but it is currently busy
Hash queue headers
28
4
64
17
5
97
98
50
10
3
35
99
blkno0 mod 4
blkno1 mod 4
blkno2 mod 4
blkno3 mod 4
busy
freelist header
Search for block 99, block busy
30
Algorithm: GetBlock
• GetBlock (file_system_no,block_no)
• while (buffer not found)
• if (buffer in hash queue)
• if (buffer busy) {
//5
sleep (event buffer becomes free)
Continue
}
• mark buffer busy
//1
• remove buffer from free list
• return buffer
• else
• if (there is no buffer on free list){
//4
sleep (event any buffer becomes free)
Continue
}
• remove buffer from free list
• if (buffer marked as delayed write){ //3
asynchronous white buffer to disk
Continue
}
• remove buffer from hash queue
//2
• put buffer onto hash queue
• return buffer
31
Algorithm: ReleaseBlock
• ReleaseBlock (locked buffer)
• wakeup all process event, waiting for any buffer to become free
• wakeup all process event, waiting for this buffer to become free
• raise processor execution level to block interrupt
• if (buffer content valid and buffer not old)
• enqueue buffer at the end of free list
• else
• enqueue buffer at the beginning of free list
• lower processor execution level to allow interrupt
• unlock (buffer)
32
Reading and Writing disk blocks
• To read block ahead
• The kernel checks if the block is in the cache or not.
• If the block in not in the cache, it invokes the disk driver to read the
block.
• The the process goes to sleep awaiting the event that the I/O is
complete.
• The disk controller interrupts the processor when the I/O is complete
• The disk interrupt handler awakens the sleeping processes
• The content of disk blocks are now in the buffer
• When the process no longer need the buffer, it releases it so that other
processes can access it
33
Reading and Writing disk blocks
• To write a disk block
• The kernel informs the disk driver that it has a buffer whose contents
should be output.
• The disk driver schedules the block for I/O.
• If the write is synchronous, the calling process goes the sleep awaiting
I/O completion and releases the buffer when awakens.
• If the write is asynchronous, the kernel starts the disk write. The kernel
release the buffer when the I/O completes.
34
Internal Representation Of File:
Lower Level File system Algorithms
namei
alloc free
ialloc ifree
iget iput bmap
buffer allocation algorithms
getblk brelse bread breada bwrite
Fig. File System Algorithms
File System Algorithms :
• The algorithm iget returns a previously identified inode.
• Algorithm iput release the inode.
• The algorithm bmap sets kernel parameters for accessing a file.
• The algorithm namei converts a user level path name to an inode
using algorithms iget,iput,and bmap.
• Algorithms alloc and free allocate and free disk blocks for files
• Algorithms ialloc and ifree assigns and free inodes for files.
Inode :
• contains the information necessary for a process to access a
file
• exits in a static form on disk and the kernel reads them into an
in-core inode
• consists of
- file owner identifier
- file type
- file access permissions
- file access times
- number of links to the file
- table of contents for the disk address of data in a file
- file size
Inodes :
• in-core copy of the inode contains
- status of the in-core inode
- logical device number of file system
- inode number
- pointers to other in-core inodes
- reference count
Algorithm iget :
1. The kernel finds the inode in inode cache and it is on inode free list
remove from free list
increment inode reference count
2. The kernel cannot find the inode in inode cache so it allocates a
inode from inode free list
remove new inode from free list
reset inode number and file system
remove inode from old hash queue, place on new one
read inode from disk(algorithm bread)
initialize inode
3. The kernel cannot find the inode in inode cache but finds the free
list empty
error
4. The kernel finds the inode in inode cache but it was locked
sleep until inode becomes unlocked
iget (inode_no) //getIncoreInode
• while (not done)
• if (inode in inode cache)
• if (inode locked)
• sleep(event inode becomes unlocked)
• continue
• if (inode on inode free list)
• remove from free list
• return locked inode
•
•
•
•
•
•
•
if (no inode on free list)…. return error
remove new inode from free list
set inode number
remove inode from old hash queue and place on new one
read inode from disk
set reference count 1
return locked inode
Algorithm iput :
- The kernel locks the inode if it has not been already locked
- The kernel decrements inode reference count
- The kernel checks if reference count is 0 or not
- If the reference count is 0 and the number of links to the file is
0, then the kernel releases disk blocks for file(algorithm free),
free the inode(algorithm ifree)
• If the file was accessed or the inode was changed or the
file was changed , then the kernel updates the disk inode
• The kernel puts the inode on free list
- If the reference count is not 0, the kernel releases the inode
lock
iput (inode_no) //releaseIncoreInode
• lock inode if not locked
• decrement inode reference count
• if (reference count==0)
• if (inode link==0)
• free disk block
• set file type to 0
• free inode
• if (file accessed or inode changed or file changed)
• update disk inode
• put inode on free list
• Release inode lock
Structure of a regular file :
Inode
Data Blocks
direct0
direct1
direct2
direct3
direct4
direct5
direct6
direct7
direct8
direct9
single indirect
double indirect
triple indirect
Fig. Direct and Indirect Blocks in Inode
Structure of a regular file :
Assuming System V UNIX :
Assume that a logical on the file system holds 1K bytes and that a block
number is addressable by a 32 bit integer, then a block can hold up to
256 block numbers
10 direct blocks with 1K bytes each=10K bytes
1 indirect block with 256 direct blocks= 1K*256=256K bytes
1 double indirect block with 256 indirect blocks=
256K*256=64M bytes
1 triple indirect block with 256 double indirect blocks=
64M*256=16G bytes
Directories :
Fig. A UNIX directory tree
Directories :
• A directory is a file whose data is a sequence of entries, each
consisting of an inode number and the name of a file contained in
the directory.
• Path name is a null terminated character string divided by slash (“/”)
• Directory layout for /etc
Byte Offset in Directory
Inode Number
File Name
0
83
.
16
2
..
32
1798
init
48
1276
fsck
.
.
Mknod
.
.
……
224
0
crash
Path conversion to an inode :
• if (path name starts with root)
• working inode= root inode
• else
• working inode= current directory inode
• while (there is more path name)
• read next component from input
• read directory content
• if (component matches an entry in directory)
• get inode number for matched component
• release working inode
• working inode=inode of matched component
• else
• return no inode
• return (working inode)
Super block :
• File System
boot block
super block
Inode list
data blocks
• consists of
- the size of the file system
- the number of free blocks in the file system
- a list of free blocks available on the file system
- the index of the next free block in the free block list
- the size of the inode list
- the number of free inodes in the file system
- a list of free inodes in the file system
- the index of the next free inode in the free inode list
- lock fields for the free block and free inode lists
- a flag indicating that the super block has been modified
Inode assignment to a new file :
Super Block Free Inode List
free inodes
83
18
array1
48
19
empty
20
index
Super Block Free Inode List
free inodes
83
18
array2
empty
19
20
index
Assigning Free Inode from Middle of List
Inode assignment to a new file :
Super Block Free Inode List
470
empty
0
array1
index
Super Block Free Inode List
535
free inodes
0
array2
476 475 471
48
49
Assigning Free Inode – Super Block List Empty
50
Inode assignment to a new file :
• algorithm ialloc : assigns a disk inode to a newly
created file
-super block is unlocked
1.There are inodes in super block inode list and inode is free
get inode number from super block inode list
get inode (iget)
initialize inode
write inode to disk
decrement file system free inode count
2. There are inodes in super block inode list but inode is not
free
get inode number from super block inode list
get inode (iget)
write inode to disk
release inode (iput)
Inode assignment to a new file :
3. Inode list in super block is empty
lock super block
get remembered inode for free inode search
search disk for free inode until super block full or
no more free inodes(bread and brelse)
unlock super block
super block becomes free
if no free inodes found on disk , stop
otherwise, set remembered inode for next free inode
search
- If super block is locked, sleep
Inode assignment to a new file :
• Locked inode illoc()
• while (not done)
• If (super block locked)
• Sleep (event super block becomes free)
• Continue
• If (inode list in super block empty)
•
•
•
•
•
•
•
•
•
•
•
Lock super block
Get remember inode for free inode search
Search until super block full or no more free inode
Unlock super block and wake up (event super block free)\
If no free inode found on disk return error
Set remebered inode for next free inode search
Get inode number from super block inode list
Get inode
Write inode to disk
Decrement free inode count
Return inode
Freeing inode :
• ifree(inode_no)
• Increment free inode count
• If super block locked return
• If (inode list full) //at super block
• if (inode number <remembered inode)
• Set remembered inode as input inode
• Else
• Store inode number in inode list
• return
Freeing inode :
535
476 475 471
remembered inode
free inodes
index
Original Super Block List of Free Inodes
499
remembered inode
476 475 471
free inodes
Free Inode 499
499
remembered inode
index
476 475 471
free inodes
Free Inode 601
index
Allocation of disk blocks :
109 106 103 100 …………………………..
109
211 208 205 202 …………………
211
310 307 304 301
…………………
310
409 406 403 400 …………………
112
214
313
linked list of free disk block number
Allocation of disk blocks :
super block list
109 …………………………………………………………
109
211 208 205 202
…………………………….. 112
original configuration
109 949 …………………………………………………..
109
211 208 205 202 ………………………………. 112
After freeing block number 949
Allocation of disk blocks :
109 ………………………………………………………..
109
211 208 205 202 ………………………………. 112
After assigning block number(949)
211 208 205 202
……………………………… 112
211
344 341 338 335 ………………………………. 243
After assigning block number(109)
replenish super block free list
System Calls :
• System calls: The mechanism used by an application
program to request service from the operating system.
• This allows the OS to perform restricted actions such as
accessing hardware devices or the memory management
unit.
read (fd, buffer, nbytes) :
Some System Calls :
File Management :
Fig. A Typical File Control Block
File Allocation Methods :
• An allocation method refers to how disk blocks are allocated
for files:
• Contiguous allocation
• Linked allocation
• Indexed allocation
Contiguous allocation :
Linked allocation :
Indexed allocation :
Access Methods :
• Sequential Access
read next
write next
reset
no read after last write
(rewrite)
• Direct Access
read n
write n
position to n
read next
write next
rewrite n
n = relative block number
Free Space Management :
• Bit vector (n blocks)
0 1
2
n-1
bit[i] =

…
• Relatively simple
1  block[i] free
0  block[i] occupied
Free Space Management :
• Linked list
• Hard to find contiguous space easily
• But no waste of space
• Grouping
• Store addresses of n free blocks in the first block
• Last of these addresses is to a block that contains addresses
of another n free blocks
• So many free blocks can be found at one time
• Counting
• Clusters of contiguous free blocks recorded together
• Keep list of first block address, count of contiguous free
ones
Disk Management :
• Low-level formatting, or physical formatting — Dividing a disk into
sectors that the disk controller can read and write
• Each sector can hold header information, plus data, plus error correction
code (ECC)
• Usually 512 bytes of data but can be selectable
• To use a disk to hold files, the operating system still needs to record its
own data structures on the disk
• Partition
• Logical formatting
• To increase efficiency most file systems group blocks into clusters
• Disk I/O done in blocks
• File I/O done in clusters
• Boot block
• bootstrap stored in ROM
• Bad Blocks
• Sector Sparing
• Sector Slipping
Swap Space :
• Swap-space — Virtual memory uses disk space as an extension of
main memory.
• Swap-space Use :
• Hold the process image
• Swap-space Location :
• Using normal file system
• Separate Raw partition
Fig. Data Structures for Swapping on Linux Systems