Sour Swinger Predominantly follows my Army & Iraq Deployment. Also has some Geek, School, and other talk.

The last programming assignment in my operating system’s class was to write a simulated file system for linux via system calls.  Basically we had to implement a read and write call for storing data via a file name. Persistence was optional.  Since my time was short, I left out persistence.  Basically all I wrote was a hash.  Write accepts a file name and string of contents or another words a key and value and stores it in a hash table.  Read accepts a file name/key and returns the string of contents/value.  Its fairly simply and provides a good example of utilizing a hash in C.  As for being a true simulated file system….far from it.

I used Horner’s algorithm to hash.  Collisions are handled by chaining.  Each table element is a struct consisting of a pointer character array and a pointer to the next collision struct.  I did not implement any rehashing or resizing of the table.  This is a very basic hash example.  Keep in mind this is not the code for implementing the hash with syscalls in linux.

Download Horner Hash.

Intro
Holy Shit! I finally finished this damn thing. LoL. Following last years coding competition, I decided to write a sprite editor for this years event which actually starts today. Talk about last minute. I got half way, and put it on the back burner a few months ago. Check out more about it here. I choose to write my own editor because the GIF conversion examples I found proved more of a burden then what it was worth. With my editor, I have tight control over how I implement things. Besides, I’ve never done anything this advance in QBasic before. Helps learn the whole graphics process better.

Included in this post is a small talk about both the sprite editor and and the demo program, as well as instructions on using them properly. Scroll to the bottom of the page to simply download everything. Unfortunately, I couldn’t get the source files to compile so you’ll have to run the program through the IDE. If anyone can supply me with the compiled versions, that’d be great. Since all this was rushed, there’s a good chance you’ll find a bug. Let me know of any you may spot.

GFX Editor
Supports only SCREEN 13. This was chosen due to the 256 color support. Max sprite size is 72×64. I included my own custom PALETTE. You may plop your own in, simply change the SUB SetPalette. Some modifications may then be needed to SUB UpdatePaletteGradient. Mouse support is also included.

Does NOT support saving multiple images into one file for animation purposes. Ran out of time to implement.

My custom PALETTE supports 15 shades of the following colors: grey, red, orange, brown, yellow, chartreuse, green, spring green, cyan, azure, blue, purple, magenta, and fuchsia. It also supports dynamic PALETTE changing based off a 30 FPS (Frames Per Second) display. There are 15 fading and 15 blinking colors derived off the main colors mentioned above. Three colors are reserved (0, 14, 255). For transparency, 0. For the grid color, 14. For the mouse, 255. Colors 3 through 13 are unused and can add additional custom colors to them.

Please note, I basically rushed this in the last few days because the competition is today. The coding style is HORRIBLE and not a good example of proper techniques nor how to accomplish certain things. Though check out SUB SaveImage for how I utilized BSAVE.

The editor has a very basic layout. The PALETTE to select your colors is on the bottom right hand side of the screen. The thumbnail of what the image will actually look like can be seen at the top right of the screen. The entire screen to the left is the actual grid to draw your graphics. Your mouse will turn to whatever color is selected to be painted with.

Left Click: Selects color when over PALETTE. Paints color when over grid.

Right Click: Erases color when over grid square. (Paints the transparency color).

f: Flips between the two PALETTEs to select colors from. This was done to save on space.

i: Displays info about the current image.

n: Create new image.

y: Save current image before starting a new one.
n: Don’t save current image, just start a new one.
c: Cancel new image selection.

1 to 72: Sets new image width.
-1: Cancels new image selection.

1 to 64: Sets new image height.
-1: Cancels new image selection.

l: <-(lower case “L”) Loads an existing image.

y: Save current image before loading.
n: Don’t save current image, just load new one.
c: Cancel load selection.

s: Saves current image.

If not saved yet, will ask for file name first.
y: Saves image.
n: Erases file name (NOT the file), recalls saves selection.
c: Cancels save selection.

-: Decreases current color selection by one shade.

=: Increases current color selection by one shade.

[esc]: Terminates program.

GFX Demo
Demonstrates good programming techniques since its meant to show how to utilize the saved graphics from the editor. Too lazy for comments. LoL. Any questions, let me know.

Supports SCREEN 13 with double buffering (via a virtual screen/page) to eliminate flicker. Supports utilizing the transparency color as well as the dynamic PALETTE changing. Displays images at a rate of 30 FPS.

Does NOT demonstrate animation. This program’s sole purpose is to show how to BLOAD said graphics and PUT to the screen. Animation is the easier part.

First hit “l” (lower case “L”) to BLOAD the graphics from hard disk. Then hit “p” to PUT images into the virtual page. Since the screen is continuously updated, the graphics will quickly display to the screen automatically. I separated the steps to allow easier understanding of the process. Hit [esc] to quite.

Files
Be advised, when loading the GFX Editor use the following command to start the Qbasic IDE: qb.exe /L qb.qlb

This is needed for the mouse routines to work. Without you won’t be able to run the program. Included in the zip is GFX Editor and GFX Demo along with needed example graphic files. I also included the qb.qlb file for those that may be missing it.

Zipped File: GFX Editor v08.410

My Operating Systems class finally came out with a new project. The first part was to successfully get a hello world program to run in Linux under Qemu. The second part was more interesting. I had to implement two new system calls in the Linux kernel. Very exciting and more practical over working with Nachos. Which almost happened. Here are the simple, few steps needed to create a new system call:

Briefing
I’m assuming you already have the source code downloaded, uncompressed, and ready to modify. I used version 2.6.23.1. Let’s also assume the files are located in /Linux/ directory and the name of the new system call to add will be “sys_mycall”. There are only 3 files in which you’ll need to change: sys.c, syscall_table.S, and unistd.h.

Step 1
Navigate to /Linux/arch/i386/kernel/. Here you’ll find syscall_table.S. This is an assembly file used to map all the system call names. At the very end of the file add the following:
.long sys_mycall

Step 2
Navigate to /Linux/include/asm/. Here you’ll find unistd.h. This file actually maps each syscall to a number that is used by the kernel. In the file, you’ll see a list of #defines that start with “__NR_”. These are actually your syscalls. You’ll notice they all define a number in sequential order. Go to the end of the syscall list and add the following:
#define __NR_mycall [some number]

Where [some number] will be the next number in the “__NR_” list count. Next look for the line:
#define NR_syscalls [some number]

You must increment NR_syscalls number for every syscall you add. So in this case, add one.

Step 3
Navigate to /Linux/kernel/. Here you’ll find sys.c. This file is where you’ll write your system call’s implementation as a function. I scrolled to the bottom to add the function, however you could just as easily place it in the beginning or even the middle of the code. Your function header will look something like:
asmlinkage long sys_mycall()

Important things to remember are the asmlinkage. This links the assembly code (syscall_table.s) in order to find the function. Second, all syscalls must return a long. Even if your function only stores a variable, you must include a return. Though I didn’t include it, you are more then welcome to have function parameters.

Usage
That’s it! Just compile the kernel and you’re good to go. Pretty easy. To use the new syscall, just include unistd.h in your program. To invoke the system call:
syscall(__NR_sys_mycall);

If you have parameters just throw them in as arguments to the syscall() function.

This semester I am taking CS1550, Intro To Operating Systems. Its a very interesting and fun class thus far. Helps that the professor is fracking awesome. He lets the occasional swear word slip and constantly rips windows. His lectures is more like a humorous stage performance. As such its hard not to pay attention. Last week he gave out our first assignment and I was incredibly excited to start it. For one, it had to be coded in C and how I love to write C. Two, the assignment was very open ended and three there’s a competition between classmates.

What Is A Page Replacement Algorithm
In short, it decides which memory page to swap out for virtual memory. This swapping is either going from disk to memory, or vice versa. This need arises when a page fault occurs. For a more detailed run down check out the Wikipedia entry.

The Assignment
Basically, we had to write a simulator for a chosen page replacement algorithm. This is the great part, we could choose any algorithm we wanted. The catch is having to supply a 1 page report on why our chosen algorithm is the best. Generally, when it comes to memory management there are a lot of “depends” situations. As such, there really is no one optimal solution.

There is no need to perfectly emulate the memory/disk nor all the internal happenings. The point of this is to learn how different algorithms effect page faults. More specifically, we read in a fixed memory size from stdin, followed by a series of FETCH # commands. Where # is the memory address being requested to be read. AKA, it needs to be in memory, not on disk.

A third, fun test given will be how effective our programs run compared to the rest of the class. The professor will run each person’s code through a series of test inputs. Obviously with the intent on causing as many page faults as possible. The person whose code performs the best (least number of page faults), wins. There is also a top spot for the most unique algorithm.

Algorithms
There are a ton of different algorithms but given the requirements, I feel there are three choice contenders to consider. The first being LRU (Least Recently Used). The page that was referenced/used last is the one swapped out. This will generally have a low page fault rate, however fails on certain looping patterns. Check out here for more info about it.

Next option would be NFU (Not Frequently Used). The page that was referenced/used least often is swapped out. NFU can succeed in those places that LRU fails. However NFU can also suffer where LRU will not. For more info, check out here.

The best method would be Aging. It combines both LRU and NFU. To explain how it accomplishes this goes beyond the scope of what I want to talk about. Once again, go here for more info. Suffice to say, I will implement Aging but in a very different way.

Since time of execution and “hardware” expense is not being tested, I decided to do something very radical. This is an attempt to also get the most unique design. Granted my chosen implementation would never work in the real world (way too expensive), so long as I can BS my reason’s why its the best…I’ll be in the clear.

Dual Doubly Link List
*Warning: Knowledge of link lists required for the following:

I couldn’t find a term for how I tracked the LRU and NFU information so was forced to make up my own. I call it a dual doubly link list. For both the LRU and NFU info, a doubly link list was required. Though to make my BSing easy, I had to ensure all possible optimizations were utilized. Using one link list is bad enough, but two?!?! Thats two nodes per memory page! Yikes!

Since data between the two were 90% identical, I combined everything into one giant node and connected them all together. That means, I now have 1 node per page. Wanna traverse the LRU link list? Just use node->prev or node->next. Wanna traverse the NFU link list? Use node->up or node->down. Suffice to say, I confused myself many times while coding this. LoL.

Probabilities and Averages
What’s the point of all that overhead? I wanted the best method to determine which page to swap out. By keeping track of LRU and NFU separately, I could make an appropriate decision using statistics (ironically I’ve never taking a stats class). First I assign each page a value or index based on its location in each link list. In effect, every page has two numbers. One for its LRU location and another for its NFU location. The closer to the end of the list, the higher the index.

I then took both the average and the probability of those two indexes. Why both? Simply using one or the other provided to many pages with equal values. By combining them, I reduced those chances and reduce the number of times I need to use rand(). For the most part, I felt using rand() to often would deviate from the LRU/NFU benefit. For those who may not be aware, probability (in this case) was the square root of the product of a pages two indexes. I then added that value to the average. (Do I really need to explain how to compute average?) Finally which ever page has the highest calculated value gets yanked.

Conclusion
In the end, I feel I created a near perfect combination of LRU and NFU. Hopefully more accurately then the normal Aging algorithm. Of course it requires a significant amount of overhead as well as a lot of computation. On ever page fault, I have to cycle through each link list at least once to assign a placement value. Followed by a third time to calculate which page to pull. Ouch! Hopefully my chosen algorithm wins in the class. Keeping my fingers crossed.

Update
-Managed a 100% on the assignment
-Uploaded source code for those interested.

Well to follow suite with the Perl idea, I went ahead a created a MIPS Assembly page. Currently I loaded up one simple program. I have about 4 others I did with the correlating class I took a couple years ago. Its hard to find MIPS examples online and figured this will surely help out someone. Question is, outside of the school environment, how many people really use MIPS?

Well I finally completed the uploading and comments of my first 3 part Perl assignment. I must admit, I’m falling in love with the language. I’m coming from a heavy C background and Perl is so radically different. I love it. I recently wrote the best programming line in my life.

foreach $info (sort keys %info) {
print “$info\n $info{$info}”;
}

ROFL, only in Perl does that Print statement make any sense. Here’s the link.

Well I’ve went a head and started working on a Perl page. Since I’m just starting to learn the language in my Web Applications class, I figured it a good idea to post my programming projects with commentary as I complete them. Perhaps someone may find them useful. As time allows, I’ll start loading up my old C code from my System Software’s class. Clicking the header will take you to my Perl Main page.