Menu

Storia del Q/86-DOS (QDOS History)

86dosTra i 1979 e il 1980 la piccola  Seattle Computer Products (SCP) aveva iniziato a commercializzare sistemi personal a 16 bit basati sulla nuova CPU Intel, fornendoli con il Microsoft Basic in versione “stand alone”, in grado di funzionare senza sistema operativo e gestire direttamente i dischi.

Questa scelta era ottimale per il BASIC in se, ma non sufficientemente flessibile per la realizzazione di software complessi come, ad esempio, i Word Processor. Così SCP comincia a guardare con attenzione Digital Research che annuncia, per la fine del 1979, la disponibilità del CP/M-86, ovvero la versione per x86 del suo famoso sistema operativo.

I continui ritardi, però, spingono SCP a pensare alla realizzazione di un proprio OS e chiedono a Tim Paterson (dipendente della società) di mettersi al lavoro. Il tecnico definisce un piano di sviluppo di ben due sistemi operativi: uno single-user ed uno multi-user, entrambi condividenti la stessa API. Il piano contempla, inoltre, la possibilità di interrompere il progetto se il CP/M-86 fosse divenuto disponibile, visto che la SCP era un’azienda di hardware e tale voleva restare.

Così il progetto parte. Lo step iniziale è quello di realizzare un primo embrione del nuovo OS, definito “quick and dirty”, da cui il primo nome Q-DOS, che diventerà 86-DOS o anche SCP-DOS.

i8086

Intel 8086

La scelta del File System

cromemcoPaterson non aveva grandi esperienze nel campo dello sviluppo di sistemi operativi: principalmente si era occupato di hardware, sviluppando per la CPU 8086 un assembler e un debugger, da fornire con i personal SCP. In fatto di utilizzo diretto, la sua esperienza era legata al North Star DOS e al Cromemco CODS, un sistema CP/M like utilizzato presso la società.

La prima sfida da affrontare è quella della scelta del File System, avendo come obiettivo quello di privilegiare quanto più possibile le performance. A tal fine Paterson effettua una serie di analisi e misurazioni su quattro candidati:

  • Un file system con allocazione contigua dei file, sulla falsa riga di quello utilizzato dal North Star DOS e dall’UCSD p-system. In questo caso il file occupa una serie consecutiva di settori e la directory che lo contiene deve terner conto solo del settore iniziale e della lunghezza del file stesso. La velocità di accesso ai dati è praticamente identica sia nel caso sequenziale che nel caso randomatico. Il grande problema di questo file system risiede nel fatto che un file, una volta scritto, non può più crescere, costringendo il sistema a spostarlo in un'altra locazione se si ha necessità di ciò e lasciando un “buco” di allocazione. Periodicamente è necessario ricompattare (deframmentare) il tutto per poter ricompattare lo spazio. Paterson scarta subito questa tipologia di file system perché ritiene che sia troppo vincolante e abbia più svantaggi che vantaggi;
  • Il secondo candidato è il file system UNIX che utilizza un approccio sicuramente più intelligente: invece di memorizzare il primo settore e la lunghezza del file, memorizza una tabella per ogni file in cui vengono mappati i settori che contengono i vari pezzi del file stesso. Se il file diventa troppo grande, alla prima tabella se ne aggiunge una seconda e la prima conterrà un riferimento non più a settori con parti del file ma a settori che a loro volta mappano i settori che contengono le parti del file. Se il file continua a crescere viene aggiunta una terza tabella e così via. Nonostante questo metodo permetta di scrivere i file in settori non contigui, al crescere del file, la lettura non sequenziale si rallenta sempre più perché richiede n-letture su disco, dovendo saltare tra le varie tabelle per identificare i settori che contengono i dati;
  • Il terzo candidato è il file system del CP/M che non salva i file utilizzando i singoli settori, ma utilizzando raggruppamenti di essi chiamati “cluster” o “unità di allocazione”. Il CP/M originale era disegnato per i floppy da 8”, che disponevano di 2002 settori in grado di memorizzare 128bit ciascuno. L’OS DRI li raggruppa in cluster da 8 settori (ottenendo 1 Kb di spazio) potendo così complessivamente contare su circa 250 cluster in tutto. Ogni cluster è identificato con un solo byte e la tabella delle directory è composta da 16 elementi, rendendo veloce ed efficiente ogni tipo di lettura per file fino a 16Kb. Il problema si verifica quando il file superava, anche di poco, i 16Kb, richiedendo l’allocazione completa di un nuovo cluster che con il primo non avevano alcun legame se non il nome e un numero per identificare quale sezione del file contenessero (definito “extent”). Ciò rallenta notevolmente le performance, soprattutto nel caso della lettura non lineare, poiché costringe il sistema a continue letture per identificare l’extent corretto;
  • Il quarto ed ultimo candidato è il File Allocation Table (FAT), usato dal Basic “stand-alone” di Microsoft. Questo sistema, a differenza degli altri, separa la gestione del contenuto della directory (nome, dimensione del file, ecc) da come i dati  vengono salvati sul disco. Come il CP/M il disco è diviso in cluster da 1Kb, così da avere circa 250 cluster sui floppy da 8”. Per ogni cluster è richiesto un entry di 1 byte, e l’intera tavola di allocazione può essere registrata in 2 settori da 128byte, con il grande vantaggio di poter mantenere l’intera tabella in memoria, cosa non così banale vista la scarsa disponibilità di Ram all’inizio degli anni ’80. Il principale vantaggio del FAT è la possibilità di trovare i dati richiesti senza dover mai fare una lettura preventiva su disco, sopperendo all’impossibilità di scorrere in modo non lineare con il suo completo caricamento in memoria, rendendo così il suo scorrimento oltre 100 volte più veloce di una singola lettura di un settore del floppy. Inoltre la dimensione del fs mappa esattamente la dimensione del disco, evitando così di sprecare spazio all’intero di cluster occupati solo a metà.

La scelta di Paterson ricade sul fs FAT, tra l’altro, come visto, già utilizzato da SCP attraverso il Basic Microsoft, anche se salta subito all’occhio che limitare il numero di cluster ad un solo byte, potendone così gestire al massimo 256 cluster è una scelta azzardata, soprattutto in previsione della crescita dello spazio dei dischi. Così lo spazio di allocazione dedicato alla tabella di allocazione viene portato a 12bit (FAT12, 1byte + 4bit), consentendo di avere fino a 4000 cluster.

Con la dimensione dei cluster a 16Kb, è possibile gestire fino a 64Mb, inoltre è comunque possibile settare la dimensione del cluster a 32Kb per raggiungere i 128Mb, anche se a scapito dello spazio residuo per ogni cluster non completamente utilizzato. Queste dimensioni, per l’epoca, erano assolutamente stratosferiche, ma negli anni ’90 divennero irrisorie, costringendo Microsoft a portare l’entry della FAT a 16bit e poi a 32bit, anche se ciò ha reso impossibile mantenere l’intera tabella di allocazione in memoria, vanificando i vantaggi prestazionali alla base della scelta di Paterson.

 

Le Performance

Sui sistemi che Paterson aveva avuto l’opportunità di provare, era subito emerso l’enorme divario di performance nelle operazione di I/O. Il North Star DOSera in grado di caricare più velocemente file piccoli (16 Kb, esattamente la dimensione di un “extent” del CP/M), rispetto al CP/M e al Cromemco CDOS.

Il sistema traeva il massimo dal proprio hardware: ogni traccia del disco era composta da 10settori di 256byte l’uno l’OS era in grado di leggerli tutti e caricarli in memoria senza interruzione. Per leggere un file di 8KB erano necessari 32 settori e il sistema garantiva la loro registrazione in 4 tracce consecutive. Con il passaggio da una traccia all’altra, l’OS perdeva l’entry di start del settore successivo ed era necessario attendere l’intera rotazione del disco, un fenomeno noto come interleaving. In particolare fondamentale era il fattore di interleaving, ovvero il numero dei settori del disco rigido da saltare per leggere consecutivamente tutti quelli della traccia, dipendente strettamente dalle caratteristiche prestazionali del disco rigido stesso, cioè dalla velocità di rotazione del disco, dal movimento dei seeker con le relative testine e dalla velocità di lettura-scrittura della stessa testina.

Tale fenomeno si verificava poiché inizialmente le CPU compivano queste azione ad una velocità inferiore della velocità di lettura/scrittura sul disco rigido, quindi, una volta elaborati i dati provenienti da un settore, la testina si trovava già oltre l'inizio del settore successivo. Alternando i settori in modo regolare e leggendoli secondo lo specifico interleaving factor, si velocizzava il disco rigido e il calcolatore (i moderni dischi rigidi non necessitano di interleaving).

In sostanza per leggere 8Kb erano necessari 6,2 rotazioni (incluse quelle per l’interleaving) e su un floppy da 5” era necessario un tempo di 1,3 secondi, visto che era possibile effettuare in un secondo 5 rotazioni complete del disco.

Nel caso del CP/M e del CDOS, le tracce dei dischi erano formate da 26 settori da 128byte. Il CP/M in particolare non era in grado di leggere tutti i settori in una sola passata, ma con una frequenza di 6 per volta. Sempre nel caso di un file di 8Kb, l’occupazione era di circa 2 tracce e 1/2 che, considerando i 6 settori leggibili per rotazione, le letture richiedeva in totale 17 rotazioni complete del disco (incluse due rotazioni di interleaving), portando a 2,8secondi il tempo necessario per la lettura completa del file. In sostanza il doppio richiesto dal North Star System, nonostante l’hardware di riferimento di quest’ultimo fosse decisamente meno performante.

Uno dei motivi della lentezza del CP/M era dovuto alle scarse performance del BIOS (Basic Input/Output System) che, per la lettura di un singolo settore, necessitava di ben 5 richieste separate: Selett Disk, Set Track, Set Sector, Set Memory address e, finalmente, Read Sector. In realtà non era chiaro se tutti e cinque i comandi fossero richiesti per tutte le letture anche se l’indirizzo era lo stesso.

Nel caso del Q-DOS, Paterson chiama le interfacce di basso livello I/O System e si sforza di non farle diventare un collo di bottiglia. Ogni lettura doveva essere effettuata tramite una sola richiesta, e la richiesta stessa deve poter essere fatta per un numero qualsiasi di settori. Ciò implicava maggior lavoro per l’I/O System (rispetto al CP/M), ma permetteva di massimizzare le performance, portando a 0,8 secondi il tempo necessario per la lettura di un file di 8Kb da dischi di 8 pollici, grazie anche al formato di memorizzazione senza interleave.

Nel 1983 Paterson fonda la Falcon Technology che realizza il primo hard disk per PC a non necessitare di interleave (la società fu poi acquisita da Microsoft, soprattutto per riportare Paterson a lavorare sul DOS). Quando gli hard-disk cominciarono ad avere la cache, l’interleave fu superato e molte delle questioni affrontate nella progettazione del BIOS – I/O System diventano superflue spostandosi su altri fronti.

Altro aspetto fondamentale da analizzare era la gestione della cache. Il sistema integrato nel CP/M obbligava l'utente ad effettuare manualmente la sincronizzazione dei dati tra disco e cache, pena il ritrovarsi file completamente corrotti.

Paterson sceglie invece la strada più lenta, ma sicura, di sincronizzare automaticamente i dati ad ogni modifica, in modo da favorire l’utilizzo del sistema anche da parte di “non tecnici” o comunque utenti non interessati ad entrare nello specifico.

Un'altra differenza significativa, sempre rispetto al CP/M, si riscontra nella gestione delle periferiche: il CP/M originale, attraverso il comando PIP, gestiva una serie di file speciali per reindirizzare le operazioni su stampanti e porte di comunicazione. Nel Q-DOS tali file divengono i device files, gestibili da qualsiasi programma e non solo dal PIP. Inoltre la funzione di copia dei file gestiti dallo stesso comando viene delegata al più intuitivo Copy.

 

CP/M Translation Compatibility

Sin dalla sua ideazione, era chiaro che, per avere successo, il DOS dovesse attrarre gli sviluppatori per realizzare applicazioni utili per l’utente finale. In realtà lo scenario era preoccupante poiché poche persone avevano acquisto i sistemi a 16-bit dell’SCP e quindi poteva essere difficile convincere le software house a investire in un mercato molto modesto.

A questo punto Paterson decide che la strada migliore è quella di realizzare un’API (Application Program Interface)  in grado di garantire la compatibilità con le chiamate effettuate dalle applicazioni “convertite” dal mondo a 8Bit a quello a 16Bit, secondo le specifiche di Intel.

Infatti la società di Santa Clara, per favorire il passaggio dal mondo a 8bit al 16bit, realizza delle precise regole di traduzione e Paterson crea un’API compatibile con quelle che le applicazioni CP/M a 8-bit avrebbero cercato nel momento in cui fossero state “traslate” a 16bit.

Questo richiese la creazione di un’API aggiuntiva molto specifica, compatibile con le suddette regole di transazione, che andava ad affiancare l’API proprietaria, maggiormente adatta al mondo a 16bit e decisamente più funzionale. Comunque entrambe le API utilizzavano i costrutti definiti dall’API del CP/M (come il “File Control Block”), non esistendo alcun motivo di realizzarne due diversi e visto che l’API di “compatibilità” doveva per forza di cosa utilizzarli. Per favorire ulteriormente la transazione, Paterson realizza anche un apposito translator che facesse il lavoro sporco, utilizzandolo in prima persona per convertire il proprio assembler (originariamente creato per il CP/M), ottenendo un perfetto tool a 16-bit per il DOS. SCP decise di includere il tool quando commercializzò il DOS ma lo stesso Paterson afferma che è quasi certo che nessuno lo abbia realmente utilizzato.