마실(Masil)

개요

#include <sys/types.h>
#include <sys/shm.h>

int shmget(key_t key, int size, int shmflg)
void *shmat( int shmid, const void *shmaddr, int shmflg )
int shmdt( const void *shmaddr)
int shmctl(int shmid, int cmd, struct shmid_ds *buf)

공유메모리는 어떻게 할당되는가

struct shmid_ds
{
    struct         ipc_perm shm_perm;    // 퍼미션
    int            shm_segsz;            // 메모리 공간의 크기
    time_t         shm_dtime;            // 마지막 attach 시간 
    time_t         shm_dtime;            // 마지막 detach 시간 
    time_t         shm_ctime;            // 마지막 변경 시간
    unsigned short shm_cpid;             // 생성프로세스의 pid
    unsigned short shm_lpid;             // 마지막으로 작동한 프로세스의 pid
    short          shm_nattch;           // 현재 접근한 프로세스의 수
};

shm_perm

공유메모리는 여러개의 프로세스가 동시에 접근 가능하므로, 파일과 같이 그 접근권한을 분명히 명시해줘야 한다.

shm_segsz

할당된 메모리의 byte 크기이다

shm_atime

가장최근의 프로세스가 세그먼트를 attach한 시간

shm_dtime

가장최근의 프로세스가 세그먼트를 detach한 시간

shm_ctime

마지막으로 이 구조체가 변경된 시간

shm_cpid

이 구조체를 생성한 프로세스의 pid

shm_lpid

마지막으로 작동을 수행한 프로세스의 pid

shm_nattch

현재 접근중인 프로세스의 수

shmget

IPC_CREAT

key 를 이용 새로운 공유메모리 공간을 만든다.

IPC_EXCL

IPC_CREAT와 같이 사용되며, 공유메모리 공간이 이미 존재할경우 error 를 되돌려준다.

int shmid;
key_t keyval;

keyval = 1234;
shmid = shmget(keyval, sizeof(keyval), IPC_CREAT | 0666)); 
if (shmid == -1)
{
    return -1;
}

shmat

shmdt

shmctl

IPC_STAT

공유메모리 공간에 관한 정보를 가져오기 위해서 사용된다. 정보는 buf 에 저장된다.

IPC_SET

공유메모리 공간에 대한 사용자권한 변경을 위해서 사용된다. 사용자 권한 변경을 위해서는 슈퍼유저 혹은 사용자권한을 가지고 있어야 한다.

IPC_RMID

공유메모리 공간을 삭제하기 위해서 사용된다. 이 명령을 사용한다고 해서 곧바로 사용되는건 아니며, 더이상 공유메모리 공간을 사용하는 프로세스가 없을때, 즉 shm_nattch 가 0일때 까지 기다렸다가 삭제된다. 즉 해당 공유메모리 공간에 대해서 삭제표시를 하는거라고 생각하면 된다.

#include <sys/ipc.h> 
#include <sys/shm.h> 
#include <string.h> 
#include <unistd.h> 


int main()
{
    int shmid;
    int pid;

    int *cal_num;
    void *shared_memory = (void *)0;


    // 공유메모리 공간을 만든다.
    shmid = shmget((key_t)1234, sizeof(int), 0666|IPC_CREAT);

    if (shmid == -1)
    {
        perror("shmget failed : ");
        exit(0);
    }

    // 공유메모리를 사용하기 위해 프로세스메모리에 붙인다. 
    shared_memory = shmat(shmid, (void *)0, 0);
    if (shared_memory == (void *)-1)
    {
        perror("shmat failed : ");
        exit(0);
    }

    cal_num = (int *)shared_memory;
    pid = fork();
    if (pid == 0)
    {
        shmid = shmget((key_t)1234, sizeof(int), 0);
        if (shmid == -1)
        {
            perror("shmget failed : ");
            exit(0);
        }
        shared_memory = shmat(shmid, (void *)0, 0666|IPC_CREAT);
        if (shared_memory == (void *)-1)
        {
            perror("shmat failed : ");
            exit(0);
        }
        cal_num = (int *)shared_memory;
        *cal_num = 1;

        while(1)
        {
            *cal_num = *cal_num + 1;
            printf("child %d\n", *cal_num); 
            sleep(1);
        }
    }

    // 부모 프로세스로 공유메모리의 내용을 보여준다. 
    else if(pid > 0)
    {
        while(1)
        {
            sleep(1);
            printf("%d\n", *cal_num);
        }
    }
}

쉘 코멘드로 공유메모리 제어하기

<프로젝트 요약>

1. 프로젝트의 개요

1. 메모리 페이지 교체 알고리즘.

2. CPU 프로세스 스케줄링 알고리즘.

3. DISK의 구조와 파일의 생성, 삭제, 수정 시 DISK의 상태변화.

1, 2, 3에 대한 성능 비교.

2. 제안 프로젝트의 필요성

1. 운영체제 자원관리에 대한 학습.

2. 자원관리 알고리즘의 성능 비교.

3. 운영체제에서 사용하는 자원관리 알고리즘 학습에 대한 자료 제공.

3. 프로젝트 개발의 목표

1. 메모리 페이지 교체 성능 비교 시뮬레이터 개발.

2. CPU 프로세스 스케줄링 성능 비교 시뮬레이터 개발.

3. DISK의 구조와 파일의 생성, 삭제, 수정 시 DISK의 상태변화

시뮬레이터 개발.

4. 개발 방법

1. 온오프라인을 이용한 대화를 통한 프로젝트 수행.

2. 각 팀원별로 특정 부분 담당.

3. Linux에서 C로 구현.

4. GDB(디버거)를 사용.




[ 다운 로드 ]

Bakery 알고리즘

======================================================================

do

{

   choosing[i] = true;

   number[i] = max(number[0], number[1], ... , number[n-1]) + 1;

  choosing[i] = false;

  for (j = 0;j <n;j++) {

      while (choosing[j]); 

      while ((number[j] != 0) &&((number[j], j) <(number[i], i)));

   }

      critical section

   number[i] = 0;

      remainder section

} while(1)
======================================================================

CS : Critical Section

먼저, 여러분들이 헷갈리는것을 미연에 방지하기 위하여 모든 프로세스들은 본 알고리즘을 자신의
내부에 내장하고 있다고 전제하며, 각각의 프로세스들이 주체가 되어 알고리즘을 이용해서 자신이 CS에 들어가야할지, 아니면 더 기다려야 할지를 결정한다는 것이다.

일단, CS에 들어갈 준비가 된 순간 프로세스 i는 i번째 번호표를 부여받는다.(이때 i는 프로세스 자신의 번호). 바로 number[i]에 부여받은 번호가 들어가게 되는데, 잘보시면 끝에 "+1"이 있다. 현재 대기중인 가장 큰 번호보다 한개가 더 큰 번호가 번호표에 기재된다. 또 보면 알겠지만 CS돌입 준비가 끝나고 번호를 받는 순간 choosing[i]은 참값이 된다는 사실에서, 다른 프로세스(CS 돌입 준비를 끝내고 대기중인)들 역시 for 루프내에서 모종의 음모를 꾸미다가 어떤 프로세스가 CS돌입을 위한 번호표를 받을때면 모든것을 엄숙하게 중단하고 번호표를 받는 프로세스를 주시하게 된다. 새로운 프로세스의 번호표에 번호가 기재됬음을 확인한 다음에야 비로서 다시 for 루프는 돌아간다. 이유를 예를 들어 설명하면,
Px가 번호표를 받는 중에 ( max값을 확인하고 +1을 하기전에...) Pi 역시 번호표를 할당받고 for루프안으로 먼저 들어왔다면  number[i]와 number[x]가 같아질 수 (즉 같은 번호표를 받을 수)있기 때문이다. 따라서 이러한 경우를 감안해서 기다려주는 것이다.

for 루프 내부를 한번 보자. 먼저 for 루프는 0부터 n-1개 까지, 즉 총 n개의 번호표 number[]를 차례로 훑어 보면서 각 번호표에 번호가 새겨져있는지를 확인하게 된다. 0은 아무 번호도 기재되어있지 않다는 뜻이다. 이 프로세스들은 CS 돌입에 대한 의사가 없는 프로세스들이다. 그래서 모두 0이면 for loop를 유유자적하게 빠져나와 CS에 돌입하게 된다. 허나, 누군가의 번호표가 0이 아님과 동시에(누군가 CS돌입을 신청) 이것이 자신의 번호표보다 작은 값인지를 확인한다. 만일 작은 값이거나 값이 같더라도 프로세스 번호가(번호표의 번호와 프로세스 번호는 다르다는것을 주지하시길) 자신보다 작다면 그냥 루프는 돌아간다는 사실에서 아직 자신은 CS에 들어갈때가 아니라는 것을 알게 된다.

만일 위의 경우가 아니라면 자신의 번호표 번호가 가장 작거나 번호표 번호가 같더라도 프로세스 번호가 자신이 가장 작은 경우이므로 그냥~ 루프에서 벗어나면서 CS로 쏙~ 들어가서 기득권을 얻게 된다.

이 알고리즘에서 번호표의 번호와 프로세스 번호를 각각 고려하는 이유는 보시면 알겠지만 공통 데이터 스트럭쳐인 배열들(바로 choosing[]과 number[]) 자체도 CS문제를 안고 있기에 동시에 두 프로세스가 CS돌입 준비를 하면서 번호표에 똑같은 번호를 받는 경우가 발생할수 있다.(+1을 한참 하려는 와중에 또 다른 프로세스가 CS돌입을 준비 해버리면 업데이트 되기도 전에 번호표를 같이 부여받는 경우) 그래서 그 경우에 대한 해결책으로써 만일 두 번호표의 내용이 같다면!? 그때는 프로세스의 고유 번호를 비교하게 되고, 결국 프로세스 번호가 낮은 녀석이 기득권을 쥐게 된다.

CS에서 일을 해결하고 나오면서 자신이 부여받은 번호표의 내용을 0으로 다시 초기화 시킴으로써 다른 사람들이 프로세스들이 CS에 돌입할수 있도록 배려를 해주게 된다. 그리고 나서 여유를 가지고 RS에서 자기 하고픈일 계속 하게 된다. 베이커리 알고리즘은 위에 프로세스의 3가지 조건을 모두 만족한다.

Mutual Exclusion

 먼저 Pi가 Critical Section에 이미 가 있고 Pk가 번호표를 이미 가지고 있다고 가정하자.
(즉 Pk는 CS에 들어가려고 시도한다고 가정)

  만약 Pi와 Pk모두 Pi가 Critical Section에 들어가야 겠다는 결정을 하기 전에 둘 모두 번호표를 가지고 있었다면   알고리즘상 number[i]와 number[k]가 비교되었을 것이고 따라서 (number[i],i)<(number[k],k)라는 조건이 만족되었음을 알 수 있다.  그렇지 않았다면 Pi는 Critical Section에 진입하지 못했을
것이다. Pi가 Critical Section에 진입한 후 Pj가 번호표를 할당받았다면 번호표를 부여하는 방식의 특성상 Pk가 받은 번호표는 Pi의 것보다 큰 것이 확실하다.

따라서 Pk는 Pi가 CS에서 나올 때까지 CS에 접근할 수 없다. Mutual Exclusion 조건이 만족된다는 이야기다.

나머지 두개의 규칙 .Progress와 Bounded Waiting은 당연히 만족한다.

나중에 번호표를 받은 프로세스들은 먼저 번호표를 받은 프로세스보다 우선순위가 작고, 번호표의 우선순위가 같은 경우 프로세스 번호를 이용하여 우선순위를 결정하게 되므로 하나의 프로세스가 영원히 기다리게 될 우려는 없다.

[ 예제 소스 다운로드 ]

참고 : http://blog.naver.com/leaders3?Redirect=Log&logNo=80019356655
          http://blog.naver.com/femalesheep?Redirect=Log&logNo=60009236314        

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <pthread.h>

#define N 2048

int **a;
int **b;
int **c;

int row_block;

void *cal_matrix(void *arg);

int main(int argc, char* argv[])
{
 FILE *fp1, *fp2, *fp3;
 
 time_t start, end;

 int i, j;

 // thread 갯수 int 형으로...
 int thread_i = atoi(argv[4]);

 // thread ID 부여받기 위한 변수
 pthread_t *tcb = (pthread_t *)calloc(thread_i, sizeof(pthread_t));

 // thread 에 argument 넘겨주기 위함
 int *arg = (int *)calloc(thread_i, sizeof(int));

 //하나의 thread 에 실행될 row 갯수
 row_block = N / thread_i;

 /*****************************/
 /* argument 검사                    */
 /*****************************/
 if (argc != 5)
 {
  printf("Argument is not enough! \n");
  exit(1);
 }

 /*****************************/
 /* FILE 열기                          */
 /*****************************/
 fp1 = fopen(argv[1], "w+");
 fp2 = fopen(argv[2], "w+");
 fp3 = fopen(argv[3], "w+");
 
 /*****************************/
 /* 배열 동적 할당                   */
 /*****************************/
 a = (int **)calloc(N, sizeof(int));
 b = (int **)calloc(N, sizeof(int));
 c = (int **)calloc(N, sizeof(int));

 for (i = 0; i < N; i++)
 {
  a[i] = (int *)calloc(N, sizeof(int));
  b[i] = (int *)calloc(N, sizeof(int));
  c[i] = (int *)calloc(N, sizeof(int));
 }

 /*****************************/
 /* 배열에 랜덤값 입력              */
 /*****************************/
 srand(time(NULL));
 for (i = 0; i < N; i++ )
 {
  for (j = 0; j < N ; j++ )
  {
   a[i][j] = rand() % 100;
   fprintf(fp1, "%d ", a[i][j]);
   b[i][j] = rand() % 100;
   fprintf(fp2, "%d ", b[i][j]);
  }
 }
 
 /*****************************/
 /* time 측정(start)                  */
 /*****************************/
 printf("program start ... \n");
 start = time(NULL);

 /*****************************/
 /* pthread 생성                      */
 /*****************************/
 for (i = 0; i < atoi(argv[4]); i++)
 {
  arg[i] = i;
  pthread_create(tcb+i, NULL, cal_matrix, arg+i);
 }
 /*****************************/
 /* thread 대기                        */
 /*****************************/
 for (j = 0; j < atoi(argv[4]); j++)
 {
  pthread_join(tcb[i], NULL);
 }

 /*****************************/
 /* 행렬 C 파일에 쓰기             */
 /*****************************/
 for (i = 0; i < N; i++)
 {
  for (j = 0; j < N; j++)
  {
   fprintf(fp3 , "%d ", c[i][j]);
  }
 }

 /*****************************/
 /* time 측정(end)                   */
 /*****************************/
 end = time(NULL);
 printf("time  :  %d  seconds\n", (end-start));
     printf("c[0][0]  :  %d\n",  c[0][0]);
 printf("program end ... \n");

 /*****************************/
 /* 동적공간 반환 & FILE 닫음   */
 /*****************************/
 free(a);
 free(b);
 free(c);
 free(tcb);
 free(arg);

 fclose(fp1);
 fclose(fp2);
 fclose(fp3);
 
 return 0;
}// main

/*****************************/
/* 배열 곱셈하는 함수             */
/*****************************/
void *cal_matrix(void *arg)
{
 int i, j, k;
 int row = row_block * (*((int *)arg));
 int box = row + row_block;
 printf("row=%d row_block=%d\n", row, row_block);
 for(i = 0; i < N ; i++)
 {
  for (j = 0; j < N; j++)
  {
   for (k = row; k < box; k++)
   {    
    c[i][j]  += a[i][k] * b[k][j];
   }//for            
  }// for
 }//for
}// cal_matrix


####### 로직은 맞는데 c 에 값이 제대로 안들어감 (누가 고쳐주셈.ㅡㅜ) #######

[보고서 다운로드]
[다른 완성본 다운로드]

#include  <stdio.h>
#include  <time.h>
#define  N 2048

main(){
      int  **a,  **b,  **c;
      register int  s,  e,  i,  j,  k, sum,  sum_col1 = 0, sum_col2 = 0;

 a = (int **)calloc(N, sizeof(int));
 b = (int **)calloc(N, sizeof(int));
 c = (int **)calloc(N, sizeof(int));

 for ( i = 0; i < N; i++ )
 {
  a[i] = (int *)calloc(N, sizeof(int));
  b[i] = (int *)calloc(N, sizeof(int));
  c[i] = (int *)calloc(N, sizeof(int));
 }

      printf("Program  Starting....\n");

      for  (i  =  0;  i  <  N;  i++){
            for  (j  =  0;  j  <  N;  j++){
                  a[i][j]  =  1;
                  b[i][j]  =  2;
                  c[i][j]  =  0;
            }
      }

    s  =  clock();
 sum = 0;
   for ( j = 0; j < N; j++ )
      {
            for ( k = j; k < N; k++ )
     {
    if ( j != k)
    {
       sum = b[j][k];
       b[j][k] = b[k][i];
       b[k][i] = sum;
    }
     }
      }
 
      for  (i  =  0;  i  <  N/2;  i++)
   {
            for  (j  =  0;  j  <  N;  j++)
   {
    sum_col1 = 0;
    sum_col2 = 0;

                  for  (k  =  0;  k  <  N/2;  k++)
      {
                       sum_col1 += (a[i*2][k*2]*b[j][k*2]) + (a[i*2][k*2+1]*b[j][k*2+1]);
        sum_col2 += (a[i*2+1][k*2]*b[j][k*2]) + (a[i*2+1][k*2+1]*b[j][k*2+1]);
      }
      c[i*2][j] = sum_col1;
      c[i*2+1][j] = sum_col2;
   }
 }
 
      e  =  clock();
      printf("time  :  %d  clocks \n",  (e-s));
      printf("time  :  %d  seconds \n",  (e-s)/CLOCKS_PER_SEC);
      printf("c[1][1]  :  %d\n",  c[1][1]);
      printf("Program  End....\n");

   for(i = 0; i < N; i++)
  {
   free(a[i]);
   free(b[i]);
   free(c[i]);
     }

     free(a);
     free(b);
     free(c);

}

[보고서 다운로드]

#include  <stdio.h>

#include  <time.h>

#define  N  512

main(){

      int  a[N][N],  b[N][N],  c[N][N];

      int  s,  e,  i,  j,  k,  sum;

      printf("Program  Starting....n");

      for  (i  =  0;  i  <  N;  i++){

            for  (j  =  0;  j  <  N;  j++){

                  a[i][j]  =  1;

                  b[i][j]  =  2;

                  c[i][j]  =  0;

            }

      }

    s  =  clock();

    //  수정해야할  코드  시작

      sum = 0;

      for ( j = 0; j < N; j++ )

      {

            for ( k = 0; k < N; k++ )

          {

                  sum = b[j][k];

                  b[j][k] = b[k][i];

                  b[k][i] = sum;

          }

      }

      for  (i  =  0;  i  <  N;  i++)

      {

            for  (j  =  0;  j  <  N;  j++)

          {

                  for  (k  =  0;  k  <  N/2;  k++)

                {

                        c[i][j]  += (a[i][k*2]*b[j][k*2]) + (a[i][k*2+1]*b[j][k*2+1]);

                }

          }

      }

      //  수정해야할  코드  끝

      e  =  clock();

      printf("time  :  %d  clocksn",  (e-s));

      printf("time  :  %d  secondsn",  (e-s)/CLOCKS_PER_SEC);

      printf("c[1][1]  :  %dn",  c[1][1]);

      printf("Program  End....n");

}

2. 설명

▷ strategy 1

1) b행렬의 가로와 세로행을 바꾼다.

이유 : b행렬을 행방향 증가로 바꾸는 이유를 예로 들어 설명하면

만약 a[0][0]을 불러오면 캐쉬에서 miss 가 나면서 메모리에서 불러온다.

이때 캐쉬에는 a[0][0]부터 a[0][512] 까지 행단위로 캐쉬에 잡히게 된다.

(컴퓨터마다 캐쉬의 크기가 조금씩 다르다.)

그래서 행단위로 읽으면 캐쉬에서 miss 가 나지 않기 때문에 좀더 빨리 읽어들일 수 있다.

하지만 열단위로 읽으면 행을 바꿀때마다 miss 가 나면서 캐쉬를 비우고 새로운 행을 캐쉬에 담게 되기 때문이다.

▷ strategy 2

1) k 값을 1/2 로 줄인다.

2) for 문을 반만큼 도는 대신에 행을 2개씩 계산한다.

이유 : loop-unrolling 기법으로 for문의 반복횟수를 줄이는 방법이다. for문은 branch의

대표적인 경우로, for문을 반으로 돌리는 대신에 같은 명령을 paste한다면 분기 예측 할

필요를 없애주기 때문에 혹시 있을지 모를 분기 예측 실패율을 막아준다.

(캐쉬와는 크게 상관은 없지만 캐쉬에 담긴 행을 2개씩 계산한다는 점에서 볼 수도 있다.)