CS 1주차 발자국

운영 체제운영체제 개요컴퓨터는 운영체제가 없어도 동작이 가능예전 전화기는 통화만 되지만 최신 휴대전화는 어플등 다양한 기능이 가능운영체제의 일프로세스 관리메모리 관리하드웨어 관리파일 시스템 관리운영체제의 역사1943 애니악1950초반 직접회로 개발후반 싱글 스트림 배치시스템1960시분할 시스템싱글 스트림 배치 시스템 한계 극복프로그램을 순서대로 실행하는 것이 아닌 메모리에 여러 프로그램을 올려 놓고 시간을 나누어서 빠르게 돌아가며 실행UNIX멀티 프로그래밍다중 사용자파일 시스템1970개인용 컴퓨터의 시대매킨토시, ms-dos 운영체제의 구조커널프로세스와 메모리, 저장 장치를 관리하는 기능사용자는 인터페이스를 통해 접속사용자는 GUI, CLI로 커널 제어어플리케이션과 커널의 인터페이스는 시스템 콜을 사용하드웨어와 커널의 인터페이스는 드라이버를 사용컴퓨터 하드웨어와 구조폰 노이만 구조CPU와 메모리 사이에 버스로 연결.메인보드다른 하드웨어를 연결하는 장치cpu와 메모리가 필수CPU(중앙처리 장치)산술 논리 연산장치, 제어장치, 레지스터의 구조메모리 종류ram전원을 끄면 메모리가 휘발ROM(Read Only Memory)전월을 꺼도 메모리가 보존.바이오스 등 수정되지 않는 데이터를 저장부팅 과정ROM에 저장된 바이오스 실행부트 오더인터럽트cpu는 입출력 작업이 들어오면 입출력 관리자에게 입출력 명령주기적으로 장치들에게 확인→ polling 방식. 효율이 좋지 않음polling방식의 단점을 보완한게 인터럽트입출력 명령을 내리고 입출력 관리자는 입출력이 발생하면 cpu에게 전달cpu는 isr실행시켜 작업 완료.하드웨어 인터럽트소프트웨어 인터럽트 프로그램하드디스크 등과 저장장치에 저장된 명령문의 집합체저장 장치만 사용하는 수동적인 존재프로세스실행중인 프로그램하드디스크에 저장되어 있는 프로그램이 메모리에 올라가있는 상태메모리도 사용하고 운영체제의 cpu 스케줄링 알고르즘도 사용, 출력와 입력도 하는 능동적인 존재프로세스 구조code, data, heap, stack 영역으로 구조code실행하는 코드가 저장data전역 변수와 static(정적) 변수가 저장heap동적으로 메모리를 할당하는데 사용.stack지역 변수와 함수를 호출했을때 필요한 정보들이 저장프로세스가 되는 과정컴파일 과정전처리기 → 컴파일러 → 어셈블러 → 링커(링킹)유니프로그래밍메모리에 오직 하나의 프로세스가 올라와 처리하는 것cpu는 프로세스를 실행하다가 i/o 작업을 만나면 기다렸다가 완료되면 작업을 처리하나의 프로세스를 다 끝내야 다른 프로세스를 실행하는 단점이 존재.멀티 프로그래밍메모리에 여러개의 프로세스를 올려서 실행cpu가 프로세스를 실행하다가 I/O 작업을 만나면 기다리면서 다른 프로세스를 실행cpu 쉬는시간이 줄어들어 효율적여러개의 프로세스를 돌아가면서 짧은시간동안 작업을 진행하여 모든 프로세스를 동시에 실행시키는 것처럼 느끼게 하는 기술→ 멀티태스킹cpu를 한개가 아니라 여러개를 이용→ 멀티 프로세서멀티 프로세서로 작업을 처리하는 방식을 멀티 프로세싱이라 칭함.PCB(Process Control Block)프로세스가 만들어지면 운영체제는 해당 프로세스의 정보를 갖고 있는 PCB를 만들고 저장.PCB들은 연결리스트라는 자료 구조로 저장.프로세스가 종료되면 연결리스트에서 해당 프로세스의 PCB를 제거.연결 리스트의 구조는 유지PCB 구조포인터부모와 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터를 저장프로세스 상태현재 프로세스의 5가지 상태를 나타냄생성, 준비, 실행, 대기, 완료프로세스 ID프로세스를 식별하기 위한 숫자프로그램 카운터다음에 실행될 명령어의 주소를 포함하는 프로그램 카운터를 저장레지스터 정보프로세스가 실행될때 사용했던 레지스터 값들을 저장메모리 관련 정보메모리에 있는 위치정보, 경계레지스터 값 등이 저장CPU 스케쥴링 정보스케쥴링에 필요한 우선순위, 최종 실행시간, CPU 점유 시간등이 저장프로세스 상태시분할 시스템을 사용하는 운영체제는 여러개의 프로세스를 돌아가면서 실행cpu가 여러개의 프로세스를 동시에 실행하는 것이 아니라 한 순간에는 하나의 프로세스밖에 처리하지 못함속도가 빨라 사람이 보기엔 동시에 처리로 보임.생성 상태PCB를 생성하고 메모리에 프로그램 적재를 요청한 상태준비 상태CPU를 사용하기 위해 준비하고 있는 상태CPU 스케쥴러에 의해 CPU가 할당됨.대부분의 프로세스 상태실행 상태준비상태에 있는 프로세스가 CPU 스케쥴러에 의해 CPU를 할당받아 실행되는 상태실행상태에 있는 프로세스의 수는 CPU의 갯수만큼부여된 시간만큼만 사용이 가능시간이 완료되면 다시 준비 상태로 변경대기 상태프로세스가 입출력을 요청하면 입출력이 완료될 때까지 기다리는 상태완료 상태프로세스가 종료된 상태데이터를 메모리에서 제거하고 생성된 PCB제거 컨텍스트 스위칭프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로세스의 상태값으로 교체하는 작업실행중인 프로세스의 작업 내용을 PCB에 저장하고 실행될 기존 프로세스의 PCB의 내용대로 CPU가 다시 세팅됨. PCB에 변경되는 값들은 프로세스 상태, 프로그램 카운터, 레지스터 정보, 메모리 관련 정보 등컨텍스트 스위칭이 발생하는 이유CPU 점유 시간이 다 된 경우I/O 요청이 있는 경우다른 종류의 인터럽트가 있는 경우프로세스 생성과 종료.exe 파일 실행시 운영체제는 포로그램의 코드영역과 데이터 영역을 메모리에 로드하고 빈스택과 빈 힙을 만들어 공간을 확보프로세스를 관리하기 위한 pcb를 만들어 값을 초기화프로세스 생성과 정은 운영체제가 부팅되고 0번 프로세스가 생성될때 딱 1번만 실행.나머지 모든 프로세스는 새로 생성하지 않고 0번 프로세스를 복사해서 사용복사는 fork()함수를 사용새로 생성하는 것보다 복사하는게 빠르기 때문복사한 프로세스는 자식 프로세스0번 프로세스는 부모 프로세스자식 프로세스는 부모 프로세스의 코드영역, 데이터 영역, 스텍 영역가 pcb 내용을 전부 복사그럼 복사하면 0번 프로세스가 똑같이 실행되는거 아닌가?맞음. 그대로 복사하니 당연한 결과자기가 원하는 코드는 exec() 함수를 이용하여 실행.부모를 복사한 자식 프로세스의 코드와 데이터 영역을 원하는 겂으로 덮어쓰게됨.자식프로세스는 부모 프로세스와 다르게 동작 부모 프로세스와 자식 프로세스는 cpu 스케줄링에 따라 실행되는데 순서는 운영체제 따라 결정.부모 프로세스가 먼저 실행되는 경우pid 값을1 받으면 17번째 줄 함수 실행자식 프로세스의 exit 실행될때까지 대기.자식 프로세스 실행12번 함수 실행 후 13번 함수를 통해 프로세스 종료를 부모 프로세스에게 전달대기하고 있던 부모 프로세서는 자식 프로세스의 종료 신호를 받고 18번 함수 19번 함수를 실행하고 종료만약 부모 프로세스가 자식 프로세스보다 먼저 종료되거나 자식 프로세스가 비정상적인 종료가 되어서 exit신호를 주지 못해 ExitStatus를 읽어오지 못하여 메모리에 계속 살아 있는 상태를 좀비 프로세스라고 함쓰레드운영체제가 작업을 처리하는 단위는 프로세스프로세스를 생성하면 pcb가 생성되고 프로세스 수만큼 pcb, 코드, 데이터, 스택, 힙 영역도 만들어줘야 하기 때문에 너무 무거워짐.그래서 프로세스가 많아질수록 메모리를 많이 차지 하게 됨.⇒ 쓰레드 고안쓰레드는 프로세스 안에 있고 한개 또는 여러개가 존재하게 됨.쓰레드들은 프로세스의 pcb, code, data, heap영역을 공유. 단 stack은 쓰레드마다 하나씩 갖고 있음. 쓰레드들에게 id를 부여하고, 쓰레드를 관리하기 위한 TCB(Thread Control Blcok)이 생성.운영체제 관점에서 쓰레드들도 구분이 가능해짐.브라우저에서 탭을 하나 추가로 생성하면, 프로세스가 생성되는 것이 아니라 쓰레드가 하나 더 생성됨.프로세스와 쓰레드의 장단점안정성프로세스는 서로 독립적이기 때문에 하나의 프로세스가 문제 있어도 다른 프로세스는 영향을 받지 않는다.쓰레드는 하나의 프로세스 안에 존재하기 때문에 프로세스에 문제가 생기면 쓰레드에게도 문제가 생긴다.프로세스 방식이 쓰레드 보다 우수속도와 자원각각의 프로세스는 서로 고유한 자원을 갖고 있음. code, data, heap, stack영역을 전부 따로 두고 있고, 프로세스간 통신을 하려면 IPC를 이용해야 해서 오버헤드가 크고 속도가 느림.쓰레드는 한 프로세스 내에서 stack 영역을 제외한 영역을 공유하므로 오버헤드가 작음. 쓰레드 간의 통신은 데이터를 공유할 수 있으니 쉽지만, 공유되는 공간에서 문제가 생길 수 있음. CPU 스케쥴링 개요운영체제는 모든 프로세스에게 cpu를 할당/해제 하는데 이를 cpu 스케쥴링이라 함.스케줄러(운영체제)의 고려사항어떤 프로세스에게 cpu리소스를 주어야 하는가.cpu를 할당 받은 프로세스가 얼마나 cpu를 사용해야 하는가.시분할 처리 방식으로 여러 프로세스에 짧은 시간동안 돌아가면서 Cpu를 할당.→ 컴퓨터의 성능에 영향을 많이 미침.cpu를 할당받아 처리하는 작업을 CPU Burst. 입출력 작업을 I/O Burst.다중 큐큐먼저 들어온걸 먼저 처리하고, 나중에 들어온걸 나중에 처리하는 구조.프로세스가 실행상태에서 준비 상태로 돌아갈때운영체제는 해당 프로세스의 우선순위를 보고 그에 맞는 준비 큐에 넣음.cpu스케줄러는 준비 상태의 다중큐에 들어있는 프로세스들 중에 적당한 프로세스를 선택해서 실행 상태로 전환.프로세스가 실행상태에서 i/o 요청을 받아 대기상태로 오면i/o 작업 종류에 따라서 분류된 큐에 들어가게 됨.hdd, lan, 키보드 큐큐에 들어가는건 프로세스의 정보를 갖고 있는 PCB가 들어감.프로세스 정보를 담고 있는 PCB는 준비상태의 다중큐에 들어가서 준비되길 기다리며, CPU스케쥴러에 의해 실행 상태로 전환.CPU스케쥴러는 준비상태의 다중큐를 참조하여 어떤 프로세스를 실행시킬지 결정I/O 작업도 종류별로 나누어진 큐에 들어가고 CPU스케쥴러는 이를 참조해 스케쥴링을 진행.스케쥴링 목표리소스 사용률CPU사용률을 높이는것을 또는 I/O 사용률을 높이는것을 목표로 할 수 있음.오버헤드 최소화스케줄링을 하기 위한 계산이 복잡하거나 컨텍스트 스위칭을 자주하면 배보다 배꼽이 커지는 상황이 발생.스케줄러는 이런 오버헤드를 최소화 하는것을 목표공평성모든 프로세스에게 공평하게 CPU가 할당되어야 함.공평의 의미는 시스템에 따라 달라질 수 있음.처리량같은 시간내에 더 많은 처리를 할 수 있는 방법을 목표로 함.대기시간작업을 요청하고 실제 작업이 이뤄지기 전까지 대기하는 시간이 짧은 것을 목표로 함.응답시간대화형 시스템에서 사용자의 요청이 얼마나 빨리 반응하는지가 중요하므로 응답시간이 짧은것을 목표로 함.모든 목표를 최고 수준으로 유지하기는 힘듬.서로 상반된 목표가 있기 때문.처리량을 높이기 위해서는 하나의 프로세스에 cpu를 오래 할당해야함.응답시간을 줄이기 위해서는 여러 프로세스에 cpu를 골고루 할당해야함.→ 처리량과 응답시간의 목표를 같이 달성할 수 없음.→ 사용자가 사용하는 시스템에 따라서 목표를 다르게 설정.스케쥴링 알고리즘FIFO(First In First Out)먼저 들어온 작업이 먼저 나감.스케쥴링 큐에 들어온 순서대로 cpu를 할당하는 방식.먼저 들어온 프로세스가 완전히 끝나야만 다음 프로세스가 실행 됨.장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 실행되기 때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야 함.또한 I/O작업이 있다면 cpu가 i/o작업이 끝날때까지 기다리기때문에 cpu 사용률이 떨어짐.스케줄링의 성능은 평균 대기 시간으로 평가평균 대기 시간은 프로세스가 여러개 실행될때 이 프로세스가 모두 실행될때까지 대기 시간의 평균.프로세스 1의 burst는 25초, 프로세스2는 5초 프로세스3은 4초.프로세스1이 먼저 도착했으므로 대기시은 0초.프로세스2는 프로세스1이 실행되고 실행 하므로 대기시간은 25초.프로세스 3은 프로세스1과 프로세스2가 실행되고 실행 하므로 대기시간은 30초.평균 대기시간은 18.3초.순서가 바뀌면프로세스3은 바로 시작 되었으므로 대기시간은 0초.프로세스2이 실행되고 프로세스2가 실행. 대기시간은 4초.프로세스1은 프로세스 3,2 실행 시간만큼 기다려서 대기시간은 9초.평균 대기시간은 4.3초.⇒ FIFO 알고리즘은 프로세스의 Burst Time에 따라 성능의 차이가 심하게 나서 현대 운영체제에서는 잘 쓰이지 않고 일괄 처리 시스템에 사용됨.SJF(Shortest Job First)FIFO의 단점을 보완.이론적으로 FIFO보다 성능이 좋음.하지만 문제점 발생어떤 프로세스가 얼마나 실행될 지 예측이 힘듦.BurstTime이 긴 프로세스는 아주 오래동안 실행되지 않을 수 있음.→ 이러한 문제때문에 SJF알고리즘은 사용되지 않음.RR(Round Robin)FIFO알고리즘은 일괄처리 시스템엔 적절하지만 시분할 처리 시스템엔 부적절SJF알고리즘의 단점은 프로세스의 종료 시간을 예측하기 힘듦.FIFO 알고리즘의 단점을 해결한 프로세스에게 일정 시간만큼 cpu를 할당하고, 할당시간이 지나면 강제로 다른 프로세스에게 일정 시간만큼 cpu를 할당.강제로 cpu를 빼앗긴 프로세스는 큐의 마지막으로 이당.프로세스에게 할당하는 일정 시간은 타임 슬라이스 또는 타임 퀀텀이라고 부름.평균 대기시간 측정타임슬라이스: 10sP1의 BursTime은 25초 / P2는 4초 / P3는 10초P1은 큐에 들어오자마 실행. 대기시간은 0초25초중 타임 슬라이스 값인 10초만 실행되고 나머지 시간은 큐의 제일 뒤로 이동.P2(4s) / P3(10s) / P1(15s)p2는 10초동안 기다림. 대기시간은 10초BurstTime인 4초만 실행하고 종료.P3(10s) / P1(15s)p3은 14초동안 기다림. 대기시간은 14초BurstTime인 10초만 실행하고 종료P1(15s)p1은 p2, p3의 실행 시가만큼 기다림. 대기시간은 14초.BurstTime이 타임 슬라이스 값보다 크므로 10초만 실행.남은 작업시간은 큐의 맨 뒤로 생성P1(5s)다시 P1의 남은 작업을 실행. 큐에 생성되자마자 실행 되므로 대기시간은 0초.→ 평균 대기시간은 12.67sRR방식과 FIFO방식의 평균 대기시간이 비슷할 수 있음.평균 대기시간이 비슷하면 RR방식이 비효율적→ 컨텍스트 스위칭이 있기 때문에 컨텍스트 스위칭 시간이 더 추가되기 때문.→ RR 알고리즘의 성능은 타임슬라이스 값에 따라 크게 달라짐.타임 슬라이스가 무제한인 경우 FIFO와 같음.타임 슬라이스가 작은경우에는 컨텍스트 스위칭이 너무 자주 발생함.타임 슬라이스에서 실행되는 프로세스의 처리 양보다 컨텍스트 스위칭을 처리하는 양이커져서 오버헤드가 너무 커지는 상황 발생.최적의 타임슬라이스를 설정하는 방법은 사용자가 느끼기에 여러 프로세스가 버벅 거리지 않고 동시에 실행된다고 느끼면서 오버헤드가 너무 크지 않는 값을 찾아야 함.윈도우는 20ms, Unix는 100msMLFQ(Multi Level Feedback Queue)가장 일반적으로 쓰이는 cpu 스케쥴링 기법탄생 배경RR의 업그레이드 된 알고리즘P1은 I/O 작업 없이 CPU연사만 하는 프로세스, P2는 1초 CPU 연산을 하고 10초 동안 I/O 작업.P1 → Cpu Bound Process // P2 → I/O Bound ProcessCpu Bound Process는 Cpu 사용률과 처리량을 중요하게 여김.I/O Bound Process는 응답 속도를 중요하게 여김타임 슬라이스 값에 따른 효율 분석. (P2가 먼저 시작된다고 가정)타임 슬라이스가 100초인 경우I/O 요청이 발생하고 P1이 100초동안 실행됨. 타임 슬라이스가 1초인 경우I/O요청이 발생하고 P1이 10번 실행되면 P2의 작업이 끝나 인터럽트가 발생되고, P2는 큐에 들어감.P2는 다시 1초 실행 되고 다시 I/O 작업을 기다림.이후 계속 반속 상황 비교CPU는 쉬지 않고 일해서 CPU사용률은 100%I/O 사용률을 보면 P1이 실행되는 동안 P2의 I/O 작업이 완료된 시점부터 기다리는 시간이 발생하기 때문에 10%밖에 되지 않음.타임 슬라이스가 작기 때문에 P2가 첫번째 상황처럼 기다리며 낭비되는 시간이 거의 없음. 90%정도 나오게 됨. CPU 사용률과 I/O 사용률이 좋게 나오는 작은 크기의 타임슬라이스를 선택그리고 CPU Boud Process 타임 슬라이스를 크게 설정.운영체제 입장에서 CPU Boud Process와 I/O Bound Process 구분하는 기준CPU를 실행하는 프로세스가 스스로 CPU를 반납하면 CPU사용량이 적은거니 I/O Bound Process일 가능성이 큼.반대로 CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 강제로 CPU를 뺏기는 상황이면 CPU Boud Process일 확률이 높음.우선 순위를 가진 큐를 여러가지 준비.우선순위가 높으면 타임 슬라이스가 낮고 우선순위가 낮을 수록 타임 슬라이스 크기가 커짐.타임 슬라이스 크기를 오버해서 강제로 Cpu를 뺏기면 원래있던 순위보다 우선순위가 낮은 큐로 이동.자료구조 자료구조데이터가 어떻게 저장되고 어떻게 사용되는지 나타냄.가장 간단한 자료구조는 변수, 배열알고리즘어떤 문제를 해결하기 위한 확실한 방법자료구조가 바뀌면 알고리즘도 바뀐다시간복잡도특정 알고리즘이 어떤 문제를 해결하는 데 걸리는 시간시간을 측정하는 시간이 아닌 실행시간을 예측반복문이 많아지면 시간이 늘어난다.최선의 경우 - $\varOmega$최악의 경우 배열의 길이만큼 - Big-O평균의 경우 - $\Theta$ 배열기본적으로 제공하는 자료구조일반적인 프로그래밍 언어는 배열을 선언할때 배열의 크기를 선언.운영체제는 메모리에서 해당 크기만큼 연속된 빈공간을 찾아서 값을 할당.할당하지 않은 부분은 의미없는 쓰레기 값을 전달하고, 운영체제는 배열의 시작 주소만 기억.배열의 인덱스 참조는 크기에 상관없이 한번에 찾아와서 O(1)의 성능을 갖는다.하지만, 데이터 삽입, 삭제의 성능은 좋지 않음.배열의 데이터는 메모리에 연속된 공간에 할당하고 있음.배열 크기를 넘어서 할당하게 되면 문제가 발생.배열의 끝에는 다른 데이터가 있을경우 운영체제는 다시 연속적인 크기의 메모리를 찾아서 다시 할당하고. 기존의 데이터를 복사까지 해주어야함.그렇다고 배열의 크기를 처음부터 크게 할당하면 일시적으로 해결된것 처럼 보이지만, 처음부터 공간을 크게 할당하면 배열하나의 메모리양이 커지고, 다 사용하지 않으면 공간의 낭비이다.JS의 배열은 상황에 따라서 연속적, 불연속적으로 메모리를 할당하지만 대부분 불연속적으로 할당.메모리는 내부적으로 연결하여 사용자에게는 연속적처럼 느껴지게함.장점읽기, 쓰기와 같은 참조에는 O(1)의 성능을 가진다단점크기 예측이 힘들기 때문에 메모리 낭비가 발생할 수 있다.데이터 삽입, 삭제가 비효율적이다.연결리스트(Linked List)배열의 단점을 보완.저장하는 데이터들을 메모리에 분산해서 할당하고 데이터들을 서로 연결.Node라는 것을 만들어서 수행Node의 구조데이터를 담는 변수다음 노드를 가리키는 변수연결 리스트는 첫 노드의 주소만 알고 있으면 다른 모든 노드에 접근 할 수 있음.연결이라는 특성 때문에 배열과 다른 장단점을 갖고 있음.장점중간에 데이터를 삽입(삭제)하게 되는 경우 다음 노드의 정보만 바꿔주면 되므로 간단.단점특정 인덱스의 데이터에 바로 접근이 힘듦. 첫번째 노드에서 부터 순서대로 원하는 인덱스까지 이동해야 하므로 데이터 참조는 O(n)의 성능을 가짐.배열과의 비교크기배열은 고정연결리스트는 노드를 만들어 연결해주므로 동적주소배열은 연속적으로 할당연결 리스트는 불연속적인 공간에 할당데이터 참조배열은 메모리 접근이 빠름(O(1)연결리스트는 앞에서부터 해당 노드에 접근해야 하므로 느림(O(n))삽입과 삭제배열은 모든 데이터를 옮겨야해서 O(n)의 성능연결리스트는 삽입하려는 노드까지 계속 노드를 타고가야 하므로 O(n)의 성능 스택(Stack)First In Last Out(FIFO)먼저 들어온 데이터가 마지막에, 가장 늦게 나온 데이터가 제일 앞에 있는 데이터 구조.큐(Queue)First In First Out덱(Deque)덱은 데이터를 tail, head에 삽입과 삭제가 자유로운 자료 구조해시 테이블(Hash Table)해시, 맵, 해시맵, 딕셔너리로 언어마다 다른 이름을 갖고 있음.장점빠른 데이터 읽기삽입, 삭제단점메모리를 많이 차지함.좋은 해시 함수의 구현이 필수정Set데이터 중복을 허용하지 않는 자료 구조해시 테이블을 사용. HashSet이라고 불리기도 함.

CS 3주차 발자국

운영체제가상 메모리개요프로세스는 운영체제 영역이 어디 있는지, 물리 메모리 크기가 얼마나 큰지 몰라도 됨.→ 프로그래머는 물리 메모리의 크기와 프로세스가 메모리의 어느 위치에 올라가는지 신경쓰지 않아도 됨.프로세스는 메모리 관리자를 통해서 메모리에 접근프로세스 입장에서는 물리 메모리에 직접 접근하지 않고 메모리 관리자에게 요청만 하면 됨.메모리 관리자는 프로세스의 요청이 있으면 그에 맞는 물리 메모리로 연결 시켜 줌.가상 메모리의 크기는 이론적으론 무한대지만, 물리 메모리의 크기와, CPU의 bit수에 의해 결정.32bit CPU인 경우엔 $2^{32}$의 값인 4GB예를 들어, 운영체제와 4GB 프로세스 5개를 실행하기 위해서는 적어도 20GB가 필요.가상 메모리 시스템은 물리 메모리 내용의 일부를 하드디스크 내 스왑 영역에 옮기고 처리가 필요할 때 물리 메모리로 가져와 실행시키기 때문에 운영체제와 프로세스를 모두 실행 할 수 있음.메모리 관리자는 물리 메모리와 스왑 영역을 합쳐서 프로세스가 사용하는 가상주소를 물리 주소로 변환.→ 동적 주소 변환(DAT, Dynamic Address Translation)동족 주소 변환을 거치면 프로세스는 마음대로 사용자의 데이터를 물리 메모리에 배치 할 수 있음.가상 메모리는 운영체제 영역을 제외한 나머지 메모리 영역을 일정한 크기로 나누어서 프로세스에게 할당가변 분할 방식(세그멘테이션)고정 분할 방식(페이징)세그멘테이션-페이징 혼용 기법가상 메모리 시스템에서 가상 주소는 메모리나 스왑영역 중 한 곳에 존재메모리 관리자는 가상 주소와 물리 주소를 일대일 매핑 테이블로 관리. 세그멘테이션가변 분할 방식을 사용하는 메모리 할당 기법관점에 따른 메모리세그멘테이션에서 프로그램은 함수나 모듈 등으로 세그먼트를 구성.프로세스 입장에서는 각 영역을 서로 인접한 것 처럼 바라봄.메모리 처리 방식사용자와 프로세스, CPU가 바라보는 주소는 논리 주소.중간에 메모리 관리자가 물리 주소로 변환을 진행.메모리 관리자는 세그멘테이션 테이블이라는 정보를 갖고 있음.Base Address / Bound Address 정보가 저장하고 이를 이용해 물리 메모리 정보를 계산Bound Address는 세그먼트의 크기를 나타냄CPU에서 논리 주소를 전달 해주면 메모리 관리자는 해당 논리 주소가 몇번째 세그먼트인지 파악.메모리 관리자 내에서 Segment Table Base Register를 이용해서 물리 메모리내에 있는 세그멘테이션 테이블을 찾고 세그먼트 번호를 인덱스로 사용하여 Base Address와 Bound Address를 찾음참고로 컨텍스트 스위칭이 발생하면 운영체제는 메모리 관리자 내의 Segment Table Base Register를 해당 프로세스의 것으로 바꿔주는 작업을 진행.메모리 관리자는 cpu에게서 받은 논리 주소와 Bound Address 크기를 비교.논리 주소가 Bound Address 보다 작다면 논리 주소와 Base Address를 더해 물리 주소를 계산.논리 주소가 Bound Address 보다 크다면 메모리를 침범했다 생각하여 에러를 발생. 장/단점장점메모리를 가변적으로 분할 할 수 있음.코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근 보호가 편리단점외부 단편화 발생페이징고정 분할 방식.세그멘테이션의 단점은 외부 단편화를 해결하기 위해 고안.메모리를 정해진 크기의 페이지를 나눔메모리 처리 방식논리 주소 공간사용자와 프로세스가 바라보는 주소 공간일정한 크기로 균일하게 나누어짐.→ 페이지라고 부름물리 주소 공간실제 메모리에서 사용 되는 주소 공간페이지의 크기와 동일하게 누님→ 프레임이라고 부름주소 변환 방식메모리 관리자는 페이지 테이블을 갖고 있음.cpu에서 논리 주소를 전달해 주면 메모리 관리자는 논리 주소가 몇번 페이지인지, 오프셋은 몇인지 계산.메모리 관리자 내의 Page Table Base Register(PTBR)를 이용해서 물리 메모리에 있는 페이지 테이블을 찾고 페이지 번호를 인덱스로 프레임 번호를 알아내고 오프셋을 이용해 물리 주소로 변환만약 페이지 테이블에 프레임이 Invalid로 표시되어 있으면 스왑 영역(하드 디스크)에 저장되어 있다는 의미.페이징과 세그멘테이션의 차이페이지의 크기세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 갖고 있음페이징은 모든 페이지 크기가 동일하여 크기를 표현하는 Bound Address가 필요 하지 않음.영역 나누는 방식세그멘테이션은 논리적인 영역별로 세그먼트를 나눔힙 영역 / 데이터 영역 / 스택 영역 / 힙 영역페이징은 크기가 고정되어 있어 논리적인 영역별로 나누지 않고 페이지로 나누기 때문에 논리적인 영역을 나눌 수 없음.특정 영역만 떼어내어 공유하거나 권한을 부여하는게 어려움.장/단점장점모든 페이지는 크기가 같기 때문에 관리가 굉장히 쉬움단점내부 단편화 발생(메모리 낭비)각 프로세스마다 페이지 테이블을 갖고 있어 프로세스가 많아질수록 페이지 테이블도 많아진다.프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦.메모리 관리자가 참조하는 페이지 테이블도 물리 메모리의 운영체제 영역에 저장 되어 있어 페이지 테이블 크기가 너무 크면 사용자 영역이 부족해 짐.페이지 테이블의 크기를 적절하게 유지하는 것이 중요.페이지드 세그멘테이션세그멘테이션과 페이징을 혼합해 장접을 취한 방식세그멘 테이션의 장점가변 분할 방식이라 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 세그먼트로 나누어서 관리.다른 프로세스와 공유가 쉽고 각 영역에 대한 메모리 접근 보호를 하기가 쉬움.페이징고정 분할 방식으로 메모리를 효율적으로 관리.오버헤드가 적음.메모리 접근 권한메모리의 특정 번지에 부여된 권한으로 읽기(Read), 쓰기(Write), 실행(Execute) 세가지가 존재.프로세스는 코드, 데이터, 스택, 힙 영역이 있는데 각 영역마다 권한이 존재.코드영역은 읽기와 실행만 가능데이터 영역은 읽기 권한이 있고 쓰기 권한은 있거나 없을수도 있다.스택과 힙 영역은 일기 쓰기 권한이 있음.접근 권한에 대한 검사는 가상 주소에서 물리 주소로 변환될 때마다 발생.권한을 위반한다면 에러를 발생단점물리 메모리에 접근하기 위해서 메모리에 접근을 두번 진행 해야함세그먼 테이션 테이블 참조 / 페이지 테이블 참조현대 운영체제는 페이징과 페이지드 세그먼테이션 기법을 적절히 섞어서 사용디멘드 페이징메모리 가져오는 방식프로세스를 이루고 있는 코드, 데이터, 힙, 스택 영역과 같은 모듈이 모두 메모리에 올라와 실행 하는것이 아니라 필요한 모듈(일부)만 올라와서 실행됨프로그램이 실행될때 90%의 시간이 10%의 코드에서 보내는 것을 발견.→ 90:10 법칙→ 지역성 이론지역성 이론공간의 지역성현재 위치와 가까운 데이터에 접근할 확률이 높음시간의 지역성최근 접근했던 데이터가 오래 전에 접근했던 데이터보다 접근할 확률이 높음지역성 이론은 조만간 쓰일 데이터를 메모리에 올리고 당분간 쓰이지 않을 데이터는 스왑 영역으로 보내 성능을 향상 시킴디멘드 페이징은 조만간 필요할 것 같은 데이터를 메모리로 가져오고, 쓰이지 않을것 같은 데이터는 스왑영역으로 보내는 정책.메모리 가져오기 정책스왑 인스왑 영역에서 물리 메모리로 데이터를 가져 오는 것스왑 아웃물리 메모리 영역에서 스왑 영역으로 데이터를 보내는 것페이지 테이블의 비트 처리페이지 테이블의 한 행을 페이지 테이블 엔트리(Page Table Entry, PTE)라고 함페이징에서 확인한 인덱스와 프레임 뿐만 아니라 다양한 비트들이 존재.비트 종류접근 비트페이지가 메모리에 올라온 후 데이터의 접근이 있었는지 알려주는 비트작업 진행했으면 1, 그렇지 않으면 0변경 비트페이지가 메모리에 올라온 후 데이터의 변경이 있는지 알려주는 비트쓰기를 했으면 1, 그렇지 않으면 0유효 비트페이지가 물리 메모리에 있는지 알려주는 비트페이지가 스왑영역에 있으면 1, 물리 영역에 있으면 0읽기/쓰기/실행 비트권한 비트해당 메모리에 접근 권한이 있는지 확인하는 비트.프레임프로세스가 가상메모리에 접근 요청을 할때 메모리 관리자는 페이지 테이블을 보고 물리 메모리의 프레임을 찾음.물리 메모리에 없으면 Page Fault 발생Page Fault가 발생하면 보조 저장 장치의 스왑 영역에 접근하고, 프로세스는 대기 상태로 변경스왑 영역에 있는 데이터가 메모리로 올라가는 작업을 진행하고, 메모리에 올라가면 대기 상태의 프로세스는 다시 실행.페이지 교체 정책메모리가 꽉 찼을때 스왑 영역으로 보내는 정책 방식.교체 방식 종류무작위 선택 방식성능이 좋지 않아 별로 사용되지 않음FIFO메모리에 들어온 가장 오래된 페이지를 교체하는 방식Optimum앞으로 가장 오랫동안 쓰이지 않을 페이지를 교체 하는 방식이론적으로만 존재하고 구현이 불가능한 이론적인 방식다른 알고리즘과 성능 비교용으로 사용LRU(Least Recently Used)최근에 가장 사용이 적은 페이지를 선택하는 방법시간의 지역성에 따르면 최근 사용한 데이터가 앞으로도 사용될 확률이 높기 때문에 최근에 가장 사용을 적게한 페이지가 앞으로도 사용될 확률이 적다는 결론을 이용Optimum 알고리즘에 근접한 성능프로그램이 지역성을 띄지 않을땐 성능이 떨어짐빌레이디의 역설(Belady’s Anomaly)Page Fault를 줄이려고 메모리를 늘리고 페이지 수를 늘렸지만, 오히려 Page Fault가 더 많이 발생하는 현상FIFO 방식에서만 발생하며 LRU에서는 발생하지 않음.LRU가 가장 좋은 방식. 그러나 LRU에는 큰 단점이 있는데 바로 시간을 기록해야 한다는 점.최근 사용을 적게한 페이지를 알려면 일정 시간동안 사용된 페이지들을 조회해야함. 그래서 시간이 필수적.하지만 시간 데이터는 비트가 많이 필요하며 시간이 지나면 비트가 초기화 되는 문제가 발생 가능성이 높음.이를 방지하기 위해 Clock Algorithm 도입 하여 적용Clock Algorithm접근 비트 하나만 사용일정 시간마다 모든 페이지의 접근 비트를 0으로 초기화페이지가 참조 되었다면 1로 설정페이지를 원형으로 연결 스왑 영역으로 옮길 페이지를 포인터로 가르키는데 포인터를 클락 핸드라고 함.클락 핸드는 시계 방향으로 동작Page Fault가 발생하면 클락 핸드는 현재 참조하고 잇는 접근 비트를 확인하여 값을 변경하고 다음 페이지로 이동.이를 반복하다가 접근 비트가 0인 페이지를 발견 하면 해당 페이지를 스왑 영역으로 보냄.향상된 시계 알고리즘(Enhanced Clock Algorithm)접근 비트 뿐만 아니라 변경 비트도 확인.스왑 영역으로 보내지는 순서는접근비트가 0 변경 비트도 0그 다음은 접근 비트가 1 변경 비트가 0그 다음은 접근 비트가 1 변경 비트도 1FIFO를 사용 하는 경우하드웨어적으로 접근 비트를 사용하지 못하는 경우에 사용성능을 높이기 위해 2차 기회 페이지 교체 알고리즘을 고안FIFO 방식에서 자주 사용하는 페이지에게는 한번의 기회를 주는 방식Page Fault없이 한번에 페이지 접근에 성공했다면 해당 페이지를 큐의 맨 뒤로 이동시켜 수명을 연장 시켜주는 방식.성능 순서LRU > 2차 기회 페이지 교체 알고리즘 > FIFO스레싱과 워킹셋스레싱CPU 스케쥴링의 목표는 CPU 사용률 향상 이고, CPU 사용률 향상은 동시에 실행사는 프로세스의 수 높이는 것.프로세스 실행 공간인 메모리가 필요한데 모든 프로세스를 담을 수 없어 스왑 영역에 일부 저장.멀티 프로그래밍이 늘어나면 스왑 영역도 많이 필요하여 CPU가 작업하는 시간보다 스왑 작업의 시간이 더 길어져 CPU 사용률이 떨어지는 문제 발생→ CPU 스케쥴링은 더 많은 프로세스를 실행시키고 다시 문제가 반복되어 오히려 CPU 사용률이 떨어지는 문제 발생→ 스레싱스레싱의 원인은 물리 메모리의 크기 부족메모리의 크기를 늘리면 하드웨어적으로 해결 됨무작정 메모리를 늘린다고 성능이 좋아 지지는 않음워킹셋프로세스가 실행되면 일정량의 페이지를 할당하고 Page Fault가 발생하면 더 많은 페이지를 할당.반대로 Page Fault가 너무 적게 발생하면 페이지를 과하게 할당해 메모리가 낭비된다고 판단하여 페이지를 회수프로세스가 실행되는 동안 해당 프로세스에 맞는 적절한 페이지 수가 결졍 됨.적절한 페이지수가 결정됐다면 어떤 페이지들을 유지할 것인지 알아야 함→ 지역성 이론을 따름메모리에 올라온 페이지는 다시 사용할 확률이 높기 때문에 하나의 세트로 묶어서 관리→ 워킹셋워킹셋은 프로세스가 준비 상태에서 실행상태가 되는 컨텍스트 스위칭이 될때마다 사용입출력 장치주변장치그래픽 카드, HDD, SSD, 키보드, 마우스 등 다양내부 구조주변 장치들은 메인보드에 있는 버스로 연결버스는 Address, Data, Control 버스로 이루어져 있음 하드웨어에 맞게 외부 인터페이스가 존재장치의 상태와 데이터들을 보관하는 레지스터가 존재레지스터들은 입출력 작업을 할 때 데이터를 저장하는 역할을 함CPU가 사용하기 위해 메모리로 이동되기도 함주변장치는 캐릭터 디바이스와 블록 디바이스 2가지로 나뉨데이터의 전송 단위가 캐릭터(글자)냐 블록이냐로 나눈 것캐릭터 디바이스마우스, 키보드, 사운드 카드, 직병렬 포트데이터 전송 단위가 캐릭터(글자)로 상대적으로 크기가 작음블록 디바이스하드디스크, SSD, 그래픽 카드데이터 전송 단위가 블록(범위)로 상대적으로 크기가 큼여러 주변 장치는 메인보드내 하나의 버스로 연결해서 사용했음CPU가 작업을 하다 I/O명령을 만나면 직접 입출력 장치에서 데이터를 가져오는 방식이였음입출력 중에는 다른 작업을 하지 못하여 CPU 사용률이 떨어짐이를 해결하기 위해 입출력 제어기(I/O Controller)와 여러개의 버스가 추가됨CPU는 I/O 명령을 만나면 입출력 제어기에게 입출력 작업을 맡기도 다른 작업을 진행입출력 제어기는 두개의 채널 시스템 버스와 입출력 버스로 구분시스템 버스는 고속으로 작동하는 CPU와 메모리가 사용입출력 버스는 주변 장치가 사용입출력 버스는 느린 장치와 빠른 장치를 구분하기 위해 고속 입출력 버스와 저속 입출력 버스로 구분됨입출력 제어기는 여러 주변장치를 처리하는데 입출력 버스에서 온 데이터를 메모리로 옮김. 메모리는 CPU의 명령으로 움직이기 때문에 입출력 제어기가 메모리에 접근하기 위해선 CPU가 필요.그래서 입출력 제어기가 CPU의 도움이 필요없도록 DMA(Direct Memory Access) 제어기가 추가 됨.입출력 제어기는 데이터를 직접 메모리에 저장하거나 가져올 수 있음.CPU와 DMA가 사용하는 메모리가 겹치지 않도록 각 메모리 영역을 나누는데 이를 Memory Mapped I/O라고 부름. 하드 디스크와 플래시 메모리하드 디스크스핀들(spindle)이라는 막대와 스핀들에는 플래터(platter)라는 원판들이 붙어 있는 구조플래터는 자기화된 원판으로 이루어져있는데 디스크암(disk arm)이 읽기/쓰기 헤드(read/wirte head)로 플래터의 포면을 읽음플래터는 여러개의 트랙(track)으로 구성되어 있고 표면에 자성이 있기 때문에 표면이 N극을 띄면 0, S극을 띄면 1로 인식헤드가 움직이면 이 헤더들은 여러개의 플래터를 가리키게 되는데 이때 여러 개의 플래터에 있는 같은 트랙의 집합을 실린더(cylinder)라고 함트랙은 다시 여러개의 섹터(sector)로 나누는데 하드디스크의 가장 작은 단위헤드를 실린더의 원하는 위치로 이동하는데 이를 seek라고 함헤드를 실린더로 이동시키는데 걸리는 시간을 Seek Time이라고 함이때문에 하드 디스크가 느림 Flash memory하드 디스크보다 더 많이 사용SSD가 대표적전기적으로 읽어 빠르고 조용자성에 안전충격에 강함특정한 지점에 데이터를 썻다면 덮어 씌우기가 불가능특정한 지점에 데이터를 쓰려면 기존에 있던 데이터를 지우고 새로 써야 하지만 플래시 디스크는 지우기 가능한 횟수가 정해져있음.알고리즘삽입 정렬(Insertion Sort)정렬된 영역과 정렬되지 않는 영역을 나누어서 정렬되지 않은 영역의 데이터를 하나씩 뽑아서 정렬된 영역내 적절한 위치에 삽입하여 정렬하는 알고리즘예시[4, 1, 5, 3, 6, 2] // 정렬된 영역: [4] // 정렬되지 않은 영역 [1, 5, 3, 6, 2] // 1. 각 영역의 첫번째 인덱스 4와 1을 비교 // 4가 1보다 크므로 4를 오른쪽 인덱스에 덮어 씌워줌 [4, 4, 5, 3, 6, 2] // 삽입할 데이터 1를 정렬된 데이터와 비교하려고 하지만 4를 오른쪽에 덮어 씌웠으니 존재하지 않음. // -> 4의 위치에 1을 삽입 [1, 4, 5, 3, 6, 2] // 정렬된 영역 [1, 4] // 정렬되지 않은 영역 [5, 3, 6, 2] // 2. 정렬되지 않은 영역의 첫번째 인덱스의 데이터를 정렬된 영역의 마지막 인덱스의 데이터와 비교 // -> 4와 5를 비교 // 4는 보보다 작으므로 자리 변경하지 않음. 5또 한 마찬가지 [1, 4, 5, 3, 6, 2] // 정렬된 영역 [1, 4, 5] // 정렬되지 않은 영역 [3, 6, 2] // 3. 정렬되지 않은 영역의 첫번째 인덱스의 데이터를 정렬된 영역의 마지막 인덱스의 데이터와 비교 // -> 5와 3을 비교 // 5는 3보다 크므로 오른쪽에 덮어씌워줌 [ 1, 4, 5, 5, 6, 2] // 다시 정렬된 영역의 뒤에서 2번째 값인 4와 3을 비교. // -> 4가 3보다 크므로 오른쪽에 덮어씌워줌 [1, 4, 4, 5, 6, 2] // 그리고 다시 4의 이전 데이터인 1과 3을 비교 // -> 1은 3보다 더 작으므로 덮어씌우지 않음 // -> 3을 마지막 인덱스에 덮어 씌워줌 [1, 3, 4, 5, 6, 2] // 정렬된 영역 [1, 3, 4, 5] // 정렬되지 않은 영역 [6, 2] // 이런식으로 정렬 진행 코드 예시코드const insertionSort = (arr) => { // 첫번째 인덱스는 정렬되어 있는 상태로 가정. for (let i = 1; i =0; j--) { if (arr[j] > insertingData) { arr[j + 1] = arr[j] } else { break; } } arr[j + 1] = insertingData; } } const arr = [4, 2, 44, 56, 1, 0, 65]; console.log('> > > 정렬 전 > > 정렬 후 결과> > > 정렬 전 > > 정렬 후 삽입 정렬의 성능시간 복잡도$O(n^2)$장 단점이해와 구현이 간단함성능이 좋지 못함.병합 정렬(Merge Sort)조금 복잡한 정렬 알고리즘재귀로 정렬하는 알고리즘분할 정복 알고리즘에 속함배열들의 데이터를 최소한을 쪼갠 후 각 단계 별로 병합을 하면서 정렬을 진행하는 방식 코드 예시코드const mergeSort = (arr, leftIdx, rightIdx) => { // 배열의 원소가 1개일때까지 분할 if (leftIdx { let leftAreaIdx = leftIdx; // 왼쪽 영역의 시작 인덱스 let rightAreaIdx = middleIdx + 1; // 오른쪽 영역의 시작 인덱스 let tempArr = new Array(arr.length).fill(0); let tempArrIdx = leftIdx; while(leftAreaIdx middleIdx) { // 오른쪽 영역이 병합이 덜 되었다면 tempArr에 나머지 값들을 넣어 준다. for (let i = rightAreaIdx; i > > 정렬 전 > > 정렬 후 결과> > > 정렬 전 > > 정렬 후 병합 정렬의 성능merge()함수내에 흩어진 배열을 합치는 경우의 성능을 평가하나의 데이터와 하나의 데이터가 두 개로 합쳐질때 비교 연산을 두 번 진행두개의 데이터와 두개의 데이터가 네개로 합쳐질때 비교 연산을 네번 진행⇒ 각 단계를 거칠 때마다 영역의 수가 반으로 줄기 때문에 $logn$이라 할 수 있음분할된 데이터를 병합 할때는 n개의 데이터를 n번 비교하므로 $O(nlogn)$의 성능을 가짐장 단점성능이 좋음이해와 구현이 어려움퀵 정렬(Quick Sort)분할 정복 알고리즘재귀를 사용정렬하기 전 배열에 있는 데이터 하나를 피벗으로 선택피벗의 선택 기준은 다양피벗의 왼쪽에서 오른쪽으로 이동하는 데이터(leftStartIdx)와 배열의 오른쪽 끝에서 왼쪽으로 이동하는 데이터(rightStartIdx)를 설정leftStartIdx를 오른쪽으로 이동시키면서 피벗보다 큰 값을 만나면 멈춤leftStartIdx가 멈추면 rightStartIdx를 왼쪽으로 이동 시키면서 피벗보다 작은 값을 만나면 멈춤.leftStartIdx의 값과 rightStartIdx의 값을 서로 교환(swap)다시 1부터 반복반복 하던 도중 leftStartIdx가 rightStartIdx의 값보다 커지면 더이상 이동하지 않고 멈춤.피벗과 rightStartIdx의 값의 위치를 교환 해줌그러면 피벗을 기준으로 좌측의 값은 피벗보다 작은 값들이 모여있고, 우측에는 피벗의 값보다 큰 값으로 모여있음.이제 왼쪽, 오른쪽의 데이터들을 다시 처음부터 반복하여 정렬 진행.코드 예시코드const quickSort = (arr, left, right) => { if (left { // 배열의 왼쪽 값을 피벗으로 설정 let pivot = arr[left]; let leftStartIdx = left + 1; let rightStartIdx = right; while(leftStartIdx = arr[leftStartIdx]) { // pivot보다 작은 값을 만날때까지 진행 leftStartIdx++; } while (rightStartIdx >= (left + 1) && pivot { let tmp = arr[idx]; arr[idx] = arr[idx2]; arr[idx2] = tmp; } const arr = [5, 3, 7, 2, 6, 4, 9, 1, 8]; console.log('> > > 정렬 전 > > 정렬 후 결과> > > 정렬 전 > > 정렬 후 퀵 정렬의 성능피벗을 기준으로 배열을 반으로 나눔.데이터가 한개가될때까지 나눔 → $logn$해당 작업을 n개반큰 작업을 해야 하므로 $nlogn$따라서 시간 복잡도는 $\theta(nlogn)$하지만 위의 경우는 평균적인 경우피벗이 중간이 아닌 한쪽에 치우쳐 있는 경우에는 $O(n^2)$하지만 대부분은 성능이 좋은 피벗을 선택하여 최악의 경우가 발생할 확률은 극히 낮음.성능만 보면 병합 정렬이 더 좋다고 볼 수 있음.퀵정렬이 더 적은 비교와 더 적은 메모리 공간을 차지하기 때문에 더 좋은 알고리즘으로 평가됨.장 단점성능이 좋음이해와 구현이 어려움. 동적 프로그래밍재귀를 사용하면 함수가 호출되어 콜스텍의 영역을 차지하는 단점 이외에도 성능에 크게 영향을 미치는 단점이 존재피보나치 수열이 대표적 예1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, …이를 재귀 함수로 구현 하면 아래와 같다.const fibonacci = (n) => { if (n === 0 || n === 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); } console.log(fibonacci(5)); 하지만 해당 코드를 보면 중복되는 결과가 호출되는 상황이 발생한다. → 중복되는 계산으로 인해 시간이 낭비됨.→ 이를 줄이는 방식은 계산 결과를 저장하여 같은 결과를 계산할때 저장된 결과를 사용.메모이제이션(Memoization)계산하려는 데이터가 있는지 검색하고, 없으면 계산을 하고 저장.중복 계산을 하지 않아서 속도가 빠름해시 테이블을 사용.하향식 계산 방식코드 예시파보나치 수열을 메모이제이션을 활용해 구현자바스크립트의 객체를 활용코드const fibonacci = (n) => { if (n === 0 || n === 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); } const fibonacci2 = (n, memo) => { if (n === 0 || n === 1) return n; if (!memo[n]) { memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo); } return memo[n]; } console.time(); console.log(fibonacci(40)); console.timeEnd(); console.time(); console.log(fibonacci2(40, {})); console.timeEnd(); 결과102334155 default: 2.716s 102334155 default: 0.141ms 재귀 방법보다 훨씬 속도가 빠르다.성능계산하는 값이 커질수록 성능이 발휘함재귀적으로 구현하면 성능은 $O(2^n)$, 메모이제이션을 사용하면 $O(n)$의 성능을 가짐.장 단점빠른 속도메모리를 사용하는 단점타뷸레이션상향식 계산 방식으로 계산에 필요한 모든 값을 전부 계산 후 테이블에 저장코드 예시코드/** * 타뷸레이션 방식으로 피보나치 수열 구현 * @param {number} n * @returns */ const fibonacci3 = (n) => { if (n 결과102334155 default: 1.786s 102334155 default: 0.259ms 102334155 default: 0.201ms 타뷸레이션 성능적은 메모리 사용인데에도 빠른 시간을 보여줌.메모이제이션과 타뷸레이션의 비교메모이제이션을 통한 피보나치 함수는 여러 번의 함수 호출로 메모리 공간의 스택을 차지하고 메모이제이션을 위한 공간까지 차지하기 때문에 메모리를 더 많이 사용한다.타뷸레이션을 통한 피보나치 함수는 적은 메모리 사용인데도 불구하고 빠른 시간을 보인다.더 좋은 방식은?메모이제이션은 문제를 하향식으로 해결하여 복잡한 문제를 쉽게 해결할 수 있는 장점이 있다.재귀만 이용한다면 중복 계산을 하기 때문에 성능에 문제가 발생하는데, 계산 결과를 저장하는 방식으로 단점을 해결했다.그렇기 때문에 분할 정복을 해결할 때 재귀가 더 직관적이라면 메모이제이션을 이용하는 것이 유리하다.하지만 재귀가 직관적이지 않은 문제라면, 타뷸레이션을 이용해 메모리도 절약하고 속도도 빠르게 해결할 수 있다.

CS 미션 3주차

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.레지스터가장 빠른 기억 장소로 CPU내에 존재.휘발성 메모리캐시레지스터와 메인 메모리 사이에 존재하는 메모리레지스터와 메인 메모리 데이터 속도의 차이 때문에 필요한 데이터를 미리 갖고와서 저장하는 공간메인 메모리실제 운영체제와 다른 프로세스가 올라가는 공간휘발성 메모리보조 저장 장치전원이 공급되지 않아도 데이터가 지워지지 않는 비 휘발성 메모리 2. 사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?경계 레지스터CPU내에 존재하는 레지스터로 메모리 관리자는 사용자 프로세스가 경계 레지스터의 값을 벗어 났는지 확인하고, 침범했다면 사용자 프로세스를 종료 시킴.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?가변 분할 방식메모리에 연속된 공간에 할당 되기 때문에 낭비되는 공간인 내부 단편화가 없음외부 단편화가 발생고정 분할 방식구현이 간단하고 오버헤드가 적음작은 프로세스도 큰 공간에 할당 되면 내부 단편화 발생CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?스레싱HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?실행이 가능하긴 하나 일반 메모리에 파일을 저장 및 운영체제를 저장하는 방식은 비효율적이라 HDD 또는 SSD가 필요하다.파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일이 직접 삭제되는게 아닌 Free Block List에 파일의 사용 공간이 등록되고 블록은 남아 있기 때문. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬이해와 구현이 간단좋지 않은 성능O(n^2)선택 정렬이해과 우견이 간단좋지 않은 성능O(n^2)삽입 정렬이해과 우견이 간단좋지 않은 성능O(n^2)병합 정렬성능이 좋음이해와 구현이 어려움 O(nlogn)퀵 정렬성능이 좋음이해와 구현이 어려움Θ(nlogn) 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요. 메모리가 부족한 시스템에서는 메모이제이션 대신 타뷸레이션을 사용메모이제이션은 중복 계산이 발생하여 성능 및 메모리 문제가 발생하지만 타뷸레이션은 중복된 값들을 저장하고 있어 중복 실행이 방지됨.

CS 2주차 발자국

운영체제프로세스간 통신프로세스는 독립적으로 실행되지만, 다른 프로세스와 데이터를 주고 받는 경우가 존재.통신은 동일한 컴퓨터 또는 네트워크에 연결된 다른 프로세스와 통신이 가능함.한 컴퓨터 내에서 프로세스간 통신하는 방법파일 & 파이프하나의 파일을 이용해 읽고 쓰는 방법운영체제가 생성한 파이프를 이요해 데이터를 읽고 쓰는 방법쓰레드한 프로세스 내에서 쓰레드간 통신을 하는 방법.쓰레드는 코드, 데이터, 힙 영역을 공유하므로 데이터 또는 힙 영역을 통해 통신네트워크소켓 통신다른 컴퓨터에 있는 함수를 호출하는 RPC(원격 프로시저 호출)를 이용해 통신하는 방법공유 자원과 임계 구역통신을 할때 공동으로 이용하는 함수나 파일이 있는데 이를 공유 자원이라 함.공유 자원은 여러 프로세스가 공유하기 때문에 각 프로세스가 접근하는 순서에 따라 결과가 달라짐.컨텍스트 스위칭으로 시분할 처리 되기 때문에 어떤 프로세스가 먼저실행되고 나중에 실행되는지 예측이 어려움.→ 연산 결과를 예측하기 힘들고 동기화 문제가 발생임계 구역여러 프로세스가 동시에 사용하면 안되는 영역을 임계 구역(Critical Section)이라 함.공유자원을 서로 사용하기 위해 경쟁하는 것은 경쟁 조건(Race Condtion)이라 함.임계 구역을 해결 하기 위해서는 상호 배제 매커니즘이 필요.상호 배제의 요구사항임계구역엔 동시에 하나의 프로세스만 접근한다.여러 요청에도 하나의 프로세스의 접근만 허용한다.임계 구역에 들어간 프로세스는 빠르게 나와야 한다.세마포어정의운영체제는 자원을 사용할 수 있는 열쇠(세마포어)를 설정해서 공유 자원 요청이 온 프로세스에게 열쇠를 전달.열쇠를 전달받은 프로세스는 공유 자원을 사용다른 프로세스가 공유자원을 요청이전의 프로세스가 열쇠를 반납할때까지 대기큐에서 대기.공유 자원을 다 사용하고 난 후 운영체제에 열쇠를 반납.운영체제는 대기 큐에서 기다리고 있는 프로세스에세 열쇠를 전달 하여 공유 자원 사용 허락.단점세마포어 호출이 꼬일 경우 원하는 대로 동작이 되지 않을 수 있다.모니터세마포어의 단점을 해결한 상호배제 메커니즘.운영체제에서 처리하는 것이 아닌 프로그래밍 언어 차원에서 지원하는 방법자바 예시public class Health { private int health = 100; synchronized void increase(int amout) { health += amout; } synchronized void decrease(int amout) { health -= amout; } } synchronized 키워드가 붙어 있는 함수는 동시에 여러 프로세스에서 실행 시킬 수 없음.상호배제가 완벽히 이루어짐.교착상태(데드락)여러 프로세스가 서로 다른 프로세스의 작업을 끝나길 기다리다가 아무도 작업을 진행하지 못하는 상태.발생 이유는 공유자원.교착상태 필요조건아래 조건들이 모두 만족하면 교착상태가 발생.하나라도 만족하지 않으면 교착 상태가 발생하지 않음.상호배제어떤 프로세스가 한 리소스를 점유 했다면 그 리소스는 다른 프로세스에게 공유가 되면 안됨.비선점리소스를 갖고 있는 프로세스 한테서 다른 프로세스가 리소스를 빼앗을 수 없다.점유와 대기리소스A를 갖고 있는 프로세스가 리소스B를 원하는 상태원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있는 상태.교착 상태 해결교착 상태 회피(Deadlock avoidance)프로세스에게 자원을 할당할때 교착 상태가 발생하는 상황을 파악해서 교착상태가 발생하지 않는 수준의 자원을 할당.전체 자원의 수와 할당된 자원이 수로 안정상태와 불안정 상태로 나눔.운영체제는 최대한 안정상태를 유지하려고 자원을 할당.불안정 상태에 있다하더라고 무조건 교착 상태에 빠지는게 아니라 교착 상태에 빠질 가능성이 높아짐.은행원 알고리즘(Banker’s Algorithm)은행이 대출해주는 방식의 알고리즘돈을 빌려줄때 은행의 여윳돈과 사업가들에게 빌려준 돈들을 보고 대출 가능한 상황인지 보고 빌려주는 알고리즘.운영체제는 프로세스에게 자원을 할당하기 전에 자신이 가지고 있는 자원의 수를 파악→ 시스테의 총 자원프로세스들은 각자 자기가 필요한 자원의 최대 수를 운영체제에 알려줌→ 최대 요구 자원 ⇒ 은행원 알고리즘은 교착 상태를 피하는 좋은 알고리즘이지만 비용이 비싸고 비효율적.교착 상태의 발생은 허용하지만, 교착 상태가 발생시 해결 방법을 연구.교착 상태 검출 방법 고민.가벼운 교착 상태 검출프로세스가 일정시간 동안 작업을 진행하지 않는다면 교착 상태에 발생했다고 감지하고 교착 상태를 해결.해결 방법은 일정 시간마다 체크포인트를 만들어 작업을 저장하고 교착 상태가 발생하면 마지막으로 저장한 체크포인트로 롤백 하는 방식.무거운 교착 상태 검출자원 할당 그래프를 사용하여 현재 운영체제에서 프로세스가 어떤 자원을 사용하는지 지켜보고 교착 상태가 발생하면 해결.자원 할당 그래프를 통해 순환 구조가 발생하면 교착 상태로 판단.교착 상태를 검출하면 교착 상태를 일으킨 프로세스를 강제 종료하고, 다시 실행할때 체크포엔트로 롤백을 진행.운영체제가 지속적으로 자원할당 그래프를 유지하고 검사해야 하기 때문에 오버헤드가 발생.가벼운 교착 상태 검출에서 발생하는 억울하게 종료되는 프로세스는 발생되지 않음.메모리 종류레지스터 - 캐시 - 메인 메모리(RAM) - 보조 저장 장치(HDD, SSD)좌 → 우 갈수록 속도가 느려지고 용량이 커지며 가격이 저렴해진다.레지스터가장 빠른 기억 장소로 CPU내에서 존재컴퓨터 전원이 꺼지면 데이터가 사라지기 때문에 휘발성 메모리라고 부름.32bit, 64bit는 레지스터의 크기.CPU는 계산을 할 때 메인 메모리에 있는 값을 레지스터로 갖고와서 계산하고 계산 결과를 메인 메모리에 다시 저장.캐시레지스터와 메인 메모리 사이에 존재하는 메모리.레지스터와 메인 메모리 데이터 속도의 차이 때문에 필요한 데이터를 미리 갖고와서 저장하는 공간.속도에 따라 L1, L2, … 캐시가 존재.메인 메모리실제 운영체제와 다른 프로세스가 올라가는 공간전원이 공급되지 않으면 데이터가 지워지기 때문에 휘발성 메모리.하드디스크나 SSD 보다 속도는 빠르지만 가격이 비싸기 때문에 실행중인 프로그램만 올라감.보조 저장 장치전원이 공급되지 않아도 데이터가 지워지지 않는 비 휘발성 메모리.메모리와 주소메인 메모리에 대한 설명오늘 날의 컴퓨터는 폰 노이만 구조.폰 노이만 컴퓨터는 모든 프로그램을 메모리에 올려 실행.유니 프로그래밍 환경에서는 하나의 프로세스만 메모리에 올라가 메모리 관리가 쉬었으나, 멀티 프로그래밍 환경에서는 여러개의 프로세스가 올라가 실행되어 복잡하고 어려워짐.운영체제는 메모리를 관리하기 위해 1바이트(8bit) 단위로 나누고 숫자를 할당.→ 주소32bit, 64bit CPU32bit CPU는 레지스터 크기가 32bit, CPU가 처리하는 ALU(산술 논리 연산 장치)도 32bit, 데이터가 이동하는 버스도 32bit. 또한 CPU가 다룰 수 있는 메모리도 2^32으로 4GB.64bit CPU는 레지스터 크기가 64bit, CPU가 처리하는 ALU(산술 논리 연산 장치)도 64bit, 데이터가 이동하는 버스도 64bit. 또한 CPU가 다룰 수 있는 메모리도 2^64으로 거의 무한대에 가까움⇒ 64bit가 32bit보다 한번에 처리할 수 있는 양이 많아 속도가 빠름.물리 주소와 논리 주소메모리를 컴퓨터에 연결하면 0x0번지부터 시작하는 주소 공간이 존재→ 물리 주소 공간.사용자 관점에서 바라보는 주소 공간→ 논리 주소 공간사용자는 물리 주소를 몰라도 논리 주소를 알면 물리 주소에 접근할 수 있음.메모리에는 운영체제와 다 수의 프로세스가 올라옴.운영체제를 위한 공간은 따로 만들어 사용자 프로세스가 운영체제에 침범 할 수 없도록 운영체제 공간과 사용자 프로세스 공간을 나누는 경계 레지스터를 만듦.경계 레지스터는 CPU내에서 존재하는 레지스터로 메모리 관리자는 사용자 프로세스가 경계 레지스터의 값을 벗어 났는지 확인하고, 침범했다면 사용자 프로세스를 종료 시킴.절대 주소와 상대 주소상대 주소개발자가 프로그램 개발 시 주소는 신경 쓰지 않고 개발.이는 컴파일러가 메모리 0번지에서 실행한다고 가정.→ 상대 주소(논리 주소 공간)절대 주소실제 프로그램이 올라간 주소→ 절대 주소(물리 주소 공간)사용자가 0x100번지 데이터를 요청하면, CPU도 0x100번지(상대 주소, 논리 주소)의 데이터를 요청. 그리고 메모리 관리자는 CPU가 요청한 0x100번지의 주소와 재배치 레지스터에 있는 프로그램이 올라간 주소(e.g. 0x4000)의 값을 더해 0x4100번지(절대 주소, 물리 주소)에 접근해서 데이터를 가져옴.재배치 레지스터에는 프로그램이 시작된 주소가 저장 되어 있음.메모리 관리자 덕분에 사용자는 모든 메모리는 0x0번지에 시작한다고 가정할 수 있고, 시작 영역이 바뀌더라도 재배치 레지스터만 변경해 하면 되므로 굉장히 유연.메모리 할당 방식메모리 오버레이(Memory overlay)메모리 보다 더 큰 프로그램을 실행 시키는 방법.큰 프로그램을 잘라서 당장 실행 시켜야 할 부분만 메모리에 올리고 나머지 부분은 하드 디스크에 저장(하드디스크의 스왑 영역)하는 방식.스왑스왑 영역에 있는 데이터 일부를 메모리에 가져오고, 메모리에 있는 데이터를 스왑 영역으로 옮기는 것사용자는 실행 중인 프로그램만큼 메모리를 사용한다고 느끼지만 실제는 그것보다 적으므로 메모리가 큰 컴퓨터보다는 느리게 동작.유니 프로그래밍에서 사용하는 방식.가변 분할 방식(세그멘테이션)프로세스의 크기에 따라 메모리를 나누는 방식.한 프로세스가 메모리에 연속된 공간에 할당되기 때문에 연속 메모리 할당 이라고 함. 고정 분할 방식(페이징)프로세스의 크기와 상관없이 메모리를 할당.메모리 분할 크기에 따라 프로세스들을 해당 크기에 맞게 나눠서 할당하는 방식.한 프로세스가 여러개로 쪼개져서 메모리에 할당 되기 때문에 비 연속 메모리 할당 이라고 함. 가변 분할과 고정 분할 방식의 장단점가변 분할 방식장점메모리에 연속된 공간에 할당 되기 때문에 낭비되는 공간인 내부 단편화가 없다.단점외부 단편화 발생중간에 다른 프로세스들이 종료되고 새로운 프로세스가 실행되는 경우 새로 시작하는 프로세스가 기존 종료된 프로세스들의 메모리 합보다 같거나 작지만, 연속된 공간에 할당 할 수 없는 상황. 해결방법조각모음.조각모음을 하려면 현재 메모리에서 실행되고 있는 프로세스들의 작업을 일시 중지해야하고 메모리 공간을 이동하는 작업을 해야 하기 때문에 오버헤드가 발생.고정 분할 방식장점구현이 간단하고 오버헤드가 적음.단점작은 프로세스도 큰 공간에 할당 되면 내부 단편화 발생할당된 공가보다 작은 크기의 프로세스를 할당할 경우 낭비 공간이 발생.해결방법은 없어서 분할되는 크기를 조절해서 내부 단편화를 최소화.버디 시스템가변분할 방식과 고정 분할 방식을 혼합해 단점을 최소화 한 방법2의 승수로 메모리를 분할해 메모리를 할당하는 방식.예시메모리 크기가 2^11승인 2024b가 존재.이때 크기가 500b인 프로세스가 메모리 할당을 원함.2의 승수로 500b 작은 값을 만날때까지 메모리 영역을 나눔1024 / 1024 → 1024 / 512 / 512 → 1024 / 512 / 256 / 256즉, 1024b / 512b / 256b / 256b 4가지 영역이 생성256b에는 500b의 프로세스를 할당할 수 없으니 512b 영역에 프로세스를 할당.12b가 낭비되는 내부 단편화 발생.내부 단편활가 발생되긴 하지만 많은 공간이 발생하지는 않음.해당 프로세스가 종료되어 메모리 공간 할당이 해제 되어도 근접한 메모리 공간을 합치기 쉬움2의 승수로 동일할게 나누어서 반대로 조립만 하면 큰 공간이 만들어져서 조각 모음보다 간단함1024 / 512 / 512 → 1024 / 1024 → 2024자료구조와 알고리즘재귀재귀어떠한 것을 정의할때 자기 자신을 참조하는 것재귀 함수예시const myFunction = (number) => { console.log(number); myFunction(number + 1); } myFunction(0); 이 함수는 실행하면 오류가 발생한다.node:internal/util/inspect:765 function formatValue(ctx, value, recurseTimes, typedArray) { ^ RangeError: Maximum call stack size exceeded 탈출 조건이 없어 계속 실행하다가 메모리가 부족해서 오류가 발생.기저 조건(탈출 조건)있는 재귀함수예시const myFunction = (number) => { if (number > 10) return; console.log(number); myFunction(number + 1); } myFunction(0); 콜 스택함수가 호출되면서 올라가는 메모리 영역으로 스택이라고도 부름.콜스택은 스택의 특성처럼 FILO(First In Last Out) 특성을 갖고 있음.함수를 호출하면 콜스택에 올라가고, 함수가 종료되면 콜스택에서 제거됨.재귀적으로 생각하기패턴1 - 단순한 반복 실행단순한 반복 실행을 재귀로 구현하면 반복문으로 구현했을 때보다 크게 이점은 없다.콜스택의 공간을 많이 차지해 반복문보다 좋지 않음.패턴2 - 하위 문제의 결과를 기반으로 현재 문제를 계산팩토리얼 함수를 예시로 설명예를 들어 5!의 계산을 구할때 5 * 4! 계산 방식으로 구하는 방법.하위문제: 4!현재 문제: 5!팩토리얼을 반복문으로도 구현이 가능하지만, 현재 문제를 해결하는데 하위 문제가 쓰이는 것이 중요한 포인트반복문은 상향식 계산.재귀 함수로 구현하면 하향식 계산.재귀를 사용한다고 무조건 하향식 계산은 아님.상향식 계산도 가능.재귀 함수의 위력은 하향식 방향 계산에서 발휘.⇒ 재귀를 사용하는 이유예시배열의 모든 원소의 합.const sumArray = (arr) => { if (arr.length === 1) return arr[0]; return sumArray(arr.slice(0, -1)) + arr[arr.length - 1]; } let arr = [1, 2, 3, 4, 5]; const res = sumArray(arr); console.log(res); 문자열의 길이 구하기const strLength = (arr) => { if (!arr[0]) return 0; return strLength(arr.slice(0, -1)) + 1 } const str = 'abcde'; const res = strLength(str); console.log(res); 지수 함수const power = (x, n) => { if (n === 0) return 1; return power(x, n - 1) * x; } console.log(power(2, 5)); // 2^5 계산 하노이 탑하향식 계산 방식의 좋은 예정렬배열에 무작위로 섞인 숫자를 정렬하는 방법.버블 정렬(Bubble Sort)가장 쉽게 생각할 수 있는 정렬중 하나구현하는 방법은 쉬우나 성능은 좋진 않다.예시 코드코드const bubbleSort = (arr) => { for (let i = 0; i = arr[j + 1]) { let tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } const arr = [4, 2, 3, 1]; console.log('> > > 정렬 전 > > 정렬 후 결과> > > 정렬 전 > > 정렬 후 버블 정렬의 성능버블 정렬의 성능을 구하면 등차수열의 합과 같은 경우의 수가 나타남$\frac{n^2 - n}{2}$시간 복잡도는 $O(n^2)$$n$이 증가할때마다 계산량은 엄청나게 증가하게 됨.성능이 중요한 시스템을 만든다면 버블 정렬 방식은 사용하기 힘듦.장단점이해와 구현이 간단함.성능이 좋지 않음.선택 정렬(Selection Sort)버블 정렬처럼 이해와 구현이 간단.아쉬운 성능배열의 정렬되지 않은 영역의 첫 번째 원소를 시작으로 마지막 원소까지 비교 후 가장 작은 값을 첫 번째 원소로 가져옴.코드 예시코드const selectionSort = (arr) => { for (let i = 0; i > > 정렬 전 > > 정렬 후 결과> > > 정렬 전 > > 정렬 후 선택 정렬의 성능버블 정렬과 마찬가지로 $\frac{n^2 - n}{2}$ 나타남.성능도 마찬가지로 $O(n^2)$ 시간 복잡도를 갖고 있음.장 단점이해와 구현이 간단함.성능이 좋지 않음.

CS 2주차 미션

운영체제 FIFO 스케줄링의 장단점이 뭔가요? 장점단순하고 직관적단점한 프로세스가 완전히 끝나야 다음 프로세스가 실행됨.때문에 실행시간이 짧고 늦게 도착한 프로세스가 실행시간이 길고 빨리 도착한 프로세스의 작업을 기다려야함. SJF를 사용하기 여러운 이유가 뭔가요? 어떤 프로세스가 얼마나 실행 될지 예측이 힘듦.BurstTime이 긴 프로세스는 아주 오랫동안 실행 되지 않을 수 있음. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?컥텍스트 스위칭이 너무 자주 발생함.프로세스의 처리 양보다 컨텍스트 스위칭을 처리하는 양이커져 오버헤드가 너무 커지는 상황이 발생. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU를 실행하는 프로세스가 스스로 CPU를 반납하면 CPU 사용량이 적음I/O Bound Process 가능성이 높음.CPU를 사용하는 프로세스가 타임 슬라이스 크기를 오버해서 강제로 Cpu를 뺏기는 상황CPU Bound Process 가능성이 높음. 공유자원이란무엇인가요?통신을 할 때 공동으로 이루는 함수나 파일을 공유자원이라고 함. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야할까요? 상호 배제어떤 프로세스가 한 리로스를 점유 했다면 그 리소스는 다른 프로세스에게 공유가 되면 안됨.비선점리소스를 갖고 있는 프로세스 한테서 다른 프로세스가 리소스를 빼앗을 순 없음.점유와 대기리소스A를 갖고 있는 프로세스가 리소스 B를 원하는 상태원형 대기점유와 대기를 하는 프로세스들의 관계가 원형을 이루고 있는 상태. 자료구조와 알고리즘 재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?콜 스택에 계속해서 함수가 생성되어 실행되어 결국 메모르가 부족한 오류가 발생하게 됨. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ // 재귀 로직 if (n == 0) return 0; return (n%2 != 0 ? n : 0) + sumOdd(n - 1) } console.log(sumOdd(10)) // 25 다음 코드는 매개변수로 주어진 파일 경로(.는 현재 디렉토리)에 있는 하위 모든 파일과 디렉토리를 출력하는 코드입니다. 다음 코드를 재귀 함수를 이용하는 코드로 변경해보세요.import fs from "fs"; import path from "path"; function traverseDirectory(directory) { const files = fs.readdirSync(directory); for (const file of files) { const filePath = path.join(directory, file); const fileStatus = fs.statSync(filePath); if (fileStatus.isDirectory()) { if (filePath.includes("git")) continue; // 특정 디렉토리 제외 console.log("디렉토리:", filePath); traverseDirectory(filePath); // 재귀 호출 } else { console.log("파일:", filePath); } } } traverseDirectory("."); // 현재 경로의 모든 하위 경로의 파일, 디렉토리 출력

CS 1주차 미션.

운영체제 while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }위 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?폴링방식은 주기적으로 확인하기때문에 효율이 좋지 않아 이를 보완한 인터럽트방식으로 해결.인터럽트 방식은 특정 이벤트가 발생하면 cpu에거 전달하여 cpu는 ISR을 실행시켜 작업을 완료하는 방식.프로그램과 프로세스가 어떻게 다른가요?프로그램: 하드 디스크등 정장장치에 저장된 명령문의 집합체프로세스: 실행중인 프로그램. 저장장치에 저장되어 있는 프로그램이 메모리에 올라가 있는 상태. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요? 멀티 프로그래밍: 메모리에 여러개의 프로세스를 올려서 실행하는 방식멀티 프로세싱: CPU를 한개가 아닌 여러개를 이용(멀티 프로세서)하여 작업을 처리하는 방식 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?프로세스의 정보를 갖고있는 PCB를 만들고 저장. 하고 프로세스들을 운영체제에서 cpu 스케쥴링을 통해 컨텍스트 스위칭이란 뭔가요?프로세스를 실행하는 중에 다른 프로세스를 실행하기 위해 실행중인 프로세스의 상태를 저장하고 다른 프로레스의 상태값으로 교체하는 작업.자료구조와 알고리즘 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요. 학생 정보를 저장하고 열람하기 위한 자료구조는 HashTable을 선택.HashTable은 빠른 데이터 읽기와 삽입, 삭제의 장점을 갖고 있어서 학생 정보를 읽어들이거나 추가, 삭제할때 용이하기 때문.여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.고객의 주문을 받고 주문이 들어온 순서대로 처리하기 위한 자료구조는 큐를 선택. 자료구조중 큐는 FIFO 구조로 처리되기 때문에 개발하려는 프로그램의 요구사항을 만족하는 자료구조이기 때문. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요. 변경 코드class Stack { constructor() { this.list = new LinkedList(); } push(data) { // this.list.insertAt(0, data); this.list.insertLast(data); } pop() { try { // return this.list.deleteAt(0); return this.list.deleteLast(); } catch (err) { return null; } } ... }해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용예시: name1 = "이운재";name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력class HashTable { // ... hashFunction(name) { // 해시 함수. 0~9의 숫자로 계산 return name.charCodeAt() % 10; } } // 테스트 코드 const hashTable = new HashTable(); hashTable.set('이운재', 1); hashTable.set('최진철', 2); hashTable.set('홍명보', 20); hashTable.set('유상철', 6); hashTable.set('송종국', 22); hashTable.set('박지성', 21); hashTable.set('김남일', 5); hashTable.set('이영표', 10); hashTable.set('최태욱', 8); hashTable.set('설기현', 9); hashTable.set('이천수', 14); console.log('1:: ', hashTable.get('이운재')); // 1 hashTable.remove('이운재'); console.log('1:: ', hashTable.get('이운재')); // null console.log('21:: ', hashTable.get('박지성')); // 21