The Elements of Computing Systems: Building a Modern Computer from First Principles (48 page)
Read The Elements of Computing Systems: Building a Modern Computer from First Principles Online
Authors: Noam Nisan,Shimon Schocken
BOOK: The Elements of Computing Systems: Building a Modern Computer from First Principles
12.52Mb size Format: txt, pdf, ePub
Figure 12.14 A trapdoor enabling complete control of the RAM from Jack.
As we have pointed out earlier, Jack arrays are not allocated space on the heap at compile-time, but rather at run-time, when the array’s new function is called. Here, however, a new initialization will defeat the purpose, since the whole idea is to anchor the array in a selected address rather then let the OS allocate it to an address in the heap that we don’t control. In short, this hacking trick works because we use the array variable without allocating it “properly,” as we would do in normal usage of arrays.
Memory.alloc(), Memory.deAlloc ( ):
These functions can be implemented by either the basic algorithm from figure 12.6a on the improved algorithm from figure 12.6b using either best-fit or first-fit. Recall that the standard implementation of the VM over the Hack platform specifies that the heap resides at RAM locations 2048-16383.
12.3.8 SysThese functions can be implemented by either the basic algorithm from figure 12.6a on the improved algorithm from figure 12.6b using either best-fit or first-fit. Recall that the standard implementation of the VM over the Hack platform specifies that the heap resides at RAM locations 2048-16383.
Sys.init: An application program written in Jack is a set of classes. One class must be named Main, and this class must include a function named main. In order to start running the application program, the Main.main( ) function should be invoked. Now, it should be understood that the operating system is itself a program (set of classes). Thus, when the computer boots up, we want to start running the operating system program first, and then we want the OS to start running the main program.
With that in mind, the chain of command is implemented as follows. First, the VM (chapter 8) includes bootstrap code that automatically invokes a function called Sys.init( ). This function, which is assumed to exist in the OS’s Sys class, should then call all the init() functions of the other OS classes, and then call Main.main(). This latter function is assumed to exist in the application program.
Sys.wait: This function can be implemented pragmatically, under the limitations of the simulated Hack platform. In particular, you can use a loop that runs approximately n milliseconds before it (and the function) returns. You will have to time your specific computer to obtain a one millisecond wait, as this constant varies from one CPU to another. As a result, your Sys.wait() function will not be portable, but that’s life.
Sys.halt: This function can be implemented by entering an infinite loop.
12.4 PerspectiveThe software library presented in this chapter includes some basic services found in most operating systems, for example, managing memory, driving I/O, handling initialization, supplying mathematical functions not implemented in hardware, and implementing data types like the string abstraction. We have chosen to call this standard software library an “operating system” to reflect its main function: encapsulating the gory hardware details, omissions, and idiosyncrasies in a transparent software packaging, enabling other programs to use its services via a clean interface. However, the gap between what we have called here an OS and industrial-strength operating systems remains wide.
For starters, our OS lacks some of the very basic components most closely associated with operating systems. For example, our OS supports neither multi-threading nor multi-processing; in contrast, the very kernel of most operating systems is devoted to exactly that. Our OS has no mass storage devices; in contrast, the main data store kept and handled by operating systems is a file system abstraction. Our OS has neither a “command line” interface (as in a Unix shell or a DOS window) nor a graphical one (windows, mouse, icons, etc.); in contrast, this is the operating system aspect that users expect to see and interact with. Numerous other services commonly found in operating systems are not present in our OS, for example, security, communication, and more.
Another major difference lies in the interplay between the OS code and the user code. In most computers, the OS code is considered “privileged”—the hardware platform forbids the user code from performing various operations allowed exclusively to OS code. Consequently, access to operating system services requires a mechanism that is more elaborate than a simple function call. Further, programming languages usually wrap these OS services in regular functions or methods. In contrast, in the Hack platform there is no difference between OS code and user code, and operating system services run in the same “user mode” as that of application programs.
In terms of efficiency, the algorithms that we presented for multiplication and division were standard. These algorithms, or variants thereof, are typically implemented in hardware rather than in software. The running time of these algorithms is
O
(
n
) addition operations. Since adding two
n
-bit numbers requires
O
(
n
)-bit operations (gates in hardware), these algorithms end up requiring
O
(
n
2
)-bit operations. There exist multiplication and division algorithms whose running time is asymptotically significantly faster than
O
(
n
2
), and, for a large number of bits, these algorithms are more efficient. In a similar fashion, optimized versions of the geometric operations that we presented (e.g., line- and circle-drawing) are often also implemented in special graphics acceleration hardware.
O
(
n
) addition operations. Since adding two
n
-bit numbers requires
O
(
n
)-bit operations (gates in hardware), these algorithms end up requiring
O
(
n
2
)-bit operations. There exist multiplication and division algorithms whose running time is asymptotically significantly faster than
O
(
n
2
), and, for a large number of bits, these algorithms are more efficient. In a similar fashion, optimized versions of the geometric operations that we presented (e.g., line- and circle-drawing) are often also implemented in special graphics acceleration hardware.
Readers who wish to extend the OS functionality are welcome to do so, as we comment on in chapter 13.
12.5 ProjectObjective
Implement the operating system described in the chapter. Each of the OS classes can be implemented and unit-tested in isolation, and in any particular order.
Implement the operating system described in the chapter. Each of the OS classes can be implemented and unit-tested in isolation, and in any particular order.
Resources
The main tool that you need for this project is Jack—the language in which you will develop the OS. Therefore, you also need the supplied Jack compiler to compile your OS implementation as well as the supplied test programs. In order to facilitate partial testing of the OS, you also need the complete compiled version of our OS, consisting of a collection of .vm files (one for each OS class). Finally, you need the supplied VM emulator. This program will be used as the platform on which the actual test takes place.
The main tool that you need for this project is Jack—the language in which you will develop the OS. Therefore, you also need the supplied Jack compiler to compile your OS implementation as well as the supplied test programs. In order to facilitate partial testing of the OS, you also need the complete compiled version of our OS, consisting of a collection of .vm files (one for each OS class). Finally, you need the supplied VM emulator. This program will be used as the platform on which the actual test takes place.
Contract
Write a Jack OS implementation and test it using the programs and testing scenarios described here. Each test program uses a certain subset of OS services.
Write a Jack OS implementation and test it using the programs and testing scenarios described here. Each test program uses a certain subset of OS services.
Testing Strategy
We suggest developing and unit-testing each OS class in isolation. This can be done by compiling the OS class that you write and then putting the resulting .vm file in a directory that contains the supplied .vm files of the rest of the OS. In particular, to develop, compile, and test each OS class Xxx.jack in isolation, we recommend following this routine:
1. Put, in the same directory, the following items: the OS class Xxx.jack that you are developing, all the supplied OS .vm files, and the relevant supplied test program (a collection of one or more.jack files).
2. Compile the directory using the supplied Jack compiler. This will result in compiling your Xxx.jack OS class as well as the class files of the test program. In the process, a new Xxx.vm file will be created, replacing the originally supplied OS class. That’s exactly what we want: the directory now contains the executable test program, the complete OS minus the original Xxx.vm OS class, plus your version of Xxx.vm.
3. Load the directory’s code (OS + test program) into the VM emulator.
4. Execute the code and check that the OS services are working properly, according to the guidelines given below.
OS Classes and Test Programs
There are eight OS classes: Memory, Array, Math, String, Output, Screen, Keyboard, and Sys. For each OS class Xxx we supply a skeletal Xxx.jack class file with all the required subroutine signatures, a corresponding test class named Main.jack, and related test scripts.
Memory, Array, Math
To test your implementation of every one of these OS classes, compile the relevant directory, execute the supplied test script on the VM emulator, and make sure that the comparison with the compare file ends successfully.
To test your implementation of every one of these OS classes, compile the relevant directory, execute the supplied test script on the VM emulator, and make sure that the comparison with the compare file ends successfully.
Note that the supplied test programs don’t comprise a full test of the Memory.alloc and Memory.deAlloc functions. A complete test of these memory management functions requires inspecting internal implementation details not visible in user-level testing. Thus it is recommended that you test these two functions using step-by-step debugging in the VM emulator.
String
Execution of the corresponding test program should yield the following output:
Execution of the corresponding test program should yield the following output:
Output
Execution of the corresponding test program should yield the following output:
Execution of the corresponding test program should yield the following output:
Screen
Execution of the corresponding test program should yield the following output:
Execution of the corresponding test program should yield the following output:
Keyboard
This OS class is tested using a test program that effects some user-program interaction. For each function in the Keyboard class (keyPressed, readChar, readLine, readInt), the program requests the user to press some keyboard keys. If the function is implemented correctly and the requested keys are pressed, the program prints the text “ok” and proceeds to test the next function. If not, the program repeats the request for the same function. If all requests end successfully, the program prints ‘Test ended successfully’, at which point the screen may look like this:
This OS class is tested using a test program that effects some user-program interaction. For each function in the Keyboard class (keyPressed, readChar, readLine, readInt), the program requests the user to press some keyboard keys. If the function is implemented correctly and the requested keys are pressed, the program prints the text “ok” and proceeds to test the next function. If not, the program repeats the request for the same function. If all requests end successfully, the program prints ‘Test ended successfully’, at which point the screen may look like this:
Other books
The Lemur by Benjamin Black
Thinking Straight by Robin Reardon
Lost Her (Lost #1) by Sharp, Ginger
Unbelievable by Lori Foster
The Daddy Decision by Donna Sterling
Dangerous Desires by Dee Davis
Changeling Winds: Episode Two (The Bachelor Battles Book 2) by Angela White
Bracelet of Bones by Kevin Crossley-Holland
Hall, Jessica by Into the Fire
The Cradle, the Cross, and the Crown by Andreas J. Köstenberger, Charles L Quarles
