NAND2GO Chapter 12. Operating System
| 1. Context |
Convert the Jack language into VM language. | ||
| 2. Goal |
Write a Jack VM code generator in Java, using recursive descent. | ||
| 3. Measurable Effects |
Finish all the eight classes in Jack OS. Acquisition in the strategy of building abstract layers. | ||
| 4. Outputs | 5. Process | 6. Inputs | |
|
The exercise of Project 12. |
Learning about the design contract in Jack OS. Learning about the implement in each class in Jack OS. Realize the strategy in building Jack OS. |
Essays about Bresenham`s Algorithm. The Elements of Computing System. The publication. Resource from Wikipedia about Bresenham`s Algorithm and thread. | |
| 7. External Factors | |||
Introduction--What is the operating system?
Before introducing the Jack OS(Jack operating system), we should know the definition of Operating System: An operating system (OS) is system software that manages computer hardware and software resources and provides common services for computer programs.
We could understand it in an intuitive way: the operating system act as a intermediary between program and hardware, and OS will give us some direct ways to utilize the hardware resource. With the assist of OS, we could focus our work and there is no need to concern about how it implements in VM machine, assembler and even hardware layers. For example, to print a charter string like "Hello world!" on our PCs, without the services from OS, we should write a complex programs that send a series commands to draw pixels on the screen!(luckily the tedious work will be replaced by the Output class in Jack OS, further we will learn how it works).*But the significance of OS are far more than this, and in fact, in some parts we couldn`t see like the management of memory, the high-efficiency operation and the building of some data structure like arrays, OS plays an important role.
The Elements in Jack OS
Although the current OS have many functions throughout the parts of memory, I/O, file system, etc., the Jack OS is so simple because it consist of only eight classes. As the description from the Nand2Tetris, the Jack OS contain the elements that a fundamental OS should contain: a series of fine encapsulations of hardware service and the expanding of high-level language(refers to the Jack language).
The management of memory
One of the most important parts that OS should h ave is the Memory Management, and all services about it are encapsulated into the Memory class in Jack OS. Once we want to allocate some space for need, we should use the service supplied by the Memory class. Besides, when we want to save or get the data in a certain segment of the memory, we could also do it with the services of the Memory class.
The extension of operation
Another important part is the extension of operation. In the past chapter, we implement the most fundamental operation--addition. But it`s not enough to meet the need of the computer system. In fact, we need to expand the operation the computer could do.
The interaction between computer and user
There is no need for us to see the process of computing in computer, but we need to interact with the computer. So the Jack OS should supply some basic I/O services like printing characters on screen or receive the character we type on our keyboard. It will be implemented in the Screen, Output and Keyboard class in Jack OS.
How do the classes work in Jack OS
All the pseudocode about the following classes are given by the Elements of Computer System.
Math
In this part, we will implement the Math class in Jack OS. In the computer system, the operation like multiplication and division are necessary as they are widely used by most programs, especially in Computer Graphics. In the chapter 3, the addition is implemented in the ALU, and we will implement some basic operations, including multiplication, division and root.
To do a multiplication like 5 * 5, we may think of the original method: 5 + 5 + 5 + 5 + 5. But it`s a foolish algorithm in computer system. In the chapter 3, we know the time complexity of finishing an operation of addition is O(n)(n is the width of a number storing in the computer, it`s differ in the type of computer.).If we do a multiplication like x * y in the above method, the time complexity will be O(n * x)(or O(n * y)), and the range of x is from 1 to 2^n, meaning that the time complexity will be O(n * 2^n)!Such a high complexity is not permitted. For example, when we do a multiplication like 123456789 * 987654321 , we will do 123456789 times of addition!
Another effective algorithm will show below.
Consider about how we do a multiplication. we divide the process of a multiplication of two n-width number into n + n times of steps. Previous n times of steps are multiplications between an n-width number and a 1-width number and other are additions of the results we get above (including the process of shifting).
So how the computer finish it? The answer is that it will transform the numbers into binary format, and do the multiplication as we do.
We could do 25 * 25 in binary format, and this is an exercise for reader. When we finish it, we will find that we just finish it in a few steps! And we could prove that the time complexity is O(n).
In fact, in this algorithm, we use a skill to reduce the complexity: shifting. When we calculate 55 * 50, we just need to get the result of 55 * 5 and shift the result.
The next is division. Likely, we could also think about the way we do a division and this operation could be implemented by recursion.
Another operation we need is square root. It could be implemented by iterative method.
Memory
The Memory class is the most important class in Jack OS. Almost the service about the hardware resource utilization is offered by this class.
Three service we need the Memory class offering is getting data, saving data in memory and allocating space.
To implement all the services, first we should know the structure of the memory in Hack Computer System.
The structure of the memory in Hack computer is linear, like this:
the memory block is connected in order, and the point named freeList point the head of them. Every word in the memory block has its own address.
The first and second could be implemented by addressing, as you search a locker by its number and put or get your things from the locker.
So how to implement the third services?
The methods differ from different types of data structure. For the linear data structure like this, we could seek the free block for need throughout the memory. When we find out a block, we could modify the status of the memory block, and return the point which points the head of the block.
But there comes a new problem: Memory Leak. In simple terms, the memory will be filled with “rubbish” and you couldn`t get more space. To solve this problem, we should release the space to the memory when we don`t need temporarily. A method to implement it is to link the block with the rest memory(like linked list), but it will make the size of every segment of the memory smaller, and finally we will not find any appropriate blocks in memory (fragmentization). To avoid this situation, we could adopt other algorithms to deallocation, such as to splice the block onto the memory list.
String
One of the task of the String class is to implement a data type that support the storage of variable-length character string. This data type is hard to implement because of the difficulty of memory manage. In fact, to implement this, we could (only) allocate an enough space to store the character string, and store the size of the used space in a variable like length. The length variable is important because it represent the status of string and most functions that act on the string including changing the length variable in fact.
Since it is named “variable-length character string”, the String class should offer some service that to edit or read the character like erasing or returning the specified character. To implement it, we could change the length variable in the class. If we want to erase the last character in the string, we could change the length into (length – 1) so that the last character is “erased” (though it is still in the memory, it wouldn`t be concluded in the variable-length string).
For getting or editing a specified character in the string, we could implement it by accessing the specified memory segment and changing the data in it (because the data structure of string is array. Once we know the address of the array, we could access any position in it).
Keyboard
Keyboard plays an important role in inputting data to the computer. The main task of Keyboard class is to set up a map from the status of keyboard to a series of specified characters. But we don’t need to implement the whole process (because the author has set up the map from the status of keyboard to a series of Boolean value in a segment of the memory in advance) and what we should do is to transform these Boolean values into characters.
In fact, we should know the start address of the segment of memory that reflects the status of the keyboard, and it`s easy to implement the transformation as we could get the Boolean value of a specified situation and transform it according to the ASCII code table.
Besides, we want to output one character or a series of characters on the screen. Since we implement the map above, what we should do is to print them on the screen, and we need other classes such as Output and Screen.
Screen
Likely, the status of the screen is mapped to another specified segment of the memory, we could change the Boolean value of a specified situation of the segment and the status will be updated which seems to draw something on the screen. In fact, each situation in memory correspond pixels on the screen.
To draw a specified pixel, we should find the corresponding position in the memory. For a pixel whose coordinate is (x, y), we could use an equation to get the situation.
Once we implement the function that draw pixels on the screen, it`s easy to draw anything. For example, to draw a line on the screen, we could draw a series of pixels that are closed to the line we need, and higher resolution the screen has, the better similarity to the line the series of pixels have.
The algorithm above is named Bresenham`s algorithm, and I will explain it in details in 12.3 To draw a circle, we could draw a series of lines that fill the circle we need one by one.
Output
Fig 12.1 One of the pixel maps
It seems that the Output class is similar to the Screen class, and it`s correct because the Output class also could output some information on the screen, but it offers other services like user interaction (e.g. deleting a character on the screen).
An important label in the Output class is cursor. The cursor represents a specified site of screen that most functions in the Output class would run on, and it could give some responses to users (us).
First, we should implement the service that enables users to print a specified character on the position of the cursor. Similarly, we should find the corresponding positions of each pixel in a small rectangular area of the screen and the area will be filled with a pixel map of a specified character. The process of filling pixel maps is also similar to the process in the Screen class, but we need to change the position of the cursor after we finish the drawing (like updating the site that functions in Output class will run on).
Array
This class implements an abstract data type and it will be called by other classes (like the String class).
The data structure of array is linear and spatial-ordered, similar to the memory, so we could allocate some space for the construction of the array and record the address of the memory block. We could make a map from the position of array to the position of the memory (because their structure is similar), and all the operations on the array will be implemented.
Sys
This class is a core class in Jack OS, not only it offers the entrance of the whole program (initializing all the classes in the Jack OS), but also it will stop the running of the program when the program occurs some severe errors.
The implement of Sys class is easy, the readers could realize the implement in the book the Element of Computer System.
Discussion and Improvement in Jack OS
As we know, Jack OS is simple, meaning that it is also limited. It only implements the basic class in OS. Besides, there may occur some unpredictable errors in Jack OS.
Overflow in String
In the String class, there exists a maximum of length. If we insert a character to the end of the string continuously, the space will be full and finally overflow. It`s a severe error for the computer because when we try to insert characters to the string, it will fail and what we insert will change other data in other segment of the memory (and the position is random, so we describe it as unpredictable error).
So how to avoid it? One way is to allocate an enough space in advance, but it may cause waste of space.
Another way is to allocate another block of memory, and transfer all the data from source to destination. But it`s inefficient because the process of transferring is slow (the time complexity is O(n), n is the length of the string).
Although it`s slow, it`s necessary. In C++, a data structure named vector includes this function, when the vector is overflowing, it will run this function automatically.
Bresenham`s algorithm
Bresenham`s Algorithm is determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points.
The following pseudocode is from Wikipedia: Bresenham`s line algorithm:
(plot(x,y) plots the pixel centered at coordinates (x,y) and abs returns absolute value)
function line(x0, y0, x1, y1)
real deltax := x1 - x0
real deltay := y1 - y0
real deltaerr := abs(deltay / deltax)
// Assume deltax != 0 (line is not vertical),
// note that this division needs to be done in a
//way that preserves the fractional part
real error := 0.0 // No error at start
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
while error ≥ 0.5 then
y := y + sign(deltay) * 1
error := error - 1.0
In fact, when a circulation ends, the algorithm need to make a judgement to decide the position the next pixel will draw in and the criterion is the distance from the pixel to the line we need. It will guarantee the best approximation.
For drawing circles, the method in the Elements of Computer System is filling the circle with a series of lines. This method may be inefficient because of the large number of calculations about square root. But we could also draw a circle with Bresenham`s algorithm. It`s similar to drawing a line.
For example, when we want to draw a circle at (0, 0) whose radius is r and what we need are:
A recursive algorithm
like
(xn and yn are the coordinate of present pixel and xn+1 is the x-coordinate of the next pixel)
A criterion
like
RE(xi,yi) is the radius error of a pixel with a
center at (xi,yi)
Thread
In computer science, a thread of execution is the smalle stsequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.
The Jack OS is simple, so that it doesn`t support create any thread in the process, but we try to implement the creation of thread in Jack OS. Because of the lack of these knowledge, I haven`t implement it yet. If the readers are interested in it, you could try to implement it.
Postscript
To sum up, it`s easy to implement all the class in Jack OS because of its simplicity.
In my opinion, although these classes are simple, the process of implement involves the strategy about staging and modularity. For example, in Screen class, when we want to draw a line, we could draw a series of pixels to form it, and it`s similar to drawing a circle (if we don`t choose Bresenham`s algorithm). These are refl ection about the strategy of staging. Besides, we could fi nd that the duty of each class is clear, it`s the strategy of modularity.
Another important strategy is contractual-design. For example, when we want to use the function printString() in the Output class, we need the string off ered by the String class. In fact, we need to design an appropriate “interface” from String to Output to guarantee the correct transferring.
Glossary of Terms
Operating System
class
recursion
Newton's method
thread
Bresenham's algorithm
overflow