Description
CPE 357 Systems Programming Assignment 1
Exercise:
Program your own malloc and free functions:
BYTE *mymalloc(int size)
BYTE *myfree(BYTE *addr)
Use brk() and/or sbrk()
MYMALLOC
Use a pagesize of 4096 bytes.
You start with a heapsize of 0, be aware of that.
The mymalloc function needs to do following:
If there is no heap, create one chunk big enough for the requested size with brk/sbrk.
You need to have a structure chunkinfo as part of each memory chunk:
struct chunkinfo
{
int size; //size of the complete chunk including the chunkinfo
int inuse; //is it free? 0 or occupied? 1
BYTE *next,*prev;//address of next and prev chunk
}
Return the correct address for the user-developer!
If there are already chunks present, travers through them as through a list and check:
If the current chunk if free and fits the size, change the chunkinfo accordingly and return the
correct address. Split if the chunk is far bigger than the user-developer needs and the rest is
bigger than a pagesize.
If no chunk is free or fits, move the program break further: Create a new chunk (and link
correctly).
MYFREE
This function sets a chunk to free. Merge adjunct free chunks accordingly.
If the chunk (or the merged chunk) is the last one, you can remove the chunk completely and
move the program break back for the size of the chunk.
MUST DO:
• Move the program break back again when the last chunk in the list is removed!
• You analyse function should print the address of the program break!
• Best fit: Search the chunks for the smallest possible chunk which satisfies the request.
Submit:
The whole project folder zipped as filename: FIRSTNAME_LASTNAME_PROGRAM_2.zip on
PolyLearn.
How we test (Please put that into your void main):
byte*a[100];
analyze();//50% points
for(int i=0;i<100;i++)
a[i]= mymalloc(1000);
for(int i=0;i<90;i++)
myfree(a[i]);
analyze(); //50% of points if this is correct
myfree(a[95]);
a[95] = mymalloc(1000);
analyze();//25% points, this new chunk should fill the smaller free one
//(best fit)
for(int i=90;i<100;i++)
myfree(a[i]);
analyze();// 25% should be an empty heap now with the start address
//from the program start
You can use following functions (they come handy)
chunkhead* get_last_chunk() //you can change it when you aim for performance
{
if(!startofheap) //I have a global void *startofheap = NULL;
return NULL;
chunkhead* ch = (chunkhead*)startofheap;
for (; ch->next; ch = (chunkhead*)ch->next);
return ch;
}
void analyze()
{
printf(“\n————————————————————–\n”);
if(!startofheap)
{
printf(“no heap”);
return;
}
chunkhead* ch = (chunkhead*)startofheap;
for (int no=0; ch; ch = (chunkhead*)ch->next,no++)
{
printf(“%d | current addr: %x |”, no, ch);
printf(“size: %d | “, ch->size);
printf(“info: %d | “, ch->info);
printf(“next: %x | “, ch->next);
printf(“prev: %x”, ch->prev);
printf(” \n”);
}
printf(“program break on address: %x\n”,sbrk(0));
}
Result for comparison
————————————————————–
no heap, program break on address: 5fff9000
————————————————————–
0 | current addr: 5fff9000 |size: 368640 | info: 0 | next: 60053000 | prev: 0
1 | current addr: 60053000 |size: 4096 | info: 1 | next: 60054000 | prev: 5fff9000
2 | current addr: 60054000 |size: 4096 | info: 1 | next: 60055000 | prev: 60053000
3 | current addr: 60055000 |size: 4096 | info: 1 | next: 60056000 | prev: 60054000
4 | current addr: 60056000 |size: 4096 | info: 1 | next: 60057000 | prev: 60055000
5 | current addr: 60057000 |size: 4096 | info: 1 | next: 60058000 | prev: 60056000
6 | current addr: 60058000 |size: 4096 | info: 1 | next: 60059000 | prev: 60057000
7 | current addr: 60059000 |size: 4096 | info: 1 | next: 6005a000 | prev: 60058000
8 | current addr: 6005a000 |size: 4096 | info: 1 | next: 6005b000 | prev: 60059000
9 | current addr: 6005b000 |size: 4096 | info: 1 | next: 6005c000 | prev: 6005a000
10 | current addr: 6005c000 |size: 4096 | info: 1 | next: 0 | prev: 6005b000
program break on address: 6005d000
————————————————————–
0 | current addr: 5fff9000 |size: 368640 | info: 0 | next: 60053000 | prev: 0
1 | current addr: 60053000 |size: 4096 | info: 1 | next: 60054000 | prev: 5fff9000
2 | current addr: 60054000 |size: 4096 | info: 1 | next: 60055000 | prev: 60053000
3 | current addr: 60055000 |size: 4096 | info: 1 | next: 60056000 | prev: 60054000
4 | current addr: 60056000 |size: 4096 | info: 1 | next: 60057000 | prev: 60055000
5 | current addr: 60057000 |size: 4096 | info: 1 | next: 60058000 | prev: 60056000
6 | current addr: 60058000 |size: 4096 | info: 1 | next: 60059000 | prev: 60057000
7 | current addr: 60059000 |size: 4096 | info: 1 | next: 6005a000 | prev: 60058000
8 | current addr: 6005a000 |size: 4096 | info: 1 | next: 6005b000 | prev: 60059000
9 | current addr: 6005b000 |size: 4096 | info: 1 | next: 6005c000 | prev: 6005a000
10 | current addr: 6005c000 |size: 4096 | info: 1 | next: 0 | prev: 6005b000
program break on address: 6005d000
————————————————————–
no heap, program break on address: 5fff9000
Bonus:
We will measure the performance of your code on one and the same computer.
The 5 fastest get 2% bonus on the whole course grade. Be creative!
My results: 521 micro seconds (VirtualBox, Xubuntu, i7-4770, 3.4 GHz)
Test case for speed test (same as above, no print statement except time duration):
byte*a[100];
clock_t ca, cb;
for(int i=0;i<100;i++)
a[i]= mymalloc(1000);
for(int i=0;i<90;i++)
myfree(a[i]);
myfree(a[95]);
a[95] = mymalloc(1000);
for(int i=90;i<100;i++)
myfree(a[i]);
cb = clock();
printf(“\nduration: % f\n”, (double)(cb – ca);
What is allowed:
You can talk and discuss everything on Piazza, helping each other out, but not sharing any code!
CPE 357 Systems Programming Program 2
Exercise:
Write a program to blend two images together.
The image files should be 24Bit per pixel (standard) BMP files. You will find several ones in the
adjunkt zip to this assigment. You can use your own ones – save them as 24Bit BMP in e.g.
photoshop.
The Program:
The program should read several parameters from the comand line:
[programname] [imagefile1] [imagefile2] [ratio] [outputfile]
e.g.
blendimages face.bmp butterfly.bmp 0.3 merged.bmp
Catch wrong or missing parameters and print a manual page.
The ratio should determine how much of imagefile1 and imagefile2 will be in the result. A ratio
of 0.5 means the resultimage will be a 50:50 mixture of both. 0.3 means 30% imagefile1 and
70% imagefile2. Got it?
So what gets blended? The pixels.
If both images have the same resolution, then the result pixel on the same x/y coordinate will
be:
red_result = red_image1 * ratio + red_image2 * (1-ratio);
and so for green and blue.
The resolution of both files might be different though. In this case, the resultimage should have
the same resolution as the bigger image (width). In this case, to blend the colors precicely, you
need a function which returns the pixelcolor on a floatingpoint position:
unsigned char get_red(unsigned char *imagedata,float x,float y,int
imagewidth, int imageheight);
And use bilinear interpolation between 4 pixel, depending on the coordinates.
Points:
80% if your program works at least for images with the same width and height.
+20% if your program works with arbitrary resolutions (bilinear interpolation).
Howto:
First read the bitmap file header infos into corresponding structures and then the image data
into an array of BYTES (unsigned char). You need to allocate this array first.
The size is dependend on the resolution, which you get with the file headers:
http://www.dragonwins.com/domains/GetTechEd/bmp/bmpfileformat.htm
Wikipedia isn’t bad here, but a bit chaotic:
https://en.wikipedia.org/wiki/BMP_file_format
Important!
Color tables and bit masks are not necessary, that’s too complex. So all optional BMP data will
be skipped!
Do this for both input images!
Now allocate a BYTE array of the target size.
Loop over the bigger image resolution (in x and y) and grab the pixel color (red, green and
blue). Request the pixel color of the other image as well based on the loop variables x and y.
Since the other image might have a different resolution, you need to map the correct x_2 and
y_2 of the other image. These values will be floats!
That means you end up grabbing a color between 4 pixels! Therefore you need to get the color
of this 4 pixels and biliear calculate the real color!
Blend the result color and assign it back to the result image.
Pseudo code (just to help you, if you have a better idea, follow that)
Read image 1 (file headers and pixel data)
Read image 2 (file headers and pixel data)
Allocate resultimage mem
Loop over the bigger one:
Loop in x
Loop in y
//Get the coords from the smaller image:
x_2 = … x …;
y_2 = … y …;
get the color from image 2:
get_red(imagedata2,x_2,y_2,…);
//and green, blue
Blend the colors
Assign them into the resultimage
Write a new header for the resultimageto a file
Write the pixeldata to the file
Done.
Structures for BMP Format
typedef unsigned short WORD;
typedef unsigned int DWORD;
typedef unsigned int LONG;
struct tagBITMAPFILEHEADER
{
WORD bfType; //specifies the file type
DWORD bfSize; //specifies the size in bytes of the bitmap file
WORD bfReserved1; //reserved; must be 0
WORD bfReserved2; //reserved; must be 0
DWORD bfOffBits; //species the offset in bytes from the bitmapfileheader to
the bitmap bits
};
struct tagBITMAPINFOHEADER
{
DWORD biSize; //specifies the number of bytes required by the struct
LONG biWidth; //specifies width in pixels
LONG biHeight; //species height in pixels
WORD biPlanes; //specifies the number of color planes, must be 1
WORD biBitCount; //specifies the number of bit per pixel
DWORD biCompression;//spcifies the type of compression
DWORD biSizeImage; //size of image in bytes
LONG biXPelsPerMeter; //number of pixels per meter in x axis
LONG biYPelsPerMeter; //number of pixels per meter in y axis
DWORD biClrUsed; //number of colors used by th ebitmap
DWORD biClrImportant; //number of colors that are important
};
Smart Start: (You do not need to follow that)
1. First read one BMP file and create a new one, saving the first one’s data. That should
result in an exact copy. Check if that is the case.
2. Do this for the second image.
3. Use two images with the same resolution.
Write a get_color function which gets the data array, the width and height, the
coordinates of the pixels, the desiert color and returns the color on the given xy.
Loop over all pixels of the bigger one in x and y
Grab their color in red green and blue.
Do this for the second image
Mix the pixels and assign them back into the target array.
Save the file and check the image.
4. Now program a get_color_bilinear and calculate the floating point coordinates for the
smaller image and try getting this done.
Result examples
Possible Hazzards:
Padding issues with reading the structures and padding issues per line of the images!
Bilinear interpolation
So you are between 4 pixels?
See image, and lets say:
x = 3.3; y = 5.8;
consequently:
x1 = 3, x2 = 4 and y1=5, y2=6
the ratio between them is also
dx = 0.3 and dy =0.8
Then the bilinear interpolation for one color, lets say red, is:
Red_left_upper = get_color(…,x1,y2);
Red_right_upper = get_color(…,x2,y2);
Red_left_lower = get_color(…,x1,y1);
Red_right_lower = get_color(…,x2,y1);
Interpolate:
Red_left = Red_left_upper * (1 – dy) + Red_left_lower * dy;
Red_right = Red_right_upper * (1 – dy) + Red_right_lower * dy;
Red_result = Red_left * (1 – dx) + Red_right * dx;
Submit:
The whole project folder zipped as filename: FIRSTNAME_LASTNAME_PROGRAM_1.zip online.
The zip must include the image files you are using, the source code file and the binary file.
CPE 357 Systems Programming Assignment 3
Exercise:
Write a “findfile” program. The findfile program will let you enter its own shell: findstuff$ Now you should be able to enter commands and react to them: Important: I leave the exact formatting and text up to you, but hold up to the premise • find -flag .. tries to find this specific file. For that, your program fork()’s a new child process which is doing that. Assign a serial exclusive number to this and each child, you will need it later with the “kill” command.
Once done, it interrupts* the scanf from the parent process and prints its result. The result should be something like >nothing found< in case nothing was found, but if, then print the file’s name and its directory. Print several lines if several files with the same name were found. e.g.: findstuff$ find test.c text.c bin/usr/desktop • flags: There are different flags: No flag … Search in the current directory. -s … search in the current directory and all sub-directories. -f … search in all directories • quit or q .. quits the program and all child processes immediatelly.
Have no more than 10 childs at a time. Report if the user attempts to exceed that limit and nicely print, that the limit is reached. *interrupt How to interrupt while the parent is in scanf-mode waiting for another input? Just interrupt with printf, the scanf will still be active later on. Redirecting stdin is not a good idea, because once redirected, it does not (at least not that easy and not on all systems let you get data from the keyboard again.
What for? Why child processes, why not simply use one process? Bevcause seaching for one file across the whole harddrive can take minutes. During this time, the user should be able to search for other files. This is why we use child processes for doing so. Also: Learning pipe(), dup2() and how to redirect stdin, lots of programing exercise due to string handling, nice use of signals and on top a useful program. How we test We send a couple of find request on the way on a big HD. So they will need some time (>3sec). Then we check if everything is nicely reporting back.
Submission: Submit the source code file(s) and the executables: MYNAME_findstuff_ass3.zip FAQ (this section will be extended in the next days) >What happens with the child when its done? E.g. finding the file(s). 1. Report its findings by printing the result. 2. It should end. To avoid a zombie, wait for that specific child with waitpid() (https://linux.die.net/man/2/waitpid). How does the parent know to wait for that child? Signal! And send its PID into a pipe or shared mem!
You need: waitpid() opendir() closedir() readdir() pipe() dup() dup2() A good Idea how to start: • Start using your lab code pipelines. It already has the redirecting. • Write a parsing function, to extract the arguments. • Write a recursive function to get all entries of a directory, something like: (pseudocode) void findstuff(char* filename_to_be_found, char *startdirectory,char *result,int search_in_all_subdirectories) { opendir(startdirectory) readdir(); if (entryname == filename_to_be_found) write to result; if(entry_is_subdirectory && search_in_all_subdirectories) findstuff(filename_to_be_found, startdirectory += ‘/’ + entryname, result, search_in_all_subdirectories) closedir(); } • Make sure not having zombies. And finally, find the bug!:
CPE 357 Systems Programming Assignment 4
Exercise:
Write a high performance program!
In fact, write two programs! Program 2 calls program 1 several times. Program 1 should share
the work with its copies over shared memory.
Things to check out:
execv()
“gather” function
named shared memory
Program 1, the performance program:
Download the assignment template and read and understand the code. Check the TODO’s.
The program basically multiplies two 10×10 matrices together and prints the result.
The idea is to be able to call this program multiple times at the same time, and each isntance
of the program shares the matrices and works ona certain part of the matrix multiplication,
so that the computational time becomes a fraction in comparison with only one instance.
The program should be called with two arguments: the par_id and the par_count.
Par_count .. how many instances of this program are there?
Par_id .. which instance are you?
Par_id = 0 (first instance) whould initialize all necessary shared memory pieces with shm_open
and the O_CREAT flag and also ftruncate and mmap! All other instances will need to use
shm_open() (without the O_CREAT flag) and mmap still!
Write the code for synching! Meaning, no instance should go beyond this point if not all
reached this point!
No copy and change the matrix multiplication function, so that different par_id’s work on
different part of the multiplication. Easiest way: on different rows.
Program 2, the “MPI” program:
This program gets two arguments:
argv[1]: The program which whould be called with execv (name of program1)
argv[2]: How many instances of program one should be called.
For every execv, you need to fork() and call execv in the child, because if successful, execv KILLS
the calling process! Call execv for every instance of program 1.
I.e.: if you decide to let program 1 run 4 times in parallel, and program 1 is named “par”, then:
$ ./program2 par 4
The execv’s need to be called now with:
4 times:
execv(programstring,args); with
char *args[4];
and:
args[0] = malloc(100);
args[1] = malloc(100);
… and so on
and:
strcpy(args[0],argv[1]);
strcpy(args[1], X); //X must be par_id
strcpy(args[2], Y); //X must be par_count
NULL //don’t forget for args[4]
with these different args:
”./par”, ”0”,”4”,NULL
”./par”, ”1”,”4”,NULL
”./par”, ”2”,”4”,NULL
”./par”, ”3”,”4”,NULL
In a nutshell:
Compile Flag!
-lrt … for shm_open
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
What for?
Program 2 is professionally called MPI, Message Passing Interface, and one of the most
important high performance software out there (along with OpenMP and CUDA). MPI does the
calling of your program, and one has to write the program 1 in respect to it: What if program 1
is called one time? What if 16 times? Etc.
How we test
Checking if you actually did the coding and then let the comaprison function decide.
Submission:
Submit the source code file(s) and the executables: MYNAME_hpc_ass5.zip
Bonus?
10% on the assignment if you print the time taken for the multiplication.
More interest?
I need dedicated people to work on a MPI competitor. I offer full elective credits or senior projects.
Piece by piece, we could achieve something even better. Where to start: Matrix multiplication is
easy, next is matrix inverting and calculating eigenvalues and eigenvectors.
CSC 357 Final Exam
Read first
This task sheet contains all information necessary to solve the final assignment. It is meant to be
short. You can of course reach out for clarification, but you already know everything there is to
know about how to approach this. You have 3 days’ time. Use it well and do not underestimate
this final. Start immediately. And now show that you mastered 357 and good luck!
Task
Write an mpi – controlled parallel program which calculates the matrix multiplication result of two
images and stores this into a result image. You will find three images: f0, f1 and f2. They are
quadradic, meaning width equals height. Read image f1 and f2, normalize the colors and make a
matrix multiplication, by using their colors as matrix elements. Do this for red, green and blue.
Your program should work with 1, 2, 4 and 8 instances. Measure and print the time it takes for the
calculation on the screen. Save the result image. Your result image will overflow the byte
limitation. I recommend multiplying the result colors with 0.03 before casting it into a byte.
Interpret
Let me know how you interpret the result on Piazza. No points for this, but its essential for image
processing. Also, if you want, exchange f2 with f0. This is relevant for AI image recognition. Yes,
you already are capable of doing so much!
Submit
Submit your two code files and all images zipped on Canvas with:
NAME_LASTNAME_FINAL.zip