27 Jul
2003
27 Jul
'03
9:12 a.m.
On Sun, 27 Jul 2003, Bob Shannon wrote:
One such way:
Have some portion of the disk set aside for a fixed
number of directory
entries (the "directory").
This is what RT-11 does, a fixed number of blocks (512 bytes each) are
set aside as the directory. They are read/written in two-block units,
called directory segments, and each segment can handle up to 72 directory
entries.
Each directory entry has a certain number of characters
for a filename
(12 is good), a file type byte, a status byte, and a pointer to the
portion of the disk where the file is stored.
It might also contain the date and time the file was created, or accessed,
or updated. RT only contains the creation date. There was some thought
at one point of getting it to record creation time as well, but was never
done by DEC. Also, RT is a single-user system with the capability of
having multiple jobs running, so for tentative files (ones which haven't
closed yet), there is information kept in the entry about the channel on
which the file is open.
The file data is then stored on consecutive sectors,
with the last one or
two words (depending on word size implemented) pointing to the next
sector of the file. Zero values means "end of file".
Or, as RT did, you have the size of the file in the directory entry, so a
file exists in the contiguous blocks 'start' to 'start+size-1'.
RT also keeps track of the end of a segment so that the directory segments
can be linked in any order as files are created and deleted.
Of course, a more simple method would be to treat the entire directory as
a contiguous set of entries and then you only need an indication of the
end of the directory.
The status info can also keep track of read-only vs. read-write files,
protected files, files which should not be moved in a 'SQUEEZE' operation,
etc.
There also needs to be a map somewhere specifying which
sectors are free/used.
That can be a lot of overhead, and can take up a fair amount of disk space
depending on how it is implemented, and with each directory entry having
start and size, it isn't needed.
With the contiguous file system on RT, one *can* extend a file, though it
either takes intimate knowledge of the directory structure on the part of
the program, or extra code to open a new copy of the file (larger), copy
everything from the old version to the new, closing the old, updating the
new one and closing the new. A program with intimate knowledge of the
directory would have to find the entry for the file, check the next entry
and if it is an empty space, it could increase the file size (up to the
size of the empty) so long as it decreased the size of the empty by the
same amount. Of course if the next entry is not empty, then you have to
revert to the first method.
A program on RT can ask to create a file: 1) a specific size, or 2) half
the largest free space on the disk or the second largest free space
(whichever is greater).
RT attempted to fulfill requests for specific sizes using a best-fit
algorithm which attempted to maximize disk usage by minimizing the size of
free space between allocated files.
Megan Gentry
Former RT-11 Developer
+--------------------------------+-------------------------------------+
| Megan Gentry, EMT/B, PP-ASEL | email: mbg at world.std.com |
| Member of Technical Staff | megan at savaje.com |
| SavaJe Technologies, Inc. | (s/ at /@/) |
| 100 Apollo Drive | URL: http://world.std.com/~mbg/ |
| Chelmsford, MA 01460 | "pdp-11 programmer - some assembler |
| (978) 256 6521 (DEC '77-'98) | required." - mbg KB1FCA |
+--------------------------------+-------------------------------------+
27 Jul
27 Jul
11:08 a.m.
On Sun, 27 Jul 2003, Megan wrote:
Using one bit per byte (or word) you can store the status of up to 2048
allocation units (sectors, blocks, whatever) in 256 (8-bit) bytes of disk
space. So assuming your allocation units--let's call them "sectors"--are
256 bytes, a map taking up one sector can give the free/used status for a
2048 sector disk, or a disk with a half-megabyte capacity. Each
additional sector assigned for use in your map gives you another
half-megabyte of allocation information. Not bad.
There also
needs to be a map somewhere specifying which
sectors are free/used.
That can be a lot of overhead, and can take up a fair amount of disk space
depending on how it is implemented, and with each directory entry having
start and size, it isn't needed. With the contiguous file system on RT, one *can*
extend a file, though it
either takes intimate knowledge of the directory structure on the part of
the program, or extra code to open a new copy of the file (larger), copy
everything from the old version to the new, closing the old, updating the
new one and closing the new. A program with intimate knowledge of the
directory would have to find the entry for the file, check the next entry
and if it is an empty space, it could increase the file size (up to the
size of the empty) so long as it decreased the size of the empty by the
same amount. Of course if the next entry is not empty, then you have to
revert to the first method.
It's a LOT easier (and much more efficient) to just implement an
allocation map.
--
Sellam Ismail Vintage Computer Festival
------------------------------------------------------------------------------
International Man of Intrigue and Danger http://www.vintage.org
* Old computing resources for business and academia at www.VintageTech.com *
1:01 p.m.
It was thus said that the Great Vintage Computer Festival once stated:
On Sun, 27 Jul 2003, Megan wrote:
Using one bit per byte (or word) you can store the status of up to 2048
allocation units (sectors, blocks, whatever) in 256 (8-bit) bytes of disk
space. So assuming your allocation units--let's call them "sectors"--are
256 bytes, a map taking up one sector can give the free/used status for a
2048 sector disk, or a disk with a half-megabyte capacity. Each
additional sector assigned for use in your map gives you another
half-megabyte of allocation information. Not bad.
But at some of the sizes being used, the use of a bit map to track
free space becomes problematic---with an 8G drive, that's 2M of space just
for the bitmap, which takes time to search. And after reading
http://www.acmqueue.org/modules.php?name=Content&pa=showpage&pid=43
which discusses the problems of ever increasing disk space, I came up with
this rather "wasteful" idea which is easy, moderate in speed, and while it
wastes disk space, it does so in a rather unusual fasion.
At the location where you can freely use space (past the fixed areas, such
as boot records, etc) you set aside a few tracks worth of space for the
"master directory." It contains a pointer to the beginning of free space on
the disk (block number, cylinder, head, sector, however you store geometry
data) and then (taking an idea from Unix) a name and pointer to where the
"file" starts on the disk (realizing that a directory is just a specially
formatted file), a layout with something like:
disklocation end_of_fixed_portion;
disklocation free_space;
/* repeats to fill rest of "master directory" */
char[FILENAME] filename;
disklocation fileloc;
char[FILENAME] filename...;
disklocation fileloc...;
Then, for each file, the first sector contains information about the file,
including the name (again, for reasons that will become apparent), size of
the file, timestamp, version (more on this in a bit) and anything else you
want to fill a sector, then sequentially, the rest of the file. When you
open a file for modification (or appending data) then a "new" file is
created, with the same name, starting with the next available free space on
the disk and any data is copied. The entry in the "master directory" is
updated to the new version (along with the free_space being recalculated as
needed).
Files are always created at the end of the used space and slowly
(depending upon how much data you are saving) eats into free space. You
also get versioning (hmmm, might want to save a pointer to previous versions
in the file metadata area) and if you construct the file metadata correct,
you can even detect where files start and end if the "master directory" is
blown away. And every file is contiguous so you avoid having to seek around
on the disk. To delete a file, just remove the entry from the "master
directory"---you don't have to bother with actually removing the data from
the disk until you absolutely need it, and if you are using an 8G drive for
an older system, it will take quite a bit (if ever) to fill it.
Now, you do loose the ability to have multiple files open for writing
(appending) but is that really a consideration?
But I'm not saying you *have* to do it this way, but given the size of
modern disks nowadays (and it seems that modern disks can be used with older
hardware) it might be worth it to use a scheme like this.
-spc (Just tossing out ideas ... )
There also
needs to be a map somewhere specifying which
sectors are free/used.
That can be a lot of overhead, and can take up a fair amount of disk space
depending on how it is implemented, and with each directory entry having
start and size, it isn't needed.
1:32 p.m.
On Sun, 27 Jul 2003, Sean 'Captain Napalm' Conner wrote:
That's because it is using 512 byte allocation units. To reduce the
allocation block map size you'd need to up the allocation unit size.
At any rate, with an 8GB drive as an example, the size of the map relative
to the total disk space is negligible (a fraction of a fraction of a
fraction of a percent), and searching the allocation map can be made more
efficient using hash algorithms or simple pointers to the beginning of the
next available string of allocation blocks.
I still think it's a better and more efficient way to go, and not much
more work to code than the simpler schemes being suggested.
--
Sellam Ismail Vintage Computer Festival
------------------------------------------------------------------------------
International Man of Intrigue and Danger http://www.vintage.org
* Old computing resources for business and academia at www.VintageTech.com *
Using one bit
per byte (or word) you can store the status of up to 2048
allocation units (sectors, blocks, whatever) in 256 (8-bit) bytes of disk
space. So assuming your allocation units--let's call them "sectors"--are
256 bytes, a map taking up one sector can give the free/used status for a
2048 sector disk, or a disk with a half-megabyte capacity. Each
additional sector assigned for use in your map gives you another
half-megabyte of allocation information. Not bad.
But at some of the sizes being used, the use of a bit map to track
free space becomes problematic---with an 8G drive, that's 2M of space just
for the bitmap, which takes time to search. And after reading 
3:59 p.m.
For a tree, the directory entry points to a block
which is a list of all
the allocation map blocks for that file. So the allocation map block list
can point to up to 256 allocation map blocks, and each allocation map
block can point to up to 256 blocks (2 bytes are used to store a block
number).
It's fairly sophisticated for an 8-bit operating system.
The thing I really don't like about this approach is that any file that uses
only a few allocation units still wastes an entire sector with a mostly
empty map block. If you look around on these disks, I'll bet you find a lot
of mostly-empty map blocks, which is just wasted space.
> Using one
bit per byte (or word) you can store the status of
up to 2048
> allocation units (sectors, blocks, whatever)
in 256 (8-bit)
bytes of disk
> > space. So assuming your allocation units--let's call them
I still think it's a better and more efficient way to go, and not much
more work to code than the simpler schemes being suggested.
I agree that it's simple, but not that it's efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles. Brute force approaches will bleed time badly as the filesystem
fills. And if you free a sparse or fragmented file in a large filesystem,
it can require resetting a lot of sparse bits in that map, which can in turn
require a lot of reads and writes to the map blocks.
If the file system is of any size (in terms of number of allocation units),
I think it's more efficient to keep the maps on some kind of linked list.
My bias would be to maintain a list very similar to the DOS FAT, with a
twist. File directory entries point to the first block a file owns, and
thereafter, the allocation list points the way to the next block, or flags
that there is no next block (end of file). This is like MS/PC-DOS. But
unlike DOS, the free blocks would be chained together in the allocation list
as well. In this way, you can quickly find a free block just by popping the
head block off the allocation list. You can also quickly delete a really
large file with a long chain of allocation units simply by setting its last
allocation block pointer to the head of the free list, then resetting the
head of the free list to the first block of the file being deleted--voila.
Patrick
4:10 p.m.
There was always the OS-9 approach (IIRC), that used the last two bytes of
each sector to link to the next sector. Worked well enough, although not
dealing with even powers of two can be a pain.
--John
On Sunday 27 July 2003 23:55 pm, Patrick Rigney wrote:
[snip]
For a tree,
the directory entry points to a block which is a list of all
the allocation map blocks for that file. So the allocation map block
list can point to up to 256 allocation map blocks, and each allocation
map block can point to up to 256 blocks (2 bytes are used to store a
block number).
It's fairly sophisticated for an 8-bit operating system.
The thing I really don't like about this approach is that any file that
uses only a few allocation units still wastes an entire sector with a
mostly empty map block. If you look around on these disks, I'll bet you
find a lot of mostly-empty map blocks, which is just wasted space.
>
Using one bit per byte (or word) you can store the status of
up to 2048
> allocation units (sectors, blocks, whatever)
in 256 (8-bit)
bytes of disk
> > space. So assuming your allocation units--let's call them I still think it's a better and more
efficient way to go, and not much
more work to code than the simpler schemes being suggested.
I agree that it's simple, but not that it's efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles. Brute force approaches will bleed time badly as the filesystem
fills. And if you free a sparse or fragmented file in a large filesystem,
it can require resetting a lot of sparse bits in that map, which can in
turn require a lot of reads and writes to the map blocks.
If the file system is of any size (in terms of number of allocation units),
I think it's more efficient to keep the maps on some kind of linked list.
My bias would be to maintain a list very similar to the DOS FAT, with a
twist. File directory entries point to the first block a file owns, and
thereafter, the allocation list points the way to the next block, or flags
that there is no next block (end of file). This is like MS/PC-DOS. But
unlike DOS, the free blocks would be chained together in the allocation
list as well. In this way, you can quickly find a free block just by
popping the head block off the allocation list. You can also quickly
delete a really large file with a long chain of allocation units simply by
setting its last allocation block pointer to the head of the free list,
then resetting the head of the free list to the first block of the file
being deleted--voila.
Patrick 
4:30 p.m.
J.C. Wren wrote:
There was always the OS-9 approach (IIRC), that used
the last two bytes of
each sector to link to the next sector. Worked well enough, although not
dealing with even powers of two can be a pain.
I thought OS/9 used a unix like file system. Flex
( http://www.evenson-consulting.com/flexusergroup/default.htm )
does use the linked sector format. However remember 32k bytes
for programs was a large amount of memory back around 1975 and some
space still left for the OS for the people that never knew small
systems. CAN you say 8k basic :)
4:50 p.m.
Yea, I think you're right. I knew it was one of the 6800 or 6809 OS's, but
it's been so long, I couldn't remember for sure. Either one was still a
pretty decent OS, in my book. Prolly better than CP/M 2.2.
--John
On Monday 28 July 2003 00:22 am, ben franchuk wrote:
J.C. Wren wrote:
There was always the OS-9 approach (IIRC), that
used the last two bytes
of each sector to link to the next sector. Worked well enough, although
not dealing with even powers of two can be a pain.
I thought OS/9 used a unix like file system. Flex
( http://www.evenson-consulting.com/flexusergroup/default.htm )
does use the linked sector format. However remember 32k bytes
for programs was a large amount of memory back around 1975 and some
space still left for the OS for the people that never knew small
systems. CAN you say 8k basic :) 
6:08 p.m.
J.C. Wren wrote:
There was always the OS-9 approach (IIRC), that used
the last two bytes of
each sector to link to the next sector. Worked well enough, although not
dealing with even powers of two can be a pain.
--John
On Sunday 27 July 2003 23:55 pm, Patrick Rigney wrote:
> snip
>
>
>
>
>>I still think it's a better and more efficient way to go, and not much
>>more work to code than the simpler schemes being suggested.
>>
>>
>I agree that it's simple, but not that it's efficient. For small micros,
>finding the first "0" bit in an arbitrarily long bit string takes a few
>cycles. Brute force approaches will bleed time badly as the filesystem
>fills. And if you free a sparse or fragmented file in a large filesystem,
>it can require resetting a lot of sparse bits in that map, which can in
>turn require a lot of reads and writes to the map blocks.
>
>Snip
>
Your lack of understanding dates you, kid-o, say hi to MSVC++ and VBASIC
Jim Davis
6:23 p.m.
Jdavis wrote:
J.C. Wren wrote:
> There was always the OS-9 approach (IIRC), that used the last two
> bytes of each sector to link to the next sector. Worked well enough,
> although not dealing with even powers of two can be a pain.
...
Your lack of understanding dates you, kid-o, say hi to
MSVC++ and VBASIC
Jim Davis
why the snide remark? other than asserting smirking superiority, what
information were you intending to supply to the roughly 650 members of
this mailing list?
no thanks.
28 Jul
28 Jul
6:05 a.m.
Your lack of understanding dates you, kid-o, say hi to
MSVC++ and VBASIC
Jim Davis
Jim, I hope you weren't addressing me. I've got 25 years behind me as a
professional software engineer, more as a hobbyist, with a lot yet to learn,
eagerly, which is why I'm here. I've seen junior guys fresh out of school
rip an established design to pieces, and the most senior engineering fellow
send an entire project permanently down a hole by missing simple details.
The two biggest lessons I've learned are (1) keep an open mind, because the
moment you think you know everything is the moment someone comes along and
hands you your ar**, and (2) everyone, regardless of experience, has
something to offer and you can learn from it. Hopefully that comment wasn't
the best you've got.
Regardless of who you were addressing, if you DO have something material to
offer, please explain it, because I'd really like to know and hear your
ideas. But if you're just going to sit out there and take pot-shots, I for
one won't give you credit for knowing jack. --Patrick
27 Jul
27 Jul
4:36 p.m.
On Sun, 27 Jul 2003, Patrick Rigney wrote:
You would just look for the first byte that is not a 255.
The thing I really don't like about this approach
is that any file that uses
only a few allocation units still wastes an entire sector with a mostly
empty map block. If you look around on these disks, I'll bet you find a lot
of mostly-empty map blocks, which is just wasted space.
I agree, but then the idea, I imagine, was that ever larger storage
mediums would render this concern obsolete. The linked-list approach in
DOS 3.3 was much more efficient.
I still think
it's a better and more efficient way to go, and not much
more work to code than the simpler schemes being suggested.
I agree that it's simple, but not that it's efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles. Brute force approaches will bleed time badly as the
filesystem
fills. And if you free a sparse or fragmented file in a large filesystem,
it can require resetting a lot of sparse bits in that map, which can in turn
require a lot of reads and writes to the map blocks.
I don't share the concern. With efficient coding, the overhead is
negligible.
--
Sellam Ismail Vintage Computer Festival
------------------------------------------------------------------------------
International Man of Intrigue and Danger http://www.vintage.org
* Old computing resources for business and academia at www.VintageTech.com *
28 Jul
28 Jul
6:22 a.m.
I agree that
it's simple, but not that it's efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles.
You would just look for the first byte that is not a 255. 
7:06 a.m.
At 11:18 AM 7/28/03 -0700, Patrick wrote:
That's absolutely true, you can do that, and from there it's fairly
straightforward. But here's what I'm thinking. Let's say you have just a
1.44MB floppy, with a 512 byte sector size. A convenient allocation size
might be one sector, because you can easily fit the total number of
allocation units (2880) into a 16-bit unsigned integer (that which is used
in the file link blocks). That takes about 360 bytes to store on disk,
which fits nicely into a single sector as well. So far, so good.
But now let's say you go to an 80MB partition with 512 byte sectors. You
then have approximately 163,840 allocation units (not discounting any space
used for boot and other common structures). That's too many for a 16-bit
word, so you decide to make your allocation units four sectors. That means
you have 40,960 allocation units, each of which is 2K in size. Your
free-space bitmap, then, would be 5,120 bytes, which takes 10 sectors or 3
allocation units to store depending on your implementation choices, but
let's just go with the smaller 10-sector size.
I'm thinking about two things: first, trying to keep the entire volume
bitmap in memory chews up almost 5K of RAM, and that's probably not good for
an 8-bit machine, at least, it's not sufficiently memory-efficient, IMO.
Second, if you decide then that you'll only deal with one sector of it at a
time to save RAM, you may have to read-then-write juggle those ten sectors a
lot. If you do a linear search for a free block, it may be that you can rip
through the 255-valued bytes quickly, but they have to be in RAM, so you may
have to do several reads to find what you want, which saps time.
I wonder if it really would sap a lot of time. Modern IDE drives have
large cache buffers so I would think that system could very likely read the
data from the buffer. I'm thinking that as slow as these old systems are
and as fast as the modern drives are that it would be better to use a
simple and fast algorithim even if it means more drive accesses.
Joe
I agree that it's simple, but not that it's
efficient. For small micros,
finding the first "0" bit in an arbitrarily long bit string takes a few
cycles.
You would just look for the first byte that is not a 255.
7:31 a.m.
lot. If you do
a linear search for a free block, it may be that
you can rip
through the 255-valued bytes quickly, but they
have to be in
RAM, so you may
have to do several reads to find what you want,
which saps time.
I wonder if it really would sap a lot of time. Modern IDE drives have
large cache buffers so I would think that system could very
likely read the
data from the buffer. I'm thinking that as slow as these old systems are
and as fast as the modern drives are that it would be better to use a
simple and fast algorithim even if it means more drive accesses.
Joe
8:26 a.m.
At 12:27 PM 7/28/03 -0700, you wrote:
Joe, that is absolutely true. I was not considering the speed or caching
abilities of the drive itself. I was thinking more generically of an
approach that would work OK for both a sluggish floppy and a faster hard
disk without software changes. Additional accesses penalize floppies, but
that may not be an issue for Bob. --Patrick
I'm also one of the people that's tinkering with the HP 1000s which are
the target systems.
I think Bob only plans on using this for a hard drive. AFIK there's no
plans to develope a floppy drive systems for these computers (although it
would be nice).
The biggest problem that I see here is that Bob wants to be able to use
this OS on systems that have as little as 16k words but still use LARGE
modern drives. I'm not sure that's practicle without a lot of wasting a lot
of drive space. But I frankly don't think wastage is a problem. There's
simply not a lot of software for this OS and I don't think we'd ever use
more than a tiny fraction of the drive. Therefore my vote ould be for
program size, speed and drive space effientcy in that order.
FWIW A FAT table and MS-DOS file system would be nice for compatibility
but without a floppy drive it would probably be a waste. You COULD put the
drive into a PC and transfer files but I don't think that's likely.
Joe
lot. If you do a linear search for a free block, it
may be that
you can rip
through the 255-valued bytes quickly, but they
have to be in
RAM, so you may
have to do several reads to find what you want,
which saps time.
I wonder if it really would sap a lot of time. Modern IDE drives have
large cache buffers so I would think that system could very
likely read the
data from the buffer. I'm thinking that as slow as these old systems are
and as fast as the modern drives are that it would be better to use a
simple and fast algorithim even if it means more drive accesses.
Joe
11:53 a.m.
The biggest problem that I see here is that Bob
wants to be able to use
this OS on systems that have as little as 16k words but still use LARGE
modern drives. I'm not sure that's practicle without a lot of wasting a lot
of drive space. But I frankly don't think wastage is a problem. There's
simply not a lot of software for this OS and I don't think we'd ever use
more than a tiny fraction of the drive. Therefore my vote ould be for
program size, speed and drive space effientcy in that order.
So what about the archiving file system I outlined? Files are stored
contiguously, and if you want to append to a file, it's copied to the end of
the used space, given a new time stamp, and it goes from there?
-spc (And if you don't want to set aside a fix amount for the master
directory, have the directory at one end of the drive, and pull
the free space from the other end, where they would meet in
the middle ... )
1:45 p.m.
Sean 'Captain Napalm' Conner wrote:
One plan we are looking at does basically this same thing.
Files will be allocated a fixed ammount of space, similar to a track per
file as in Northstar DOS.
A file can be smaller that its allocated space, and grow. If the file
needs to be larger than its allocated
space, it moves to the end of the disk, and a second file is created as
an 'extent' to the first file.
Files are always linear, so the HP DCPC control code remains simple.
The biggest
problem that I see here is that Bob wants to be able to use
this OS on systems that have as little as 16k words but still use LARGE
modern drives. I'm not sure that's practicle without a lot of wasting a lot
of drive space. But I frankly don't think wastage is a problem. There's
simply not a lot of software for this OS and I don't think we'd ever use
more than a tiny fraction of the drive. Therefore my vote ould be for
program size, speed and drive space effientcy in that order.
So what about the archiving file system I outlined? Files are stored
contiguously, and if you want to append to a file, it's copied to the end of
the used space, given a new time stamp, and it goes from there?
-spc (And if you don't want to set aside a fix amount for the master
directory, have the directory at one end of the drive, and pull
the free space from the other end, where they would meet in
the middle ... )
A directory of logical volumes on disk can be held in the last directory
entry of the 'boot' file system. All
DOS disk calculations within a volume are relative to the directory
block, so be changing one disk address
value and treating logical volumes as 'directories'. Actually each
'directory' is its own file system.
This way large volumes can support subdirectory-like functionality, and
the same exact code is used to
support disks from 2.5 mb up to 8 gb.
I think people had to think their software designs through more
carefully when they only has 32K. Now that
a machine with 32 meg is frowned upon, file systems have become a very
different thing in terms of implementation.
2:08 p.m.
It was thus said that the Great Bob Shannon once stated:
Files will be allocated a fixed ammount of space, similar to a track per
file as in Northstar DOS.
A file can be smaller that its allocated space, and grow. If the file
needs to be larger than its allocated
space, it moves to the end of the disk, and a second file is created as
an 'extent' to the first file.
Files are always linear, so the HP DCPC control code remains simple.
I have a few questions then. 1) What is the smallest amount of data that
can be transferred? The largest amount? Any restrictions on data
placement? (for instance, on old PCs, you could only use the lower 1M (16M
for 286 or better) of RAM, the smallest amount was 512 bytes, largest 64k
(128k for 286 or better) but you could not cross a 64k boundary) How much
space can you set aside for disk buffering?
I think people had to think their software designs
through more
carefully when they only has 32K. Now that
a machine with 32 meg is frowned upon, file systems have become a very
different thing in terms of implementation.
Another question: about how big do you expect the average file to be?
And what type of files do you expect there to be?
-spc (Interesting problem ... )
30 Jul
30 Jul
5:32 p.m.
Sean 'Captain Napalm' Conner wrote:
Your getting to the real issues here!
First, the average file size, I do not beleive we really know at this
point. Lets look at the file types first, and
then look at the relative file sizes.
The first, and most primative file type the O/S understands is an ABS
binary image. This is a variable length
string of 8-bit bytes in a blocked, raw binary format with checksums and
block addresses. These images describe
an absolute addressed binary image which cannot hold more than 32K
words. So the maximum practical ABS
file size is somewhere around 75 kb.
But ABS images must be processed on the fly, during load time, so DMA is
not an option. The result is that ABS
files are not a practical disk format. But ABS is the format
HPdistributed their early software in (like HP Basic, etc).
ABS is really a paper-tape format, best used with hardware emulators as
ultra-fast boot devices.
Once an ABS image is loaded into memory, it can be saved directly to
disk in a raw binary format for fast DMA
transfers. These ram binary image files are never longer than 32K
words. This is the disk boot format.
So once you boot either an ABS image from a paper tape reader emulator,
or a raw binary file from a disk device
and you have the programming language / operating system running we have
a bare-bones system with free memory.
At this point you can load IPL source code into the comand line
interpreter and 'compile' definitions in the dictionary
to provide new keywords for hardware device drivers, floating point
package, or other optional and customized functions
to taylor the running image for your application. So once the engine is
loaded into memory and running it needs to
read a series of 'library' files. These are ASCII IPL source code files
and are generally a few K bytes at most.
It may be practical to place many named definitions inside one disk
'file', and then call them by name from a common
library file.
Of course we want to support general data files for the programmers use
at well.
I have a few questions then. 1) What is the smallest amount of data that
can be transferred? The largest amount? Any restrictions on data
placement? (for instance, on old PCs, you could only use the lower 1M (16M
for 286 or better) of RAM, the smallest amount was 512 bytes, largest 64k
(128k for 286 or better) but you could not cross a 64k boundary) How much
space can you set aside for disk buffering?
1. The smallest ammount of data read or written to disk is 1024 words.
This value is used due to the HP 1000's paged memory design on all
CPU's, as well as the virtual memory
scheme on the late model 21MX processors. All disk drivers 'translate'
hardware tracks and sectors into
1024 word 'blocks', so all O/S level disk address calculations are
indentical to VM page address calculations.
(in fact, they are the very same routines)
Data is always word-aligned, although 21MX CPU's do support byte
(limited) addressing.
As for 'placement' issues, HP's can only 'see' the current 1024 word
'page', and page zero, not unlike a 16-bit
PDP-8 with larger pages and extra registers. There are only 32 pages at
a time, but you can have 2 mappings
of physical memory (up to 1024 K words) to logical memory (the 32 pages).
Transfers to and from disk do not need to be block boundry aligned.
The current plan (quickly evolving) is to support two disk buffers, each
of 1024 words. Only two files can
be attached at one time without thrashing, but a rather unique method of
saving the file access pointer for each
file in the directory structure. This was a file can be opened,
accessed, then closed, and re-opened at the point of
last access + 1, or you can open the file at the start and seek to any
point in the tranditional method.
I think people
had to think their software designs through more
carefully when they only has 32K. Now that
a machine with 32 meg is frowned upon, file systems have become a very
different thing in terms of implementation.
Another question: about how big do you expect the average file to be?
And what type of files do you expect there to be?
-spc (Interesting problem ... )
28 Jul
28 Jul
2:31 p.m.
At 07:49 PM 7/28/03 -0400, Bob wrote:
That sounds fine to me.
Joe
The biggest
problem that I see here is that Bob wants to be able to use
this OS on systems that have as little as 16k words but still use LARGE
modern drives. I'm not sure that's practicle without a lot of wasting a lot
of drive space. But I frankly don't think wastage is a problem. There's
simply not a lot of software for this OS and I don't think we'd ever use
more than a tiny fraction of the drive. Therefore my vote ould be for
program size, speed and drive space effientcy in that order.
So what about the archiving file system I outlined? Files are stored
contiguously, and if you want to append to a file, it's copied to the end of
the used space, given a new time stamp, and it goes from there?
1:56 p.m.
Joe wrote:
I'm also one of the people that's tinkering with the HP 1000s which are
the target systems.
I think Bob only plans on using this for a hard drive. AFIK there's no
plans to develope a floppy drive systems for these computers (although it
would be nice).
The biggest problem that I see here is that Bob wants to be able to use
this OS on systems that have as little as 16k words but still use LARGE
modern drives. I'm not sure that's practicle without a lot of wasting a lot
of drive space. But I frankly don't think wastage is a problem. There's
simply not a lot of software for this OS and I don't think we'd ever use
more than a tiny fraction of the drive. Therefore my vote ould be for
program size, speed and drive space effientcy in that order.
FWIW A FAT table and MS-DOS file system would be nice for compatibility
but without a floppy drive it would probably be a waste. You COULD put the
drive into a PC and transfer files but I don't think that's likely.
Joe
Actually, the DOS code will support:
HP 7900A, CS/80, and my ATA disk hack at first. MAC support could be
developed, but I know of no
operational hardware available for development. Having redone the ATA
hack in 5 chips, I have no desire
for any HP drives other than CS/80.
I would love to support the HP 9885M floppy disk, I have the hardware,
but very limited and incomplete
programming information. I will take another stab at programming this
beast, as I've found that it can format
totally blank media after all.
In terms of memory, file system access is going to require 32K words of
memory, and there is a very real
possibility that DMS (HP 21MX only) will be required. It might be
possible to really trim down the dictionary
and run DOS functions in less than 32K, but it would not be very practical.
The reason for this, is that using DMS we can read an ABS program like
HP BASIC or HP ALGOL into
virtual memory, then swap those pages into the SYSTEM map from 0 to 31K
words with the top 1K used
for a block swapping loader, so when HP BASIC terminates your right back
inside your running IPL program.
This was IPL programs can load and run existing HP software under
program control, being a 'real' O/S.
This actually takes a lot less code than conventional disk swapping, and
its vastly faster too. It makes very good
use of HP's DMS architecture.
12:58 p.m.
Joe wrote:
<snip>
I wonder if it really would sap a lot of time. Modern IDE drives have
large cache buffers so I would think that system could very likely read the
data from the buffer. I'm thinking that as slow as these old systems are
and as fast as the modern drives are that it would be better to use a
simple and fast algorithim even if it means more drive accesses.
Joe
Hold on here, the IDE drive (technically, the ATA drive, but nevermind
that...) may have a buffer, this
it quite irrelevant here.
As soon as you hook your fast ATA disk up to a classic CPU like an
HP1000 or an Imlac, you now have
a slow disk system by any modern standard.
Also, if the classic CPU is running the disk access code, there is
another layer of performance hit.
Another little detail of reality...
Some HP disk systems force the use of DCPC (DMA) transfers. The boot
mechanisim also forces the
use of some linear files, files that use contiguous sectors on disk to
store boot images.
If some FAT system is used that allows non-linear files, then the code
to control the DCPC logic has to
deal with 2 cases, simple linear file transfers, and non-linear file
transfers performed as a series of smaller
DCPC block transfers.
This is complexity I don't need, especially since many other disks don't
demand DCPC transfers.
Lets be a bit more analytical here, clearly people have deep seated
emotions on the subject. This only
complicates objective engineering.
From all I've read so far, the only advantages FAT based approaches
offer are:
1. Allowing efficient disk space use by implementing non-linear files.
2. Easing disk optimization tricks.
But non-FAT based DOS's have been implemented, and once SQUEEZED, appear
to be just as efficient
as other schemes. Yes, fragmentation is an issue, but this is more
easily solved (via SQUEEZE) then the code
needed to maintain the FAT.
Simplicity suggests that if its not needed, its not implemented.
Traditional file systems tend to need to be tweaked in different ways
(FAT sizes, cluster sizes, etc) for different
kinds of media. I think there is a very different way to approach all
this, and have a single scheme for all sizes
of disks that will deliver a common level of efficiency in all cases.
Think this is impossible? FORTH's block address scheme works. The
trick is to very carefully adopt some
features of other file systems while challenging their fundemental
assumptions and take only what makes sense.
I think there is a lot to be learned from vintage file systems like
TSS-8, RT-11, Northstar DOS, etc.
This discussion is fascinating and very helpful, but not being familiar
with the guts of the variety of DOS's being
thrown into the duscussion I'd really appreciate it if we could be a
little more clear on the specific advantages
each implementation choice implies.
There seems to be a real lack of any objective anatomical dissection of
different methods in print, at least in a
readable (approachable) form. This is proably the only place such a
discussion could ever take place, as so
few people new to file system internals ever develop new approaches.
What was the last 'really different' way
to store stuff on disk?
29 Jul
29 Jul
3:56 p.m.
On Mon, 28 Jul 2003, Bob Shannon wrote:
But non-FAT based DOS's have been implemented, and
once SQUEEZED, appear
to be just as efficient
as other schemes. Yes, fragmentation is an issue, but this is more
easily solved (via SQUEEZE) then the code
needed to maintain the FAT.
Ok, so when it comes time to do a SQUEEZE, how long is it going to take,
and on a sufficiently large drive with very large allocation units, how
are you going to do an effective SQUEEZE with only 16K words?
Simplicity suggests that if its not needed, its not
implemented.
There is the possibility that this is being over-simplified.
I think there is a lot to be learned from vintage file
systems like
TSS-8, RT-11, Northstar DOS, etc.
Me too: how NOT to design an OS :)
There seems to be a real lack of any objective
anatomical dissection of
different methods in print, at least in a
readable (approachable) form. This is proably the only place such a
discussion could ever take place, as so
few people new to file system internals ever develop new approaches.
There have probably been dozens of books covering this topic written
throughout the 1960s, 1970s and into the 1980s. One such title that comes
up from my current catalog is titled _File Structures For On-line Systems_
by David Lefkovitz (1969). I can guarantee there are many more.
--
Sellam Ismail Vintage Computer Festival
------------------------------------------------------------------------------
International Man of Intrigue and Danger http://www.vintage.org
* Old computing resources for business and academia at www.VintageTech.com *
7597
days inactive
7601
days old
24 comments
11 participants
participants (11)
-
bfranchuk＠jetnet.ab.ca -
bshannon＠tiac.net -
frustum＠pacbell.net -
jcwren＠jcwren.com -
jpdavis＠gorge.net -
mbg＠TheWorld.com -
patrick＠evocative.com -
rigdonj＠cfl.rr.com -
spc＠conman.org -
vance＠neurotica.com -
vcf＠siconic.com