Archive for category Lecture Comments

Basic Table Tennis Game Code Samples

This blog entry outlines some basic information to get up to speed with the development of a basic table tennis game. At this point, it is not meant to be a complete implementation neither is it going to impose any particular (other than what’s obvious) design and/or architectural understanding of the project’s terms of reference.

  • Basic introduction to OpenGL: you need to get a basic OpenGL program up and running; this will give you an understand of the OpenGL environment generally and how much code it takes to have a Window display on your computer. I found this tutorial to be a useful introduction to OpenGL; it is useful for an absolute beginner as it walks you through OpenGL step by step. There are also Visual C++ 6.0 project code downloads from the tutorial.
  • The Game’s Screen: the game is essentially comprised of quadrilaterals (rectangles of varying widths and height – assuming a square (the ball) can be called a rectangle as well. From the tutorial in the point above, identify the code section that is responsible for rendering images on the screen. To draw a rectangle in OpenGL you need the coordinates of its four corners (vertices); strictly speaking, you just need the coordinates of one of the corners of the rectangle. The image below illustrates that; the coordinates of the single vertex is required to establish the position of the rectangle.

image 

Update: added game layout diagram

image

The following artifacts in the game can be represented as rectangles:

  • The Game boundary: the largest rectangle in the drawing depicting the game;
  • The Ball: it can be represented as a filled square (strictly speaking not a rectangle but it requires the drawing of four sides);
  • Computer Player Pad and Human Player Pad: rectangles of varying heights;
  • Net: a filled rectangle;

The following code sample renders a rectangle in OpenGL:

glColor3f(0.4f, 1.f, 0.2f);
glBegin(GL_LINE_LOOP);
glVertex3f(-1.5, -1.0f, 0.0);
glVertex3f(1.5, -1.0f, 0.0);
glVertex3f(1.5, 1.0f, 0.0);
glVertex3f(-1.5, 1.0f, 0.0);
glEnd();

And the next one renders a filled rectangle:

glColor3f(0.4f, 1.f, 0.2f);
glBegin(GL_POLYGON);
glVertex3f(-1.5, -1.0f, 0.0);
glVertex3f(1.5, -1.0f, 0.0);
glVertex3f(1.5, 1.0f, 0.0);
glVertex3f(-1.5, 1.0f, 0.0);
glEnd();

With information above it is possible to create a method that renders a rectangle, given one corner or vertex, as well as the rectangle’s width and height. This would be optimal because most of the shapes in the Game’s screens are rectangle which would mean writing complicated code that would be seemingly hard to debug.

void draw_rectangle(Point start_point, width, height){

glColor3f(0.1f, 1.f, 0.2f);
glBegin(GL_LINE_LOOP);
glVertex3f(start_point.x, start_point.y, 0.0);
glVertex3f(start_point.x+width, start_point.y, 0.0);
glVertex3f(start_point.x+width, start_point.y+height, 0.0);
glVertex3f(start_point.x, start_point.y+height, 0.0);
glEnd();

}

/**

 * In order to user the above form, you will need to create a Point  * class.

 **/

Or it can be implemented like this:

void draw_rectangle(float x, float y, float width, float height){

glColor3f(0.1f, 1.f, 0.2f);
glBegin(GL_LINE_LOOP);
glVertex3f(x, y, 0.0);
glVertex3f(x+width, y, 0.0);
glVertex3f(x+width, y+height, 0.0);
glVertex3f(x, y+height, 0.0);
glEnd();

}

I hope the above information is helpful. If there is any improvements you think need to be included in the aforementioned, please add a comment – it might help someone.

Happy hacking!

Advertisements

6 Comments

Beginning of a New Semester

This week saw the start of a new semester which means same old challenges to go through and for some reason it is increasingly becoming clear that the start of a semester must necessarily suck! While I am not a fan of mourning about the realities of life, I must admit the bulk of the usual challenges I deal with at the start of the semester are largely taken care of; only one unit has been scheduled in a lecture room that requires scaling an ungodly number of stairs. I am hoping this will be sorted out soon.

This semester I have one IT-centric unit in the name of Computer Graphics; I am yet to have the first lecture but I think this is something I intend to enjoy and hopefully be a good reason to become more friendly with graphics. I am mostly biased towards web applications and the web apps I have developed so far aim for simplicity and some elegant but eye catching use of color. In short not much graphics come into play when I work on a web app. Of course a web app is suppose to serve a purpose and hence most of the bling bling is not necessary. I don’t think the Computer Graphics unit is going to be about those kinds of graphics though but it will be fun to discover more details about graphics.

World Civilization I is the humanity elective that I am taking this semester. From the first lecture it is going to be an interesting unit though the fact that I am taking evening classes will some what mean less involvement in the lectures on my part. I liked the introductory lecture and it is the kind of lecturing that I prefer: no notes provided. Single Origin theory was fascinating; I had a look at the Wikipedia entry on the subject and my mind was abuzz with the possibilities. In all the world, there is the greatest genetic diversity in Africa which according to the theory means that Africa was the birth place of the modern man. From a simplistic view, it is hence acceptable to posit that new generation of human beings are more likely to emerge from the great genetic diversity present in Africa. I am currenlty following the Heroes TV series; in this series, a number of people have super human abilities as a result of evolution …

The other units for the semester include Business Law, Introduction to Macroeconomics and Cost Accounting. All these are business units and that’s all I am going to say about them for now other than the fact that there will be a need to read a large amount of notes.

Leave a comment

Presentation: Internal Structure of Minix

Overview

This is a presentation of the Internal Structure of Minix and it is not intended to go into details of how the structure is implemented, the various techniques employed etc. So basically, the presentation should make sense to any lay person who wants to have an appreciation of the structure of Minix without concern for the nity gritty of computer science theories and practices. I think that is a fair amount of assurance that there will be no code or anything apparently geeky in this presentation. My apologies to those looking for geeky materials. ๐Ÿ™‚

Objectives of this Presentation

  • Discuss architectural Design: Micro-Kernel design of Minix and Its implications
  • Show Internal Structure of Minix: show the various layers and their general function

Background Information

Minix is an open source Unix like operating system that has been designed and implemented with the aim of being an education tool. It was designed by Andrew S. Tanenbaum and in order to achieve its objective of being an education tool, Minix is modular and the available source code is well commented. The Minix kernel has about 4000 lines of code. 

Minix has a had a great history in the academic community and it holds the honor of being the inspiration behind the Linux kernel, the poster child of open source. When Linus Torvalds started working on the Linux kernel he used a Minix system hence Linux and Minix share a lot in design as well as drivers in those early days. However there is a significant difference in design between Linux and Minix: the former is implemented using the monolithic structure while Minix uses a micro-kernel architecture.

Minix Layered Micro Kernel architecture

Design & Architecture

The Minix operating system implements a layered, micro-kernel architecture as showed in the diagram above. The Unitโ€™s main text talks about five different structures of operating systems: monolithic, layered, virtual machine, exokernels and client/server. Minix combines two of these structures: the layered structure and client/server structure.

The layered system structure breaks the system into a number of layers which implement specific functions. In such a setup, typically the higher level layers relay on the services provided by the lower level layers. Minix has four layers, each with a specific and well defined function.

In a micro-kernel architecture most of the key functions of the operating system are implemented as servers that run separately from the core kernel. This design makes the operating system module and extensible since additional services can be developed and improved without much changes to the kernel. Key services provided by a Micro-Kernel: address space management, thread management, inter-process communication and timer management.

Structure of Minix

Disclaimer: this part of the presentation is not exhaustive

Minix 3 is structured into four layers as follows:

Layer 1: Kernel

This layer provides the lowest level services that are needed to run the system. These include management of interrupts, traps, scheduling and communication. The lowest part of this layer that details with interrupts is written in assembly language while the rest of it is written in C.

This layer does the following:

  • Manage interrupts and Traps
  • Saving and restoring registers
  • Scheduling 
  • Providing Services to the next layer
  • Messaging and communication services 

Layer 2: Device Drivers

Input/Output devices that are found in this layer are such peripherals like disks, keyboards, printers, CD drivers etc.

Layer 3: Server Processes

This layer provides services that are used by all programs that are running in layer 4. Processes in this layer can access the services of the device driver layer but programs in Layer 4 cannot have direct access to Layer 2 processes.

Example of some of these services include: File system, reincarnation server, network server, information server, memory manager, process manager etc. In a typically layered approached, the servers provide services to processes/programs that run in layer 4 while consuming services from the lower layers.

Layer 4: User Processes

This forms the userland section of the Minix operating system in which user programs are executed. These programs relay on the services that are provided by the lower level services. Programs that are typically found in this layer include daemons of various types, shells, commands and any other program that the user may want to run.

The layer 4 processes have the least privileges to access resources and typically gets to privileged resources through the lower level processes. For example, a user can execute the ping command which requires the use of the networking server process. The ping command, does not call the networking server process directly. Instead it goes through the file system server process.

Merits of the Architecture

  • Modularity: the system is well structured and the relationship between the various components is equally well defined.
  • Security: the combination of the layered system structure and micro-kernel design makes for a architecture that allows for better incorporation of security. Layers 2 โ€“ Layer 3 run in User mode while only layer 1, runs in Kernel mode which has all the privileges needed to access any part of the system.
  • Extensibility: in order to have a functional system, one needs the kernel setup as well as the key services that are needed to start off. All the other functions can be added as and when needed. This makes it simpler to extend and/or specialize the function of the system.
  • Performance & Stability: most problems that cause instability on a computer system are a result of poor designed and/or poorly compiled drivers and user programs. The micro kernel architecture allows these programs to be executed and implemented independent of the core components of the operating system, which means that a failure in any of those programs is not catastrophic to the system. The system is able to maintain uptime, despite errors.

Demerits of the Architecture

  • Complexity: the architecture is complex and hence makes it harder to design in the first place and to evolve as time moves on. The computer industry is probably amongst the fastest moving industry of the global economy and as such there is a real need to adjust to new developments in hardware as well as innovations in software.
  • Communications and Messaging: the architecture needs fast and efficient communications architecture so as to ensure faster communication between the various processes that are running in their individual address spaces as well as with varied security levels. A poor communications implement would negatively impact on the performance of the system.

Conclusion

The design and architecture is good for its intended purpose of being an education tool. It allows students to appreciate the design and implementation of an operating system. However, this goal may not be a true reflect of a what a real world, enterprise grade operating system looks like and how it is implemented. The sheer number of processes that are started when a general purpose operating system boots indicates that while the principles largely remain the same as those demonstrated by Minix, there is a much more complex implementation and design effort going into producing operating systems like Linux, Windows, Solaris and other variants of Unix.

The debate about monolithic vs micro-kernel OS design has been going on for sometime but this debate is also becoming more important in this day and age where virtualization and multi-core processors are increasingly main stream. Questions like how a monolithic design can efficiently take advantage of multi-core processors will become important. But it is also necessary to address the tools that used to produce these programs: at the moment, there is poor support for parallel programming.

References

4 Comments

File Management

File Systems are an integral part of any modern operating system with a pattern whereby most proprietary operating system support a single file system while Linux (the poster child of open source) supports a number of file systems. The role of the file system as the operating systems way of storing and organizing data cannot be disputed. However the increased capacity of storage media such as the hard disk and flash based media requires additional capabilities that perhaps build on the file system.

Anyone who keeps a significant and varied amount of data on a recently purchased computer would be interested in searching his locally stored data using the same approach that is used by internet search engines like Google. There are a number of desktop search products available and Google offers the Google Desktop that indexes data on a hard disk and allow subsequent searching. My experience with Google Desktop has been good though upgrading between versions has caused some problems in the past. I have heard complains of how much of a resource hog it is but that is not something that I can say I have experience; the initial indexing will take sometime that is why it would take a lot of resources.

File Systems & Desktop Search

File systems need to provide extensive meta data about the files that they store and more importantly perhaps include additional services that will analyze and group these meta data in a manner that makes sense to a user. For example, it should be possible and easy to group documents that concern a particular company or business proposal into a single unit regardless of whether these files are Word documents, spreadsheets or PDF documents. This is important for the future usability of computer since hard disk capacity has been increasing and soon enough we will have 1 terabyte hard disks which represents a lot of information to keep in folders. Microsoft’s ambitious WinFS was rumoured to offer such capabilities but that particular “pillar” of Windows Vista has been removed and some of its technologies have been integrated into other Microsoft projects.

File Systems

  • FAT: this is perhaps the most widely used and simplest file systems of all. It was created by Microsoft and used in consumer version of Windows up to Windows Me. Most PC OSes support FAT which makes it the common demoniator for such tasks as data sharing across disparate operating system platforms as well as for use in removable media such as floppy disks or flash disks. There are three version of FAT (FAT12, FAT16 and FAT32) with support for varying sizes of disks and file, long file names. The file system uses File Allocation Tables to keep track of which areas of the disks have data stored in them, which areas are free and which are potentially unusable for data storage. FAT file system tends to fragment as it scatters data across the disk; this reduces the performance of the file system and makes defragmentation (on a regularly basis) necessary. FAT32 supports a maximum volume size of 8 TB (terabyte).
  • NTFS (New Technology File System): this is the file system that is used in newer versions of Microsoft’s Windows operating system; all versions of Windows based on the NT kernel (Windows NT, Windows 2000, Windows XP, Windows Server 2003 and Windows Vista) use NTFS as the primary file system though this may not be the case with Home editions of the some of the OS releases or perhaps the basic editions (where applicable). NTFS include features such as support for metadata (file attributes) and use of advanced data structures to improve performance, reliability and disk utilization. NTFS includes support for Access Control Lists and file system journaling which enables the OS to recover from potentially damaging events like power blackouts that threaten the integrity of the file system.
  • Ext3 (the third extended file system): is an open source file ssytem commonly used by default in most Linux distributions. It was created by Stephen Tweedie and includes journaling capabilities. It is an extension of ext2; it adds journaling and tree based directory indices over ext2. Because of its close relationship with ext2, it is easy to upgrade to ext3 from ext2 and most of the ext2 tools will continue to work on ext3. However this close link to ext2 is a disadvantage because ext3 lacks features that are available in most modern files systems such as dynamic allocation of i-nodes. Ext3 lacks and online defragmentation tool …

    Further Reading, more

Interesting Concepts (will be expounded as time passes)

Extent: this is a contigous area of storage allocated for the storage of a file.

Journaling:

B+tree Data Structure:

Leave a comment