[CS지식] OS(운영체제)

운영체제: 컴퓨터 하드웨어를 관리하는 소프트웨어 -> 자원 할당자. 하드웨어와 밀접

애플리케이션과 사용자들 간에 제어 및 조정

＊ 컴퓨터 시스템은 하드웨어, 운영체제, 응용 프로그램, 사용자 4가지 요소로 구분됨

 

1. Interrupt

 운영체제는 인터럽트 기반으로 동작함.

 하드웨어나 소프트웨어에서 어떤 사건이 발생하면 이를 인터럽트로 사용하여 시스템에 알림

 CPU가 인터럽트 되면, CPU는 하던 일을 멈추고 즉시 고정된 위치로 실행을 옮겨 인터럽트를 처리함

 

■ 인터럽트 핸들링: 인터럽트는 인터럽트 벡터를 사용해 제어를 인터럽트 서비스 루틴으로 넘긴다.

 인터럽트 벡터는 모든 서비스 루틴의 주소를 가지고 있다.

 

■ 인터럽트 공통 기능

 인터럽트 구조에서 인터럽트 당한 명령의 주소는 저장되어야 한다.

 인터럽트 처리가 끝나면 인터럽트 당한 명령어로 실행이 옮겨갈 수 있다.

 

■ 인터럽트 처리

 운영체제는 인터럽트를 처리하기 이전에 현재의 레지스터와 프로그램 카운터 등을 비롯한 CPU의 상태를 보존한다.

 발생한 인터럽트의 종류를 파악한다.

 

■ 폴링(polling)

  벡터 사용

 인터럽트 종류에 따라 해야 할 작업을 결정하는 코드를 분리한다.

 

5. Kernel Data Structures 커널 자료구조

1) 리스트, 스택, 큐

 배열은 각 원소가 직접 접근될 수 있는 단순한 자료구조. 메인 메모리는 하나의 배열로 구축된다

 크기가 변하는 데이터는 어떻게 저장? 한 데이터를 제거하고 나머지 데이터들을 유지할 때는?

배열 대신 다른 자료구조 사용

 

1) 리스트: 리스트의 항은 배열과 달리 특정 순서로 접근해야 한다. 리스트는 데이터 값들의 집단을 하나의 시퀀스로 표시함.

연결리스트(linked list): 각 항이 다른 하나에 연결되어 있음.

가변 수의 항들을 수용하고 항의 삭제와 삽입이 쉬움.

단점은 길이가 n인 리스트에서 특정 항을 인출할 때의 성능이 선형, 즉 O(n)이라는 것

커널 알고리즘에 의해 직접 사용되며 리스트는 자주 스택이나 큐 같은 보다 강력한 자료구조를 구축하는 데 사용됨

 

2) 스택: 순차적 순서를 가진 자료구조. 후입선출(LIFO) (마지막에 넣은 항이 먼저 인출됨)

 스택 항 삽입/인출 -> PUSH/ POP

 운영체제는 함수를 호출할 경우 종종 스택을 사용함

 

3) 큐: 순차 순서의 자료구소. 선입선출(FIFO) 각 항은 삽입된 순서대로 큐로부터 제거됨.

 EX. 상점 계산대에서 기다리는 사람들, 프린터에 보내진 작업, CPU에서 수행을 기다리는 태스크들은 종종 큐로 구성

 

2) 트리(Trees): 데이터의 서열을 표시

 데이터 값들이 부모-자식 관계로 연결됨

 일반 트리: 부모가 임의의 수의 자식을 가짐

 이진 트리: 최대 두 개의 자식을 가짐 / 좌측 자식, 우측 자식

 이진 탐색 트리: 추가로 부모의 두 자식 사이에 좌측 자식 <= 우측 자식의 순서를 요구함

 균형 이진 탐색 트리: CPU 스케줄링 알고리즘의 일부로 균형 이진 탐색 트리 사용

 

3) 해시 함수와 맵: 데이터를 입력으로 받아 이 데이터에 산술 연산을 수행하여 하나의 수를 반환하며 이 수는 데이터를 인출하기 위해 테이블(전형적으로 하나의 배열)의 인덱스로 사용할 수 있음

 해시함수의 어려운 점은 두 개의 서로 다른 입력이 하나의 출력 값을 가질 수 있다는 것. 즉, 테이블의 동일 위치로 색인될 수 있음 -> 해시 충돌(hash collision) -> 테이블의 각 항에 연결 리스트를 두어 동일한 해시 값을 갖는 모든 항을 수록하게 함.