운영체제 3주차 학습 요약

가상메모리

• 컴퓨터의 물리적 메모리의 크기를 확장하기 위해 사용되는 기술

• 운영체제가 각 프로세스마다 독립적인 메모리공간을 할당할 수 있게 해줌

• 이때문에 프로그래머는 프로그램이 메모리 어디에 위치하는지 신경쓰지 않고, 0부터 시작된다고 생각하고 프로그래밍 함

동적주소변환 (DAT)

메모리관리자가 가상메모리의 논리주소를 물리주소로 변환하는 것을 말함

세그멘테이션 분할 방식에서 논리 주소를 물리주소로 변환

• 메모리관리자는 CPU에서 받은 논리주소를 세그멘테이션 테이블을 이용하여 물리주소를 찾음

페이징 분할 방식에서 논리 주소를 물리주소로 변환

• 메모리관리자는 CPU에서 받은 논리주소를 페이지 테이블을 이용하여 물리주소를 찾음

페이지드 세그멘테이션 분할 방식에서 논리 주소를 물리주소로 변환

• 세그멘테이션 테이블의 속성값으로 페이지 테이블의 인덱스를 추가할 수 있게하여 세그멘테이션, 페이지 테이블을 모두 이용해서 물리주소를 찾음

• 가상메모리는 세그멘테이션으로 분할되어 있고, 물리메모리는 페이징으로 분할되어 있어 각 분할방식의 장점을 취할 수 있게 함

메모리 접근권한

• 세그멘테이션 테이블에 메모리의 특정번지에 권한을 부여하는 속성을 추가하여, 메모리 접근시 권한을 검사할 수 있음

디멘드 페이징 정책

• 조만간 필요할 것 같은 데이터를 메모리에 가져오고 쓰이지 않을 것 같은 데이터는 스왑영역으로 보내는 정책

• 필요한 데이터를 언제 메모리로 가져올지를 결정하는 것

페이지 테이블 엔트리

• 접근비트, 변경비트, 유효비트, 권한비트 (프레임번호만 있는게 아님)

페이지 폴트

프로세스가 가상메모리에 접근요청했을때 물리메모리에 데이터가 없을때 발생하는 인터럽트

페이지 폴트가 발생하면 보조저장장치의 스왑영역에 접근하여 스왑영역에 있는 데이터를 메모리에 올리는 작업을 함

페이지 교체정책

• 스왑영역에서 데이터를 찾아 메모리에 올리려고 했는데, 이미 메모리가 가득찼을때 조회할 데이터를 메모리에 추가하기위해 데이터를 남기거나 스왑영역으로 보내는 정책

• 무작위, FIFO, Optimum, LRU, Clock Algorithm, Enhanced Clock Algorithm

스레싱과 워킹셋

스레싱

제한된 물리 메모리에 프로그램을 많이 올려 스왑 영역에 데이터가 많이 저장되고 Page Fault가 자주 발생하게 되면 CPU 사용률이 떨어짐. 스케줄러에 의해 운영체제는 CPU 사용률을 올리기 위해 더 많은 프로세스를 메모리에 올리게 되고 이를 반복하게 되면 CPU 사용률이 0에 가깝게 떨어지는데 이를 스레싱이라고 함

워킹셋

현재 메모리에 올라온 페이지는 다시 사용할 확률이 높기에 하나의 세트로 묶어서 메모리에 올리는데 이를 워킹셋이라고 함

입출력장치

• 주변장치(I/O 디바이스, 저장장치)들은 메인보드에 있는 버스로 연결되어 있음

• 각 하드웨어에 맞게 외부 인터페이스가 존재

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

   

• 입출력 제어기는 두 개의 채널, 시스템 버스와 입출력 버스로 구분

파일과 파일시스템

운영체제가 파일을 관리하기 위한 파일 관리자

파일을 관리하는 하드디스크나 Flash Memory(SSD)는 블록 디바이스, 파일 시스템은 전송 단위는 블록이지만, 사용자는 바이트 단위로 파일에 접근이 가능해야 함, 파일 관리자가 이를 중간에서 관리

파일의 종류

• 순차파일구조, 직접파일구조, 인덱스파일구조

디렉토리

• 관련있는 파일을 모아둘 수 있도록 하는 장치

알고리즘 & 자료구조 3주차 학습 요약

삽입 정렬 (Insertion Sort)

• 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내 적절한 위치에 "삽입"해서 정렬하는 알고리즘

• 삽입하려는 데이터를 정렬된 영역의 원소를 역순으로 순회하면서 비교

  • O(n²)

  • 장점 : 작은 데이터나 거의 정렬된 데이터에 대해 매우 효율적

  • 단점 : 속도가 느려서 대규모 데이터에 비효율적

     

병합 정렬 (Merge Sort)

• 정렬하려고 하는 배열을 잘게 쪼갠다음, 순서에 맞게 재배열하는 알고리즘 (재귀)

  • O(n log n)

     

  • 장점 : 속도가 빠르며 대규모 데이터에서도 일정한 성능을 보임

     

  • 단점 : 추가 메모리 공간이 필요하며, 메모리 효율이 떨어질 수 있음

퀵 정렬 (Quick Sort)

• 배열의 숫자중 하나를 피벗으로 설정하고, 피벗의 왼쪽에는 작은값, 피벗의 오른쪽에는 큰값을 정렬하는 알고리즘

• 분할시 왼쪽과 오른쪽의 포인트가 교차하면 피벗과 오른쪽 포인트의 값과 교환하여 피벗값을 정렬해나감

  • 평균 O(n log n), 최악 O(n²)

     

  • 장점 : 평균적으로 매우 빠르고, 메모리 사용이 적음

     

  • 단점 : 피벗 선택에 따라 성능이 달라지며, 최악의 경우 속도가 느려질 수 있음 (그러나 최악이 되는 경우는 거의 없음)

동적프로그래밍

• 메모이제이션

  • 계산 결과를 따로 기억해서 여러 번 중복 계산하지 않도록 하는 기법

  • 하향식 계산 방식으로 활용

• 타뷸레이션

  • 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장하는 기법

  • 상향식 계산 방식으로 활용

회고

스터디의 마지막 주차가 되었네요. 나름 정리도 하고 CS전공지식 스터디 내부에서 다른분들이랑 모여 발표 스터디도 하면서 열심히 학습하면서 많이 배운시간이 었던거 같아요. 특히나 알고리즘을 직접 구현해보면서 각 알고리즘의 장.단점을 외우지 않아도 조금만 생각해보면 장.단점을 도출할 수 있게 되어서 좋았어요.

스터디 발표 & 정리 자료 캡쳐

빠르게 끝나 아쉬움반 후련함반이 있지만, 계속 복습하고 부족한 부분 채워나가면서 열심히 해나가겠습니다.
많이 배웠습니다. 즐거웠어요.