Circles represent operating-system manager software; non circles represent
resources, either hardware (such as the disk) or software (exited processes).
Arrows between managers indicate interactions via subroutine calls; the caller
is pointing and the called is being pointed at. The labels associated with
each arrow gives the system event that triggers the subroutine call. For
example the arrow labeled "Exit" from the Process Manager to the Disk
Manager indicates that the Process Manager makes a subroutine call to the Disk
Manager (via a routine provided by the Disk Manager) whenever a process exits
the system.
The disk manager is responsible for loading programs. The interrupt handler is responsible for initializing the other managers on system boot-up; these interactions are not shown in the diagram.
interrupt_handler()
passing along the raised interrupt's code.
<interrupt handlers>=
void interrupt_handler(interrupt_types i) {
switch (i) {
case disk_i:
disk::ihandler();
break;
case reboot_i:
reboot_ih();
break;
case system_call_i:
syscall_ih();
break;
<the countdown interrupt>
case invalid_address_i:
process::exit();
break;
default:
panic("Unrecognized interrupt %d in interrupt_handler()", i);
}
if (process::done() and disk::idle())
process::halt();
}
Definesinterrupt_handler(links are to index).
On boot-up, initialize the process, storage, and disk resource managers. When initialized, the disk resource manager starts reading in the first program.
<interrupt handlers>+=
void reboot_ih(void) {
process::init();
storage::init(usr_base, usr_size/words_per_disk_block);
disk::init();
}
Definesreboot_ih(links are to index).Used below; previous and next definitions.
The system-call interrupt handler dispatches on the system-call code stored in register 0.
<interrupt handlers>+=
static void syscall_ih(void) {
word w0, w1, w2;
process::id pid;
fetch_mem(0, w0, syscall_ih);
fetch_mem(1, w1, syscall_ih);
fetch_mem(2, w2, syscall_ih);
switch (w0) {
case system_call::exec:
store_mem(0, process::exec(w1, pid), syscall_ih);
store_mem(1, static_cast<word>(pid), syscall_ih);
break;
case system_call::exit:
process::exit();
break;
case system_call::get_slot: {
const status::responses s = process::get_slot(pid, w0);
store_mem(0, s, syscall_ih);
if (status::ok == s) {
store_mem(1, w0, syscall_ih);
store_mem(2, static_cast<word>(pid), syscall_ih);
}
break;
}
case system_call::put_slot:
store_mem(0,
process::put_slot(static_cast<process::id>(w1), w2), syscall_ih);
break;
case system_call::yield:
store_mem(0, status::ok, syscall_ih);
process::yield();
break;
default:
store_mem(0, status::bad_system_call, syscall_ih);
}
}
Definessyscall_ih(links are to index).Used below; previous definition.
That's it for interrupt handling.
<interrupts.cc>=
#include "os.h"
#include "disk.h"
#include "storage.h"
#include "process.h"
// Deja vu c++ style.
static void reboot_ih(void);
static void syscall_ih(void);
unsigned read_clock(void) {
word c;
fetch_mem(clock_register, c, read_clock);
return c;
}
<interrupt handlers>
Definesinterrupts.cc,read_clock(links are to index).This code is written to a file (or else not used).
<process interface declarations>= typedef unsigned id;
Definesprocess::id(links are to index).
The first set of process-manager interface routines are the internal implementations of the system calls provided by the OS.
<process interface declarations>+= void exit(); bool yield(); status::responses exec(word, id &); status::responses put_slot(id, word); status::responses get_slot(id &, word &);
Used below; previous and next definitions.
The other parts of the process-manager interface are internal routines available to the rest of the OS.
process::init() initializes the process manager;
process::add() completes creation of a process; it's called by the
program loader when a program has been fully loaded into.
process::done() returns true if and only if the process manager
has no more work to do.
process::halt() halts the simulation.
process::put_register() stores a value into the saved register
context for a process.
<process interface declarations>+= void init(void); void add(const storage::chunk &, id); bool done(void); void halt(void); void put_register(id pid, unsigned r, word v);
Used below; previous definition.
The process table entry also contains code to allocate process ids and save and restore process register contexts.
<process data structures>=
struct process_table_entry {
static process::id next_id;
process_table_entry() : id(next_id++), slot_free(true) { }
const process::id id;
word registers[next_register];
word slot_value;
bool slot_free;
process::id slot_sender;
storage::chunk sc;
void save_state(void) {
for (address a = 0; a < next_register; a++)
fetch_mem(a, registers[a], save_state);
}
void restore_state(void) const {
for (address a = 0; a < next_register; a++)
store_mem(a, registers[a], restore_state);
}
};
unsigned process_table_entry::next_id = 1000;
Definesprocess_table_entry,restore_state,save_state(links are to index).
Process-table entries are stored in a list, with special iterators indicating the entries for the currently running process and the idle process.
<process data structures>+= typedef std::list<process_table_entry> process_table; typedef process_table::iterator ptab_iter; static process_table ptab; static ptab_iter running_process; static ptab_iter idle_process;
Definesidle_process,process_table,ptab,ptab_iter,running_process(links are to index).Used below; previous definition.
<the ready ring>=
namespace ready_ring {
typedef std::list<ptab_iter> Ring;
typedef Ring::iterator ring_iter;
static Ring ring;
static ring_iter current;
<ready-ring procedures>
}
Used below.
Add the given process-table entry to the ready ring. If the ready ring's empty before the addition, the new process becomes the current process.
<ready-ring procedures>=
void
add(ptab_iter pte) {
ring.push_back(pte);
if (ring.size() == 1)
current = ring.begin();
}
Definesready_ring::add(links are to index).
Make the successor process to the current process the new current process and return a pointer to the new current process (which may be the old current process if there's only one process on the ready ring).
<ready-ring procedures>+=
ptab_iter
advance() {
assert(not ring.empty());
if (ring.size() > 1) {
++current;
if (ring.end() == current)
current = ring.begin();
}
return *current;
}
Definesready_ring::advance(links are to index).Used above; previous and next definitions.
Return the number of processes in the ready ring.
<ready-ring procedures>+=
unsigned
ready_count() {
return ring.size();
}
Definesready_ring::ready_count(links are to index).Used above; previous and next definitions.
Remove the currently executing process from the ready ring and, if there's a successor process in the ring, set the given reference to it and return true. If the ready ring's empty after the removal, return false.
<ready-ring procedures>+=
bool
remove_current(ptab_iter & pte) {
assert(not ring.empty());
current = ring.erase(current);
if (ring.empty())
return false;
if (ring.end() == current)
current = ring.begin();
pte = *current;
return true;
}
Definesready_ring::remove_current(links are to index).Used above; previous definition.
The qunatum is fixed at 15 ticks, but there is a little trick: if there's less than two process on the ready ring, then there's no need to set a quantum because there's no other process to switch to.
<process macros>=
#define set_quantum(_n) \
store_mem(clock_countdown_register, \
ready_ring::ready_count() > 1 ? 15 : 0, process::_n)
Definesset_quantum(links are to index).Used below.
The countdown interrupt just calls process::yield(), as if the running
process itself decided it was time to cede the CPU.
<the countdown interrupt>= case countdown_i: process::yield(); break;
Used above.
process::exec(), creates a process table entry for the new process and
starts loading the program associated with the new process. When the program
is fully loaded, the program loader performs the second step by calling
process::add().
The new process is added to the process table but not to the ready ring, so it won't be selected for execution.
<process interface definitions>=
status::responses
exec(word pindx, id & new_pid) {
process_table_entry new_pte;
new_pid = new_pte.id;
const status::responses s = disk::load(pindx, new_pid);
if (status::ok == s) {
new_pte.registers[0] = status::ok;
new_pte.registers[1] = running_process->id;
for (unsigned i = 2; i < next_register; i++)
fetch_mem(i, new_pte.registers[i], process::exec);
new_pte.registers[ps_register] = 0;
ptab.push_front(new_pte);
}
return s;
}
Definesprocess::exec(links are to index).
Yield the running process to another waiting process. Return false if there's no other waiting process (in which case the calling process continues to run). Return true if the calling process has yielded the CPU to another process. Nothing is done if the calling process would yield to itself.
<process interface definitions>+=
bool
yield() {
assert(ready_ring::ready_count() > 0);
if (ready_ring::ready_count() == 1)
return false;
context_switch(ready_ring::advance());
return true;
}
Definesprocess::yield(links are to index).Used below; previous and next definitions.
The calling process exits. The only resource held by an exiting process is its allocated storage, which is returned to the storage manager. If the disk is suspended because there's not enough space to load a program, freeing up this space may enable the disk to continue loading; poke the disk so it can check.
<process interface definitions>+=
void exit() {
debugp(dbp_execute, dbpe_format "exits.\n",
read_clock(), running_process->id);
storage::release(running_process->sc);
disk::poke();
ptab.erase(running_process);
ptab_iter new_process;
if (not ready_ring::remove_current(new_process))
new_process = idle_process;
load_cpu(new_process);
}
Definesprocess::exit(links are to index).Used below; previous and next definitions.
The running process wants to store a value in another process's slot. If the receiving proces exists and it slot is empty, go right ahead; otherwise the put call fails.
<process interface definitions>+=
status::responses
put_slot(id receiver, word value) {
ptab_iter rcvr;
if (not find_proc(receiver, rcvr))
return status::bad_id;
if (not rcvr->slot_free)
return status::no_resource;
rcvr->slot_value = value;
rcvr->slot_free = false;
rcvr->slot_sender = running_process->id;
debugp(dbp_slot, dbpe_format "sends value %d to %d.\n",
read_clock(), running_process->id, value, receiver);
return status::ok;
}
Definesprocess::put_slot(links are to index).Used below; previous and next definitions.
The running process wants to retreive a value from its slot. If the the slot is empty, the call fails; otherwise store the value and the sending process's id in the given references.
<process interface definitions>+=
status::responses
get_slot(id & sender, word & value) {
if (running_process->slot_free)
return status::no_resource;
value = running_process->slot_value;
sender = running_process->slot_sender;
running_process->slot_free = true;
debugp(dbp_slot, dbpe_format "receives value %d from sender %d.\n",
read_clock(), running_process->id, value, sender);
return status::ok;
}
Definesprocess::get_slot(links are to index).Used below; previous and next definitions.
<process interface definitions>+=
void halt(void) {
store_mem(halt_register, 0, halt);
}
Definesprocess::halt(links are to index).Used below; previous and next definitions.
Context switch to the given process.
<process procedure definitions>=
static void
context_switch(ptab_iter pti) {
debugp(dbp_execute, dbpe_format "leaves the cpu.\n",
read_clock(), running_process->id);
running_process->save_state();
load_cpu(pti);
}
Definescontext_switch(links are to index).
Loading a process into the CPU involves changing the process's state to executing and restoring the saved register state.
<process procedure definitions>+=
static void
load_cpu(ptab_iter & pi) {
pi->restore_state();
running_process = pi;
set_quantum(load_cpu);
debugp(dbp_execute, dbpe_format "runs.\n",
read_clock(), running_process->id);
}
Definesload_cpu(links are to index).Used below; previous and next definitions.
Once a new process's program as been completly loaded, the program loader calls
process::add() to finish creating the process.
<process interface definitions>+=
void add(const storage::chunk & sc, id tag) {
ptab_iter pti = get_proc(tag);
const address a = storage::chunk_address(sc);
pti->registers[base_register] = a;
pti->registers[top_register] =
a + storage::chunk_size(sc)*words_per_disk_block;
pti->registers[pc_register] = a;
pti->registers[ps_register] = 0;
pti->sc = sc;
ready_proc(pti);
}
Definesprocess::add(links are to index).Used below; previous and next definitions.
ready_proc() is called whenever the given process becomes ready to run. If
the newly ready process is the only process in the ready ring, then the idle
process is running now and can be rescheduled. If the newly ready process is
the second process in the ready queue, then the other process is the current
process and is running without a quantum; schedule one to initiate time
sharing.
<process procedure definitions>+=
static void
ready_proc(ptab_iter ptei) {
ready_ring::add(ptei);
if (running_process == idle_process) {
assert(ready_ring::ready_count() == 1);
load_cpu(ptei);
}
else if (ready_ring::ready_count() == 2)
set_quantum(ready_proc);
}
Definesready_proc(links are to index).Used below; previous and next definitions.
The process manager's done when the idle process is the only process left to manage. However, that doesn't mean execution is done because the disk may still be at work loading programs.
<process interface definitions>+=
bool done(void) {
return ptab.size() == 1;
}
Definesprocess::done(links are to index).Used below; previous and next definitions.
Process manager initialization defines and runs the idle process; the idle process is not stored in the ready ring.
<process interface definitions>+=
void init(void) {
process_table_entry idle_pte;
idle_pte.registers[pc_register] = idle_start;
idle_pte.registers[base_register] = idle_start;
idle_pte.registers[top_register] = idle_end;
idle_pte.registers[ps_register] = 0;
idle_process = ptab.insert(ptab.begin(), idle_pte);
load_cpu(idle_process);
}
Definesprocess::init(links are to index).Used below; previous and next definitions.
Store the given value in the given register of the given process's saved context.
<process interface definitions>+=
void put_register(id pid, unsigned r, word v) {
assert(r < next_register);
ptab_iter pti = get_proc(pid);
pti->registers[r] = v;
}
Definesprocess::put_register(links are to index).Used below; previous definition.
Look for a process with the given id. If found, set the given iterator reference to point to the process and return true; otherwise return false.
<process procedure definitions>+=
static bool
matching_pid(const process_table_entry pte, process::id pid) {
return pte.id == pid;
}
static bool
find_proc(process::id pid, ptab_iter & i) {
const ptab_iter & e = ptab.end();
i = find_if(ptab.begin(), e, bind2nd(ptr_fun(matching_pid), pid));
return e != i;
}
Definesfind_proc(links are to index).Used below; previous and next definitions.
Return an iterator to the process-table entry with id equal to pid; die
with an error if there's no such entry.
<process procedure definitions>+=
static ptab_iter
get_proc(process::id pid) {
ptab_iter i;
if (not find_proc(pid, i))
oops("Can't find the process with process-id %d", pid);
return i;
}
Definesget_proc(links are to index).Used below; previous definition.
<process.h>=
#ifndef _process_h_defined_
#define _process_h_defined_
#include "storage.h"
namespace process {
<process interface declarations>
}
#endif
This code is written to a file (or else not used).
<process.cc>= #include#include <list> #include <functional> #include "process.h" #include "disk.h" #include "storage.h" #include "os.h" #define dbpe_format "At time %4d, process %2d " <process macros> <process data structures> // Deja vu, c++ style using std::ptr_fun; using std::bind2nd; static void load_cpu(ptab_iter &); <the ready ring> <process procedure definitions> namespace process { <process interface definitions> }
Definesprocess.cc,process.h(links are to index).This code is written to a file (or else not used).
init() initializes the disk manager.
ihandler() handles disk interrupts.
load() reads a program from disk and schedules it for execution.
poke() wakes up the disk manager in case it's been suspended until
more resources (usually User Space) become available.
idle() returns true if the disk manager has no programs to load.
<disk interface declarations>= void init(void); void ihandler(void); status::responses load(unsigned, process::id); void poke(void); bool idle(void);
Used below.
<disk manager data structures>=
struct program_location {
unsigned start, size;
program_location(unsigned size, unsigned start)
: start(start), size(size) { }
};
static std::vector<program_location> program_index;
Definesprogram_index,program_location(links are to index).
Program load requests can be issued faster than programs can be loaded, so the exess requests have to be queued up to be handled later. A program-load request contains
pno - the program index.
pid - the associated process's identifier.
<disk manager data structures>+=
struct load_request {
unsigned pno;
process::id pid;
load_request(unsigned pno, process::id pid)
: pno(pno), pid(pid) { }
};
Definesload_request(links are to index).Used below; previous and next definitions.
The program-load requests are queued in load_requests.
<disk manager data structures>+= static std::deque<load_request> load_requests;
Definesload_requests(links are to index).Used below; previous and next definitions.
If true, a program's being read in;
<disk manager data structures>+= static bool program_being_read;
Definesprogram_being_read(links are to index).Used below; previous and next definitions.
The number of blocks to read from the disk.
<disk manager data structures>+= static unsigned blocks_to_read;
Definesblocks_to_read(links are to index).Used below; previous and next definitions.
The disk index of the next block to read.
<disk manager data structures>+= static unsigned next_block_to_read;
Definesnext_block_to_read(links are to index).Used below; previous and next definitions.
The next disk block read gets stored at the address given by
next_program_address.
<disk manager data structures>+= static address next_program_address;
Definesnext_program_address(links are to index).Used below; previous and next definitions.
The chunk of user-space storage into which the program is being read.
<disk manager data structures>+= storage::chunk program_chunk;
Definesprogram_chunk(links are to index).Used below; previous definition.
<disk interface definitions>=
void init(void) {
next_block_to_read = 0;
next_program_address = usr_base;
program_being_read = true;
disk_read(disk::init);
}
Definesdisk::init(links are to index).
Schedule a load of the program with the given index for the process with the given id. Return ok if the load was scheduled without error; otherwise return an error indication.
<disk interface definitions>+=
status::responses
load(unsigned i, process::id pid) {
if (i >= program_index.size())
return status::bad_id;
queue_request(i, pid);
return status::ok;
}
Definesdisk::load(links are to index).Used below; previous and next definitions.
If there's no programs to read or a read is in progress, there's no reason to start another read. Otherwise, there's more programs to read and reading isn't in progress, so start another read assuming there's enough User Space for the program.
<disk interface definitions>+=
void poke(void) {
if (load_requests.empty() or program_being_read)
return;
const program_location & pl = program_index[load_requests.front().pno];
program_chunk = storage::get_chunk(pl.size);
if (storage::chunk_size(program_chunk) > 0) {
program_being_read = true;
blocks_to_read = pl.size - 1;
next_block_to_read = pl.start + blocks_to_read;
next_program_address =
storage::chunk_address(program_chunk) + blocks_to_read*words_per_disk_block;
disk_read(poke);
}
}
Definesdisk::poke(links are to index).Used below; previous and next definitions.
If there's no program-load requests queued and there's no read in progress then the disk manager's idle.
<disk interface definitions>+=
bool idle(void) {
return load_requests.empty() and not program_being_read;
}
Definesdisk::idle(links are to index).Used below; previous and next definitions.
<disk interface definitions>+=
void ihandler(void) {
static bool first_time = true;
if (first_time) {
handle_index_block();
first_time = false;
}
else
handle_next_block();
}
Definesdisk::ihandler(links are to index).Used below; previous definition.
Once the disk index block lands in User Space, copy the information into
program_index so the disk manager has easy access to program information
and start loading the first program (if it exists). Invalid program sizes
panic the system; it's hard to know what to do otherwise.
<disk procedure definitions>=
static void
handle_index_block(void) {
check_disk_error(handle_index_block);
<squirrel away the index block>
program_being_read = false;
<kick off the first program, if possible>
}
Defineshandle_index_block(links are to index).
<squirrel away the index block>=
unsigned start = 1;
for (unsigned i = 0; i < words_per_disk_block; i++) {
word w;
fetch_mem(next_program_address + i, w, handle_index_block);
if ((w < 0) or (w > static_cast<word>(usr_size/words_per_disk_block)))
panic("invalid program size %d read from batch disk", w);
if (w == 0)
break;
program_index.push_back(program_location(w, start));
start += w;
}
Used above.
If there's at least one program on the batch disk, run the first program. This code pretends the idle process is doing the execing.
<kick off the first program, if possible>=
if (not program_index.empty()) {
process::id pid;
status::responses s = process::exec(0, pid);
assert(status::ok == s);
}
Used above.
Handle a disk-interrupt that's the result of reading a program block. If all the program's blocks have been read in, then the program is ready to run; hand it off to the process manager and go read then next program, if any. Otherwise, schedule a disk-read for the next block in the program.
<disk procedure definitions>+=
static void handle_next_block(void) {
check_disk_error(handle_next_block);
if (blocks_to_read-- == 0) {
<ready the new process>
}
else {
next_block_to_read--;
next_program_address -= words_per_disk_block;
disk_read(handle_next_block);
}
}
Defineshandle_next_block(links are to index).Used below; previous and next definitions.
Once the new program's been completely read into User Space, make it ready to run, pop the request from the queue, and start the next load request (if any).
<ready the new process>= assert(not load_requests.empty()); const load_request & req = load_requests.front(); process::add(program_chunk, req.pid); load_requests.pop_front(); program_being_read = false; disk::poke();
Used above.
i make by process pid. Poke the
disk manager just in case it was sittin' around, waitin' for something to do.
<disk procedure definitions>+=
static void queue_request(unsigned i, process::id parent) {
load_requests.push_back(load_request(i, parent));
disk::poke();
}
Definesqueue_request(links are to index).Used below; previous definition.
Check for a disk-io error on behalf of _caller and die if found.
<disk macro definitions>=
#define check_disk_error(_caller) \
do { \
word w; \
fetch_mem(disk_status_register, w, _caller); \
if (w != status::ok) \
panic("disk read error %d in " #_caller "()", w); \
} while (false)
Definescheck_disk_error(links are to index).
Issue a disk read on behalf of _caller.
<disk macro definitions>+=
#define disk_read(_caller) \
do { store_mem(disk_block_register, next_block_to_read, _caller); \
store_mem(disk_address_register, next_program_address, _caller); \
store_mem(disk_command_register, device::read, _caller); } while (false)
Definesdisk_read(links are to index).Used below; previous definition.
<disk.h>=
#ifndef _disk_h_defined_
#define _disk_h_defined_
#include "process.h"
#include "os.h"
namespace disk {
<disk interface declarations>
}
#endif
This code is written to a file (or else not used).
<disk.cc>=
#include <vector>
#include <deque>
#include "os.h"
#include "disk.h"
#include "storage.h"
#include "process.h"
// Deja vu c++ style.
static void queue_request(unsigned, process::id);
<disk manager data structures>
<disk macro definitions>
<disk procedure definitions>
namespace disk {
<disk interface definitions>
}
Definesdisk.cc,disk.h(links are to index).This code is written to a file (or else not used).
Correspondingly, the data representation for allocated storage is simple too. Each chunk of user space allocated to a program is represented by a pair of numbers giving the lowest user-space address and size of the chunk in disk blocks.
<storage-management interface definitions>=
typedef std::pair<address, unsigned> chunk;
inline address chunk_address(const chunk & sc) {
return sc.first;
}
inline unsigned chunk_size(const chunk & sc) {
return sc.second;
}
Defineschunk,chunk_address,chunk_size(links are to index).
The storage manage needs to be initialized with both the lowest address and size in disk blocks of the allocatable storage.
<storage-management interface definitions>+= void init(address base, unsigned size);
Used below; previous and next definitions.
Allocate a chunk of User Space containing the given number of blocks.
<storage-management interface definitions>+= chunk get_chunk(unsigned);
Used below; previous and next definitions.
And it should be possible to return an allocated chunk to the free-storage
<storage-management interface definitions>+= void release(const chunk & sc);
Used below; previous definition.
Allocatable storage is organized into a sequence of blocks, each the size of a disk block. The whole of allocatable store is represented by a bit map, where bit i represents the availability of storage block i.
base_address keeps track of the lowest address in allocatable storage.
<allocatable-storage data structures>= static std::vector<bool> free_blocks; static address base_address;
Definesbase_address,free_blocks(links are to index).
The internal representation of allocated storage is similar to the external representation. The only difference is using an index (into the bit map) instead of an address to indicate the start of the allocation. To avoid confusion between the representations, the internal representation is called an index range, and the external representation is called a storage chunk.
<allocatable-storage data structures>+= typedef std::pair<unsigned, unsigned> index_range; #define range_start(_r) (_r).first #define range_size(_r) (_r).second
Definesindex_range,range_size,range_start(links are to index).Used below; previous and next definitions.
There needs to be a way of converting between the internal and external representations of allocated storage.
<allocatable-storage data structures>+=
static index_range sc2ir(const storage::chunk & sc) {
return std::make_pair(
(storage::chunk_address(sc) - base_address)/words_per_disk_block,
storage::chunk_size(sc));
}
static storage::chunk ir2sc(const index_range & ir) {
return std::make_pair(base_address + range_start(ir)*words_per_disk_block,
range_size(ir));
}
Definesir2sc,sc2ir(links are to index).Used below; previous definition.
Return the next range of free blocks at or to the right of the block at start.
Return a range of zero length if there's no free blocks.
<storage routine definitions>=
static index_range find_free_range(unsigned size) {
for (unsigned i = 0; i < free_blocks.size() - size + 1; i++)
if (free_blocks[i]) {
bool found = true;
for (unsigned j = i + 1; (j < i + size) and found; j++)
found = free_blocks[j];
if (found)
return std::make_pair(i, size);
}
return std::make_pair(static_cast<unsigned>(0), static_cast<unsigned>(0));
}
Definesfind_free_range(links are to index).
Set the free-map bits in the index range ir to the value bv. Die if
any of the bits in the range are already equal to bv.
<storage routine definitions>+=
static void set_range(const index_range & ir, bool bv) {
const unsigned e = range_start(ir) + range_size(ir);
assert(e <= free_blocks.size());
for (unsigned i = range_start(ir); i < e; i++) {
assert(free_blocks[i] != bv);
free_blocks[i] = bv;
}
}
#define release_range(_ir) set_range(_ir, true)
#define allocate_range(_ir) set_range(_ir, false)
Definesallocate_range,release_range,set_range(links are to index).Used below; previous definition.
The storage manager is initialized with the start (lowest address) and size of the storage area to be managed. Initially, all storage is free.
<storage namespace definitions>=
void init(address start, unsigned size) {
assert(size > 0);
base_address = start;
while (size-- > 0)
free_blocks.push_back(true);
}
Definesstorage::init(links are to index).
Allocate and return an s-block chunk of User Space, or a chunk of 0 size if
there's no such chunk.
<storage namespace definitions>+=
chunk get_chunk(unsigned s) {
index_range free_range = find_free_range(s);
allocate_range(free_range);
return ir2sc(free_range);
}
Definesstorage::get_chunk(links are to index).Used below; previous and next definitions.
Return the allocated storage sc to the free list.
<storage namespace definitions>+=
void release(const chunk & sc) {
release_range(sc2ir(sc));
}
Definesstorage::release(links are to index).Used below; previous definition.
A quick check to make sure the storage-management code is working without problems.
<storage testing code>=
#ifdef TESTING_STORAGE
// g++ -DTESTING_STORAGE -g -o testing-storage -ansi -pedantic -Wall -I ../arch storage.cc && ./testing-storage
int main() {
storage::init(1024, 32);
storage::chunk sc = storage::get_chunk(32);
assert(storage::chunk_address(sc) == 1024);
assert(storage::chunk_size(sc) == 32);
storage::chunk sc2 = storage::get_chunk(1);
assert(storage::chunk_size(sc2) == 0);
storage::release(sc);
sc2 = storage::get_chunk(1);
assert(storage::chunk_size(sc2) == 1);
sc = storage::get_chunk(32);
assert(storage::chunk_size(sc) == 0);
sc = storage::get_chunk(31);
assert(storage::chunk_size(sc) == 31);
assert(storage::chunk_address(sc) == 1024 + words_per_disk_block);
}
#endif
Used below.
<storage.h>=
#ifndef _storage_h_defined_
#define _storage_h_defined_
#include <algorithm>
#include "system.h"
namespace storage {
<storage-management interface definitions>
}
#endif
This code is written to a file (or else not used).
<storage.cc>=
#include <vector>
#include "storage.h"
#include <cassert>
<allocatable-storage data structures>
<storage routine definitions>
namespace storage {
<storage namespace definitions>
}
<storage testing code>
Definesstorage.cc,storage.h(links are to index).This code is written to a file (or else not used).
<os.h>=
#ifndef _os_h_defined_
#define _os_h_defined_
#include <iostream>
#include "mass.h"
#include "utils.h"
#define fetch_mem(_a, _v, _w) \
do if (mem_fetch(_a, _v) != Memory::ok) \
panic(#_a " fetch failed in " #_w "()"); while (false)
#define store_mem(_a, _v, _w) \
do if (mem_store(_a, _v) != Memory::ok) \
panic(#_a " store failed in " #_w "()"); while (false)
#define dbp_execute dbp_f31
#define dbp_slot dbp_f30
extern unsigned read_clock(void);
#endif
Definesdbp_execute,fetch_mem,os.h,store_mem(links are to index).This code is written to a file (or else not used).
disk.cc>: D1
disk.h>: D1
interrupts.cc>: D1
os.h>: D1
process.cc>: D1
process.h>: D1
storage.cc>: D1
storage.h>: D1
This page last modified on 13 November 2004.