Algorithm

• 한 번 정렬이 진행될 때마다 피벗이 정렬되고 정렬될 배열을 좌우로 나눠 재귀호출하여 모든 원소를 정렬한다.

Quick Sort

구현 방법

1. 피벗 선택

   • 배열에서 피벗으로 사용할 요소를 선택

   • 일반적으로 첫 번째, 마지막, 또는 중간 요소를 선택

2. 분할 (Partition)

   • 피벗을 기준으로 배열을 두 부분으로 나눈다.

   • 피벗보다 작은 요소들은 왼쪽으로, 큰 요소들은 오른쪽으로 이동

3. 재귀 호출

   • 분할된 두 부분 배열에 대해 Quick Sort를 재귀적으로 적용한다.

4. 종료 조건

   • 부분 배열의 크기가 1 이하가 될 때까지 재귀를 반복한다.

5. 결합

   • 정렬된 부분 배열들이 자동으로 하나의 정렬된 배열로 합친다.

시간 복잡도

• 평균 케이스: O(n log n)

• 최악의 케이스: O(n^2)

• 최선의 케이스: O(n log n)

장점

• 공간 효율성: 추가 메모리 공간을 거의 필요로 하지 않는 제자리 정렬 알고리즘

• 캐시 친화적: 지역성이 좋아 캐시 성능이 우수

• 병렬화 가능: 분할 정복 접근 방식으로 인해 병렬 처리에 적합

단점

• 불안정 정렬: 동일한 키 값을 가진 요소들의 상대적 순서가 보존되지 않을 수 있다.

• 최악의 경우 성능: 피벗 선택이 잘못되면 O(n^2)의 시간 복잡도를 가질 수 있다.

• 재귀적 특성: 재귀 호출로 인해 스택 오버플로우가 발생할 수 있다.

OS

주변 장치

• 여러 주변장치는 메인보드 내의 버스로 연결된다.
  - 기존에는 하나의 버스로 연결되었음
  → CPU가 I/O 작업을 수행할 때 다른 작업을 할 수 없음
  → I/O Controller(입출력 제어기)와 여러 개의 버스가 추가되었다.
  

입출력 제어기

• 입출력 버스에서 온 데이터를 메모리로 옮긴다.
  → 메모리는 CPU의 명령으로 움직인다.
  → 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요하다.
  → 입출력 제어기가 CPU의 도움이 필요 없도록 DMA(Direct Memory Access) 제어기가 추가되었다.

• DMA 제어기를 통해 데이터를 직접 메모리에 저장하거나 가져올 수 있다.

• CPU와 DMA가 사용하는 메모리가 겹치지 않도록 구분한다.(=Memory Mapped I/O)

입출력 버스

• 세부적으로 느린장치와 빠른장치를 구분하기 위해 두개의 채널로 나뉜다.

  • 고속 입출력 버스

  • 저속 입출력 버스
    → 속도 차이로 인한 병목현상을 해결한다.

시스템 버스

• 고속으로 작동하는 CPU와 메모리가 사용한다.

입출력 버스

• 주변장치가 사용한다.

그래픽 카드

• 매우 대용량의 데이터를 다룬다.
  → 고속 입출력 버스도 감당할 수 없다.
  → 시스템 버스에 바로 연결해 사용한다.

내부 구조

• 메인보드에 있는 버스로 연결된다.

• 하나의 버스는 Address 버스, Data 버스, Control 버스로 구성되어 있다.
  → I/O 디바이스는 세 세가지 버스를 따로 받을 수 있다.

• H/W에 맞게 외부 인터페이스가 존재한다.

• 레지스터 : 입출력 작업을 할 때 데이터를 저장하는 역할을 수행

  • CPU 작업을 위해 메모리로 값이 이동하기도 한다.

데이터의 전송단위에 따른 분류

캐릭터 디바이스

• 상대적으로 적은 양의 데이터를 전송한다.

• 마우스, 키보드, 사운드 카드, 직렬/병렬 포트, etc..

블록 디바이스

• 많은 양의 데이터를 전송한다.

• HDD, SSD, 그래픽 카드, etc...

광학 마우스

• 마우스 하단부의 작은 카메라가 초당 1500회 이상의 사진을 찍어 마우스의 디바이스 컨트롤러 내의 DSP(Digital Signal Processor)로 전송한다.

• DSP는 사진을 분석해 마우스의 x, y축 움직임을 캐치한다.

• DSP가 마우스의 움직임과 클릭같은 데이터를 감지하면 디바이스 컨트롤러는 CPU에게 인터럽트를 보내고 마우스 드라이버가 동작해서 데이터를 읽어간다.

• 마우스 드라이버는 OS에게 이벤트를 주고, OS는 이벤트를 Foreground 애플리케이션으로 전달한다.

키보드

• 사용자가 키보드를 누르면 키보드의 디바이스 컨트롤러가 어떤 키를 입력받았는지 알아낸다.

• 디바이스 컨트롤러가 CPU에게 인터럽트를 보낸다.

• 키보드 드라이버는 OS에게 이벤트를 보낸다.

• OS는 이벤트를 Foreground 애플리케이션으로 전달한다.

HDD

• 블록 디바이스의 한 종류

구조

• Spindle : 막대

• Platter : 자기화된 원판

  • 여러 개의 track으로 구성

  • 표면에 자성이 있다.

    • N극 : 0

    • S극 : 1
      → 자석을 갖다대면 데이터가 손상된다.

  • 일반적으로 플래터 수는 2개 이상

• Read/Write Head : 플래터의 표면을 읽는다.

• Cylinder : 여러 개의 플래터에 있는 같은 트랙의 집합

• Track : Platter를 구성하고 있는 부분

• Sector : Track을 구성하는 부분

  • HDD의 가장 작은 단위

• Disk Arm : Read/Write Head가 붙어 있는 장치

데이터를 읽는 방법

1. User Process가 HDD의 특정 섹터에 접근 요청

   • 실린더 C로 가서 트랙 B에 있는 섹터 D를 읽어들여라.

2. Seek 동작 수행

   • 디스크 암은 헤드를 실린더 C로 이동시킨다.

   • Seek Time 헤드를 실린더로 이동시키는 걸리는 시간
     → HDD가 느린 이유

3. 트랙B의 섹터D가 Read/Write Head에 닿을 때 까지 스핀들을 회전시킨다.

4. 헤드에 섹터D가 읽히면 작업 완료

Flash Memory(SSD)

• 블록 디바이스의 종류

• 전기적으로 데이터를 읽어들인다.

• 특정한 지점에 데이터를 쓰면 덮어쓰기가 불가능하다.

  • 데이터를 지우기 가능한 횟수가 정해져있다.
    → 같은 지점에 지우기를 자주 사용하면 망가져 사용할 수 없다.