#include <iostream>
#include <ctime>

#define SIZE 16

using namespace std;

template <class data>
void merge_sort(data *arr, int size);

int main()
{
        int arr[SIZE];
        srand(time(0));

        for(int i = 0 ; i < SIZE ; i++)
        {
               arr[i] = rand()%100 + 1;
               cout<<arr[i]<<" ";
        }

        merge_sort(arr, SIZE);
        cout<<endl<<endl;

        for(int i = 0 ; i < SIZE ; i++)
        {
               cout<<arr[i]<<" ";
        }
        return 0;
}

template <class data>
void merge_sort(data *arr, int size)
{
        if(size==1)
        {  
               return;
        }
 

        merge_sort(arr, size/2);
        merge_sort(arr+(size/2), size-(size/2));

        int tmp1[SIZE+1], tmp2[SIZE+1];
        int i;
        int l = 0, r = 0;

        for(i = 0 ; i < size/2 ; i++)
        {
                 tmp1[i] = arr[i];
        }

        tmp1[i] = INT_MAX;

        for(i = 0; i < size-(size/2) ; i++)
        {
                tmp2[i] = arr[i+(size/2)];
        }

        tmp2[i] = INT_MAX;

        for(i = 0 ; i < size ; i++)
        {
               if(tmp1[l] > tmp2[r])
               {
                      arr[i] = tmp2[r];
                      r++;
               }
               else
               {
                      arr[i] = tmp1[l];
                      l++;
               }
        }
}

'Algorithm > _Source' 카테고리의 다른 글

분할정복(Divide and Conquer)  (0) 2010.07.16
DFS를 이용한 스도쿠 문제 풀이 알고리즘  (0) 2010.02.05
Posted by Dakuo

메모리 종류 :

1. 메인(Main) 메모리 : 램(RAM) (D램)

2. 레지스터(Register) : CPU 안에 내장되어 있어서 연산을 위한 저장소 제공

3. 캐쉬(Cache) : S램.  CPU와 램사이에서 중간 저장소 역할

4. 하드디스크(Hard Disk)와 이외 장치 : 하드 디스크, I/O 장치 등등



메모리 계층 구조(Memory Hierarchy) :


메모리들은 프로그램이 실행하는 동안 데이터의 입력 및 출력을 담당한다.

메모리들의 차이는 CPU 와의 거리에서 온다.

CPU와의 거리가 가까울수록 빠르고 용량이 작으며 멀수록 느리고 용량이 크다.(기술과 돈의 문제)

하드디스크에 있는 내용은 프로그램의 실행을 위해 메인 메모리로 이동한다.

메인 메모리에 있는 일부 데이터도 실행을 위해 L2 캐시로 이동한다.

L2 캐시에 있는 데이터 일부는 L1 캐시로 이동한다.

L1 캐시에 있는 데이터중 연산에 필요한 데이터는 레지스터로 이동한다.


반대로 연산에 필요한 데이터가 레지스터에 없으면 L1 캐시를 살펴본다. 없으면 L2캐시 없으면 메인 메모리,

그래도 없으면 하드디스크를 참조한다. 하드디스크에서 데이터를 찾은 후 다시 메인 메모리 L2 캐쉬 L1 캐시를 거쳐

레지스터로 데이터가 들어오게 되는데 이경우 극심한 속도저하가 발생한다.

(참고 :

캐시를 없애 중간단계를 줄이는 것이 속도가 빠르지 않냐 생각할수 있는데
L1 캐시와 L2 캐시에, 연산에 필요한 데이터가 존재할 확률이 90% 이상이다.따라서 캐시는 속도향상에 도움을 준다)



L1 캐시와 L2 캐시 :

시스템의 성능을 좌우하는 클럭속도는 느린쪽에 맞춰진다.

CPU는 고속화되었지만 메인 메모리의 처리속도는 이를 따라가지 못한다.

CPU가 연산을 하기 위해선 데이터를 가지고 와서 연산을 한 후 연산결과를 메모리에 저장한 후에

다음작업을 수행할 수 있다.

따라서 아무리 CPU가 빠르게 연산을 수행한다 하더라도 데이터를 가지오고 저장하는 작업이 느리다면

전체적인 처리속도는 결코 빠를수 없다.

L1캐시는 이러한 레지스터와 메인 메모리간의 속도차이에 의한 성능저하를 막기 위해

메인 메모리의 저장된 데이터 중 자주 접근하는 데이터를 저장한다.

L1 캐시는 CPU 내부에 존재하므로 L1 캐시에서 데이터를 참조할 경우 속도저하는 발생하지 않는다.

하지만 여전히 L1 캐시는 메인 메모리의 모든 데이터를 저장할 수 없기에 L1 캐시에 없는 데이터를

CPU가 요구할 경우 속도의 저하로 이어진다.

따라서 캐시를 하나 더둔다.(L1 캐시에 용량을 증가시키는데ㄷ에도 한계가 있다(돈과 기술))

L2 캐시까지 존재함으로써 메인 메모리에 대한 접근은 더욱 줄어든다.

따라서 병목현상은 L1캐시와 메인 메모리에서 L2 캐시와 메인 메모리로 발생지역이 옮겨지게 된다.



캐쉬(Cache)와 캐쉬 알고리즘 :

템퍼럴 로컬리티(Temporal Locality) : 한번 접근이 이뤄진 주소의 메모리 영역은 자주 접근한다.

스페이셜 로컬리티(Spatial Locality) : 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다.

캐시 프렌드리 코드(Cache Friendly Code) : 템퍼럴 로컬리티와 스페이셜 로컬리티를 최대한 활용하여
                                                             캐시의 도움을 받을수 있도록 구현한 코드



캐시 알고리즘 :


캐시 힛(Cache Hit) : 연산에 필요한 데이터가 L1 캐시에 존재할 경우


캐시 미스(Cache Miss) : 연산에 필요한 데이터가 L1 캐시에 존재 하지 않을 경우
(참고 : 이경우 L2 캐시를 검사하며 L2 캐시 미스가 발생하면 메인 메모리에서 데이터를 가져온다)


데이터의 이동은 블록 단위로 진행하여 스페이셜 로컬리티의 특성을 성능향상에 활용한다.
(예 : 0x10000 번지의 데이터를 요청하면 0x10000을 포함한 블록 전체가 전송된다)

(참고 : 현재 L2 캐시는 CPU 내부에 존재한다)

메모리 계층 아래로 갈수록 전송되는 블록 크기가 커진다.

아래에 존재하는 메모리에 대한 접근 횟수를 줄여준다.


캐시 교체 정책(Cache's Replacement Policy) :

프로그램이 실행된느 동안 모든 메모리는 항상 채워져 있다.

메모리가 꽉 채워져 있어요 요구하는 데이터를 가지고 있을 확률이 높아지기 때문이다.

이때문에 가지고 있지 않은 데이터를 요구할 경우 메모리가 꽉 찾기 때문에 메모리 블록을 교체해야 한다.

블록 교체 알고리즘은 캐시 교체 정책에 의해 달라진다.
(참고 :

대표적 블록 교체 알고리즘 :
LRU(Least-Recently Used) : 가장 오래 전에 참조된 블록을 밀어내는 알고리즘)

'Windows > _System Programming' 카테고리의 다른 글

StackBasedOverflows-Windows-Part1 (기본 개념)  (2) 2011.06.07
메모리 컨트롤  (0) 2010.03.24
메모리 계층(Memory Hierarchy)  (0) 2010.03.24
MMF(Memory Mapped File)  (0) 2010.03.12
라이브러리(Library)  (0) 2010.03.11
비동기 I/O 와 APC  (0) 2010.03.08
Posted by Dakuo

base64 개념 :

64진수를 베이스로 하여 정보를 표현한다.(컴퓨터는 2진수 기반)

따라서 최소비트 (64=2^6) 6 비트를 가진다.

하지만 컴퓨터는 기본이 되는 정보를 1 바이트(8 비트)를 사용하여 표현한다.
(2=2^1  1 비트이지만... ASCII 코드 1바이트 사용)

그래서 6 과 8의 최소공배수인 24 비트(3 바이트)를 기준으로 하여 정보를 표현한다.

24비트는 6비트씩 4개가 나오므로 base64로 인코딩된 값의 길이는 4의 배수이다.


위의 그림과 같이 값을 24비트에 걸쳐서 표현한다.

앞에서부터 6비트씩 짤라서 4개의 문자를 만든다.

여기에 심볼을 대입한다.



base64 심볼 : (ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=)

'A' = 0 , 'B' = 1, …… '/' = 63,

' = '  이 심볼은 인코딩 하려는 데이터가 3바이트(24 비트) 로 나누어 떨어지지 않는 경우를 의미한다.

만약 'a' 를 입력했다면 1 바이트가 채워진다.

24 비트중에 앞에 8비트만 채워지므로

6비트로 나누어 보면 첫번째 6비트가 채워지므로 심볼하나가 나오고,

두번째 6비트중 앞에 2비트가 채워지므로 두번째 심볼이 나오지만

세번째 6비트부터는 입력된 데이터가 없다. 이럴때 세번째 심볼과 네번째 심볼은 ' = ' 이 된다.

따라서 최대 '='의 개수는 2개이다. (ex. **==)



base64 인코딩, 디코딩 예 :

인코딩(encoding) :

'A' 입력  -> 'A' 의 아스키값 : 65(Dec)

1 2 3 4 5 6 7 8        9 10 11 12 13 14 15 16        17 18 19 20 21 22 23 24
0 1 0 0 0 0 0 1  
                                            ↓

1 2 3 4 5 6        7 8 9 10 11 12        13 14 15 16 17 18        19 20 21 22 23 24
0 1 0 0 0 0        0 1

첫번째 6비트 값 = 16 = 'Q'
두번째 6비트 값 = 16 = 'Q'
세번째 6비트 값 = ' = '
네번째 6비트 값 = ' = '


디코딩(decoding) :

'QQ==' 입력

1 2 3 4 5 6        7 8 9 10 11 12        13 14 15 16 17 18        19 20 21 22 23 24
0 1 0 0 0 0        0 1 
                                            ↓

1 2 3 4 5 6 7 8        9 10 11 12 13 14 15 16        17 18 19 20 21 22 23 24
0 1 0 0 0 0 0 1 

첫번째 바이트 값 = 65 = 'A'



base64 인코딩, 디코딩 툴 : http://dakuo.tistory.com/entry/암호-인코딩encoding-디코딩decoding-툴SnDRT

'Cryptology' 카테고리의 다른 글

base64 인코딩 알고리즘  (0) 2010.03.12
Posted by Dakuo

우선순위(Priority) 스케줄링(Scheduling) 알고리즘 :

각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행한다.

우선순위가 다른 두 프로세스를 동시 실행할 때,

우선순위가 높은 프로세스가 작업을 마치지 않는다면(블로킹 상태가 되거나 I/O 작업을 하지 않는다면)
우선순위가 낮은 프로세스는 절대로 실행되지 않는다. (기아 상태 : Starvation)



라운드 로빈(Round-Robin) 스케줄링 알고리즘 :

우선순위가 동일한 프로세스들의 형평성 유지를 위해
정해진 시간 간격(타임 슬라이스(Time Slice), 퀀텀(Quantum))만큼만 실행하고 CPU 할당을 넘긴다.

타임 슬라이스 ↑ -> 반응속도 ↓
타임 슬라이스 ↓ -> 성능 ↓ (잦은 컨텍스트 스위칭 발생으로 인하여 시스템이 무리가 가서 성능이 저하된다)



Windows의 스케줄링 알고리즘 :




스케줄링이 진행되는 시점 :

1. 매 타임 슬라이스마다 스케줄러 동작.
2. 프로세스가 생성 및 소멸될 때마다 스케줄러 동작
3. 현재 실행 중인 프로세스가 블로킹 상태에 놓일 때마다 스케줄러 동작



Windows 프로세스 우선순위 :

 Priority  의미
 IDLE_PRIORITY_CLASS  기존 우선순위 4
 NORMAL_PRIORITY_CLASS  기존 우선순위 9
 HIGH_PRIORITY_CLASS  기존 우선순위 13
 REALTIME_PRIORITY_CLASS  기존 우선순위 24
 ABOVE_NORMAL_PRIORITY_CLASS  NORMAL_PRIORITY_CLASS 보다 높고
 HIGH_PRIORITY_CLASS 보다 낮다.( 9< x < 13 )
 BELOW_NORMAL_PRIORITY_CLASS  IDLE_PRIORITY_CLASS 보다 높고
 NORMAL_PRIORITY_CLASS 보다 낮다. ( 4 < x < 9 )

프로세스 우선순위 변경 :

BOOL SetPriorityClass(
        HANDLE hProcess,              // 우선순위를 변경할 프로세스의 핸들
        DWORD dwPriorityClass        // 새롭게 적용할 우선순위 상수값
);


Priority Inversion :

프로세스의 우선순위가 뒤바뀌는 상황

(예 :

프로세스 A > 프로세스 B > 프로세스 C (우선순위)

프로세스 A가 실행이 되다가 프로세스 C에게 데이터를 받을 일이 생겼다.

프로세스 C가 실행이 되게 하기 위해 자신이 Blocked 상태가 되었다.

하지만 프로세스 C보다 우선순위가 높은 프로세스 B가 실행이 되어 프로세스 C가 실행이 되지 않으므로

프로세스 A 또한 실행이 될수 없게 된다.
(즉, 프로세스 A 보다 우선순위가 낮은 프로세스 B가 우선순위가 가장 높은것처럼 되었다))

'Windows > _System Programming' 카테고리의 다른 글

쓰레드(Thread)  (2) 2010.02.28
환경변수  (0) 2010.02.25
스케줄링 알고리즘과 우선순위  (0) 2010.02.25
파이프(Pipe) IPC 통신 소스  (0) 2010.02.24
메일슬롯(MailSlot) IPC 통신 소스  (0) 2010.02.24
커널 오브젝트(Kernel Object) - 2  (0) 2010.02.23
Posted by Dakuo
#include <iostream>
using namespace std;
int sdocu[9][9]={0};         // 정답을 저장할 배열
int success = 0;               // 성공변수
int dfs(int c, int r)
{
         if(c==9)                  // 끝에 도달시
         {
                success = 1;
                return 0;
         }
         if(sdocu[c][r]!=0)    // 숫자가 있다면
         {
                if(r==8)
                {
                          c++;
                          r=0;
                }
                else
                {
                          r++;
                }
                dfs(c, r);
                if(success==1)
                {
                          return 0;
                } 
                if(r==0)           // 되돌아가기
                {
                          c--;
                          r=8;
                }              
                else
                {
                          r--;
                }
                return 0;
        }
        else
        {
                int temparr[9]={1,2,3,4,5,6,7,8,9};  // 빈칸에 들어갈 수 있는 숫자배열
                for(int i = 0; i < 9 ; i++)
                {
                        for(int j = 0 ; j < 9 ; j++)
                        {
                               if(sdocu[c][i]==temparr[j] || sdocu[i][r]==temparr[j]) // 가로줄 세로줄에 있는 숫자 제외
                               {
                                         temparr[j]=0;
                               }
                        }
               }
               int l = (c/3)*3;               // 포함된 정사각형 영역 숫자 제외
               int m = (r/3)*3;         
               for(int i = l ; i < l+3 ;i++)
               {
                             for(int j = m ; j < m+3 ; j++)
                            {
                                        for(int k = 0 ; k < 9 ; k++)
                                       {
                                                  if(sdocu[i][j]==temparr[k])
                                                  {
                                                             temparr[k]=0;
                                                  }
                                        }
                            }
              }
              for(int i = 0 ; i < 9 ; i++)             // 빈칸에 숫자대입
              {
                           if(temparr[i]!=0)
                           {
                                       sdocu[c][r]=temparr[i];
                                       if(r==8)
                                       {
                                                  c++;
                                                  r=0;
                                       } 
                                      else
                                      {
                                                  r++;
                                      }
                                      dfs(c, r);
                                      if(success==1)
                                      {
                                                 return 0;
                                      }    
                                     
                                      if(r==0)                           //되돌아가기
                                      {
                                                 c--;
                                                 r=8;
                                      }
                                      else
                                      {
                                                 r--;
                                      }
                            }
                }
                sdocu[c][r]=0;
                return 0;
        }
}
int main()
{
       char temp[10]={0};
       cout<<"intput data : "<<endl;
       for(int i = 0; i < 9; i++)
       {
               cin>>temp;
               for(int j = 0 ; j < 9 ; j++)   // 숫자 입력
               {
                         sdocu[i][j]=temp[j]-'0';
               }
      }
      cout<<endl<<"output data : "<<endl;
 
      dfs(0, 0);
 
      for(int i = 0; i < 9 ; i++)
      {
               for(int j = 0 ; j < 9 ; j++)
               {
                       cout<<sdocu[i][j];
               }
               cout<<endl;
      }
      system("pause");
      return 0;
}
 

'Algorithm > _Source' 카테고리의 다른 글

분할정복(Divide and Conquer)  (0) 2010.07.16
DFS를 이용한 스도쿠 문제 풀이 알고리즘  (0) 2010.02.05
Posted by Dakuo


티스토리 툴바