Salsa - Networking
Topics
Nachos
Virtual
Memory in Nachos
[
Source code in code/network
|
Quiz
]
Distribution of computation between several physical processors has become
common in computer systems. This document discusses the networking component
of operating systems. We first discuss networking in general terms and then
explain the network implementation in Nachos.
Networking
Two schemes are in vogue for distributed computation. In a
multiprocessor system, the processors share memory and a clock, and
communication usually takes place through shared memory. In a
distributed system, the processors do not share memory or a clock and
communicate with one another through various communication networks, such as
high-speed buses or telephone lines. From the point of view of a specific
processor in a distributed system, the rest of the processors are
remote, whereas its own resources are local. The processors
in a distributed system may be called a host, site, or a
node. When a process at site A wants to communicate with a
process at site B, the message needs to routed properly to that site.
This is the responsibility of a router. It can either be a host
computer with routing software or a special-purpose device. Various
routing protocols exist for determining the actual route on which a
message will be sent.
The sites in a distributed network can be connected physically in a number of
ways. We list the most common ones below:
- Fully Connected Networks Each site is directly linked
with all other sites in the system. The cost of this configuration is high
since a direct communication line must be present between all the sites.
Messages however, can be sent fast; only one link needs to be used.
Reliability of such systems is also high since many links must fail for the
system to become partitioned.
- Partially Connected Networks Direct links exist between
some, but not all pairs of sites. The cost of configuration is lower than
that of the above scheme. However, a message from one site to another may
have to be sent through several intermediate sites, resulting in slower
communication.
- Hierarchical Networks The sites are organized as a tree.
Each site has a unique parent and possibly some children. The parent and the
child communicate directly and the children communicate through the parent
site. In general, the failure of any node (except a leaf) in this
configuration partitions the network into several disjoint subtrees.
This configuration is commonly used for corporate networks.
- Star Networks One of the sites in the system is
connected to all other sites. None of the other sites are connected
to any other. The cost of this system is linear in the number of sites. The
communication cost is also low, because a message requires at most two
transfers.
- Ring Networks Each site is connected to exactly two other
sites. The ring can either be unidirectional or bidirectional. In the
former, a site can send a message to only one of its neighbors and all the
sites must send the messages in the same direction. A single site failure
partitions the network in this case. In a bidirectional ring, a site can
send a message to both of its neighbors. However, two links must fail before
the network is partitioned.
- Multiaccess Bus Networks There is a single shared link
(the bus) to which all sites in the network are connected. The sites may be
organized as a straight line or as a ring and communicate directly with each
other through the shared link. The failure of one site does not affect
communication along the link. However, if the link fails, the network is
partitioned completely. The Ethernet network is based on this model.
- Hybrid Networks Different types of networks are connected
together. That is, each site in the network can have a different
configuration. Communication between sites is complicated because multiple
protocols must be followed.
The actual design (and implementation) of a network is specified by the
International Standards Organization (ISO). In the ISO model, the network is
organized as seven layers on each site. Each layer on a site communicates
with the equivalent layer on the remote site. These are briefly listed below:
- Physical Layer Concerned with transmitting raw bits over a
communication channel.
- Data-link Layer Responsible for handling the
frames, or fixed-length parts of packets, including any error
detection and recovery that occurred in the physical layer.
- Network Layer Responsible for providing connections and
for routing packets in the communication network. Routers work at this layer.
- Transport Layer Responsible for low-level access to the
network and for transfer of messages between the clients.
- Session Layer Responsible for implementing sessions, or
process-to-process communication protocols.
- Presentation Layer Responsible for resolving the
differences in formats among the various sites in the network, including
character conversions.
- Application Layer Interacts directly with the users of the
network. Deals with file transfer, remote-login protocols, email etc.
Networking in
Nachos
Nachos provides the abstraction of unreliable, ordered, fixed-size
message delivery to mailboxes on other directly connected machines.
Messages can be dropped by the network but are never corrupted. Any thread
running on Nachos can send a message to a mailbox on a directly connected
machine using the PostOffice object. The PostOffice
delivers packets to a specific buffer (a MailBox), based on the
mailbox number stored in the packet header. Mail waits in the mailbox until a
thread asks for it; if the mailbox is empty, threads can wait for mail to
arrive in it. Thus, the PostOffice de-multiplexes incoming packets,
delivering them to the appropriate thread. Each message contains a return
address which is the id of the machine that sent the message, and a from
box which is the number of the mailbox on the sending machine to which
the receiving thread can send an acknowledgement.
The PostOffice class
The PostOffice class is defined in the the files post.h and
post.cc in the network
directory. This class defines a post-office or a collection of mailboxes.
It is a synchronized object that provides two main operations: Send -
send a message to a remote machine, and Receive - wait until a
message is in the mailbox, then remove and return it. Incoming messages are
put by the PostOffice into the appropriate mailbox, waking up any threads
waiting on Receive.
The file post.h also defines three other classes - Mail,
MailHeader and MailBox. Mail defines the format of
an incoming/outgoing message. The constructor function of this class
initializes a single mail message, by concatenating the PacketHeader
(explained below) and the MailHeader. The MailHeader is
part of the message header. It is prepended to the message by the PostOffice
before the message is sent to the Network and contains the the destination
mailbox address, the source mailbox address and the number of bytes in the
message data. Thus, the packet that is delivered to the remote machine
contains the actual message, the MailHeader and the
PacketHeader (the
Mail object). Finally, the MailBox class defines a single
mailbox for messages. Incoming messages are put by the PostOffice into the
appropriate mailbox, and these messages can then be retrieved by threads on
that machine. A mailbox is implemented simply as a list of messages using the
SynchList object (synchlist.h(cc)).
The Network Device
The emulation of a physical network connection is implemented in the
files network.h and network.cc in the machine
directory. The abstraction is one of ordered, unreliable, fixed-size packet
delivery to other machines on the network. The class PacketHeader
defines a network packet header and contains the network address of the
destination and source machine, and the number of bytes in the message
(excluding the PacketHeader but including the MailHeader).
The actual network device is defined by the Network class. This
class simulates a network interface, using UNIX sockets to deliver packets
between multiple invocations of Nachos. It contains routines to send and
receive a packet from a remote machine.
The following figure summarizes the above discussion.
Want to know more about
Networking?
Source code in code/network
Quiz
Back to Top
Last modified on