FCFS (First - come,First - serverd)

 

FCFS는 말 그대로 맨처음 오는 프로세스를 맨처음에 실행시키는 알고리즘이다.

오는 순서대로 Linked List 자료구조로 FCFS Queue에 Process - PCB를 넣어서 하나하나 차례로 실행시키고 프로세스의 자발적 CPU반납(프로세스의 종료, I/O요청)이 일어나기 전까지 실행시키는 가장 단순한 구조의 알고리즘이다.

구현은 가장 쉽지만, 효율성이 많이 떨어짐.

 

 

 

위와 같이 P1,P2,P3가 차례로 도착하고 각 프로세스의 burst time이 다음과 같다면.

 

 

CPU는 위 사진과 같이 실행할 것이다.

대기시간을 따지면,

P1 = 0 , P2 = 24, P3=27이 되어 평균 대기시간은 0+24+27/3 = 17s 가 된다.

만일, P2 ,P3 ,P1 순으로 도착했으면, 평균 대기시간은 0 + 3 + 6 /3 = 3s 가 된다. 이처럼 FCFS는 효율성이 떨어지고, 만일 여러개의 짧은 I/O CPU bound Process와 하나의 긴 CPU bound Process가 들어온다면, 여러개의 I/O Process들은 Ready Queue에서 CPU bound Process의 종료를 기다린다. 짧은 Process들을 먼저 처리하는 것과 효율성의 차이가 많이 나는데 이러한 문제점을     Convoy Effect    라고 한다.

 

이때의 Turnaround time

P1 = 0 + 24 = 24

P2 = 24 + 3 = 27

P3 = 27+ 3 = 30

 

 

'O.S' 카테고리의 다른 글

Process Scheduling - Priority  (0) 2012.04.19
Process Scheduling - SJF  (0) 2012.04.19
Critical Section - 공유메모리  (2) 2012.04.17
Interrupt  (0) 2012.04.17
Thread  (0) 2012.04.17

프로세스간의 통신 방법에는 여러가지 방법이있다.

IPC - InterProcees Communication 의 준말로 '프로세스 간 통신'을 뜻함.

 

<< IPC 종류 >> 

 

그 중에서 공유메모리 설정을 통한 프로세스간 통신을 알아보도록 알아보자.

IPC 방법중에서 가장 빠른 방법이다.하지만 Critical Section과 같은 문제점이 발생하기도 하기 때문에 이를 조심하며 프로그램을 만들어야 한다.

※Critical Section 이란 두개의 프로세스가 공유되있는 변수혹은 저장공간을 사용하는도중 생기는 문제점이 있는 코드영역을 말함.

ex)

count =0 이라는 공유변수가 있다.

Producer 프로세스와 Consumer 프로세스가 있을떄

 

while(TRUE){

/* Produce an item in nextProduced */

while(counter== BUFFER_SIZE);

buffer[i] = nextProduced;

in = (in +1) % BUFFER_SIZE;

counter++;

}

 

while(TRUE){

/*consume the item in nextConsumed */

while(counter == BUFFER_SIZE );

nextConsumed = buffer[out];

out = ( out + 1) %BUFFER_SIZE;

count --;

}

 

각각의 프로세스의 중간에 저러한 코드가 있다.

Producer 프로그램은 공유메모리(Queue)에 item을 저장하고 consumer프로그램은 공유메모리(Queue)에서 item을 받고 있다.

C언어 코드로는 문제가 없어보이지만, C언어를 어셈블러로 바꾸면 1줄의 코드가 여러줄로 바뀌게 된다.

 

count ++ ==> assembly

 

count -- ==> assembly

C언어 코드로는 한줄이지만, assembly언어로 보면 3줄이다. 만약 Producer의 count++;의 assembly를 수행중에 Context-switch가 일어나게 되는 상황을 생각해보자.

 

ex) count = 5;

Producer의 어셈블리 코드중 add1까지 수행하고 Context-switch가 일어난다.

(Produce의 count=6 이지만 Consumer의 count=5인 상황.)

consumer의 명령이 끝나고 count=4;로 저장되고 Context-switch가 일어남.

PCB 테이블의 Produce count=6이다. Producer 프로그램의 나머지 명령

mov $0x0,%eax에 의해서 count=6이 되어버린다.

 

이러한 문제점이 발견되는 코드영역을 Critical Section이라 부름.

 

공유메모리를 사용하는 방법중에는 fork를 이용한 부모,자식 프로세스간의 메모리 공유이다.

운영체제 강의 시간에 Critical Section 의 solution 중 Peterson's solution을 듣고 직접 해보기 위해 간단한 Pipe를 이용한 프로그램 코드를 구성.

 

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

int main()
{
        int pipe1[2];
        pid_t pid;
        int pass=0,process[2]={0},status,count=5;

        //두개의 파이프를 생성.
        pipe(pipe1);
        pipe(process);
        pid=fork();     //자식프로세스를 생성한다.
        if(pid==-1)
                printf("fork 실패, Process Id : %d\n",pid);
        printf("fork 성공, Process Id : %d\n",pid);

        do{
                if(pid!=0)
                        pass=1;                 //부모를 통과시킴.
                while(process[0]==0 && pass==0);//자식프로세스를묶어둠.
                if(pid!=0){
                        close(process[0]);
                        close(pipe1[0]);
                        process[0]=write(pipe1[0],&pass,sizeof(int)); 

//부모의 pass를 자식의 process[0]에 넣는다.
                        pid=wait(&status);
                        if(WIFEXITED(status))        

//자식프로세스가 끝날때까지 부모프로세스가 기다림.
                                printf("Normal exit child process\n");
                        count++;
                }
                else
                        count--;
                printf("%d\n",count);
                break;
        }while(1);
        printf("Process ID : %d\n",pid);

        return 0;
}

(자식프로세스가 끝날때까지 부모가 기다리고나서 count를 증가시킨다. 이때 위의 4는 자식의 count이고 6은 부모의 count이다. 부모의 프로세스가 자식이 종료된 후에 count를 증가시켜준다는 것을 보여준다.)

'O.S' 카테고리의 다른 글

Process Scheduling - Priority  (0) 2012.04.19
Process Scheduling - SJF  (0) 2012.04.19
Process Scheduling - FCFS  (0) 2012.04.19
Interrupt  (0) 2012.04.17
Thread  (0) 2012.04.17

Interrupt

 

컴퓨터 작동 중에 예기치 않은 문제가 발생한 경우라도 업무 처리가 계속될 수 있도록 하는 컴퓨터 운영체계의 한 기능을 인터럽트라고 한다.

작동 중인 컴퓨터에 예기치 않은 문제가 발생한 경우 CPU 자체가 하드웨어적으로 상태를 체크하여 변화에 대응하는 것을 말한다. 인터럽트가 발생하면 그 순간 운영체계 내의 제어프로그램에 있는 인터럽트처리루틴(routine)이 작동하여 응급사태를 해결하고 인터럽트가 생기기 이전의 상태로 복귀시킨다.

인터럽트가 발생하는 원인으로는 프로그램을 실행하는 도중 갑작스런 정전이나 컴퓨터 자체 내에서 기계적인 문제가 발생한 경우(기계검사 인터럽트), 오퍼레이터나  타이머에 의해 의도적으로 프로그램이 중단된 경우(외부인터럽트),  입출력의 종료나 입출력의 오류에 의해 CPU의 기능이 요청되는 경우(입출력 인터럽트) 프로그램 실행 중 보호된 공간 내에 접근하거나 불법적인 명령과 같은 프로그램의 문제가 발생한 경우(프로그램 검사 인터럽트) 등이 있다. 

프로그래밍 방식에는 인터럽트 방식과 폴링(polling) 방식이 있는데 인터럽트 방식을 사용하면 두 가지 이상의 프로세서를 동시에 수행할 수 있고, 이상현상을 쉽게 파악할 수 있어 훨씬 효율적이다.

  

폴링방식은 항상 While문 같은 반복문으로 항상 감시하고 있다가 조건에 만족하는 어떠한 일이 일어나면 미리 약속해둔 일을 하는 방식이고,  인터럽트 방식으로는 해당 프로그램을 실행하다가 인터럽트가 발생하는 순간 인터럽트 처리 루틴에 해당하는 일을 처리한 후에 다시 실행하던 프로그램을 실행하는 것이다.

 

예를들어 ,

폴링(polling)방식은

While(1){

if(조건)

//조건에 해당하는 어떠한 일

} 이라고 한다면.

 

인터럽트 방식은

 

int main()

{

프로그램 실행중

.     <- 인터럽트 발생

}

 

void interrupt()

{

//인터럽트 수행

}

 

이러한 식이다. 폴링 방식은 프로세서가 계속 할당되어 있어야 하기 때문에 속도가 안맞느다거나 속도가 느려지면 해당 발생하는 조건이 발생해도 알아채지 못할 경우가 생기지만, 인터럽트 방식은 해당 프로그램이 목적으로 하는 일을 하다가 인터럽트가 발생하는 순간 처리루틴에 해당하는 일을 하고 다시 원래의 프로그램으로 복귀하는 것이기 때문에 훨씬 효율적이며 리소스를 절약할 수 있다.

 

인터럽트는 크게 두가지로 구분 하는데 하드웨어 인터럽트, 소프트웨어 인터럽트 로 나뉜다.

하드웨어 인트럽트는 패리퍼럴요청에 의해서 발생되는 인터럽트이고,

소프트웨어 인터럽트는 사용자가 프로그램 내에서 발생하도록 설정 하는 것이다.

※패러퍼럴 => CPU를 제외한 구성요소를 일반적으로 패러퍼럴이라 부른다.

 

먼저 하드웨이 인터럽트를 살펴보자.

실례로 임베디드 시스템인 휴대폰에서 문자나,카톡을 보내던 도중 전화가 오는 상황이라고 가정하자.

카톡이나,문자를 보내던 도중 전화가 오면 보내던 내용등을 저장을 하고 인터럽트가 호출되며 전화를 끝내면 인터럽트가 종료됨과 동시에 원래 하던 프로그램을 다시 실행하게 된다.

이떄 일어나는 일련을 과정을 보면,

 

Main Program 실행 -> 인터럽트 발생 -> Main Program의 환경을 PCB에 저장 -> IVT에서 맞는 인터럽트를 찾아 수행 -> 인터럽트 서브 루틴 -> 인터럽트 서브 루틴 종료 -> PCB에서 원래의 Program환경을 Set -> Context Switch가 일어남.

 

의 과정을 치게 된다.

 

각각의 패리퍼럴인터럽트 선을 인터럽트 컨트롤러에 연결하고, 프로그램을 플래시메모리에 내장시키면 임베디드 시스템이 작동을 하게 되는 것이다.

이때 인터럽트가 발생되면, 에프아이큐 혹은 아이알큐 모드로 들어 가게 되는데, 둘을 나눠둔 이유는 인터럽트 요청이 동시에 들어왔을 때를 위함인데, 이때는 먼저 처리해야 할 것을 에프아이큐 모드로, 그 후에 해도 되는 인터럽트를 아이알큐 모드에 저장한뒤, 고정 어드레스(IVT : Interrupt Vetor Table)로 가서 해당되는 인터럽트를 찾고, 인터럽트를 실행 시키기 위해 인터럽트 서브 루틴으로 이동한다.

 

그 다음으로는 소프트웨어 인터럽트이다.

소프트웨어 인터럽트는 주로 System Call을 사용하는 OS에서 정의한 API이다.

OS에는 유저영역과 커널영역이 있는데, 유저영역에 있는 프로세스들은 패리퍼럴을 직접 제어할 수 있는 권한을 가지고 있지 않다. 따라서 패리퍼럴을 제어하려면 운영체제의 도움을 받아야 하는데 프로세스가 운영체제에게 패리퍼럴을 제어하게 끔 도와 달라고 요청하는 것이 System Call이다.

 

 

소프트웨어 인터럽트는 유저영역에 있는 프로그램이 System Call을 호출하게 되면, 소프트웨어 인터럽트가 발생되고, 이때 발생 된 인터럽트는 IVT 0x0000 0008번지에 있는 소프트웨어 인터럽트를 찾아 인터럽스 서비스루틴으로 가게된다.

 

 

<Interrupt & System Call>

'O.S' 카테고리의 다른 글

Process Scheduling - Priority  (0) 2012.04.19
Process Scheduling - SJF  (0) 2012.04.19
Process Scheduling - FCFS  (0) 2012.04.19
Critical Section - 공유메모리  (2) 2012.04.17
Thread  (0) 2012.04.17

+ Recent posts