알고리즘

퀵정렬

• 퀵정렬은 병합정렬과 같이 분할 정복 알고리즘으로~재귀를 사용한다.

  • 피벗 : 첫 피벗은 첫번째 인덱스

  • left, right : 각자 왼쪽 오른쪽 끝에 있는 것

  • rightStartIndex : 왼쪽으로 이동, 피벗보다 작은 값을 만나면 멈춘다.

  • leftStartIndex : 오른쪽으로 이동, 피벗보다 큰 값을 만나면 멈춘다.

• rightStartIndex와 leftStartIndex가 조건에 의해 멈췄을 때 두값을 스왑하여 바꾼다.

• rightStartIndex와 leftStartIndex가 지나칠 때 멈춘다.
  rightStartIdnex값과 피벗 위치를 바꿔 피벗은 5, rightSI는 4가된다.

  
  -> 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값으로 나뉘게되고
  나눠진 그 배열을 또 위에서 정렬한 것처럼 반복

• 피벗을 기준으로 배열을 반으로 나눈다 -> O(log n)
  이작업을 데이터 n개만큼 반복해야하므로 n을 곱한다. -> O(nlog n)

• 최악의 경우 : 피벗이 가운데가 아니고 한쪽으로쏠림 -> O(n^2)

• 근데 평균성능보는거라 Θ(nlogn) Θ는 세타

• 병합이랑 퀵이랑 비교했을 때 병합이 더 좋아보이지만 퀵은 적은비교 적은 메모리사용으로 퀵이짱인것이다~

   

운영체제

주변장치

• 내부구조를 보자면...

  • 레지스터들 : 입출력 작업 시에 데이터를 저장하는 역할
    이 값들은 메모리에 이동되기도 한다.

  • 세가지 버스를 따로 받을 수있다. Address, Data, Control

  

• 캐릭터 디바이스와 블록 디바이스

  • 데이터 전송단위가 캐릭터(글자)이거나 블록 단위

  • 캐릭터 디바이스 특 :

    데이터 전송단위가 캐릭터로 상대적으로 작다. 마우스,키보드

  • 블록 디바이스 특 :

    데이터 전송단위가 블록단위로 캐릭터보다는 크다. 하드디스크 ,ssd

     

• 주변 장치들은 메인보드 내의 버스로 연결된다.

  • 하나의 버스였지만 I/O작업을 수행하기위해서 입출력 제어기와 여러 개의 버스가 추가됐다.
    (CPU가 I/O 작업때문에 다른작업을 못했기때문)

  • CPU는 I/O작업을 만나면 입출력 제어기에게 입출력 작업을 맡기고 다른 작업을 실행하러간다.

    • 입출력제어기 - 시스템버스와 입출력 버스로 구분
      시스템버스는 CPU, 메모리가 사용하고 입출력 버스는 주변장치들이 사용

    • 입출력버스 - 고속입출력, 저속입출력
      ->속도차이로인한 병목현상을 해결

  • 그래픽카드는 주변 장치이지만 대용량의 작업을 실행하기때문에 시스템 버스를 사용한다.

  • 입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮겨야한다. -> 입출력 제어기가 메모리 접근을 위해 CPU를 거쳐야되는데 CPU 도움없이 DMA제어기를 추가시켰다.

  • Direact Memory Access : cpu없이 입출력 제어기가 메모리에 접근할 수있도록 한다.

  • Memory Mapped I/O : cpu와 DMA 제어기가 사용하는 메모리 영역을 나눠 혼돈을 막는다.

마우스

• 광학마우스 , 키보드

  • 아래 카메라를 통해 초당 1500회를 찍어 디바이스 컨트롤러 안 DSP로 보낸다.
    x,y 축 좌표 움직임을 캐치한다.

  • DSP가 움직임과 클릭을 감지했을 때 cpu에게 인터럽트를 발생시켜 마우스 드라이버가 동작해 데이터를 읽어간다.

  • 마우스 드라이버는 운영체제에게 이벤트 신호를 주고 운영체제는 이 이벤트를 foreground 애플리케이션으로 전달해준다.

  • 해당 애플리케이션은 받은마우스 이벤트를 처리한다.

     

하드디스크

• 하드시스크 구조

  • 플레터 : 플레터는 여러개의 트랙으로 구성되었고 표면을 자성을 띈다. n극일경우 0, s일경우 1

  • 스핀들 : 플레터 자기화된 원판으로 이뤄졌다. 디스크암이 읽기/쓰기 헤드로 플레터의 표현을 read

  • 헤드 : 헤드는 여러 개 있고 항상 같이 움직인다.
    이 헤드들은 여러 개의 플래터를 가리키게 된다.

  • 실린더 : 여러개의 같은 집합의 플래터에 있는 트랙의 집합을 실린더라고한다.

  • 트랙 : 여러 개의 섹터로 나뉜다.

  • 섹터 : 하드디스크의 가장 작은 단위

• 유저프로세스가 하드 디스크의 특정 섹터에 접근하고 싶어서 이러한 요청을 보낸다.

  • 실린더 c로 가서 트랙 b에 있는 섹터 d를 읽어라

    • seek : 디스크암은 헤드를 실린더 c로 이동

    • seek time : 헤드를 실린더로 이동시키는데 시용하는 시간

    • 트랙b의 섹터가 d 가 헤드에 닿을 때가지 스핀들ㅇ르 회전시키고 헤드에 섹터d가 읽히면 작업이 끝난다.

  • 다른 전자 기기 작업시간은 ns 단위지만 헤드 이동시간은 ms라 하드디스크가 느리다.

     

• 플레시 메모리(ssd)와 하드디스크

  • 자성을 띄는 하드디스크는 자석을 가져다대면 망가지지만 플레시 메모리는 그러지 않고 전기적으로 데이터를 읽어 조용하다.

  • 스핀들과 같은 회전축때문에 충격에 약한 하드디스크

  • ssd 단점 : 특정 지점에 데이터를 썼다면 덮어쓰기가 불가능하다.
    똑같은 지점에 데이터를 쓰고 싶으면 지워야하지만 메모리 지우기 기능 횟수가 정해져있다. ->똑같은 구간에 지우기 쓰기를 여러 번할 경우 망가질 수있다.