Transcript Layer 2 I/O Tasks

MINIX Operating System
Presented by: Pravendra Lohiya
Introduction to MINIX Operating System
•MINIX is an experimental OS used by students to dissect a real OS.
•MINIX name stands for mini-UNIX.
•MINIX was written in C programming language.
•Structured in more modular way than UNIX and is compatible with UNIX from
user point of view but totally different from inside.
•Many of the basic programs, such as cat, grep, ls, make and the shell are
present and perform the same functions as UNIX
•MINIX requires 20 MB of hard disk partition.
•MINIX is not as efficient as UNIX because it is designed to be readable.
History
•Version 6.0 of UNIX was widely available under AT&T license and frequently
studied.
•During the release of version 7.0 AT&T realized that it can be used for
commercial purpose.
• Teaching only theory does not give student full view of what an operating
is really like.
• Mr.Tanenbaum wrote a new operating system from scratch, compatible with
UNIX from user’s point of view.
•This OS is now used by students to get a view of what goes inside an OS.
Internal Structure of MINIX
Layer
4
Init
3
Memory manager File System
2
Disk Task TTY Task Clock Task System Task -----
1
User Process
User Process User Process
Network System
-----
Process Management
Layer 1 Process Management: This layer has 2 main functions:
(1) Catching the traps and interrupts, saving and restoring
registers and scheduling.
(2) The mechanics of messages; checking for legal
destinations, locating send and receive buffers in physical
memory, and copying bytes from sender to receiver.
Layer 2 I/O Tasks: A task is needed for each device type including
disks, printers, terminals, network interfaces, and clocks.
Internal Structure of MINIX
•All of the tasks in layer 2 and all the code in layer 1 are linked together in a
single binary called kernel.
•System task does not do I/O in the normal sense but exists in order to provide
services, such as copying between different memory regions, for processes,
which are not allowed to do such things for themselves.
Layer3 Server Process: Runs at a less privileged level than kernel and tasks
and cannot access I/O ports directly. The memory manager carries out all the
MINIX system calls that involve memory management, such as FORK, EXEC.
The file system carries out all the file system calls, such as READ, MOUNT,
and CHDIR
In MINIX resource management is done largely in kernel in layer 1 and 2 and
system call interpretation is in layer 3.
Layer4 User Process: It contains all user process- shells, editors, compilers,
and user written programs.
Process Management
•Processes in MINIX follow the general process model. Processes can create
sub processes, which in turn can create more sub processes, yielding a tree of
processes.
•All the user processes in the whole system are part of a single tree with init at
the root.
•During the initialization phase, the kernel starts the task, and then the memory
manager, the file system, and any other servers that run in layer. When all of
these have run and initialized themselves, they will block waiting for something
to do.
•init the first user process will be executed. It forks a child process for each
terminal. After a successful login, shell waits for the command to be typed and
then forks off a new process for each command.
•The two main MINIX system calls for process management are FORK and
EXEC. FORK is the only way to create a new process. EXEC allows a process
to execute a specified program.
•All the information about the process is kept in the process table, which is
divided up among kernel, memory manager and file system, with each one
having those fields that it needs.
Interprocess Communication
MINIX uses three primitives for sending and receiving messages.
•Send(dest, &message); to send a message to dest process
•Receive(source, &message);To receive a message from process source (or
any),
•Send_rec(src_dst, &message); To send a message and wait for a reply from the
same process.
•The second parameter in each process is the local address of the message data.
• The message passing mechanism in the kernel copies the message from the
sender to the receiver.
•The reply (for send_rec) overwrites the original message.
•Each process or task can send and receive messages from processes and tasks
in its own layer, and from those in the layer directly below it. User process may
not communicate directly with the I/O tasks.
Process Scheduling
3
Disk
Tty
Clock
2
MM
File System
Network
Servers
1
User
User
User
User
process
Tasks
•The MINIX scheduler uses a multilevel queuing system with three levels.
Highest priority, priority3 goes to system tasks and next higher priority, priority2
goes to server processes. These processes run until they block, using FCFS.
• User processes has lowest priority, priority1 and they are scheduled using
round robin, using time quantum of 100 msec.
• When picking a process to run, the scheduler checks to see if any tasks are
ready. If one or more are ready, the one at the head of the queue is run. If no
tasks are ready, a server (MM or FS) is chosen; otherwise a user process is
run.
Overview of Input/Output
Layer
User Processes
Device Independent
software
Device Driver
Interrupt Handler
Hardware
Make I/O call; format I/O;spooling
Naming, protection, blocking, allocation
Set up device registers; check status
Wake up driver when I/O requested
Perform I/O Operation
Overview of Input/Output
•The top four layers correspond to the four-layered structure of MINIX.
• For each class of I/O device present in a MINIX system, a separate I/O task
(device driver) is present. These drivers are full-fledged processes, each with
its own state, registers, stack and so on.
•In MINIX a process reads a file by sending a message to the file system
process. The file system, in turn may send a message to the disk driver
asking it to read the needed block.
File System
Device Driver
User Process
User Space
Kernel Space
Overview of Input/Output
Outline of the main procedure of an I/O task
Message mess;
/* message buffer*/
Void io_task() {
Initialize ();
/* only once during system init */
While (TRUE) {
receive(ANY, &mess);
caller = mess.source
/* wait for a request to work */
/* process from whom message came */
switch(mess.type) {
case READ:
rcode = dev_read(&mess); break;
case WRITE:
rcode = dev_write(&mess); break;
/* Other cases go here, including OPEN, CLOSE, and IOCTL */
default:
rcode = ERROR;
}
mess.type = TASK_REPLY;
mess.status = rcode;
/* result code */
send(caller, &mess);
/* send reply message back to caller */
}
}
Overview of Memory Management
•Memory management in MINIX is simple: neither paging nor swapping is used.
•The memory manager maintains a list of holes sorted in memory address order.
Hole is the hole list is searched using first fit for a hole that is big enough.
•Once a process is placed in memory, it remains in exactly the same place until it
terminates. It is neither swapped out and also never moved to another place in
memory.
This strategy deserves some explanation. It derives from three factors:
(1) the idea that MINIX is for personal computers, rather than for large
time sharing systems.
(2) the desire to have MINIX work on all IBM PCs
(3) a desire to make the system straightforward to implement on other small
computers.
Overview of MINIX File System
• The MINIX file system is a big C program that runs in user space.
•To read and write files, user processes send, messages to the file system
•The file system can be modified, experimented with, and tested almost
completely independently of the rest of MINIX .
•The structure of a file system is basically the same as that of the memory
manager and all I/O tasks.
File System Layout
Boot Block Super Block
I-Nodes
I-Nodes
Bit map
Zone Bit map
One disk block
Data
Overview of MINIX File System
•Each file system begins with a boot block.
•The super block contains information describing the layout of the file system.
•The disk storage can be allocated in units of 1,2,4,8 or in general 2n, blocks.
•The idea behind the zone is to help ensure that disk blocks that belong to the
same file are located on the same cylinder
•MINIX keeps track of which I-nodes and zones are free by using two bit maps,
I-node bit map and zone bit map.
•super block has a field which points to the first free I-node
•super block also has a field which points to the first free zone.
•Larger zone size means more disk space is wasted
•Another alternative would have been to have different zone sizes.
•MINIX I-node occupies 64 bytes and has information like I-node access,
modification time and I-node change times
Overview of MINIX File System
• When a file is opened its I-node is located and brought into the I-node table
in memory.I-node table has a counter per I-node.
•The main function of the I-node is to tell where the data blocks are. The first
seven zone numbers are in the I-node itself.
• Files up to 7k don’t need indirect block.
• With 1k block and zone size and 32 bit zone numbers, a single indirect block
holds 256 entries.
• The double indirect block points to 256 single indirect blocks, giving access
up to 64 MB.
• The maximum size of MINIX file system is 1G, so triple indirect block may be
also be used
Overview of MINIX File System
16 bits
Mode
Number of links
Uid
Gid
File Size
Access Time
Modification Time
64 bytes
File type and rwx bits
Directory entries for this file
Identifies User
Owner’s group
Number of bytes in file
Time in seconds
Status Change time
Zone0
Zone 1
Zone 2
Zone 3
Zone 4
Zone 5
Zone 6
Indirect Zone
Double indirect zone
Unused
Zone number
For first 7 data zones
I-node structure
Conclusion
•MINIX is a collection of processes that communicate with each other and
with user processes using single inter-process communication primitive message passing. This design gives more modular and flexible structure.
•MINIX operating system is very helpful for the students who are interested
in learning more about what goes inside an operating system.