태양 만세!

Win + 숫자 : 작업표시줄 프로그램 실행    

Win + D : 바탕화면 보기   

Win + L : 화면 잠금    

Win + E : 탐색기 실행    

Win + Home : 현재 사용 중인 창만 제외하고 모두 내림    

Win + ↑ : 현재 창을 최대화    

Win + ↓ : 현재 창을 작업표시줄로 내림

Win + ←, → : 현재 창을 화면의 왼쪽, 오른쪽 절반으로 조정  

Alt + Tab : 프로그램 전환    

Ctrl + Tab : 브라우저 창간 이동

Alt + Print Screen : 현재 창만 캡처

Ctrl + W : 현재 탭만 닫기    

Ctrl + Shift + T : 닫은 탭 다시 열기    

Shift + 다시시작 : 재부팅시 부팅옵션 표시 (windows 8 이상)

• 인덱싱과 해싱 II

  10.1 B-트리 인덱스

• B-트리 인덱스
  • B+-트리의 원형
  • B-트리와 B+-트리의 차이점
    • 단말 노드의 검색키가 비단말 노드에 중복되어 삽입되지 않음
    • 리프 노드의 모든 검색키와 레코드가 순차적으로 정렬되고 연결되어 있지 않음

         

  • 비단말 노드의 구조

    

       

    

10.2 정적 해싱과 동적 해싱

• 해싱의 개념

  검색키 값에 직접 산술적인 연산을 적용하여 데이터가 저장되어 있는 버킷의 주소를 계산하여 데이터에 접근하는 방법

  • 해시 함수 : 검색키 값을 입력하면, 레코드에 대한 디스크 블록 주소(버킷)를 반환하는 함수
  • 버킷
    • 해시 파일 구조에서 사용하는 한 개 이상의 레코드를 저장할 수 있는 공간의 단위
    • 일반적으로 버킷 하나가 디스크 블록 하나를 나타내지만 크기 조정이 가능함

      

• 정적 해싱
  • 정적 해싱: 저장 공간의 단위인 버킷 개수가 고정된 기법

       

  • 정적 해싱에서 키값이 𝑘𝑖인 레코드 삽입
    • ℎ𝐾𝑖을 통하여 𝐾𝑖에 대응하는 버킷 주소를 구함
    • 레코드를 해당 버킷에 저장

         

  • 정적 해싱에서의 레코드 탐색
    • ℎ𝐾3=hK7= 𝑗 인 경우
    • 두 레코드 모두 같은 버킷에 있으므로 𝑗 번 버킷안의 모든 레코드를 탐색하여 선택하는 과정이 필요

         

• 해시 함수
  • 충돌: 서로 다른 레코드가 동일한 버킷에 대응되는 경우
  • 동거자: 같은 버킷 주소를 갖는 레코드들
  • 오버플로
    • 버킷에 레코드를 저장할 수 있는 여유 공간이 없을 때 발생
    • 주로 별개의 버킷을 할당하여 처리
    • 오버플로는 많이 발생할수록 레코드 접근시간이 길어지고 성능이 저하

         

    

     

• 동적 해싱
  • 정적 해싱의 문제점
    • 데이터베이스의 크기가 커짐에 따른 성능 감소
    • 미리 큰 공간을 잡을 경우 초기에 상당한 양의 공간이 낭비
    • 재구성 시 새로운 해시 함수를 선택하면 모든 레코드에 대하여 다시 계산하고 버킷에 할당하는 비용이 발생
  • 동적 해싱: 버킷의 개수가 데이터베이스의 크기에 따라 변경되는 기법

       

• 확장성 해싱
  • 데이터베이스의 증대 혹은 축소에 따른 인덱스의 구조를 조절하기 위해 해시 함수의 동적 변경을 허용하는 기술
  • 디렉터리와 버킷으로 구성된 2단계 구조
    • 디렉터리는 디스크에 저장되는 버킷 주소 테이블
    • 디렉터리 깊이를 의미하는 정수값 d를 포함하는 헤더와 데이터가 저장된 버킷에 대한 2^d개의 포인터로 구성
  • 모조키(pseudo key)
    • 레코드의 키 값을 일정 길이와 비트 스트링으로 변환한 것
    • 모조키의 첫 d 비트를 사용하여 디렉터리에 접근
  • 버킷 헤더
    • 정수값 𝑖(≤𝑑)가 저장되어 있음을 표시
    • –𝑖는 버킷에 저장되어 있는 레코드의 모조키들이 처음부터 𝑖 비트까지 일치함을 표시

         

      

         

  • 레코드 삽입에 의해 분할된 확장성 해싱 파일

       

    

       

  10.3 비트맵 인덱스

• 비트맵 인덱스
  • 다중키를 가진 질의를 효율적으로 처리하기 위해 고안된 특수한 형태의 인덱스
  • 비트맵
    • 간단한 비트의 배열
    • 릴레이션 𝑟의 속성 𝐴 에 대한 비트맵 인덱스는 𝐴가 가질 수 있는 값에 대해 비트맵을 구성
    • 각 비트맵은 릴레이션에 있는 레코드 수 n개 만큼의 비트로 표현
  • 𝑖 번째 레코드가 속성 𝐴에 대해 해당 속성값을 가지면 비트맵의 𝑖 번째 비트를 1로, 그렇지 않으면 0으로 설정

    

• 비트맵 인덱스의 사용 예
  • 성별이 남자이고 성적이 B인 학생의 정보를 출력

    => SELECT *FROM 학생

    WHERE 성별='남자' AND 성적='B'

       

  • 성별의 '남자'와 성적의 'B'의 비트열에 대한 비트 논리곱 연산을 수행

    => 성별 남자 1 0 0 1 0 1

    &

    성적B 1 0 0 1 0 0

    1 0 0 1 0 0

       

    

       

  • 비트맵의 활용
    • 속성에 대한 값이 유한하고 범위가 비교적 작은 규모일 때 용이

      Ex) 직책, 학과, 혈액형 등

  • 비트맵 인덱스의 크기
    • 실제 렐레이션 크기에 비해 자유로움
    • 레코드의 길이가 수백 바이트가 되어도 바이트 인덱스에서는 하나의 비트로 표시

1. 병행 프로세스 I

   4.1 병행 프로세스

• 병행성
  • 병행성(concurrency)
    • 여러 개의 프로세스 또는 쓰레드가 동시에 실행되는 시스템의 특정

      

• 병행 프로세스의 실행 상태
  • CPU 개수에 따른 병행 프로세스의 실행 형태
    • 하나의 CPU에서 인터리빙 형식으로 실행

      

         

    • 여러 개의 CPU에서 병렬 처리 형식으로 실행

      

     

  • 메모리 구조에 따른 병행 프로세스의 실행 형태
    • 강결합 멀티프로세서 시스템-공유 메모리 구조

      

         

    • 약결합 멀티프로세서 시스템-분산 메모리 구조

      

     

• 병행성 문제
  • 병행성 프로세스들이 상호작용하는 경우 발생
    • 공유자원 점유 문제
    • 동기화 문제
    • 통신 문제

         

  • 상황에 따른 구분
    • 단일 프로세스 내의 병행성
    • 프로세스 간의 병행성

         

• 단일 프로세스 내의 병행성
  • 우선순위 그래프

    

       

  • Fork/Join 구조
    • Fork L : 2개의 병행 수행을 만듦(레이블 L위치부터와 fork 명령어 다음부터)
    • Join n : 병행하는 n개의 흐름을 하나로 재결합

      

         

      

         

  • 병행문
    • 1개의 프로세스가 여러 가닥의 병렬 프로세스로 분할 되었다가 다시 하나로 결합
    • Parbegin / parend 문

      

         

      

• 프로세스 간의 병행성
  • 비동기 병행 프로세스

    

       

    

     

     

  4.2 동기화와 임계영역

• 동기화와 임계영역
  • 프로세스 동기화
    • 2개 이상의 프로세스에 대한 처리순서를 결정하는 것

      Ex) 동시에 사용할 수 없는 공유자원,

      한 프로세스의 처리 결과에 따라 다른 프로세스의 처리가 영향을 받는 경우

  • 임계영역
    • 2개 이상의 프로세스가 동시에 액세스하면 안 되는 공유자원을 액세스하는 코드 영역
  • 상호배제
    • 2개 이상의 프로세스가 동시에 임계영역에 진입하지 못하도록 하는 것

         

• 임계 영역의 예
  • 상호배제를 통한 프로세스 동기화

    

• 임계 영역을 갖는 프로세스의 일반적 구조

  

• 임계 영역 문제해결을 위한 요구조건
  • 상호배제
    • 한 프로세스가 임계영역에서 실행 중일 때, 다른 어떤 프로세스도 임계영역에서 실행될 수 없음
  • 진행
    • 임계영역에서 실행 중인 프로세스가 없고 여러 프로세스가 임계 영역에 진입하고자 할 때 그 중에서 적절히 한 프로세스를 결정해야 하며 이 결정은 무한정 미룰 수 없음
  • 제한된 대기
    • 한 프로세스가 임계영역 진입 요청을 한 후 수락될 때까지

      다른 프로세스가 임계영역 진입을 허가 받는 횟수는 제한이 있어야 함

         

• 임계영역 문제해결을 위한 도구
  • Test-and-Set
  • 세마포어

       

• Test-and-Set
  • Test-and-Set 명령어(TS 명령어)
    • 상호배제의 하드웨어적 해결 방법
    • 분리가 불가능한 단일 기계 명령어(원자적으로 수행)

    

       

  • 상호배제의 구현

    

       

    

  • 문제점
    • 많은 프로세스가 임계영역에 들어가기를 원할 때 기아가 발생할 수 있음
    • Busy waiting을 함으로써 다른 작업이 사용할 수 있는 CPU 사이클을 낭비

      *기아(starvation)

      프로세스가 필요한 자원할당을 받지 못하고 계속적으로 대기하게 되는 상황

• 세마포어
  • 세마포어(semaphore)
    • Dijkstra가 제안한 동기화 도구
    • 세마포어 s : 사용가능한 자원의 수 또는 잠김/열림 등의 상태를 나타내는 값을 저장하는 정수형 공용변수
    • 세마포어 s는 두 표준단위 연산 P와 V에 의해서만 접근됨

         

    

• 상호배제의 구현

  

     

  

     

  

     

  

     

  

• 동기화 문제 해결
  • 프로세스1이 문장 S1을 실행한 후 프로세스2가 문장 S2를 실행하도록 동기화(block/wakeup 프로토콜)