Problem
This is one of the assignment in Operating System course. The deadline is passed already, and I would like to take notes here descripting how I implemented this assignment.
In this assignment, we are ask to calculate the multiplication(matrix C) of two input matrix A and B. A and B is simply defined in n dimension, the are same and looks like:
[ [ 0, 1, ....., n-1],
[ n, n+1, ...,2n-1],
[... , ......n*n] ]
which mean A[i][j] = B[i][j] = i*n + j.
We are asked to use shared memory for matrix C. And threads are forked in the original process, so that this multiplication can be processed by 2 or 4 processes in the same time, which will showed much faster if using 4 processes. The result we have to show is the sum of matrix C.
Tools
To create, attach, detach and release the shared memory, we can apply the following functions:
- shmget(key, sizeof(unsigned int) * n * n, shmflg)
- Getting a shared memory ID from the system, you will get the same ID if you are using the same input key, which can be any integer.
- shmat(shmidC, NULL, 0))
- By passing the shared memory ID, shmat returns the real address of the shared memory.
- shmdt(C)
- After we've done all the things related to the shared memory, we have to detach the shared memory (this should be called before exiting any child process).
- shmctl(shmidC, IPC_RMID, 0)
- Release the shared memory. While we're not using the shared memory anymore, it's time to release the memory, so that the operating system won't have to clean up manually.
Code
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <unistd.h>
#include <sys/ipc.h>
#include <sys/shm.h>
#include <sys/wait.h>
#include <sys/time.h>
/* Magic Number for Key */
#define MAGIC_NUMBER 1111
/* Global Array for A, B */
unsigned int A[800][800], B[800][800];
unsigned int *C;
/* Function Definitions */
unsigned long long processOne(int n);
unsigned long long processTwo(int n);
unsigned long long processFour(int n);
void initMemory();
/* Global Variables for shared memory ID */
int shmidC;
/* Self-write Functions for Attaching Shared Memories */
unsigned int *attachSharedMemoryC(int n);
void detachSharedMemory();
void detachAndReleaseSharedMemory();
/* Main */
int main() {
// inits
unsigned long long sum = 0;
int n, sec, usec;
struct timeval start, end;
printf("Input the matrix dimension: ");
scanf("%d", &n);
initMemory(n);
// 1-partition
gettimeofday(&start, 0);
sum = processOne(n);
gettimeofday(&end, 0);
sec = end.tv_sec - start.tv_sec;
usec = end.tv_usec - start.tv_usec;
printf("Multiplying matrices by 1 process: %f sec\n", sec + (usec/1000000.0));
printf("Element Sum: %llu\n\n", sum);
// 2-partition
gettimeofday(&start, 0);
sum = processTwo(n);
gettimeofday(&end, 0);
sec = end.tv_sec - start.tv_sec;
usec = end.tv_usec - start.tv_usec;
printf("Multiplying matrices by 2 processes: %f sec\n", sec + (usec/1000000.0));
printf("Element Sum: %llu\n\n", sum);
// 4-partition
gettimeofday(&start, 0);
sum = processFour(n);
gettimeofday(&end, 0);
sec = end.tv_sec - start.tv_sec;
usec = end.tv_usec - start.tv_usec;
printf("Multiplying matrices by 4 processes: %f sec\n", sec + (usec/1000000.0));
printf("Element Sum: %llu\n\n", sum);
//
return 0;
}
void initMemory(int n){
int i, j;
for( i=0 ; i<n ; i++ ){
for( j=0 ; j<n ; j++ ){
A[i][j] = B[i][j] = i*n + j;
}
}
}
unsigned long long processOne(int n){
int i, j, k;
unsigned long long sum = 0;
// calculate C
for( i=0 ; i<n ; i++ ){
for( j=0 ; j<n ; j++ ){
unsigned int tc = 0;
for( k=0 ; k<n ; k++ ){
tc += (A[i][k] * B[k][j]);
}
sum += tc;
}
}
return sum;
}
unsigned long long processTwo(int n){
int i, j, k;
C = attachSharedMemoryC(n);
// sum saves here
unsigned long long sum = 0;
// fork here
pid_t pid;
pid = fork();
if(pid <0) {
// if error, fork failed
fprintf(stderr, "Fork Failed");
exit(-1);
}
else if(pid == 0){
// child, and calc the first part, i=0 ~ n/2
for( i=0 ; i<n/2 ; i++ ){
for( j=0 ; j<n ; j++ ){
C[i*n + j] = 0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
detachSharedMemory();
exit(0);
}
else {
// parent, i=n/2 ~ n
for( i=n/2 ; i<n ; i++ ){
for( j=0 ; j<n ; j++ ){
C[i*n + j] =0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
// if parent
wait(NULL);
// sum up here
for( i=0 ; i<n*n ; i++ ) sum += C[i];
detachAndReleaseSharedMemory();
}
return sum;
}
unsigned long long processFour(int n){
int i, j, k;
unsigned long long sum = 0;
C = attachSharedMemoryC(n);
// fork here
pid_t pid;
pid = fork();
if(pid <0) {
// if error, fork failed
fprintf(stderr, "Fork Failed");
exit(-1);
}
else if(pid == 0){
// fork here
pid_t pid2;
pid2 = fork();
if(pid2 <0) {
// if error, fork failed
fprintf(stderr, "Fork Failed");
exit(-1);
}
else if(pid2 == 0){
// child, and calc the first part, i=0 ~ n/2
for( i=0 ; i<n/2 ; i++ ){
for( j=0 ; j<n/2 ; j++ ){
C[i*n + j] = 0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
detachSharedMemory();
exit(0);
}
else {
// parent, i=n/2 ~ n
for( i=n/2 ; i<n ; i++ ){
for( j=0 ; j<n/2 ; j++ ){
C[i*n + j] = 0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
wait(NULL);
}
detachSharedMemory();
exit(0);
}
else {
// fork here
pid_t pid3;
pid3 = fork();
if(pid3 <0) {
// if error, fork failed
fprintf(stderr, "Fork Failed");
exit(-1);
}
else if(pid3 == 0){
// child, and calc the first part, i=0 ~ n/2
for( i=0 ; i<n/2 ; i++ ){
for( j=n/2 ; j<n ; j++ ){
C[i*n + j] = 0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
detachSharedMemory();
exit(0);
}
else {
// parent, i=n/2 ~ n
for( i=n/2 ; i<n ; i++ ){
for( j=n/2 ; j<n ; j++ ){
C[i*n + j] = 0;
for( k=0 ; k<n ; k++ ){
C[i*n + j] += A[i][k] * B[k][j];
}
}
}
// if parent
wait(NULL);
wait(NULL);
// sum up here
for( i=0 ; i<n*n ; i++ ) sum += C[i];
detachAndReleaseSharedMemory();
}
}
return sum;
}
void detachAndReleaseSharedMemory(){
detachSharedMemory();
if (shmctl(shmidC, IPC_RMID, 0) == -1) {
fprintf(stderr, "shmctl(IPC_RMID) failed\n");
exit(1);
}
}
void detachSharedMemory(){
if (shmdt(C) == -1) {
fprintf(stderr, "shmdt failed\n");
exit(EXIT_FAILURE);
}
}
unsigned int *attachSharedMemoryC(int n){
// setup shared memory
key_t key = MAGIC_NUMBER;
int shmflg = IPC_CREAT | 0666;
if((shmidC = shmget(key, sizeof(unsigned int) * n * n, shmflg)) == -1) {
perror("shmget: shmget failed");
exit(1);
}
unsigned int *sC;
if((sC = shmat(shmidC, NULL, 0)) == (unsigned int*)-1) {
perror("shmat: attach error");
exit(1);
}
return sC;
}
.png)