Windows Hooking을 연구하다가 기초가 너무 없음을 느끼고서 차근차근 해보자는 심정으로 조사를 해봤다.

일단. GDT!

1) GDT

GDT : Global Descriptor Table의 약자이며, 해당 레벨에 사용할 메모리 영역을 지정하는데 이때 메모리 전체의 사용 영역을 서술하는 테이블을 GDT라고 한다.

이때! 레벨에 사용할 메모리 영역을 지정하는게 또 뭔가...ㅠ

사용자가 커널공간을 침범하기 못하게 하기 위해 CPU자체에서 메모리 접근에 대한 검사를 하는데 이때 이 특권링, 혹은 특권레벨을 검사하게 된다. 

Level 0 : 커널 공간(Core)

Level 1~2 : 커널 공간(Subsystem )

Level 3 : 유저 공간

으로 나뉘어 지며, Level 0에는 커널의 핵심 부분이 위치하고, 디바이스나 GUI같은 서비스들은 Level 1~2에 위치하며 User Application은 Level 3에 위치하게 된다. 하지만 보통의 운영체제는  0,3 두가지만 사용된다고 한다.

GDT는 세그먼트 디스크립터 자료구조를 이용해 테이블에 저장하는데, 세그먼트 디스크립터의 구조를 보면 다음과 같다.

< 세그먼트 디스크립터(SD : Segment Descriptor) >

GDT의 자세한 구조는 IA-32 Intel(R) Architecture Software Developer's Manual에 나와있습니다.

우리가 알아볼 것은 GDT에서 중요한 DPL과 Type필드인데 

DPL - (Descriptor Privilege Level)로 2비트로 되어 있으며, 특권 레벨 지정에 쓰인다.

Type - 해당 영역이 코드인지, 데이터 혹은 읽기/쓰기 권한, 실행 권한을 지정한다.

2) LDT

LDT : Local Descriptor Table의 약자이며, GDT가 운영체제와 모든 어플리케이션에서 참조하는 세그먼트들을 정의할 때 쓰인다면, LDT는 각각의 어플리케이션마다 고유한 세그먼트를 정의할 때 사용된다. 또한 LDT의 특징으로는 태스크 전환에 연동되어 전환이 가능한 테이블이며,Base address, access rights, 타입, 길이, 그리고 현재 세그먼트에 대한 사용 정보를 저장합니다. 

LDT의 위치를 나타내는 세그먼트 디스크립터를 GDT안에 저장한뒤에, 그떄의 인덱스를 LDTR레지스터에 넣어주면, CPU는 LDT를 읽어들임으로써 태스크의 전환이 일어나게 되는것이다.

3) IDT

IDT : Interrupt Descriptor Table의 약자로써, 인터럽트가 발생하였을 때 처리해주는 함수의 루틴을 포함하는 테이블이다.(인터럽트에 관한 자료는 이전 포스팅 참조)

< IDT 구조 >

Offset 15:0과 Offset 31:16 이 두 필드가 합쳐진 32비트 값이 실제 인터럽트처리 루틴의 주소를 가지고 있는 인터럽트오브젝트의 주소를 나타낸다. 만일, 프로세서가 여러 개라면 IDT도 프로세서의 개수에 맞추어 존재한다. 

4) SSDT

SSDT : System Service Dispatch Table 의 약자이며, System service API함수(Native API)의 주소를 담고 있는 테이블이다. System service API는 유저모드 애플리케이션이 Kernel service를 받고자 할 때 사용되는 함수이다.

KeServiceDescriptorTable은 커널이 제공하는 테이블로써 SSDT의 주소를 가지고 있다.

총 4개의 서비스 테이블로 구성되어 있고 각각의 서비스 테이블은 ServiceDescriptorEntry라는 구조체로 이루어져 있다.

typedef struct ServiceDescriptorEntry{

PDWORD base

PDWORD counter

DWORD limit

PBYTE arg

}SDE;

typedef struct ServiceDescriptorTable{

SDE ntoskrnl;

SDE win32k;

SDE reserved[2];

}SDT;

< SDT 구조 >

base - 함수 테이블의 시작주소를 가르킴

counter - 각 함수가 몇 번 호출되었는지를 기록함.

limit - 함수 테이블에 포함된 함수의 개수를 저장.

arg - 인자크기를 저장하는 테이블 시작주소 가르킴.

1) Flag register

Flag register는 CPU 내부 기구중 하나로 산술 연산 결과의 상태를 보여주는 레지스터이다.

(상태 레지스터)

CPU에 의해 세팅되며, 프로세서의 상태를 결정한다.

상태 플래그

CF (Carry Falg)

부호 없는 산술 연산에 쓰임.

PF(Parity Flag)

1인 비트의 수가 짝수면 1, 홀수면 0으로 설정된다.

ZF(Zero Flag)

연산 결과가 0이 되었을떄 설정

SF(Sign Flag)

연산 결과중에 음수로 바뀌었을 떄 설정

OF(Overflow Flag)

부호를 갖는 산술 연산에서 오버플로우 발생 유무 표시

1=overflow 

Mutex란?

Mutual Exclustion의 으로, Critical Section문제를 해결하기 위한 방법중 하나이다.

뮤텍스 개체는 잠겨지지 않은(unlocked)상태와 잠금(locked)상태의 두가지 상태를 가지며, 동시에 둘 이상의 쓰레드가 소유할 수 없다. 뮤텍스는 잠그기 위해 기다리는 쓰레드들을 위한 큐를 가지고 있어서, 이미 다른 쓰레드에 의해 잠겨 있는 뮤텍스를 획득하려고 시도하면 쓰레드는 큐에 들어가고 다시 대기상태로 빠지게 된다.

Mutex 생성,소멸 함수.

#include<pthread.h>

int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *addr);

int pthread_mutex_destroy(pthread_mutex_t *mutex);

mutex -> 뮤텍스 생성시에는 뮤텍스의  참조 값 저장을 위한 변수의 주소 값 전달, 그리고 뮤텍스

소멸 시에는 소멸하고자 하는 뮤텍스의 참조 값을 저장하고 있는 변수의 주소값 전달.

attr -> 생성하는 뮤텍스의 특성정보를 담고 있는 변수의 주소 값 전달. 별도의 특성을 지정하지 않을

   경우 NULL 전달.

Mutex lock,unlock 함수

#include<pthread.h>

int pthread_mutex_lock(pthread_mutex *mutex);

int pthread_mutex_unlock(pthread_mutex *mutex);

예제)

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

#define NUM_THREAD 100

void *thread_inc(void *arg);
void *thread_des(void *arg);
long long num =0;

int main(int argc,char *argv[]){

        pthread_t thread_id[NUM_THREAD];    //Thread ID를 저장할 배열.
        int i;

        printf("sizeof long long : %d\n",sizeof(long long));
        for(i=0;i<NUM_THREAD;i++){
                if(i%2)
                        pthread_create(&(thread_id[i]),NULL,thread_inc,NULL);    

//thread를 생성하고, 생성된 thread는 thread_inc를 실행한다.
                else
                        pthread_create(&(thread_id[i]),NULL,thread_des,NULL);

//thread를 생성하고, 생성된 thread는 thread_des를 실행한다.
        }

        for(i=0;i<NUM_THREAD;i++)
                pthread_join(thread_id[i],NULL);    //각각의 thread가 끝날때까지 주프로세스가기다림.

        printf("result : %lld \n",num);
        return 0;
}

void *thread_inc(void *arg){    //짝수 thread가 실행하는 부분.
        int i;
        for(i=0;i<50000000;i++)
                num+=1;
}

void *thread_des(void *arg){    //홀수 thread가 실행하는 부분.
        int i;
        for(i=0;i<50000000;i++)
                num-=1;
}

<출처 : 윤성우 열혈 TCP/IP 소켓프로그래밍>

위와 같은 소스를 가지고 있는 프로그램이 있다. 쓰레드를 100개 생성시키고, 50개는 num을 증가시키고 나머지 50개는 num을 감소시키는 프로그램이다. 이 프로그램을 실행시키면 원하는 답은 0이지만 실행 결과는 그렇지 않다.

위와 같은 일이 발생하는 이유는 Critical Section(임계영역)문제인데, 이와 관련해서는 이 전의 포스팅을 참조하기 바란다.

http://taesun1114.tistory.com/entry/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4%EA%B0%84-%ED%86%B5%EC%8B%A0%EA%B3%B5%EC%9C%A0%EB%A9%94%EB%AA%A8%EB%A6%AC

따라서, 각각의 쓰레드가 num+=1 or num-=1을 실행할 때는 다른 쓰레드가 이 부분에 접근하면 안된다. 이를 위해서 Mutex를 사용한다.

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

#define NUM_THREAD 100

void *thread_inc(void *arg);
void *thread_des(void *arg);
long long num =0;

int main(int argc,char *argv[]){

pthread_t thread_id[NUM_THREAD];    //Thread ID를 저장할 배열.
int i;

pthread_mutex_init(&mutex,NULL);    // mutex생성함수.

printf("sizeof long long : %d\n",sizeof(long long));

for(i=0;i<NUM_THREAD;i++){
        if(i%2)
            pthread_create(&(thread_id[i]),NULL,thread_inc,NULL);

//Thread를 생성하고 thread_inc를 실행한다.
        else
            pthread_create(&(thread_id[i]),NULL,thread_des,NULL);

//Thread를 생성하고 thread_des를 실행한다.
}

for(i=0;i<NUM_THREAD;i++)
        pthread_join(thread_id[i],NULL);    //각각의 thread가 끝날때까지 기다림.

printf("result : %lld \n",num);

pthread_mutex_destroy(&mutex);    //Mutex소멸함수.

return 0;
}

void *thread_inc(void *arg){
    int i;

    pthread_mutex_lock(&mutex);    //Mutex를 이용,다른쓰레드의 접근을 막는다.
    for(i=0;i<50000000;i++)
        num+=1;

    pthread_mutex_unlock(&mutex);    //Critical section을 벗어났으므로, 다른쓰레드 접근허용.
}

void *thread_des(void *arg){
    int i;

    pthread_mutex_lock(&mutex);    //다른 쓰레드의 접근을 막는다.
    for(i=0;i<50000000;i++)
        num-=1;

    pthread_mutex_unlock(&mutex);    //Critical section을 벗어났으므로, 다른쓰레드 접근허용.

}

Classic Problems of Synchronization

Classic Problems of Synchronization에는 몇가지가 있는데.

1.The Bounded -Buffer Problem

2. The Readers - Writers Problem

이다.

1. Bounded - Buffer Problem

공유버퍼를 가지고  한쪽에서는 데이터를 입력하고 (Producer) 다른 한쪽에서는 데이터를 받아보기만 하는(Consumer) 두 프로세스의 동기화 방법이다.

Mutex로 크리티컬 섹션을 구별하기 위해 사용하고, Full,empty 변수로 입력이가능한지 혹은 데이터가 버퍼안에 들어있는지를 판단한다.

2.Reader and Writer Problem

공유데이터를 여러명이 보기만 하는 것은 상관이없으나, 쓰는도중에 보는 것은 문제가 된다. 이러한 동기화 문제를 해결하기 위해서 세마포어 변수로 wrt와 mutex를 사용하고, int readcount를 하나 더 설정한다.

readcount== 0 이라면 읽는 사람이 없는 것이므로 데이터를 수정하거나 새로 쓰는 것이 가능하지만, 누군가가 읽고 있다면, readcount!=0이라면 수정을 할 수가 없도록 wait(wrt)를 걸어 프로세스를 lock한다.

Monitor

단일 처리기인 경우에는 Critical Section인 경우에 interrupt를 disable 시키면 되지만, 다중 처리기 환경에서는 비효율적이다. 왜냐하면 interrupt를 보내지 말라는 메세지를 모든 처리기에 전달해야 되고 Critical Section에 들어가기전에 메세지를 일일이 다 확인해야 하기 때문이다.

따라서 많은 하드웨어들이 동기화 문제를 해결하기 위한 Synchronization hardware를 가지고있는데 이중, testandset과 swap을 살펴보자.

testandset();

boolean TestAndSet(boolean *target){ 

boolean rv = *target;

*target = TRUE;

return rv;

}

testandset함수는 들어온 값을 TRUE로 바꿔주고 원래있던 값을 반환하는 함수이다.

do{

while(TestAndSet(&lock));    //lock을검사하고 TRUE면, 루프를 FALSE면 CriticalSection진입.

// Critical Section

lock = FALSE;                    //CriticalSection을통과하고다른프로세스의 진입을 허용한다는 의미로 lock을 FALSE로 바꿔준다.

//remainder section

}while(TRUE);

lock은 맨처음 FALSE로 초기화가 되어 있다. 맨처음에 들어온 프로세스가 testandset을 거치고 나면 lock은 TRUE로 바뀌고 맨처음에 들어온 프로세스는 Critical section에 들어오게 된다. Context-switch가 일어나도 lock은 FALSE이기 때문에 다른 프로세스들은 while루프를 돌게됨.

하지만 임의의순서대로 Critical Section에 들어가기 때문에 어느 한 프로세스는 계속 기다리는 경우의 수가 발생할 수도 있다. 따라서 Bounded waiting을 만족하지못한다.

swap();

void Swap(boolean *a,boolean *b){

boolean temp = *a;

*a = *b;

*b=temp;

}

do{

key = TRUE;

while(key == TRUE)            //맨처음 프로세스가 통과할때 lock은 FALSE이므로while루프를

swap(&lock,&key);            //한번실행하고 나가지만 다른프로세스가 들어오면 lock,key 모두 TRUE이므로 계속해서 while을 돌게 된다.

//Critical Section

lock = FALSE;                //Critical section을 사용하고 난 후에는 lock = FALSE;로 바꿔주어서 다른 프로세스의 진입을 허용함.

//remainder section

}while(TRUE);

하지만 swap();도 Bounded waiting을 만족하지 못함.

최종적인 코드 (Bounded waiting 만족)

do{

waiting[i]=TURE;

key = TRUE;

while(waiting[i] && key)        //맨처음프로세스만 lock=FALSE이므로 통과하고 나머지는

key=TestAndSet(&lock);  //계속 루프를 돌게 된다.

waiting[i]=FALSE;                //크리티컬섹션의 진입허용권을 얻게되었으므로 표시를해줌.

  //Process와Bounded waiting 을 만족하게끔.

//Critical section

j=(i + 1) % n;                    //최대갯수 n개로 나눠준다. 원형 Queue를 생각하면 편할듯.

while((j != i) && !waiting[j])

j=(j+1)%n;

if(j==i)                            //if 문 조건에 해당하면 나말고 다른 프로세스가 없다는 뜻.

lock =FALSE;

else                            //다른 프로세스의 진입허용.

waiting[j] = FALSE;

//remainder section

}while(TRUE);

Semaphore

int형 변수로 사용자마음대로 수정할 수 없고 wait,signal을 이용해서만 수정이 가능하다.

공유데이터 문제(Critical Section)을 해결하기 위한 문제중 하나로써, Critical Section 코드 위에 세마포어로 락을 걸어주어 프로세스가 크리티컬 섹션을 진행하다가 Context-Swich가 일어나도 다른 프로세스의 접근을 막아주어 하나의 프로세스만 들어가게 끔 만들어 준다.

Wait(S){                 // S는 세마포어를 지칭함.

while(S<=0);    // 세마포어 변수가 0이하 일때에는 루프를 돌게해서 락을 건다.

s--;                // 세마포어 변수가 1이라서 락인부분을 통과하면 Critical Section을 사용하고 다른 프로세스의 접근을 막기위해서 세마포어를 -1 시켜준다.

}

Signal(S){

S++;                //Critical Section을 거치고 난 프로세스가 실행하는 함수로 다른 프로세스의 접근을 허용함.

}

또한, 하나의 프로세스가 wait,singal을 사용하여 세마포어 값을 변경하고 있을 때에는 다른 프로세스가 값을 변경할 수 없다. Wait , Signal을 실행시에는 Atomic 해야 한다.

Atomic => 실행중에 interrupt가 발생하지 않도록 해주는 것.

운영체제는 세마포어를 Binary semaphore와 Counting semaphore로 나누기도 한다.

바이너리 세마포어는 0 or 1만을 값으로 가지지만 카운팅 세마포어의 값은 제한이 없다. 바이너리 세마포어(이진 세마포어)는 위에서 설명한 방식대로 공유리소스에 하나의 프로세스만 넣는 기법이고, 카운팅 세마포어는 공유리소스의 접근할 수 있는 최대 허용치만큼을 초기값으로 가지고 나서 공유 자원에 프로세스가 들어갈때 마다 값을 -1 해주고 세마포어 변수가 0이 되면 다른 프로세스의 접근을 막는 방식이다.

세마포어의 방법에는 2가지가 있는데...

Busy waiting

Critical Section을 사용중인 프로세스가 signal에 들어가기 전까지 다른 프로세스들은 while루프를 돌고 있으므로 오버헤드가 단점이다.

Blocking & Wake-up

waiting Queue를 만들어 waiting process를 저장하고 뮤텍스를 두어서 Critical Section을 사용한 프로세스가 waiting queue에 있는 process중 하나에게 뮤텍스를 전달하면 전달받은 프로세스가 Critical Section에 들어가는 방식. 하지만 크리티컬섹션 실행시간이 아주 짧을때는 큐에 집어넣고 뮤텍스를 전달하고 다시 큐를 빠져 나오게 해야 하므로 오버헤드가 busy waiting보다 더 클 수가 있다.

Semaphore problem

Deadlock 현상

프로세스들이 Critical Section에 들어가지 못하고 계속 while루프만 도는 것을 의미함. 예를 들어

P1                             P2

wait(S);                   wait(Q);

wait(Q);                   wait(S);

     C r i t i c a l   S e c t i o n

Signal(S);                Signal(Q);

Signal(Q);                Signal(S);

와 같은 코드가 있다면, 맨처음 p1의 wait(S);가 일어나고 Context-Switch가 일어 난 후에 P2의 wait(Q);가 실행되고 다시 P1이 실행된다면 P2의 wait(Q);에 의해서 P1 프로세스는 wait(Q);에서 signal(Q);가 있을때까지 루프를 돌게 된다. 루프를 돌던 중 P2가 실행되고 P2도 wait(S);에서 계속 루프를 돌게 된다. P1,P2둘다 아무런 진척이 없이 무한루프에 빠지는 현상을 Deadlock현상이라고 한다.

Starvation 현상

앞의 스케쥴링 기법에서도 있었던 문제점인데, 세마포어를 사용할때 Block & wake-up 방식을 이용한다고 가정하자. 이때 Queue는 LIFO방식으로 작동한다면, 처음에 들어온 프로세스는 Starvation현상이 발생할 것이다.

Priority Inversion(우선순위 역전현상)

우선순위가 낮은 프로세스가 Critical Section을 실행하던 중 우선순위가 높은 프로세스가 들어오면 CPU는 우선순위가 높은 프로세스를 실행한다. 그러다가 실행중 프로세스보다 더 높은 우선순위의 프로세스가 들어왔는데 Critical Section에 진입해야 하는 경우에 wait를 이미 한번 호출했기 때문에 진입을 할 수가 없다. 이처럼 우선순위가 낮은 프로세스가 문제가 되어 우선순위가 높은 프로세스가 진행할 수 없는 경우를 뜻한다.

이럴경우 우선순위 계승방법으로 해결이 가능한데, 우선순위가 낮은 T3가 signal을 호출하기 전까지만 T1의 우선순위를 계승하는 방법이다. signal을 호출하고 나면 우선순위가 원래대로 돌아오게 됨.

파일 디스크립터

파일을 관리하기 위해 운영체제가 필요로 하는 파일의 정보를 가지고 있는 것이다. FCB라고 함.

FCB - File Control Block 이라고 하며 FCB에는 다음과 같은 정보들이 저장되어 있다.

파일 이름

보조기억장치에서의 파일 위치

파일 구조 : 순차파일, 색인 순차 파일, 색인 파일

액세스 제어정보

파일 유형

생성 날짜와 시간, 제거 날짜와 시간

최종 수정 날짜 및 시간

액세스한 횟수

결론은 파일디스크립터란 운영체제가 만든 파일 또는 소켓의 지칭을 편히 하기 위해서 부여된 숫자이다.

※파일디스크립터를 파일핸들이라고도 하는데, 핸들이라는 표현은 윈도우에서 사용되는 용어임.

기본적으로 파일 디스크립터는 정수형으로 차례로 넘버링 되고 0,1,2는 이미 할당되어 있어서 3부터 파일 디스크립터를 부여한다.

저번 포스팅 Critical section - 공유메모리 에서 pipe로 통신하는 방법 외에도 여러가지 방법이 있어서 그중, 공유메모리를 이용한 통신을 알아보도록 하자.

일단 기본적으로 프로세스간 통신을 위해 알아야 할 함수들이다.

int shmget(key_t key, size_t size, int shmflg); // key: 공유하는 키값, size:크기, shmflg:생성 및 접근, 성공하면 양의 정수, 실패 시 -1 리턴

shmflg 옵션들

1) IPC_CREATE

키에 해당하는 값이 없다면 새로 생성한다.

IPC_CREATE 값을 입력후 | 연산자를 덧붙여 허용권한 설정.

만약 있다면 무시하며, 접근권한을 설정해준다.

2)IPC_EXCL

공유 메모리가 이미 있다면 실패를 반환하고 접근 불가능.

이옵션을 제거해 주어야 기존 공유메모리에 접근할 수 있다.

void* shmat(int smId, const void* shm_addr, int flag); // smId:공유메모리 식별자, shm_addr:공유 메모리와 연결하고자 하는 프로세스 내부의 메모리.(프로그래머가 직접 정해주는 것보다 시스템에 의해 할당되는 것이 좋으므로 일반적으로 null(0)을 세팅) flag: 속성 설정(SHM_RND:공유메모리와 연결되는 프로세스 내부 어드레스를 시스템이 관리하도록 함 , SHM_RDONLY: 읽기 전용으로 메모리를 연결, SHM_REMAP:연결영역을 대체)
가상 메모리와 물리적메모리 영역을 연결해주는 함수.

int shmdt(const void* shm_addr);
프로세스가 작업을 끝내고 더 이상 메모리 공유가 필요 없을 때, 공유메모리와 연결된 프로세스 내부의 가상 메모리 연결을 해제.

공유메모리를 설정하면 공유메모리의 semid가 주어지는데 이 ID로 공유메모리를 식별하거나 찾아들어간다.

ipcs : 현재 공유메모리 보기.

ipcrm shm [shmid] : 공유메모리 제거.

간단한 예제를 보면서 사용법을 익히기로 한다.

shared.c

#include<stdio.h>
#include<stdlib.h>
#include<sys/shm.h>                //공유메모리 함수의 라이브러리

struct shared_use_st{               //some_text 배열을 공유메모리로 사용할 것임.
                int written_by_you;
                char some_text[2048];
};

int main()
{
        int shmid;
        void* shared_memory=(void*)0;
        int running=1;
        struct shared_use_st* shared_stuff;

        shmid = shmget((key_t)1234,sizeof(struct shared_use_st),0666 | IPC_CREAT);    

        //공유메모리생성
        if(shmid == -1){
                printf("Shmget Error\n");
                exit(1);
        }
        shared_memory = shmat(shmid,(void*)0,0);    //생성한 공유메모리를 shared_memory변수에 붙인다.
        if(shared_memory == (void*)-1)
        {
                printf("Shared_memory location Error\n");
                exit(1);
        }
        shared_stuff = (struct shared_use_st *)shared_memory;//형변환후 최종적으로 구조체를 공유메모리로 설정한다.
        shared_stuff->written_by_you = 0;
        while(running){
                if(shared_stuff->written_by_you)        //written_by_you ==1이면 입력받은내용이있으므로 출력후에 0으로 바꿔줌.
                {
                        printf("Wirten is : %s\n",shared_stuff->some_text);
                        sleep(rand()%4);
                        shared_stuff->written_by_you =0;
                        if(strncmp(shared_stuff->some_text,"end",3)==0)    // end를 입력하면 종료.
                                running=0;
                }
        }

        return 0;
}

shared1.c

#include<sys/shm.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct shared_use_st{
        int written_by_you;
        char some_text[2048];
};

int main()
{
        int running =1;
        void *shared_memory =(void *)0;
        struct shared_use_st* shared_stuff;
        char buffer[100];
        int shmid;

        shmid = shmget((key_t)1234,sizeof(struct shared_use_st),0666|IPC_CREAT);

        if(shmid==-1){
                printf("Shmid Error\n");
                exit(1);
        }
        shared_memory = shmat(shmid,(void*)0,0);
        if(shared_memory == (void*)-1)
        {
                printf("Shamt Error\n");
                exit(1);
        }
        printf("Memory located at %p\n",shared_memory);
        shared_stuff = (struct shared_use_st*)shared_memory;
        while(running)
        {
                while(shared_stuff->written_by_you==1)
                {
                        sleep(1);
                        printf("waiting for client...\n");
                }
                printf("Enter some text...\n");
                fgets(buffer,100,stdin);
                strncpy(shared_stuff->some_text,buffer,2048);
                shared_stuff->written_by_you=1;
                if(strncmp(buffer,"end",3)==0)
                {
                        running=0;
                }
        }
        return 0;
}

shared.c과 shared1.c가 서로 통신을 하면서 shared1.c에서 입력한 값을 shared.c에서  출력하게 끔하는 소스이다.

shm_com.h라는 라이브러리에 sturct shared_use_st구조체가 선언되어 있다는 것을 알게됬으나, Ubuntu 11.10버전에서는 이상하게 라이브러리가 존재하지 않아서 소스딴에서 전역변수로 넣어주었다. 공유메모리 어렵다 ...조금더 확실히 알고 가야할듯하다. 하지만 지금은 시험보기 3시간전ㅋㅋㅋㅋㅋㅋㅋㅋ

Multilevel Queue scheduling

Multilevel Queue scheduuling은 기존의 FCFS or SJF or Priority의 방법은 Queue를 하나씩 두었던 반면에 이 Multilevel scheduling은 Queue를 여러개 두어 각각의 큐마다 우선순위를 두는 방식이다.

우선순위는 위의 System Process Queue가 가장 높고 밑의 Student Process가 가장낮다.

Multilevel Queue Scheduling은 각각의 큐가 서로다른 Priority를 가지고 있어서 기존의 Priority 알고리즘보다 조금 더 세밀한 프로세스의 관리가 가능하고 각각의 Queue마다 서로 다른 알고리즘 구현이 가능하다는 장점이 있지만, 프로세스가 한번 큐에 속하게 되면 다른 큐로 이동이 불가능 하다는 단점이 있다.  만약 student process에 대기중인 프로세스가 있지만, system Queue에 계속해서 프로세스가 들어온다면 student Queue에 있던 프로세스는 stavation 현상이 일어나게 된다.

※Stavation = 프로세스가 실행되지 못하게 계속 남게 되는 현상.

Priority 알고리즘에서는 Queue가 하나이기 때문에 Aging기법으로 해결하였으나, Multilevel Queue알고리즘에는 큐가 여러개이고 한번 속하면 다른 큐로 이동이 불가능 하기 때문에

Multilevel Feedback Queue Scheduling을 이용하여 문제를 해결하였다.

Multilevel Feedback Queue Scheduling

Multilevel Feedback Queue scheduling 은 위의 Multilevel Queue Scheduling 알고리즘을 확장한 개념으로, 프로세스가 큐를 이동할 수 있다는게 특징이다.

위처럼 Queue가 3개가 있다고 가정하자.

맨 위Queue의 우선순위가 가장 높고 맨밑의 우선순위가 가장낮다.

Multilevel feedback Queu Scheduling은 마지막큐를 제외하고는 time quantum을 두어서 실행시킨다.만일 첫번째 큐에 프로세스가 들어왔지만, 지정된 타임퀀텀내에 실행이 종료되지않으면 preemptive가 일어나게 되고 실행되던 프로세스는 두번째 Queue에 들어가게 된다. 만일, 두번째 Queue에서도 실행이 종료되지 않으면 마지막 FCFS Queue에 들어가게되며 실행이 종료된다.

하지만,  quantum=16인 Queue의 프로세스가 실행되던 도중에 첫번쨰 Queue에 프로세스가 들어오게 되면 Preemptive가 일어게 됨.

[Scheduling 기준척도]

CPU utilization  = CPU를 가능한 바쁘게 유지시키는지.

Turnaround time = 하나의 프로세스가 끝나는 시간.

Throughput = 시간 단위당 비슷한 프로세스가 몇개나 완료되는지.

Response Ratio(서비스시간+대기시간)/서비스시간 = 멀티태스크

nonpreemptive 스케줄링은 CPU에게 하나의 프로세스가 할당되면 그 프로세스가 I/O요청을 하여 빠져나오거나 종료 될 때까지 계속 프로세스를 실행 시키는 것이다.

preemptive스케줄링은 공유메모리 관련해서 문제가 일어난다.(프로세스의통신(공유메모리)참조.)

Process의 Scheduling에는 4가지 종류가 있는데

1. FCFS (First - come,First-serverd)

2. SJF (Shortest - Job - First)

3. Priority

4. Round - Robin