Only the portions of the solution which represent additions or significant changes to the solution for the first programming assignment are described here. Everything not described here is essentially identical the the solution for the first programming assignment.
Sharing the terminal is simple, largely because the terminal is a serially-reusable resource, and so can only be used by one process at a time. Sharing in this case consists of figuring out which process gets the terminal next, which, assuming you're not worried about fairness, isn't a complicated task.
Sharing the terminal is also simple because it only needs to be shared among user processes; the operating system doesn't make use of the terminal. The disk, however, is shared between the user processes and the operating system, and this makes sharing a bit more complicated. Some of the complication is an consequence of the two-part simulator, but some is due to the privileged position kernel code holds over user processes. Fortunately, this second form of complication can be controlled by designing the operating system so that the differences between user and kernel code are reduced, which, in addition to reducing complications, is a generally useful design guideline.
<disk driver interface declarations>= (U->) [D->] extern void init(void);
and clients of the disk driver need to be able to make disk I-O requests, passing along the following information
bno - the disk-block number involved in the I-O request.
loc - the lowest user-space address involved in the I-O request.
op - the disk I-O operation: read or write.
f - the function to call when the request is complete.
arg - the argument to pass to f() when it's called.
<disk driver interface declarations>+= (U->) [<-D] extern void request( device::operations op, unsigned bno, address loc, callback f, void * arg);
When a disk I-O request has finished, the disk driver will call the callback function associated with the request, passing in the status returned by the disk-io operation and the argument passed in with the request.
<disk driver interface typedef>= (U->)
typedef void (* callback)(status::responses, void *);
Definesdisk_dvr::callback(links are to index).
A client's disk I-O request information is kept in a structure, the fields of
which have the same interpretation as the corresponding parameters in the
disk_dvr::request() procedure.
<disk driver data structures>= (U->) [D->]
struct request {
unsigned bno;
address loc;
device::operations op;
disk_dvr::callback f;
void * arg;
};
Definesrequest(links are to index).
Pending I-O requests are hung on a queue.
<disk driver data structures>+= (U->) [<-D->] typedef std::queue<request> Requests; static Requests pending;
Definespending,Requests(links are to index).
The driver needs to keep track whether or not a disk I-O request has been issued but not completed.
<disk driver data structures>+= (U->) [<-D] static bool in_progress = false;
Definesin_progress(links are to index).
Every once in a while (such as when a new disk I-O request gets hung on the queue), the disk driver needs to be poked to make sure it's handling outstanding requests.
If there's a I-O request in progress, or there's no pending requests, there's nothing for the disk driver to do. Otherwise, it should start the disk I-O operation requested at the head of the pending queue. The pending request is left on the queue so it can be dealt with when the request is finished.
<disk driver procedures>= (U->) [D->]
static void poke(void) {
// Handle another disk-io request, if possible.
if (!in_progress && !pending.empty()) {
const request & req = pending.front();
store_mem(disk_address_register, req.loc, disk_dvr::poke);
store_mem(disk_block_register, req.bno, disk_dvr::poke);
store_mem(disk_command_register, req.op, disk_dvr::poke);
in_progress = true;
}
}
Definespoke(links are to index).
A disk interrupt marks the end of a disk I-O request made by the head of the pending queue. After notifying the requester via the supplied call-back, the disk driver starts the next request, if any.
<disk driver procedures>+= (U->) [<-D]
static void disk_ih(void) {
assert(!pending.empty());
const request & req = pending.front();
word w;
fetch_mem(disk_status_register, w, disk_dvr::disk_ih);
(req.f)((status::responses) w, req.arg);
pending.pop();
in_progress = false;
poke();
}
Definesdisk_ih(links are to index).
Initializing the disk driver involves setting the disk interrupt handler.
<disk driver interface procedures>= (U->) [D->]
void init(void) {
mass.memory->set_ihandler(disk_i, disk_ih);
}
Definesdisk_dvr::init(links are to index).
The information associated with a disk I-O request gets hung on the pending requests queue and the driver gets poked in case it was idle, waiting for a new request. This roundabout way can be optimized slightly by issuing the request directly if the queue is empty, but the extra code is more complex than the code below, and the time saved is immeasurable compared to the disk I-O time anyway.
<disk driver interface procedures>+= (U->) [<-D]
void request(
device::operations op, unsigned bno, address loc, callback f, void * arg) {
::request req;
req.bno = bno;
req.loc = loc;
req.op = op;
req.f = f;
req.arg = arg;
pending.push(req);
poke();
}
Definesdisk_dvr::request(links are to index).
<disk-dvr.h>= #ifndef _disk_dvr_h_ #define _disk_dvr_h_ #include "system.h" namespace disk_dvr { <disk driver interfacetypedef> <disk driver interface declarations> }; #endif
Definesdisk-dvr.h(links are to index).
<disk-dvr.cc>=
#include "disk-dvr.h"
#include "os.h"
#include <queue>
<disk driver data structures>
<disk driver procedures>
namespace disk_dvr {
<disk driver interface procedures>
}
Definesdisk-dvr.cc(links are to index).
<disk manager interface declarations>= (U->) [D->] void open(void);
Closing a connection to the disk requires the disk id associated with the connections.
<disk manager interface declarations>+= (U->) [<-D->] void close(word);
A disk I-O operation needs to know the operation (op), the disk I-O channel
involved with the operation (dev), the user-space address involved with the
operation (loc), and the number of the disk block involved (n).
<disk manager interface declarations>+= (U->) [<-D->] void operation( system_call::system_calls op, word dev, address loc, unsigned n);
Finally, a predicate that determines whether or not the given value is a valid disk id.
<disk manager interface declarations>+= (U->) [<-D] bool is_valid_id(word);
Each instance of an opened disk is referenced by an unsigned integer called the
Disk_id. The set of currently active disk ids is stored in,
naturally, a set.
This is not a particularly intelligent or safe approach to take, but it has the great virtue of being simple. It can be made safer against spoofing by keeping track of a (pid, did) pairs, where did is an disk id and pid is the id of the process to which did was allocated. A disk id did would be valid if and only if the id of the process holding did is pid and (pid, did) is a recognized pair.
<disk manager data structures>= (U->) [D->] typedef unsigned Disk_id; static Disk_id next_disk_id = 0; static std::set<Disk_id> disk_ids;
DefinesDisk_id,disk_ids,next_disk_id(links are to index).
When a process's disk I-O request is done, the disk manager needs to know
pid - the requesting process' id.
bno - the disk-block number involved in the request.
op - the requested disk I-O operation.
to finish processing the request.
<disk manager data structures>+= (U->) [<-D]
struct disk_cb_info {
const process::id pid;
const unsigned bno;
const device::operations op;
disk_cb_info(process::id p, unsigned b, device::operations o) :
pid(p), bno(b), op(o) { }
};
Definesdisk_cb_info(links are to index).
When a process's disk I-O request is complete, the disk manager needs to store the return values in the process's registers and return the process on the ready queue.
<disk manager procedures>= (U->)
static void dsk_cb(status::responses s, void * arg) {
disk_cb_info * dcbi = reinterpret_cast<disk_cb_info *>(arg);
process::put_register(dcbi->pid, 0, s);
if (dcbi->op == device::read)
process::put_register(dcbi->pid, 1, dcbi->bno);
process::ready(dcbi->pid);
delete dcbi;
}
Definesdsk_cb(links are to index).
Assuming the disk id is valid, closing a disk connection involves just removing the disk id from the set of currently valid disk ids and returning ok to the closing process.
<disk manager interface procedures>= (U->) [D->]
void close(word dev_id) {
assert(is_valid_id(dev_id));
disk_ids.erase(dev_id);
store_mem(0, status::ok, disk_mgr::close);
}
Definesdisk_mgr::close(links are to index).
A disk id is valid if it's in the set of valid disk ids. (How convenient is that?)
<disk manager interface procedures>+= (U->) [<-D->]
bool is_valid_id(word dev_id) {
return disk_ids.find(dev_id) != disk_ids.end();
}
Definesdisk_mgr::is_valid_id(links are to index).
Because any process can establish a connection to the disk and the disk can support any number of connections, disk opens always succeed.
<disk manager interface procedures>+= (U->) [<-D->]
void open(void) {
word dev_id = next_disk_id++;
disk_ids.insert(dev_id);
store_mem(1, dev_id, disk_mgr::open);
store_mem(0, status::ok, disk_mgr::open);
}
Definesdisk_mgr::open(links are to index).
After checking the arguments to make sure they're reasonable, the disk I-O request is forwarded to the disk driver and the calling process is suspended until the request is completed.
<disk manager interface procedures>+= (U->) [<-D]
void operation(
system_call::system_calls op, word dev_id, address loc, unsigned n) {
assert(is_valid_id(dev_id));
assert((op == system_call::read) || (op == system_call::write));
if (!legal_range(loc, disk_block_size)) {
store_mem(0, status::bad_address, disk_mgr::operation);
return;
}
const device::operations dop =
(op == system_call::read ? device::read : device::write);
disk_dvr::request(
dop, n, loc, dsk_cb, new disk_cb_info(process::block(), n, dop));
}
Definesdisk_mgr::operation(links are to index).
<disk-mgr.h>=
#ifndef _disk_mgr_h_
#define _disk_mgr_h_
#include "system.h"
namespace disk_mgr {
<disk manager interface declarations>
}
#endif
Definesdisk-mgr.h(links are to index).
<disk-mgr.cc>=
#include <set>
#include "disk-mgr.h"
#include "os.h"
#include "process.h"
#include "disk-dvr.h"
<disk manager data structures>
<disk manager procedures>
namespace disk_mgr {
<disk manager interface procedures>
}
Definesdisk-mgr.cc(links are to index).
<terminal manager interface declarations>= (U->) [D->] void close(word);
The parameters for an open are passed via the registers used to make the system call; the return values are passed the same way.
<terminal manager interface declarations>+= (U->) [<-D->] void open(void);
A terminal I-O operation needs to know the operation (op), the terminal I-O
channel involved with the operation (dev), the user-space address involved
with the operation (loc), and the number of bytes involved (n).
<terminal manager interface declarations>+= (U->) [<-D->] void operation( system_call::system_calls op, word dev, address loc, unsigned n);
Finally, some way of determining whether or not a word holds a valid terminal id.
<terminal manager interface declarations>+= (U->) [<-D] bool is_valid_id(word w);
Because there can be at most one outstanding terminal I-O request, handling the request data is considerably simpler than it is for the disk, which may have to keep track of the data for an arbitrary number of outstanding I-O requests.
The terminal manager uses a set of global variables rather than define a structure and a queue. The globals are
tty_cnt - The number of characters processed so far.tty_free - True if and only if the tty hasn't been opened.
tty_id - The tty channel identifier.
tty_loc - The address of the next word to process.
tty_n - The maximum number of characters to process.
tty_proc - The id of the process having the tty open.
<terminal manager data structures>= (U->) static address tty_loc; static process::id tty_proc; static bool tty_free = true; const int tty_id = 1956; static unsigned tty_cnt; static unsigned tty_n;
Definestty_cnt,tty_free,tty_id,tty_loc,tty_n,tty_proc(links are to index).
Check the previous terminal I-O operation to make sure it went off without an error; die if there was an error.
<terminal manager macros>= (U->) [D->]
#define check_tty(_caller) \
do {word _w; \
fetch_mem(terminal_status_register, _w, _caller); \
assert(_w == status::ok); } while (false)
Definescheck_tty(links are to index).
Do the terminal I-O operation _op on behalf of procedure _c.
<terminal manager macros>+= (U->) [<-D->] #define tty_op(_op, _c) \ store_mem(terminal_command_register, device:: ## _op, _c)
Definestty_op(links are to index).
Store into _c the character found at address _l on behalf of procedure
_w. This is a little bit tricky because if the _l is in the
process's register set, the character has to come from the process's saved
context (the process having been suspended until the requested I-O operation is
finished).
<terminal manager macros>+= (U->) [<-D] #define fetch_char(_l, _c, _w) \ if (_l < pc_register) _c = process::get_register(tty_proc, _l); \ else fetch_mem(_l, _c, _w)
Definesfetch_char(links are to index).
When an interrupt signaling the end of the previous terminal write arrives, then either all the characters have been written to the terminal and the requesting process can be hung back on the ready queue, or there's still more characters to write, in which case the next character should be fetched and written to the terminal.
<terminal manager procedures>= (U->) [D->]
static void write_terminal_ih(void) {
check_tty(write_terminal_ih);
if (++tty_cnt == tty_n) {
process::put_register(tty_proc, 0, status::ok);
process::put_register(tty_proc, 1, tty_cnt);
process::ready(tty_proc);
}
else {
word w;
tty_loc++;
fetch_char(tty_loc, w, write_terminal_ih);
store_mem(terminal_data_register, w, write_terminal_ih);
tty_op(write, write_terminal_ih);
}
}
Defineswrite_terminal_ih(links are to index).
When an interrupt signaling the end of the previous terminal read arrives, then either an actual character was read or the terminal sent an eof. An actual character has to be stored wherever the caller specified (keeping in mind that characters going into the register set have to be stored in the process's saved context).
If all the characters requested have been read, or there's an eof, then the requesting process can be hung back on the ready queue. Otherwise, go read the next character from the terminal.
<terminal manager procedures>+= (U->) [<-D]
static void read_terminal_ih(void) {
check_tty(read_terminal_ih);
word w;
fetch_mem(terminal_data_register, w, read_terminal_ih);
if (w != device::eof_char) {
if (tty_loc < pc_register)
process::put_register(tty_proc, tty_loc, w);
else
store_mem(tty_loc, w, read_terminal_ih);
tty_cnt++;
tty_loc++;
}
if ((tty_cnt == tty_n) || (w == device::eof_char)) {
process::put_register(tty_proc, 0, status::ok);
process::put_register(tty_proc, 1, tty_cnt);
process::ready(tty_proc);
}
else
tty_op(read, read_terminal_ih);
}
Definesread_terminal_ih(links are to index).
Closing the connection frees the terminal to be re-opened.
<terminal manager interface procedures>= (U->) [D->]
void close(word dev_id) {
assert(is_valid_id(dev_id));
tty_free = true;
store_mem(0, status::ok, terminal_mgr::close);
}
Definesterminal_mgr::close(links are to index).
terminal_mgr::is_valid_id() is too simple, because it can be spoofed. Oh
well.
<terminal manager interface procedures>+= (U->) [<-D->]
bool is_valid_id(word dev_id) {
return (dev_id == tty_id) && !tty_free;
}
Definesterminal_mgr::is_valid_id(links are to index).
Either the terminal is available for opening, in which case it's allocated to the requestor, or it already open, in which case the requestor gets an error.
<terminal manager interface procedures>+= (U->) [<-D->]
void open(void) {
if (tty_free) {
tty_free = false;
store_mem(0, status::ok, terminal_mgr::open);
store_mem(1, tty_id, terminal_mgr::open);
}
else
store_mem(0, status::device_busy, terminal_mgr::open);
}
Definesterminal_mgr::open(links are to index).
After checking the arguments to make sure they're reasonable,
terminal_mgr::operation() suspends the calling process until the request is
completed and issues the requested terminal I-O operation. Each I-O operation
has a different interrupt handler; the proper interrupt handler is installed
before the operation is issued.
<terminal manager interface procedures>+= (U->) [<-D]
void operation(
system_call::system_calls op, word dev_id, address loc, unsigned n) {
assert(is_valid_id(dev_id));
if (!legal_range(loc, n)) {
store_mem(0, status::bad_address, terminal_mgr::operation);
return;
}
if (n == 0) {
store_mem(0, status::ok, terminal_mgr::operation);
store_mem(1, 0, terminal_mgr::operation);
return;
}
tty_proc = process::block();
tty_loc = loc;
tty_n = n;
tty_cnt = 0;
if (op == system_call::read) {
mass.memory->set_ihandler(terminal_i, read_terminal_ih);
tty_op(read, terminal_mgr::operation);
}
else {
word c;
assert(op == system_call::write);
mass.memory->set_ihandler(terminal_i, write_terminal_ih);
fetch_char(loc, c, terminal_mgr::operation);
store_mem(terminal_data_register, c, terminal_mgr::operation);
tty_op(write, terminal_mgr::operation);
}
}
Definesterminal_mgr::operation(links are to index).
<terminal-mgr.h>=
#ifndef _terminal_mgr_h_
#define _terminal_mgr_h_
#include "system.h"
namespace terminal_mgr {
<terminal manager interface declarations>
}
#endif
Definesterminal-mgr.h(links are to index).
<terminal-mgr.cc>=
#include "terminal-mgr.h"
#include "os.h"
#include "process.h"
<terminal manager data structures>
<terminal manager macros>
<terminal manager procedures>
namespace terminal_mgr {
<terminal manager interface procedures>
}
Definesterminal-mgr.cc(links are to index).
This section describes the changes made to the rest of the operating system. Only examples of the changes will be described here; see the solution for the first assignment for full details of the remaining parts.
Despite the significant change in the assumption about disk ownership, the actual code changes needed in the program-loader code are minor. The program loader no longer directly manipulates the disk-control registers to perform disk I-O, but rather makes a disk-driver request.
<program loader macros>= (U->) [D->]
# define disk_read(_cb) \
disk_dvr::request(device::read, next_block_to_read, \
next_program_address, _cb, 0)
Definesdisk_read(links are to index).
Also, the disk status comes back as an argument to the callback function; no need to access the disk-control register for the status.
<program loader macros>+= (U->) [<-D]
# define check_disk_error(_caller) \
do { if (r != status::ok) \
panic("disk read error %R in " #_caller "()", r); \
} while (false)
Definescheck_disk_error(links are to index).
The disk-interrupt handlers have to be rewritten as disk-driver callback
functions, but that involves changing the handler signature to match that of
the disk-driver callback prototype. For example, the read_rest_program()
interrupt handler now has the signature
void read_rest_program(status::responses r, void *)
Because the program-loader has at most one outstanding disk I-O request at a time, the information on the request can be kept as global variables, and the pass-along argument to the callback isn't used. The signatures of the other interrupt handlers used by the program loader are changed similarly; the body of each program loader remains unchanged.
For example, the read and write system calls are folded into one case-statement branch and dealt with using a general-purpose device-io procedure.
<read and write system calls>= (U->) case system_call::read: case system_call::write: do_dev_io((system_call::system_calls) w); break;
After retrieving the system-call arguments, do_dev_io() figures
out what the device-type is and calls the proper operation procedure.
<interrupt-handler procedures>= (U->) [D->]
static void do_dev_io(system_call::system_calls syscall_code) {
word dev_id, addr, n;
fetch_mem(1, dev_id, do_dev_io);
fetch_mem(2, addr, do_dev_io);
fetch_mem(3, n, do_dev_io);
if (disk_mgr::is_valid_id(dev_id))
disk_mgr::operation(syscall_code,
dev_id,
(address) addr,
(unsigned) n);
else if (terminal_mgr::is_valid_id(dev_id))
terminal_mgr::operation((system_call::system_calls) syscall_code,
dev_id,
(address) addr,
(unsigned) n);
else
store_mem(0, status::bad_device, do_dev_io);
}
Definesdo_dev_io(links are to index).
The reboot interrupt handler also has to be changed to initialize the disk and program loader separately.
<interrupt-handler procedures>+= (U->) [<-D]
void reboot_ih(void) {
mass.memory->set_ihandler(system_call_i, syscall_ih);
disk_dvr::init();
process::init();
storage::init(usr_base, usr_size/disk_block_size);
program_loader::init();
program_loader::poke();
}
Definesreboot_ih(links are to index).
a and a size in words n to make sure it's
contained within the running process's range of valid address
(remembering, of course, that the registers below the program counter
are part of the range of valid addresses).
<utility procedures>= (U->)
bool legal_range(address a, unsigned n) {
if (a + n <= pc_register)
return true;
else {
word t, b;
fetch_mem(base_register, b, legal_range);
fetch_mem(top_register, t, legal_range);
return (static_cast<address>(b) <= a) &&
(a + n <= static_cast<address>(t));
}
}
Defineslegal_range(links are to index).
typedef>: D1, U2
disk-dvr.cc>: D1
disk-dvr.h>: D1
disk-mgr.cc>: D1
disk-mgr.h>: D1
mpool.cc>: D1
mpool.h>: D1
os.cc>: D1
os.h>: D1
os-utils.cc>: D1
os-utils.h>: D1
process.cc>: D1
process.h>: D1
program-loader.cc>: D1
program-loader.h>: D1
storage.cc>: D1
storage.h>: D1
terminal-mgr.cc>: D1
terminal-mgr.h>: D1
This page last modified on 9 January 2002.