[패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 44회차 미션

 

환급미션 44일째...

 

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 18. 참고_IPC 기법1

운영체제 - 프로세스와 스케쥴러의 이해 - 19. 참고_IPC 기법2

운영체제 - 프로세스와 스케쥴러의 이해 - 프로세스 총정리와 프로그램 성능 개선 방법의 이해

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 08. 정렬 - 퀵 정렬

 

 

 

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 18. 참고_IPC 기법1

 

 

 

 

- 다양한 IPC 기법 (InterProcess Communication)

 

1. file 사용

2. Message Queue

3. Shared Memory

4. Pipe

5. Signal

6. Semaphore

7. Socket

...

2번부터는 커널공간을 공유한다는 특징이 있다.

 

 

위의 기법들을 자세히는 다루지 않을 예정이고 (학부과정에서도 자세히 다루는 경우는 거의 없다고 한다.)

일부를 대략적으로 다루고 넘어갈 예정이라고 한다.

 

 

 

* pipe (파이프)

 

 

기본 파이프는 단방향 통신

fork()로 자식 프로세스를 만들었을 때, 부모와 자식 간의 통신

fork를 실행하면 새로운 프로세스가 생기는데, 

기존 프로세스를 복사한다. (부모 프로세스 / 자식 프로세스)

 

pid값(process ID)이 다르게 반환된다.

 

위의 코드에서

부모 프로세스에서는 fd[1]을 사용, 자식 프로세스는 fd[0]을 사용하는데,

부모 프로세스에서 msg 값을 write함수로 fd[1]에 쓰면,

자식 프로세스에서 read를 이용해 읽을 수 있다.

부모->자식 으로 단방향적으로만 진행되며 양방향으로는 진행될 수 없다.

 

 

 

 

* 메시지 큐 (message queue)

 

 

큐 이므로, 기본적으로 FIFO 정책으로 데이터 전송

 

 

•A 프로세스

특별한 key값을 부여해서 msqid 반환,

해당아이디의 sbuffer(&sbuf)에 데이터를 넣어두고 msgsnd(send)함수를 호출해서

데이터를 큐처럼 하나씩 넣게 된다.

 

•B 프로세스

동일한 key를 msqid에 반환, msgrcv(receive) 함수를 통해 0으로 채워진(공란) 변수인 rbuf에 sbuf의 데이터를 넣는다.

 

-> A프로세스의 데이터가 B프로세스에 전달

 

 

 

 

* 파이프 vs 메시지 큐

 

message queue - 어느 프로세스 간에도 데이터 송수신 가능 , FIFO 방식, 양방향 가능

pipe - 부모/자식 프로세스간 only or not, 단방향만 가능

 

둘 모두 kernel 공간의 메모리를 사용한다.

 

 

 

 

 

 

* 공유 메모리 (Shared Memory)

 

 

kernel space에 메모리 공간을 만들고, 해당 공간을 변수처럼 사용

FIFO 방식이 아니라, 해당 메모리 주소를 변수처럼 접근하는 방식

공유메모리 key를 가지고, 여러 프로세스가 자유자재로 접근할 수 있다.

 

 

key값을 가지고 shmget이라는 특별한 함수를 사용, shmid를 만들 수 있다.(공유 메모리 공간을 만든다)

shmaddr - 그 공유메모리 공간에 대한 주소를 shmat라는 함수를 사용해서 언제든 해당 메모리의 주소를 가져온다.

위의 그림의 2,3번에서 보는 것과 같이 언제든 자유롭게 해당 주소값(shmaddr)을 이용해 해당 메모리 공간에 접근할 수 있다.

 

 

 

 

 

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 19. 참고_IPC 기법2

 

 

 

- IPC 기법이지만, 이외에도 많이 사용되는 두 가지 기술 ( signal, socket )

 

 

 

* 시그널 (signal)

 

 

유닉스에서 30년 이상 사용된 전통적인 기법

커널/프로세스에서 다른 프로세스에 어떤 이벤트가 발생되었는지 알려준다.

프로세스 관련 코드에 관련 시그널 핸들러를 등록해서, 해당 시그널 처리 실행

•시그널 무시

•시그널 블록(블록을 푸는 순간, 프로세스에 해당 시그널 전달)

•등록된 시그널 핸들러로 특정 동작 수행

•등록된 시그널 핸들러가 없다면, 커널에서 기본 동작 수행

 

 

*

미리 정의되어있는 시그널 종류

SIGKILL : 프로세스를 죽여라 (슈퍼관리자가 사용, 프로세스는 어떤 경우든 죽는다)

SIGALARM : 알람을 발생

SIGSTP : 프로세스를 멈춰라 (Ctrl+z)

SIGCONT : 멈춰진 프로세스를 실행

SIGINT : 프로세스에 인터럽트를 보내서 프로세스를 죽여라 (Ctrl+c)

SIGSEGV : 프로세스가 다른 메모리 영역을 침범했다.

SIGUSR1, SIGUSR2 : 기본동작 x, 특별한 동작을 하도록 만들 수 있음 (서로 통신 가능)

 

 

시그널 핸들러 등록 / 핸들러 구현

위의 코드 예제에서 

if (signal (SIGINT, signal_handler) ...

부분을 살펴보면

SIGINT 라는 signal을 받으면, 원래 정의되어있는 SIGINT의 기본동작을 하지 않고, signal_handler 함수를 실행시킨다.

이처럼, 기본동작 대신 특별한 동작을 하도록 구현할 수 있다는 것이다.

 

 

시그널 핸들러 무시

위의 코드 예제에서

SIG_IGN은 어떤 함수가 아니라, signal ignore의 약자로

SIGINT라는 signal을 받으면 무시하라는 게 된다.

 

 

 

PCB에 signal 관련 처리를 하는 다양한 자료구조가 있으며, 

signal을 받으면 관련 정보를 관리한다.

커널모드 -> 사용자모드 전환되는 시점에 signal을 처리하게 된다.

 

 

 

 

* 소켓 (socket)

 

네트워크 기술에 대한 이해가 있어야 자세히 알 수 있는 부분이기 때문에,

기본적인 부분만 다룰 예정이라고 한다.

 

 

네트워크 통신을 위한 기술 (네트워크 기기를 이용할 수 있는 시스템콜이라고 봐도 무방)

기본적으로 클라이언트와 서버 등 두 개의 다른 컴퓨터 간의 네트워크 기반 통신을 위한 기술

 

이 기술을 사용하면, 컴퓨터 한 대 내의 다른 프로세스 사이에서도 전달을 주고받을 수 있기 때문에 IPC에 포함된다.

 

 

 

 

 

 

 

 

 

 

 

 

정리 

 

1. 주요 IPC 기법 - pipe, message queue, shared memory

2. 모두 커널 공간을 활용해서 프로세스 간 데이터 공유

3. signal

4. socket

 

 

 

 

 

운영체제 - 프로세스와 스케쥴러의 이해 - 프로세스 총정리와 프로그램 성능 개선 방법의 이해

 

 

지금까지 배운 프로세스 내용을 총 정리할 예정

 

c언어로 작성된 코드 예제

 

 

1. 최상단에서 라이브러리 (헤더파일)를 불러옴

2. 메인함수

변수 fd 선언 -> data.txt라는 파일을 읽기 전용으로 불러옴

fd==-1 : 파일 오픈 결과값이 -1, 즉 파일을 읽어오는 데 실패했다면 에러 메시지 출력

파일을 읽었다면 파일을 읽었다는 메시지를 출력하고 프로그램 종료

 

3. 컴파일 -> 실행파일 

4. 실행파일 실행을 위해 shell 사용하여 운영체제에 요청

 

 

 

프로세스가

Stack, HEAP, BSS(uninitialized), DATA(initialized), TEXT(code)

영역으로 이루어지게 됨

 

text 영역에 코드가 들어가고,

 

 

실행파일이 만들어지고 -> ready state -> 스케쥴러에 의해 running state

 

 

 

 

ex)

 

0.05초마다 A<->B context switching 할 것이다.

-> 일정시간 (0.01초 가정)마다 타이머 인터럽트를 운영체제에 알려줌

 

•cpu는 사용자 모드를 커널모드로 변경

•IDT(Interrupt Descriptor Table)에서 0x80에 해당하는 주소(함수)를 찾아서 실행

•system_call() 함수에서 eax로부터 시스템 콜 번호를 찾아서, 해당 번호에 맞는 시스템콜 함수로 이동

•시스템콜 함수 실행 후, 다시 커널모드에서 사용자모드로 변경하고, 해당 프로세스의 다음 코드 진행

 

-> 코드는 아래와 같은 방식으로 작성될 것이다.

--------

sys_timer(){

 count++;

 if(count>4) {

  call scheduler (context switching);

 }

}

------------

=> 결과적으로 이 코드에 의해

인터럽트가 5번 실행이 되면 ready 상태에 있는 어떤 프로세스를 running 상태로 바꾸고,

running 상태의 프로세스를 ready 상태로 바꿀 것이다.

 

 

 

이렇게 컨텍스트 스위칭이 일어나면,

 

기존 running state인 프로세스1의 PCB 정보를 메인 메모리에 저장 & ready state로 바꿔주고

new or ready state였던 프로세스2의 PCB정보를 메인 메모리에서 로드 & running state로 바꾸게 된다.

 

 

 

여기까지 과정이 진행되면

 

 

 

 

 

드디어 프로그램이 시작된다.

 

unistd.h 헤더파일 안에 있는 open 함수가 실행되면, 

open() 이라는 함수는 시스템콜이기 때문에 시스템콜을 처리하기 위해

-----

mov eax, 1 //시스템콜 번호가 들어간다

mov ebs, 0 //시스템콜 인자 정보가 들어간다

int 0x80 //CPU가 제공하는 op code(operand), 인터럽트 번호(0x80)를 전송 소프트웨어 인터럽트 명령

-----

위의 내용이 포함된다. 

 

 

 

다시 위에서 다루었던 내용을 돌아보면

 

•cpu는 사용자 모드를 커널모드로 변경

•IDT(Interrupt Descriptor Table)에서 0x80에 해당하는 주소(함수)를 찾아서 실행

•system_call() 함수에서 eax로부터 시스템 콜 번호를 찾아서, 해당 번호에 맞는 시스템콜 함수로 이동

•시스템콜 함수 실행 후, 다시 커널모드에서 사용자모드로 변경하고, 해당 프로세스의 다음 코드 진행

 

=>

int라는 명령 자체가 

사용자 모드를 커널 모드로 바꿔주고,

IDT (Interrupt Describtor Table) - os 부팅될 때 만들어짐 - 에서 번호마다 실행 커널 함수 주소가 적혀있고,

시스템콜 같은 경우 0x80을 쓰게 되서

커널 안에 있는 system_call() 함수를 사용하게 된다. 

system_call 함수 내에 있는 eax에 있는 번호를 확인하는데, 번호마다 시스템 콜 처리 커널함수의 주소가 들어있다.

해당 주소로 이동하게 되는 것이다.

.

.

.

 

 

위와 같은 과정들을 거쳐 결국 프로세스가 종료되면 프로그램이 끝나게 된다.

 

 

 

 

 

 

소프트웨어 베이직 - 자료구조와 알고리즘 - 08. 정렬 - 퀵 정렬

 

퀵 정렬의 원리 & c언어로 구현

 

 

* 퀵 정렬

 

빠른 정렬 알고리즘

피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법

값을 서로 교체하는 데에 N번,

엇갈린 경우 교체 이후에 원소가 반으로 나누어지므로 

전체 원소를 나누는 데에 평균적으로 logN번이 소요되므로

평균적으로 θ(NlogN)의 시간 복잡도를 갖는다.

 

 

초기값 가정

피벗 값이 가장 왼쪽 값이라고 가정하고,

알고리즘을 구현했을 때

피벗값이 5가 된다.

배열의 왼쪽에서부터 출발해서 5보다 큰 값을 찾는다 -> 8

배열의 오른쪽에서 출발해서 5보다 작은 값을 찾는다 -> 2

 

 

두 값을 교체해준다.

 

값이 바뀌면

다시 왼쪽에서부터 5보다 큰 값을 찾는다 -> 9

오른쪽에서부터 5보다 작은 값을 찾는다 -> 1

 

마찬가지로 두 값을 교체하고,

 

 

 

동일한 과정을 거쳐야 하는데...?

이번엔 큰 값과 작은 값이 엇갈리게 된다. (6, 1)

=> 피벗값과 작은 값을 교체한다.

 

 

5가 중간에 오게 되는데,

이제 각각의 부분들을 (1,4,3,2,5), (67,9,10,8) 각자 정렬을 수행하면

총 NlogN으로 정렬을 수행하게 된다.

 

 

 

위의 예시와 같이 원소를 절반씩 나눌 때 logN의 시간 복잡도가 나오는 경우의

대표적인 예시는 완전 이진트리라고 하며, 컴퓨터 공학에서 가장 선호하는 이상적인 형태라고 한다.

 

완전 이진트리

 

 

 

 

- c언어로 퀵정렬 구현하기

 

 

 

* 배열 선언

 

-------------

#include <stdio.h>

#define SIZE 1000

 

int a[SIZE];

 

void swap(int *a, int*b)

{

    int temp = *a;

    *a = *b;

    *b = temp;

}

----------------

 

기존의 정렬 방식과 마찬가지로 사이즈만큼 배열 a를 할당하고,

값을 교체하는 swap 함수도 만들어준다.

강의에서는 swap 함수를 int 자료형으로 만들었지만,

또 리턴 문제 때문에 void를 사용했다.

 

 

 

* 퀵 정렬 구현

 

----------

void quickSort(int start, int end)

{

    if (start >= end) return;

    int key = start, i = start+1, j = end, temp;

    //key=start : 피벗값을 부분배열의 첫 번째 원소가 되도록 함.

    while (i <= j) //엇갈릴 때까지 반복

    {

        while (i <= end && a[i]<=a[key])

            i++;

        while (j>start && a[j]>=a[key])

            j--;

        //왼쪽에서 출발, 피벗보다 큰 값 & 오른쪽에서 출발, 피벗보다 작은 값을 찾는다

        if (i>j)

            swap(&a[key], &a[j]);

        //엇갈리는 상황이 발생한다면, 피벗값과 작은 값을 교체

        else

            swap(&a[i], &a[j]);

        //큰 값, 작은 값을 서로 교체

    }

    quickSort(start, j-1);

    quickSort(j+1, end);

    //다시 부분배열로 재귀적으로 두 번 호출하도록 만들어준다.

}

----------

 

 

 

* 퀵 정렬 사용해보기

 

 

------------------

int main(void)

{

    int n;

    printf("원소의 갯수 입력 : ");

    scanf("%d", &n);

    printf("\n");

    

    for (int i=0; i<n; i++)

    {

        printf("원소 %d : ", i+1);

        scanf("%d", &a[i]);

    }

    quickSort(0, n-1);

    printf("정렬 결과 : ");

    for (int i=0; i<n; i++)

        printf("%d ", a[i]);

    printf("\n");

    

    return 0;

}

------------------

 

 

그냥.... 보기 편한 출력값 몇 가지를 추가해서 작성해보았고

정렬 결과는 아래와 같다.

 

 

 

 

 

*

편향된 분할 ( 반반이 아니라 어느 한 쪽으로 치우쳐서 분할되는 상황이 반복되는 경우 등)

이 발생하면 연산의 양이 0(N²) 이 된다. => 동작이 느려질 수 있다.

 

=> 실제로 정렬을 할 때, c언어로 직접 퀵정렬을 구현하지 않고

C++의 알고리즘 라이브러리를 사용한다. 

Algorithm 라이브러리의 sort() 함수는 퀵 정렬을 기반으로 하는 동시에 0(NlogN)의 시간 복잡도를 보장하게 된다.

 

 

 

 

 

 

 

 

 

 

올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE