Round - Robin Scheduling

 

round - robin scheduling은 프로세스 마다 time quantum을 둔다.

※Time Quantum = 프로세스마다 CPU를 점유할 수 있는 시간을 정해 두는 것.

 

실행중이던 프로세스가 타임퀀텀에 의해 종료되면 Ready Queue의 제일 뒤쪽으로 옮겨진다.

Time Quantum이 너무 클 경우에는 FCFS Scheduling과 같은 알고리즘이 되고, 반면에 Time Quantum이 너무 작을 때에는 너무 잦은 Context-switch가 일어나 오버헤드가 발생, Time Quantum이 Context-switch보다 작을 때는 프로세스환경을 셋팅하다가 타임퀀텀이 끝나버려서 정작 프로세스의 실행을 하지 못하고 다시 CPU를 반환해야 한다.

일반적으로 Time Quantum = CPU Burst time 의 80%를 기준으로 한다.

 

만약 Ready Queue에 N개의 프로세스가 있고 Time Quantum 을 p라 한다면, 프로세스가 CPU를 점유하기 위한 최대 시간은 (N-1)*q이다. 

 

 

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

Process Scheduling - Multilevel Queue scheduling,Multilevel feedback Queue Scheduling  (0) 2012.04.22
Process Scheduling  (0) 2012.04.19
Process Scheduling - Priority  (0) 2012.04.19
Process Scheduling - SJF  (0) 2012.04.19
Process Scheduling - FCFS  (0) 2012.04.19

Priority Scheduling

 

Priority Scheduling는 각각의 프로세스마다 우선순위를 부여한 후에 우선순위가 가장 높은 프로세스를 먼저 실행시키는 알고리즘이다.

Nonpreemptive / Preemptive 둘다 가능하다.

 

위와 같이 5개의 프로세스가 존재하고 각각 프로세스의 우선순위는 다음과 같다면 CPU는 위사진과 같이 실행하게 될 것이다.

이때의 Turnaround time

P1 = 6 + 10 = 16

P2 = 0 + 1 = 1

P3 = 16 + 2 = 18

P4 = 18 + 1 = 19

P5 = 1 + 5 = 6

 

하지만, Priority Scheduling에는 Starvation 이 발생한다.

Starvation => 우선순위가 계속 높은 프로세스만 Ready Queue에 들어오게 된다면 낮은 것은 무한히 처리가 되지 않는 문제를 말함.

이같은 문제를 처리하기 위한 방법으로는 Aging기법이 있다.

 

Aging => 한프로세스가 기다리는 시간에 비례해서 우선순위를 올려주는 방법.

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

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

SJF (Shortest - Job - First)

 

SJF의 기본적인 알고리즘은 CPU burst time이 짧은 것부터 실행시키는 것이다.

SJF는 Preemptive / Nonpreemptive 둘다 가능하다.

 

Nonpreemptive SJF는 현재 시점에 대기중인 프로세스 중 CPU burst time이 가장 짧은 것을 실행시킨 후에, 프로세스가 종료되거나 wait상태가 되기 전까지 실행한 후에 다시 Ready Queue를 보고 가장 짧은 burst time을 가진 프로세스를 실행시키는 방법이다.

이와 같이 burst time이 가장짧은 P4 -> P1 -> P3 -> P2 순으로 실행시킨다.

이때의 평균 대기시간은 3 + 16 + 9 + 0 /4 = 7s 이다.

 

Preemptive SJF는 프로세스 실행중 남아있는 burst time보다 적은 burst time을 가진 프로세스가 들어오면, 현재 실행하고 있던 프로세스를 Ready Queue에 넣고 더적은 burst time을 가진 프로세스를 실행하는 것이다.

 

 

맨처음에 도착한 P1을 실행하던 도중 P2가 도착한다. 이때 P1의 Burst time = 7 , P2의 Burst time = 4이므로 CPU는 P2를 실행하게 된다. 그러던 도중 P3가 들어오지만 P2의 Burst time이 더 적으므로 계속 P2를 실행시킴. P2의 실행이 끝나고 난 뒤 각각의 프로세스의 Burst time을 보면,

P1 = 7 ,P2 = 0(종료) ,P3 = 9 ,P4 = 5 이므로 CPU는 P4를 실행하게 된다.

 

이때의 Trunaround time(대기시간 + 실행시간)

P1 = 9 + 8 = 17

P2 = 0 + 4 =4

P3 = 15 + 9 = 24

P4 = 2 + 5 = 7

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

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

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

Thread란??

 

Thread는 프로세스 내에 존재하는 것으로 실제로 실행되는 독립적인 작업단위이다. Thread는 Process의 모든 자원을 공유할 수 있으며, CPU는 각각의 Thread를 수행하고 각각의 Thread는 해당 Thread만의 고유한 작업을 가지고 있다.

  가령 예를들어, 인터넷 웹브라우저를 킨 후에 네이버를 들어갔을 경우에, 네이버의 광고(검색바 밑에)가 다 나오기 전에 기사글이 먼저 나오고 그 후에 광고나 이미지가 나오는 경우를 많이 봐왔을 것이다.

웹브라우져에서도 Thread가 각각 존재하여, html,image,script를 받아오는 쓰레드가 따로 존재하여 효율적이면서, 빠른 속도로 인터넷 서핑이 가능한 것이다.

 

쓰레드는 프로세스처럼 메모리자원을 할당 받는 것이 아니고, 이미 할당받아져 있는 프로세스 안에서 생성되는 것이기 때문에 프로세스를 새로 할당 받는 것보다 생성속도가 무려 67배가 빠르다고 한다.

보통은 한 프로세스당 하나의 쓰레드를 가지나 여러 쓰레드를 가지고 있는 경우를 Multi-Thread라 한다.

또한 프로세스가 할당받은 자원에 있는 것을 공유하기 때문에 Context-switch보다 훨씬 저렴한 자원으로 이용할 수 있다.

 

Thread에도 종류가 있는데 User-Thread와 Kernel-Thread이다.

User-Thread는 user레벨 권한에서 Thread를 제어한다. 따라서 System Call을 사용할 필요는 없지만 kernel system call을 기반에 두고 사용하여야 한다.

반면에, Kernel-Thread는 System Call로 구현되어 진다.

 

Multi-Thread의 경우 User-Thread와 Kernel-Thread에 따라서 모델이 나뉘게 된다.

 

One to one Model

User-Thread와 Kernel-Thread가 일대일로 매칭되는 구조이다.

자원낭비가 심하고 오버헤드가 발생할 확률이 높다.

 

 

 

Many to one Model

Kernel-Thread가 하나만 존재하는 것을 말한다. 병렬성이 떨어지고 속도가 늦다.

 

 

Many to many Model

User-Thread와 Kernel-Thread가 복수개 인 것을 말한다.(요즘 대부분의 OS는 이 모델을 따르고 있다.)

하지만 이때 Kernel-Thread는 User-Thread보다 항상 적다.

또한, Many to many Model이지만 OS가 생각하기에 중요한 Thread는 Many to many모델안에서 One to one Model을 따르게 된다.

 

※Multi-Thread System은 PCB가 저장되고 복귀하는 것(Context-switch)가 일어나지 않기 때문에 오버헤드도 줄고 효율성이 올라간다.

'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
Interrupt  (0) 2012.04.17

+ Recent posts