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

네트워크를 전혀 모르다가 이제 갓 네트워크를 시작하고 싶어서

평소 관심있어하던 네트워크 패킷분석을 위해 책을 찾던 도중,

 

Wireshark Network Analysis라는 책을 발견하였다. 책에 보면 추적파일도 많이 제공하고 Wireshark 사용법에 대한 전반적인 지식을 설명하기에 이 책을 잡고 공부를 하고 있다.

헌데 각 장이 끝날때마다 어떤 추적파일을 들면서 문제를 내주는데 책에는 답도 없고, 인터넷에 뒤져도 나오지 않길래 공부도 할 겸 내가 틀렸는지 맞았는지 확실히 알기 위해 여기에 포스팅 해보도록 한다.

책에서 준 패킷파일은 무려 200MB가 넘는다 ㅠㅠ 하나씩 해보도록 하자.

아마도 하나씩 기초부터 밟아나가고 싶어서 하나하나 간단한 것도 포스팅 하겠다.

 

자 처음으로 http-download-good.pcap파일이다.

(책에서 제공하는 모든 추적파일은 왠지 파일제목만 봐도 느낌이온다)

 

일단 패킷을 살펴 보면 처음 1,2,3번째 패킷으로 3-way-handshaking하는 과정이 보인다.

 

3-way-handshaking이란?

 TCP Protocol은 패킷을 주고 받기 이전에 미리 가상의 경로를 설정하는 연결지향형 프로토콜이다. 따라서 TCP에는 먼저 연결을 설정해야 하는데 이 과정을 3-way-handshacking이라 한다.

 

 

 <3-way-handshaking 개념도>

1.   연결을 하기 이전에는 클라이언트는 포트가 닫힌 closed 상태이고 서버는 해당 서비스의 포트가 열려있는 listening상태이다.

 

2.   클라이언트 측에서 서버와 연결을 하고 싶을 때는 임의의 포트번호를 받고 SYN패킷을 서버측으로 보낸다.

 

3.   클라이언트로부터 SYN패킷을 받은 서버는 SYN패킷과 함께 잘 받았다는 응답과 패킷을 보내도 된다는 의미로  ACK패킷을 보낸다.

 

4.  클라이언트는 다시 응답을 받았으므로 이제 연결을 하고 패킷을 보내겠다는 뜻으로 ACK를 보내면 연결이 완료된것이다.

 

 

이때의 클라이언트의 ip는 10.0.52.164가 되고 서버의 ip는 204.152.184.134이다.

다시 본론으로 돌아와서, 추적파일을 봐도 별다른 이상이 있어보이지 않는다. 3-way-handshaking으로 연결을 하고, 서버로 부터 00o_2.0.0_win32Intel_install.exe파일을 요청하고 그에 대한 응답으로 서버에서 데이터를 보내주고 있다.

 

<HTTP Protocol을 이용 GET방식으로 exe파일을 요청하고 있다.>

 

이 추적파일에서는 더이상 볼만한 것은 남아있지 않은 것 같으므로, 다운로드 받았던 데이터를 조립해 보도록 하자.

 

데이터를 자세히 보니 파일헤더가 MZ로 시작한다. 위 패킷으로 알수 있듯이 보냈던 exe파일이 아마 이것일 것이다. 위에 다 떼버리고 MZ부터 밑으로 쭉 긁어서 Winhex로 붙여서 a.exe파일로 저장해본다.

 

원래 win32Intel~~~.exe 파일이었으니 윈도우 32bit용 파일이라 64bit인 내컴퓨터에서는 어자피 안돌아갈테니까 제대로 파일을 꺼냇는지 알기 위해 실행이나 한번. ㅋㅋㅋ

 

첫포스팅이고 잠도 오니까 정말 간단한 예제를 들어서 포스팅을 했다. 책을 공부하면서 점점 포스팅도 해가고 일단 기본적인 네트워크지식부터 다시 제대로 다지기 위해 포스팅을 할 생각이다.

처음이라 이거했다가 저거했다가 글이 너무 길어진 느낌이지만 하다보면 괜찮아지겟지 ㅠㅠ 다음엔 주제를 가지고 하나씩 .... 하고 싶지만 과제가 너무 많아 ㅠㅠ

 

'NetWork' 카테고리의 다른 글

VMware network  (0) 2012.07.10
tcphdr , tcphdr??  (0) 2012.07.09
ARP_Spoofing  (2) 2012.07.06
ICMP Protocol  (0) 2012.07.06
TCP / IP 프로토콜 스택  (0) 2012.04.25

+ Recent posts