워밍업 클럽 CS 3주차 발자국 : 미션

운영체제메모리의 종류는 어떤것들이 있나요? 각 메모리의 특징도 함께 적어주세요.주기억장치 (RAM):특징: 휘발성 메모리로, 전원이 꺼지면 데이터가 사라집니다. 빠른 접근 속도를 가지며, 운영체제와 애플리케이션이 실행될 때 사용됩니다.보조기억장치 (HDD, SSD 등):특징: 비휘발성 메모리로, 전원이 꺼져도 데이터가 유지됩니다. HDD는 기계적인 구조로 상대적으로 느리지만 큰 용량을 제공하고, SSD는 전자적인 구조로 빠른 속도를 제공합니다.캐시 메모리:특징: CPU와 RAM 사이에 위치하여 자주 사용되는 데이터를 저장합니다. 빠른 접근 속도를 제공하여 CPU의 성능을 향상시키는 역할을 합니다.ROM (읽기 전용 메모리):특징: 비휘발성 메모리로, 주로 부팅 프로그램이나 펌웨어가 저장됩니다. 일반 사용자가 데이터를 수정할 수 없습니다.가상 메모리:특징: 물리적인 메모리 용량보다 큰 메모리를 사용할 수 있도록 해주는 기술로, 하드디스크의 일부를 메모리처럼 사용합니다.사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 어떤 레지스터일까요?사용자 프로세스가 메모리의 운영체제 영역에 침범하지 못하도록 만든 레지스터는 경계 레지스터(Bound Register)입니다.설명: 경계 레지스터는 프로세스가 접근할 수 있는 메모리의 범위를 정의합니다. 이 레지스터는 프로세스가 사용 가능한 메모리 영역의 최댓값을 설정하여, 프로세스가 해당 범위를 벗어나 메모리의 운영체제 영역이나 다른 프로세스의 영역에 접근하는 것을 방지합니다.작동 방식:프로세스가 메모리 접근을 시도할 때, CPU는 해당 주소가 경계 레지스터에 설정된 범위 내에 있는지 확인합니다.만약 접근하려는 주소가 경계 레지스터의 한계를 초과하면, CPU는 메모리 접근을 차단하고 오류를 발생시킵니다. 이를 통해 운영체제는 메모리의 보호 및 안정성을 유지할 수 있습니다.이러한 방식으로 경계 레지스터는 운영체제와 사용자 프로세스 간의 안전한 메모리 관리를 도와줍니다.메모리 할당 방식에서 가변 분할 방식과 고정 분할 방식의 장단점은 뭔가요?고정 분할 방식:장점: 관리가 간편하고, 메모리 할당 속도가 빠릅니다.단점: 내부 단편화가 발생할 수 있으며, 메모리의 유효 활용도가 떨어질 수 있습니다.가변 분할 방식:장점: 메모리를 더 효율적으로 사용할 수 있으며, 내부 단편화가 줄어듭니다.단점: 관리가 복잡하고, 외부 단편화 문제가 발생할 수 있습니다.CPU 사용률을 올리기 위해 멀티프로그래밍을 올렸지만 스왑이 더 많이 이루어져 CPU 사용률이 0%에 가까워 지는 것을 뭐라고 할까요?CPU 스케줄링의 목표는 CPU 사용률을 높이는 것입니다. 이를 위해 멀티 프로그래밍을 통해 동시에 실행되는 프로세스 수를 늘립니다. 하지만 프로세스 수가 많아지면 물리 메모리가 부족해져 일부 프로세스는 스왑 영역에 저장되고, 이로 인해 페이지 폴트가 빈번하게 발생합니다. 결국 스왑 작업이 CPU 작업 시간을 초과하게 되어 CPU 사용률이 떨어지고, 이 현상을 스레싱(thrashing)이라고 합니다. HDD나 SSD는 컴퓨터를 실행시키는데 꼭 필요한 걸까요?HDD나 SSD는 컴퓨터를 실행하는 데 필수적이지는 않지만, 데이터와 프로그램을 저장하는 데 중요한 역할을 합니다. 일부 시스템은 RAM을 활용한 메모리 부팅이 가능하여, 저장 장치 없이도 작동할 수 있는 임베디드 시스템이 존재합니다. 그러나 일반적으로 컴퓨터 운영에 필요한 데이터를 지속적으로 저장하기 위해 HDD나 SSD와 같은 저장 장치가 필요합니다. 파일을 삭제해도 포렌식으로 파일을 복구할 수 있는 이유가 무엇일까요?파일을 삭제하더라도 포렌식으로 복구할 수 있는 이유는, 파일 시스템이 삭제된 파일의 모든 정보를 즉시 지우지 않기 때문입니다. 파일이 삭제될 때, 파일 시스템은 해당 파일의 헤더를 파일 테이블에서 삭제하고 빈 공간을 관리하는 프리 블록 리스트에 추가합니다. 이 과정에서 파일의 데이터는 여전히 디스크에 남아 있습니다. 사용자는 파일이 삭제된 것처럼 느끼지만, 실제로는 데이터가 그대로 존재하기 때문에, 전문적인 도구와 기술을 사용하면 삭제된 파일의 데이터를 복구할 수 있습니다. 자료구조와 알고리즘지금까지 배운 5개의 정렬 알고리즘의 장단점과 시간 복잡도를 적어주세요.버블 정렬장점: 구현이 간단하고 직관적이며, 이미 정렬된 경우 최선의 성능을 보인다.단점: 효율성이 떨어지며, 평균 및 최악의 경우 시간 복잡도가 O(n²)로 비효율적이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)선택 정렬장점: 구현이 간단하고, 추가적인 메모리 공간을 사용하지 않는다.단점: 비효율적이며, 항상 O(n²) 시간 복잡도를 가진다.시간 복잡도:최선: O(n²)평균: O(n²)최악: O(n²)삽입 정렬장점: 작은 데이터 집합에 대해 빠르게 동작하며, 안정적인 정렬 알고리즘이다.단점: 큰 데이터 집합에 대해서는 O(n²)로 비효율적이다.시간 복잡도:최선: O(n)평균: O(n²)최악: O(n²)병합 정렬장점: 안정적인 정렬 방식이며, O(n log n)의 시간 복잡도로 효율적이다.단점: 추가적인 메모리 공간이 필요하여, 공간 복잡도가 O(n)이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n log n)퀵 정렬장점: 평균적으로 O(n log n)의 시간 복잡도를 가지고, 메모리 사용이 효율적이다.단점: 최악의 경우 O(n²)로 성능이 떨어질 수 있으며, 불안정한 정렬이다.시간 복잡도:최선: O(n log n)평균: O(n log n)최악: O(n²) 메모리가 부족한 시스템에서 어떤 문제를 해결하는데 재귀로 쉽게 구현이 가능할 것 같습니다. 여러분이라면 메모이제이션과 타뷸레이션 중 어떤 걸 이용하실 건가요? 이유를 함께 적어주세요.메모리가 부족한 시스템에서는 타뷸레이션을 사용할 것입니다. 타뷸레이션은 하향식 접근 방식으로, 모든 가능한 상태를 테이블에 저장하여 나중에 재사용할 수 있게 합니다. 메모리 사용량이 제한된 상황에서, 문제를 작은 하위 문제로 나누어 해결하기 때문에 최적의 공간 효율성을 유지할 수 있습니다.반면, 메모이제이션은 재귀적인 방식으로 구현되어, 메모리가 부족한 시스템에서는 스택 오버플로우가 발생할 가능성이 높아질 수 있습니다. 따라서 타뷸레이션은 메모리를 더 효율적으로 활용하면서도 문제를 해결하는 데 유리한 선택이 될 것입니다.

워밍업 클럽 CS 3주차 발자국 : 운영체제

가상 메모리가상 메모리 개요가상 메모리는 부족한 물리 메모리를 효율적으로 사용하기 위한 기술로, 메모리 관리자가 가상 주소를 물리 주소에 매핑하여, 실제 물리 메모리보다 더 큰 메모리 공간을 사용할 수 있게 합니다. 이를 통해 각 프로세스는 독립적인 메모리 공간을 가지며, 안정성과 보안을 높입니다. 개발자는 물리 메모리의 크기나 위치에 신경 쓰지 않고, 0x0 번지에서 시작한다고 생각하며 프로그래밍할 수 있습니다. 실제 메모리 접근은 메모리 관리자가 처리하며, 프로세스는 물리 메모리에 직접 접근하지 않습니다. 가상 메모리의 크기는 CPU의 비트 수에 따라 결정됩니다. 예를 들어, 32비트 CPU는 4GB의 가상 메모리 공간을 제공합니다. 물리 메모리가 부족할 때는, 일부 내용을 하드디스크의 스왑 영역으로 옮겨 필요한 경우 다시 가져와 실행합니다. 이 과정을 동적 주소 변환이라 부르며, 이를 통해 물리 메모리 부족 문제를 해결할 수 있습니다. 메모리 관리는 가상 주소를 물리 주소로 변환하고, 프로세스의 메모리 배치, 스왑 영역 처리 등 복잡한 과정을 수행합니다. 물리 메모리 0번지는 운영체제에 할당되며, 프로세스는 사용할 수 없습니다. 가상 메모리 시스템에서는 메모리를 고정 크기로 나누어 프로세스에 할당하는 페이징과, 가변 크기로 할당하는 세그멘테이션 방식을 사용합니다. 페이징은 내부 단편화, 세그멘테이션은 외부 단편화의 단점이 있으며, 이를 보완한 세그멘테이션-페이징 혼용 기법이 사용됩니다. 가상 주소는 메모리나 스왑 영역에 위치하며, 메모리 관리자는 가상 주소와 물리 주소를 1대1로 매핑해 관리합니다 배치 정책세그멘테이션세그멘테이션은 가변 분할 방식을 사용하여 메모리를 분할하는 기법입니다. 프로그램은 함수나 모듈 등으로 나뉘며, 각각의 세그먼트가 생성됩니다. 예를 들어, 메인 코드, 전역 데이터, 힙, 스택 등의 영역이 각각 독립적인 세그먼트로 구성됩니다. 이 세그먼트들은 물리 메모리에서 서로 인접하지 않아도 되지만, 프로세스는 이를 인접한 것처럼 인식합니다. 프로세스와 CPU가 바라보는 논리 주소는 실제 메모리 주소와 다르며, 이를 물리 주소로 변환하는 역할은 메모리 관리자(MMU)가 수행합니다. MMU는 세그멘테이션 테이블을 사용하여 논리 주소를 물리 주소로 변환합니다. 이 테이블에는 베이스 주소(Base Address)와 바운드 주소(Bound Address) 정보가 포함되어 있습니다. 논리 주소가 주어지면, 메모리 관리자는 해당 논리 주소가 속하는 세그먼트를 찾고, 세그멘테이션 테이블에서 해당 세그먼트의 베이스와 바운드 주소를 참조하여 물리 주소를 계산합니다. 논리 주소가 바운드 주소 범위 내에 있으면 베이스 주소와 더해져 물리 주소가 계산되며, 범위를 초과하면 메모리 침범 오류를 발생시켜 해당 프로세스를 종료합니다. 예시 1: CPU가 세그먼트 1번의 논리 주소 0x632로 접근메모리 관리자가 세그먼트 1번을 확인세그멘테이션 테이블에서 1번 세그먼트의 베이스 주소(5200)를 찾음논리 주소(632)와 바운드 주소(1000)를 비교하여 범위 내임을 확인논리 주소와 베이스 주소를 더해 물리 주소 5832로 변환 예시 2: CPU가 세그먼트 3번의 논리 주소 750으로 접근메모리 관리자가 세그먼트 3번을 확인논리 주소(750)가 바운드 주소(500)를 초과하므로 메모리 침범 오류 발생프로세스가 종료됨 세그멘테이션의 장점은 메모리를 가변적으로 나눌 수 있어 코드, 데이터, 스택, 힙 영역을 모듈로 처리할 수 있고, 각 영역에 대한 접근 보호와 공유가 용이하다는 점입니다. 반면, 단점은 가변 분할 방식에서 발생하는 외부 단편화입니다. 페이징페이징은 메모리 관리를 위한 고정 분할 방식으로, 외부 단편화 문제를 해결하기 위해 고안되었습니다. 페이징에서는 메모리를 일정한 크기의 페이지로 나누어 할당합니다. 모든 페이지의 크기가 동일하기 때문에 관리가 용이하며, 외부 단편화가 발생하지 않습니다. 대신, 페이지 크기보다 작은 데이터를 저장할 때는 내부 단편화가 발생할 수 있습니다. 논리주소와 물리주소논리주소공간: 사용자와 프로세스가 바라보는 주소 공간물리주소공간: 실제 메모리에서 사용되는 주소 공간논리주소공간과 물리주소공간은 일정한 크기의 페이지와 프레임으로 나뉘며, 두 공간은 매칭됩니다. 주소 변환 과정페이징에서도 메모리 관리자는 페이지 테이블을 사용해 논리주소를 물리주소로 변환합니다. 논리주소가 전달되면, 메모리 관리자는 해당 논리주소가 몇 번 페이지에 속하는지 확인하고, 페이지 번호와 오프셋을 이용해 물리주소를 계산합니다.논리주소에서 페이지 번호를 추출: 페이지 테이블의 인덱스 역할해당 인덱스를 참조해 프레임 번호를 가져옴오프셋을 더해 최종 물리주소로 변환페이징에서 페이지 테이블에 "invalid"로 표시된 페이지는 스왑 영역(하드디스크)에 저장되어 있다는 의미입니다.또한, 컨텍스트 스위칭 시, 운영체제는 페이지 테이블을 해당 프로세스에 맞게 업데이트해야 합니다. 32비트 CPU 주소 변환 예시가상 메모리의 크기는 약 4GB (2^32 바이트)가상 메모리를 16MB(2^24 바이트) 페이지로 나누면, 24비트는 페이지 크기, 나머지 8비트는 페이지 번호를 나타냅니다. 즉, 총 256개의 페이지가 존재하게 됩니다.물리 메모리는 가상 메모리와 동일한 크기로 페이지로 나뉘지만, 물리 주소 공간이 더 작아도 문제가 없습니다. 부족한 메모리는 스왑 처리로 해결되기 때문입니다. 주소 변환 예시 1: 논리주소 1000번지페이지 번호: 1000 / 16777216 = 0오프셋: 1000 % 16777216 = 1000페이지 테이블의 0번 인덱스를 참조해 프레임 3을 가져오고, 오프셋을 더해 물리주소를 구함.주소 변환 예시 2: 논리주소 31554432번지페이지 번호: 31554432 / 16777216 = 1오프셋: 31554432 % 16777216 = 14777216페이지 테이블의 1번 인덱스를 참조해 프레임 1을 찾아 물리주소로 변환. 페이징과 세그멘테이션의 차이페이지 크기: 페이징은 고정된 크기의 페이지를 사용하며, 세그멘테이션은 프로세스마다 다른 크기의 세그먼트를 가짐.단편화: 페이징에서는 내부 단편화가 발생하고, 세그멘테이션에서는 외부 단편화가 발생합니다.메모리 접근 방식: 세그멘테이션은 코드, 데이터, 스택, 힙 등 논리적 영역에 맞춰 나누지만, 페이징은 고정된 크기의 페이지로 나누기 때문에 특정 영역을 떼어내서 공유하거나 권한을 부여하기 어렵습니다. 페이징의 한계페이징에서 가장 신경 써야 하는 점은 페이지 테이블의 크기입니다. 각 프로세스는 고유한 페이지 테이블을 가지며, 프로세스 수가 많아질수록 페이지 테이블이 차지하는 메모리 공간도 증가합니다. 메모리 관리자 역시 물리 메모리 내의 운영체제 영역에 페이지 테이블을 저장하기 때문에, 페이지 테이블이 커지면 사용자 영역의 메모리가 부족해질 수 있습니다.따라서 페이지 테이블의 크기를 적절하게 유지하는 것이 매우 중요합니다. 페이지드 세그멘테이션페이지드 세그멘테이션은 세그멘테이션과 페이징의 장점을 결합한 메모리 관리 방식입니다. 세그멘테이션은 영역별로 메모리를 관리하고, 페이징은 메모리를 일정 크기로 나누어 관리 효율성을 높입니다. 이 방식은 두 기법의 이점을 활용할 수 있지만, 새로운 단점도 존재합니다. 장점세그멘테이션의 가변 분할 방식을 사용해 프로세스의 코드, 데이터, 스택, 힙 영역을 독립적으로 관리 가능. 각 영역에 대해 메모리 접근 보호 및 공유가 용이합니다.페이징의 고정 분할 방식을 통해 메모리를 효율적으로 관리하고 외부 단편화를 줄일 수 있습니다.단점이 기법의 단점은 메모리 접근이 두 번 이루어진다는 점입니다:세그멘테이션 테이블을 참조하여 세그멘트 정보를 가져올 때페이지 테이블을 참조하여 페이지 정보를 가져올 때이중 접근으로 인한 오버헤드가 발생할 수 있습니다. 메모리 접근 권한각 프로세스는 영역별로 읽기, 쓰기, 실행 권한이 다르게 부여됩니다:코드 영역: 읽기와 실행 권한만 있고, 수정이 불가능합니다.데이터 영역: 읽기와 쓰기 권한이 있으며, 실행 권한은 없습니다.스택 & 힙 영역: 읽기와 쓰기 권한이 있으나 실행 권한은 없습니다.이 권한은 가상 주소를 물리 주소로 변환할 때마다 확인되며, 만약 권한 위반이 발생하면 에러를 발생시키고 프로세스를 종료시킵니다. 페이지드 세그멘테이션의 주소 변환 과정세그멘트 번호를 가상 주소에서 추출하여 해당 세그먼트에 대한 메모리 접근 권한을 확인합니다.권한이 적합하면, 세그멘트에서 페이지 번호와 페이지 개수를 가져옵니다.페이지 번호로 페이지 테이블에 접근하여 해당 프레임 번호를 찾습니다.물리 메모리의 프레임에 접근해 오프셋을 더하여 최종 물리 주소를 계산합니다.만약 해당 프레임이 물리 메모리에 없다면, 스왑 영역에서 불러옵니다. 현대 운영체제는 페이징과 페이지드 세그멘테이션을 상황에 맞게 혼합하여 사용하고 있습니다. 페이지드 세그멘테이션의 장점은 두 기법의 이점을 취해 메모리 관리의 유연성과 효율성을 높이는 반면, 오버헤드로 인한 성능 저하를 피하기 위해 적절한 균형을 유지하는 것이 중요합니다. 가져오기 정책디멘드 페이징 정책디멘드 페이징은 프로세스 실행 시 필요한 데이터만 메모리에 올려서 실행하는 방식으로, 메모리 효율을 극대화하는 가져오기 정책입니다. 이 방법은 프로세스의 모든 데이터가 처음부터 메모리에 로드되지 않고, 필요한 시점에만 가져오므로 메모리 자원을 아낄 수 있습니다. 지역성 이론과 디멘드 페이징90:10 법칙에 따르면 프로그램은 90%의 시간을 10%의 코드에서 소모합니다. 이 원리를 지역성 이론으로 설명할 수 있는데, 지역성 이론에는 두 가지 중요한 개념이 있습니다:시간적 지역성: 최근에 접근한 데이터는 다시 접근할 가능성이 높다.공간적 지역성: 현재 접근한 데이터와 가까운 위치에 있는 데이터가 곧 접근될 가능성이 높다.디멘드 페이징은 이 이론을 바탕으로, 메모리에서 당장 필요하지 않은 데이터는 스왑 영역으로 보내고, 필요할 것 같은 데이터만 메모리에 올리는 정책입니다. 메모리 계층 구조레지스터: CPU 내에서 가장 빠른 메모리.캐시 메모리: CPU에서 비교적 가까운 메모리로, 빠른 속도로 접근 가능.메인 메모리: 데이터 접근이 캐시보다 느리지만 대용량 데이터를 저장.보조저장장치 (스왑 영역): 메모리보다 훨씬 느리지만 데이터를 저장하는 데 사용됨. 스왑 인/스왑 아웃스왑 인: 보조저장장치(스왑 영역)에 있던 데이터를 물리 메모리로 가져오는 과정.스왑 아웃: 물리 메모리에 있는 데이터를 보조저장장치(스왑 영역)로 내보내는 과정.운영체제는 효율적인 메모리 관리를 위해 스왑 인/스왑 아웃을 최소화하려고 합니다. 페이지 테이블과 비트프로세스가 가상 메모리에 접근할 때 운영체제는 페이지 테이블을 통해 물리 메모리와 스왑 영역 간의 데이터를 관리합니다. 페이지 테이블의 각 항목은 페이지 엔트리(PTE)라고 불리며, 여러 가지 비트를 포함하고 있습니다:접근 비트: 페이지가 메모리에 올라온 후에 접근되었는지 나타냅니다.변경 비트: 페이지의 데이터가 변경되었는지 나타냅니다.유효 비트: 페이지가 물리 메모리에 있는지 스왑 영역에 있는지 알려줍니다.읽기/쓰기/실행 비트: 페이지에 대한 접근 권한을 정의합니다. Page Fault와 프로세스 대기프로세스가 가상 메모리에 접근하려 할 때, 만약 요청한 페이지가 물리 메모리에 없으면 Page Fault라는 인터럽트가 발생합니다. 이때 운영체제는 스왑 영역에 접근하여 필요한 페이지를 물리 메모리로 가져오고, 프로세스는 대기 상태로 전환됩니다. 이후 페이지가 메모리에 올라가면 프로세스는 다시 실행됩니다. 3가지 상황에서의 처리 과정스왑이 필요 없는 경우: 요청된 페이지가 이미 물리 메모리에 있으면 즉시 데이터에 접근할 수 있습니다.스왑 영역에 있는 데이터를 참조하는 경우: 요청된 페이지가 스왑 영역에 있으면 물리 메모리로 데이터를 가져와서 사용합니다.물리 메모리가 꽉 찬 경우: 새로운 페이지를 가져오기 전에, 현재 물리 메모리에서 사용하지 않는 페이지를 스왑 영역으로 옮겨 공간을 확보합니다. 디멘드 페이징은 지역성 이론에 기반하여 메모리 자원을 효율적으로 사용하는 기법입니다. 메모리 관리자는 페이지 교체 알고리즘을 통해 스왑 인/아웃을 최적화하고 성능을 유지하려고 합니다. 페이지 교체 정책페이지 교체 정책은 메모리 공간이 부족할 때 어떤 페이지를 선택해 스왑 영역으로 보낼지를 결정하는 중요한 알고리즘입니다. 이 과정에서 페이지 폴트가 발생하며, 메모리에 새로운 페이지를 불러오려면 기존의 페이지를 교체해야 하는 상황이 생깁니다. 페이지 교체 정책은 주로 프로그램의 지역성 원칙을 바탕으로 하며, 다양한 알고리즘들이 존재합니다. 주요 페이지 교체 정책 1. 무작위 선택 (Random) - 랜덤하게 페이지를 선택해 교체합니다. - 지역성 이론을 고려하지 않기 때문에 성능이 좋지 않으며, 거의 사용되지 않습니다.2. FIFO (First In, First Out) - 가장 먼저 메모리에 들어온 페이지를 먼저 내보내는 방식입니다. - 구현이 간단하지만, 자주 사용되는 페이지도 교체될 수 있다는 단점이 있습니다. - FIFO는 페이지 폴트를 줄이려고 메모리를 늘렸을 때, 오히려 페이지 폴트가 증가하는 빌레이디의 역설이 발생할 수 있습니다.3. Optimum (OPT) - 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 방식입니다. - 이론적으로 최적의 방법이지만, 앞으로의 메모리 접근을 예측할 수 없기 때문에 실제로 구현하기는 어렵습니다.4. LRU (Least Recently Used) - 가장 최근에 사용되지 않은 페이지를 교체하는 방식입니다. - 시간의 지역성에 기반하여, 최근에 사용된 페이지가 다시 사용될 확률이 높다는 가정에 따라 작동합니다. - 실제로 많이 사용되는 알고리즘이며, 성능이 우수하지만 구현이 복잡하고 추가적인 하드웨어 지원이 필요할 수 있습니다. LRU와 유사한 알고리즘1. Clock Algorithm (클락 알고리즘) - LRU의 구현 복잡성을 해결하기 위해 고안된 방식입니다. - 페이지의 접근 비트를 사용하여, 일정 시간 동안 참조된 페이지인지 아닌지를 판단합니다. - 클락 핸드가 시계 방향으로 움직이며, 접근 비트가 0인 페이지를 교체 대상으로 선택합니다. - Enhanced Clock Algorithm은 접근 비트 외에 변경 비트까지 고려하여 성능을 더 향상시킵니다.2. Second Chance Algorithm (2차 기회 알고리즘) - FIFO 방식의 문제점을 보완하기 위해, 자주 사용되는 페이지에 두 번째 기회를 주는 방식입니다. - FIFO 큐에서 페이지가 교체 대상이 될 때, 해당 페이지가 최근에 참조된 경우 큐의 맨 뒤로 이동시켜 수명을 연장시킵니다. 선택적 사용시스템 하드웨어가 LRU 구현을 지원하지 않으면 FIFO를 사용할 수밖에 없는 경우가 있습니다. 이때는 성능 향상을 위해 2차 기회 알고리즘이나 다른 보완 기법들을 사용할 수 있습니다.결론적으로, LRU는 가장 좋은 성능을 보이는 경우가 많지만, 구현 복잡성을 고려해 Clock Algorithm 같은 유사 알고리즘이 더 자주 사용됩니다. 스레싱과 워킹셋스레싱(Thrashing)은 CPU 사용률을 높이기 위해 멀티 프로그래밍 정도를 지나치게 높였을 때 발생하는 문제로, CPU가 실제 작업을 처리하는 것보다 스왑 작업에 더 많은 시간을 소비하는 현상입니다. 이로 인해 성능이 급격히 저하되며, 결국 CPU 사용률도 떨어지게 됩니다. 스레싱 발생 과정1. 멀티 프로그래밍 정도 증가: 동시에 실행되는 프로세스의 수가 늘어나면 CPU 사용률을 높이려는 의도에서 물리 메모리에 더 많은 프로세스를 올리게 됩니다.2. 메모리 부족: 메모리는 한정되어 있기 때문에 모든 프로세스의 모든 페이지를 물리 메모리에 적재할 수 없으며, 페이지 폴트가 빈번하게 발생합니다.3. 페이지 폴트 증가: 페이지 폴트가 많아지면 프로세스가 필요로 하는 페이지를 계속 스왑 영역에서 불러와야 하며, 이에 따라 스왑 작업이 많아집니다.4. CPU 사용률 감소: 페이지 폴트로 인한 스왑 작업이 지나치게 많아지면 CPU가 작업에 집중하지 못하고, 결국 CPU 사용률이 낮아집니다.5. 스레싱: 스왑 작업이 CPU의 작업을 방해하게 되어 CPU 사용률이 0에 가까워지며, 시스템이 스왑 작업에 묶여 제대로 동작하지 않는 상태가 됩니다.스레싱은 물리 메모리의 부족이 근본 원인으로, 이를 하드웨어적으로 해결하려면 물리 메모리의 크기를 늘리면 되지만, 단순히 메모리 크기를 늘린다고 해서 항상 성능이 크게 향상되는 것은 아닙니다. 워킹셋(Working Set)워킹셋은 각 프로세스가 실행되기 위해 필요한 페이지들의 집합을 의미합니다. 프로세스는 지역성 이론에 따라 특정 시간 동안 주로 사용하는 데이터나 코드를 메모리에 올려두는데, 이 페이지들의 집합을 워킹셋이라고 합니다. 워킹셋을 정의하는 것은 스레싱을 방지하고 시스템 성능을 최적화하는 중요한 방법 중 하나입니다.- 지역성 이론: 프로세스는 특정 시점에서 일정한 범위의 메모리 공간을 집중적으로 참조하는 경향이 있습니다. 이 지역성을 고려해, 자주 사용하는 페이지들만 메모리에 올려두는 것이 효율적입니다. 스레싱 방지 방법: 워킹셋 모델운영체제는 각 프로세스가 어느 정도의 페이지를 필요로 하는지 모니터링하여, 워킹셋 모델을 통해 적절한 페이지 수를 유지합니다. 다음과 같은 과정을 통해 스레싱을 방지할 수 있습니다.1. 페이지 할당 및 조정: - 프로세스가 실행되면 처음에 일정량의 페이지를 할당합니다. - 페이지 폴트가 발생하면 해당 프로세스에 더 많은 페이지를 할당해 메모리 사용량을 늘립니다. - 반대로 페이지 폴트가 거의 발생하지 않으면 페이지가 과도하게 할당된 것으로 간주하고, 메모리 낭비를 방지하기 위해 일부 페이지를 회수합니다.2. 워킹셋 유지: - 현재 메모리에 적재된 페이지들이 프로세스의 워킹셋에 속한다고 가정하고, 이 페이지들을 유지합니다. - 페이지 폴트가 많이 발생하면 워킹셋에 필요한 페이지를 추가하고, 사용 빈도가 낮은 페이지를 스왑 영역으로 내보냅니다. 스레싱은 프로세스와 메모리 간의 균형이 깨질 때 발생하며, 이를 방지하기 위해서는 프로세스마다 적절한 양의 페이지를 메모리에 적재하고, 워킹셋을 기반으로 효율적으로 관리해야 합니다. CPU 사용률을 높이기 위한 멀티 프로그래밍의 정도는 물리 메모리의 용량과 페이지 교체 정책에 의해 결정되며, 운영체제는 이를 지속적으로 모니터링하여 스레싱을 방지할 수 있습니다. 입출력 장치주변장치 주변장치의 기본 구성I/O 디바이스는 CPU와 메모리 외부에 있는 장치들로, 그래픽카드, 하드디스크, SSD, 키보드, 마우스 등 여러 가지가 포함됩니다.이들은 메인보드에 버스를 통해 연결되며, 각각의 장치 상태와 데이터를 보관할 수 있는 레지스터들을 가집니다.장치마다 데이터를 전송하는 방식이 다르며, 캐릭터 디바이스와 블록 디바이스로 나뉩니다.캐릭터 디바이스: 마우스, 키보드 등 적은 양의 데이터를 전송하는 장치.블록 디바이스: 하드디스크, SSD 등 많은 양의 데이터를 전송하는 장치. 입출력 제어기와 버스초기에는 CPU가 직접 주변장치에서 데이터를 가져오면서 입출력 작업을 처리했으나, 이는 효율성이 떨어졌습니다. 이를 해결하기 위해 입출력 제어기(I/O Controller)가 도입되어 CPU가 다른 작업을 할 수 있도록 입출력 제어기가 입출력 작업을 관리하게 되었습니다.입출력 제어기는 CPU와 빠른 메모리를 연결하는 시스템 버스와, 주변장치들을 연결하는 입출력 버스로 구성됩니다.속도 차이를 해결하기 위해, 입출력 버스는 고속 입출력 버스와 저속 입출력 버스로 나뉩니다. 예를 들어, 그래픽 카드와 같은 고속 장치는 시스템 버스에 바로 연결되기도 합니다.DMA(Direct Memory Access) 제어기가 도입되어 CPU의 개입 없이도 입출력 제어기가 메모리에 직접 데이터를 읽고 쓸 수 있게 되었으며, 이를 Memory Mapped I/O라고 부릅니다. 마우스, 키보드마우스광학 마우스는 카메라로 마우스 아래의 이미지를 초당 수천 회 촬영해 마우스의 움직임을 감지합니다.마우스의 디바이스 컨트롤러는 이 데이터를 분석하고 인터럽트를 통해 CPU에 알립니다. CPU는 운영체제와 애플리케이션이 마우스 이벤트를 처리할 수 있게 해줍니다.키보드키보드도 마우스와 비슷한 방식으로 동작하며, 사용자가 입력한 키를 디바이스 컨트롤러가 감지해 CPU로 인터럽트를 보냅니다. 운영체제는 해당 이벤트를 적절한 애플리케이션에 전달합니다. 하드디스크, SSD하드디스크하드디스크는 물리적으로 회전하는 플래터(Platter)와 이를 읽는 헤드(Head)로 구성됩니다.실린더(Cylinder)는 여러 개의 트랙이 있는 위치를 의미하며, 섹터(Sector)는 하드디스크의 가장 작은 저장 단위입니다.하드디스크의 성능은 데이터를 읽기 위해 헤드를 움직이는 시간이 느려지는 탐색 시간(Seek Time)에 의해 제한됩니다. 이 시간 때문에 하드디스크는 상대적으로 느리게 동작합니다.SSD(Flash Memory)SSD는 전기적으로 데이터를 읽고 쓰기 때문에 빠르고 조용하며, 하드디스크와 달리 기계적 움직임이 없어서 충격에 강합니다.다만, 플래시 메모리는 같은 지점에 데이터를 여러 번 쓰고 지우는 작업에 한계가 있어, 반복적인 쓰기 작업이 장치의 수명을 단축시킬 수 있습니다. 파일 시스템파일과 시스템파일 시스템은 데이터 저장 및 관리를 위해 설계된 소프트웨어 구성 요소로, 파일과 디렉토리의 생성, 수정, 삭제를 포함한 다양한 작업을 처리합니다. 파일 시스템의 구조와 역할파일 시스템은 파일 및 디렉토리를 관리하며, 디스크와 같은 저장 장치에 데이터를 효율적으로 저장합니다. 주요 기능은 다음과 같습니다:파일 및 디렉토리 생성, 수정, 삭제파일 접근 권한 관리데이터 무결성 보장백업 및 복구, 암호화 파일 구조파일은 다양한 데이터 집합으로 이루어지며, 그 구성 방식에 따라 세 가지 주요 구조로 구분됩니다:순차 파일 구조: 데이터가 연속적으로 저장되는 구조로, 파일의 특정 지점에 접근하는 데 시간이 오래 걸리지만 구조가 단순하여 공간 낭비가 적습니다.직접 파일 구조: 해시 함수를 이용해 데이터를 저장하는 방식으로, 데이터 접근이 빠르지만, 해시 함수의 선택이 중요합니다.인덱스 파일 구조: 순차 접근과 직접 접근의 장점을 결합한 방식으로, 인덱스 테이블을 이용해 빠르게 데이터를 검색할 수 있습니다. 디렉토리디렉토리 역시 파일의 한 종류로, 다른 파일들의 정보를 저장하는 역할을 합니다. 다단계 디렉토리 구조를 통해 트리 형태로 파일을 관리할 수 있으며, 윈도우의 바로가기처럼 순환 구조를 가지기도 합니다. 파일과 디스크파일이 저장될 때, 디스크는 일정 크기로 나뉜 블록으로 데이터를 저장합니다. 블록 할당 방식은 크게 두 가지로 구분됩니다: 연속 할당: 파일의 블록이 연속적으로 저장되는 방식으로, 외부 단편화 문제가 발생할 수 있어 현대 시스템에서는 잘 사용하지 않습니다.불연속 할당: 파일의 블록들이 분산되어 저장되며, 연결 할당과 인덱스 할당 방식이 존재합니다.연결 할당: 연결 리스트 구조로 파일 블록을 관리하는 방식입니다.인덱스 할당: 인덱스 블록을 통해 여러 데이터 블록에 접근하는 방식입니다. 유닉스와 리눅스에서는 이를 i-node로 관리합니다. 디스크 관리 및 블록 크기블록 크기가 작으면 내부 단편화가 줄어들어 공간 낭비가 적어지지만, 관리할 블록 수가 많아집니다. 반대로, 블록 크기가 크면 내부 단편화로 인해 공간 낭비가 발생할 수 있지만, 관리할 블록 수는 줄어듭니다. 파일 삭제 및 복구파일을 삭제할 때, 실제로 파일의 데이터가 사라지지 않고 파일 시스템은 파일 테이블에서 파일의 헤더만 삭제하고, 사용했던 블록을 프리 블록 리스트에 추가합니다. 이런 이유로 데이터 복구 프로그램을 통해 삭제된 파일의 데이터를 복원할 수 있습니다.

워밍업 클럽 CS 3주차 발자국 : 자료구조와 알고리즘

알고리즘 삽입 정렬삽입 정렬은 구현이 간단하지만 성능이 아쉬운 정렬 알고리즘입니다. 배열을 두 영역으로 나누어, 정렬되지 않은 부분에서 데이터를 하나씩 꺼내어 정렬된 부분에 적절한 위치에 삽입하는 방식으로 동작합니다. 이때, 정렬되지 않은 영역의 첫 번째 원소를 정렬된 영역의 마지막 원소부터 역순으로 비교하여 자리를 찾습니다. 시간 복잡도는 최악의 경우 O(n²)입니다. 병합 정렬병합 정렬은 비교적 복잡한 정렬 알고리즘으로, 분할 정복 기법을 사용합니다. 배열을 부분집합으로 나눈 후, 각 부분을 재귀적으로 정렬하고 합병하여 전체 배열을 정렬합니다. 병합 과정에서 n개의 데이터를 n번 비교하므로 시간 복잡도는 O(n log n)입니다. 성능 면에서 매우 뛰어나지만, 구현이 어려울 수 있다는 단점이 있습니다. 퀵 정렬퀵 정렬도 병합 정렬처럼 분할 정복 알고리즘에 속하며, 재귀적으로 배열을 정렬합니다. 배열에서 하나의 숫자를 '피벗'으로 선택한 뒤, 피벗보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하여 다시 같은 방식을 적용해 정렬합니다. 평균적인 성능은 O(n log n)이지만, 피벗 선택이 좋지 않을 경우 최악의 시간 복잡도는 O(n²)입니다. 그러나 퀵 정렬은 실제로는 병합 정렬보다 더 적은 메모리와 비교 횟수를 사용하여 더 효율적인 경우가 많습니다. 동적 프로그래밍 - 메모제이션재귀 함수는 중복된 계산을 여러 번 수행하여 성능에 악영향을 미칠 수 있습니다. 이를 해결하기 위해 메모제이션을 사용하여, 이미 계산된 값을 저장하고 필요할 때 이를 다시 사용하여 성능을 개선할 수 있습니다. 메모제이션은 주로 해시 테이블을 사용하여 빠르게 결과를 조회하고 저장하는 방식으로 동작합니다. 다만, 메모리 사용량이 늘어난다는 단점이 있습니다. 동적 프로그래밍 - 타뷸레이션타뷸레이션은 상향식 접근 방식으로, 필요한 값들을 미리 테이블에 계산하여 저장해두고 사용합니다. 메모리 사용량이 적으면서도 재귀를 사용하지 않기 때문에 메모제이션보다 더 빠를 수 있습니다. 재귀가 직관적인 경우에는 메모제이션을 사용하는 것이 좋지만, 그렇지 않은 경우에는 타뷸레이션을 통해 더 효율적으로 문제를 해결할 수 있습니다.

워밍업 클럽 CS 2주차 발자국 : 미션

운영체제FIFO 스케줄링의 장단점이 뭔가요?장점:단순성: FIFO 스케줄링은 구현이 매우 간단합니다. 프로세스가 도착한 순서대로 CPU를 할당받습니다.예측 가능성: 각 프로세스가 실행될 순서를 쉽게 알 수 있어, 작업의 순서가 명확합니다.단점:젊은 프로세스 대기: 새로운 프로세스가 도착하면 오래된 프로세스가 끝날 때까지 기다려야 하므로, 긴 작업이 젊은 프로세스의 대기 시간을 증가시킬 수 있습니다.비효율적인 CPU 사용: 짧은 작업이 긴 작업 뒤에 대기하게 되면, 전체 대기 시간과 응답 시간이 길어져 시스템 자원의 비효율성을 초래할 수 있습니다.또한 입출력 작업이 있다고 한다면 CPU는 입출력 작업이 끝날 때까지 쉬고 있기 때문에 CPU 사용률이 하락합니다. SJF를 사용하기 여러운 이유가 뭔가요?예측의 어려움: SJF는 각 프로세스의 실행 시간을 미리 알아야 최적의 스케줄링이 가능하지만, 실제 실행 시간은 정확히 알기 어렵습니다.선택의 문제: SJF를 구현하기 위해 모든 프로세스의 실행 시간을 파악해야 하므로, 이 정보를 수집하는 데 시간이 소요될 수 있습니다. 또한, 이를 위해 프로세스를 정렬해야 하므로 CPU 자원을 추가로 사용해야 합니다.스타베이션: 짧은 작업이 우선적으로 실행되므로, 긴 작업이 계속해서 대기 상태에 있을 수 있으며, 이로 인해 긴 작업이 스타베이션에 빠질 위험이 있습니다. RR 스케줄링에서 타임 슬라이스가 아주 작으면 어떤 문제가 발생할까요?과도한 문맥 전환: 타임 슬라이스가 너무 작으면 각 프로세스의 실행 시간이 짧아져 문맥 전환이 자주 발생합니다. 이로 인해 CPU의 부하가 증가하고, 문맥 전환에 소요되는 시간이 전체 실행 시간을 초과할 수 있습니다.응답 시간 증가: 각 프로세스가 CPU를 할당받는 시간이 줄어들어, 응답 시간이 증가할 수 있으며, 특히 I/O 바운드 프로세스에서는 더 큰 영향을 받을 수 있습니다.비효율적인 자원 사용: CPU가 실행 중인 프로세스를 자주 변경함에 따라 자원 사용의 비효율성이 발생할 수 있습니다. 운영체제가 MLFQ에서 CPU Bound Process와 I/O Bound Process를 어떻게 구분할까요?CPU Bound Process: CPU 자원을 주로 사용하는 프로세스로, 계산이 많이 필요합니다. 프로세스가 타임 슬라이스 크기를 오버해서 CPU 스케줄러에 의해 강제로 CPU를 뺏기는 상황이면 CPU 사용이 많은 것이니, CPU 바운드 프로세스일 확률이 높습니다.I/O Bound Process: 주로 I/O 작업을 수행하며, CPU 사용 시간이 짧고 대기 시간이 깁니다. CPU를 사용하는 프로세스가 실행하다가 스스로 CPU를 반납하면 CPU 사용이 적은 거니, I/O 바운드 프로세스일 확률이 높습니다. 공유자원이란 무엇인가요?공유자원은 프로세스 간 통신에서 여러 프로세스 또는 스레드가 동시에 접근하거나 사용할 수 있는 자원을 의미합니다.공유자원은 협업과 데이터 통신을 용이하게 하지만, 공유 자원에 대한 접근 순서에 따라 연산 결과가 달라질 수 있습니다. 컨텍스트 스위칭으로 인해 어떤 프로세스가 먼저 실행될지 예측할 수 없어 동기화 문제가 발생할 수 있습니다.또한 동시에 여러 프로세스가 접근할 경우 교착상태나 경쟁 상태와 같은 문제를 초래할 수 있습니다. 교착상태에 빠질 수 있는 조건은 어떤 것들을 충족해야 할까요?교착상태가 발생하기 위한 네 가지 조건은 다음과 같습니다:상호 배제 (Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있어야 하며, 다른 프로세스는 사용할 수 없다.점유와 대기 (Hold and Wait): 적어도 하나의 프로세스가 자원을 점유한 상태에서 다른 자원을 요청해야 한다.비선점 (No Preemption): 이미 점유한 자원은 자발적으로 반환되기 전까지 다른 프로세스가 빼앗을 수 없다.환형 대기 (Circular Wait): 프로세스들이 서로 자원을 기다리며, 대기하는 프로세스의 원이 형성되어야 한다. 자료구조와 알고리즘재귀함수에서 기저조건을 만들지 않거나 잘못 설정했을 때 어떤 문제가 발생할 수 있나요?무한 재귀: 기저 조건이 없거나 잘못 설정되면 재귀 함수가 종료되지 않고 무한히 자기 자신을 호출하게 됩니다. 이로 인해 스택 메모리가 소진되어 스택 오버플로우가 발생할 수 있습니다.비효율적인 성능: 재귀 호출이 계속되어 성능 저하가 발생할 수 있으며, 필요한 자원(메모리, CPU 시간)이 비효율적으로 소모됩니다. 0부터 입력 n까지 홀수의 합을 더하는 재귀 함수를 만들어보세요.function sumOdd(n){ if (n

워밍업 클럽 CS 2주차 발자국 : 운영체제

CPU 스케줄링 알고리즘SJF: Shortest Job FirstSJF는 Burst time(실행 시간)이 짧은 프로세스를 먼저 실행하는 알고리즘입니다.이론적으로는 FIFO보다 성능이 좋습니다.하지만 실제 구현에서는 두 가지 문제가 발생합니다: 프로세스의 실행 시간을 미리 예측하기 어렵습니다. 짧은 프로세스만 우선적으로 처리되면서, 긴 프로세스는 오랫동안 실행되지 않을 수 있습니다.결과적으로, 이러한 문제들로 인해 SJF 알고리즘은 실제 운영체제에서 많이 사용되지 않습니다. RR: Round RobinRound Robin(RR) 알고리즘은 FIFO의 단점을 해결하기 위해 고안된 알고리즘입니다.각 프로세스에 타임 슬라이스 또는 타임 퀀텀이라는 고정된 시간 동안 CPU를 할당합니다.할당된 시간이 지나면 해당 프로세스는 큐의 뒤로 밀려나고, 다음 프로세스가 실행됩니다.성능:평균 대기 시간은 상황에 따라 FIFO와 비슷할 수 있습니다. 그러나 RR 알고리즘은 컨텍스트 스위칭으로 인해 추가적인 오버헤드가 발생합니다.타임 슬라이스 크기에 따라 성능이 달라집니다: 타임 슬라이스가 크면: 사실상 FIFO와 비슷해집니다. 타임 슬라이스가 작으면: 마치 여러 프로세스가 동시에 실행되는 것처럼 보이지만, 잦은 컨텍스트 스위칭으로 인해 오버헤드가 커집니다.최적의 타임 슬라이스는 여러 프로세스가 버벅거리지 않고 동시에 실행되는 것처럼 보이면서도, 오버헤드가 최소화되는 값을 찾아야 합니다. MLFQ: Multi-Level Feedback QueueMLFQ는 오늘날 운영체제에서 널리 사용되는 CPU 스케줄링 기법으로, RR 알고리즘을 개선한 방식입니다. 주요 개념:CPU-bound 프로세스: CPU 연산을 많이 수행하며, CPU 사용률과 처리량이 중요한 프로세스.I/O-bound 프로세스: I/O 작업이 많아 응답 속도가 중요한 프로세스. MLFQ는 CPU-bound와 I/O-bound 프로세스를 적절히 구분하여 최적의 성능을 제공합니다.프로세스의 특성에 따라 타임 슬라이스를 다르게 적용하는데, CPU-bound 프로세스에는 더 긴 타임 슬라이스를, I/O-bound 프로세스에는 짧은 타임 슬라이스를 할당합니다. 동작 원리:운영체제는 CPU-bound 프로세스와 I/O-bound 프로세스를 어떻게 구별할까여요?I/O-bound 프로세스는 주로 입출력 작업을 수행하므로, CPU를 잠깐 사용하고 스스로 CPU를 반납합니다. 이 때문에 CPU 사용이 적은 경우가 많아 I/O-bound 프로세스일 확률이 높습니다.반면, CPU-bound 프로세스는 CPU에서 연산을 주로 수행하며, 타임 슬라이스를 초과하여 CPU를 사용하다가 강제로 CPU를 빼앗기게 됩니다. 이 경우 CPU 사용량이 많아 CPU-bound 프로세스일 가능성이 큽니다.이를 바탕으로 MLFQ는 여러 개의 우선순위 큐를 사용해 프로세스를 관리합니다.우선순위가 높은 큐에는 작은 타임 슬라이스가 할당되어 빠른 응답이 필요한 프로세스가 실행됩니다.우선순위가 낮은 큐로 갈수록 타임 슬라이스가 커지며, CPU-bound 프로세스는 우선순위가 낮은 큐로 이동해 더 긴 시간을 할당받고 실행됩니다.요컨대,타임 슬라이스를 초과하여 강제로 CPU를 뺏긴다면, 해당 프로세스는 우선순위가 더 낮은 큐로 이동합니다.이후, 더 큰 타임 슬라이스가 할당되며, 우선순위가 낮은 큐로 이동할수록 타임 슬라이스는 점점 커집니다.결국, 프로세스는 거의 FIFO처럼 연속적으로 실행될 수 있게 됩니다.이 방식으로 CPU 사용량이 많은 프로세스와 응답 속도가 중요한 프로세스 모두에게 적절한 스케줄링을 제공합니다.프로세스 동기화프로세스 간 통신프로세스는 독립적으로 실행될 수 있지만, 다른 프로세스와 데이터를 주고받으며 통신할 때도 있습니다. 이러한 통신은 같은 컴퓨터 내의 프로세스 간이거나, 네트워크를 통해 다른 컴퓨터와 할 수도 있습니다. 통신의 종류한 컴퓨터 내에서의 통신파일: 여러 프로세스가 하나의 파일을 사용해 데이터를 읽고 씁니다.파이프: 운영체제가 생성한 파이프를 통해 데이터를 주고받습니다. 스레드 간 통신스레드는 코드, 데이터, 힙을 공유하고, 각자의 스택만 따로 갖습니다. 전역 변수나 힙을 사용해 데이터를 주고받을 수 있습니다. 네트워크 통신운영체제가 제공하는 소켓 통신이나 RPC(원격 프로시저 호출)를 통해 네트워크로 통신합니다. 공유 자원과 임계 구역프로세스 간 통신에서 여러 프로세스가 동시에 사용하는 변수나 파일을 공유 자원이라 부릅니다. 하지만 공유 자원에 대한 접근 순서에 따라 연산 결과가 달라질 수 있습니다. 컨텍스트 스위칭으로 인해 어떤 프로세스가 먼저 실행될지 예측할 수 없어 동기화 문제가 발생합니다.임계 구역: 여러 프로세스가 동시에 접근해서는 안 되는 영역.경쟁 조건: 공유 자원에 대해 여러 프로세스가 경쟁하는 상황. 이 문제를 해결하려면 상호 배제 메커니즘이 필요합니다.상호 배제 요구 사항:임계 구역에 동시에 하나의 프로세스만 접근해야 합니다.여러 요청이 있어도 한 번에 하나의 프로세스만 접근을 허용해야 합니다.임계 구역에 들어간 프로세스는 빠르게 나와야 합니다. 세마포어세마포어는 상호 배제를 구현하는 메커니즘 중 하나로, 여러 프로세스가 동시에 공유 자원에 접근하지 못하게 합니다.세마포어는 정수형 변수로 표현되며, 여러 개의 세마포어가 존재할 수 있습니다.세마포어의 동작 방식:프로세스 A가 세마포어를 받으면(wait) 공유 자원을 사용하고, 그동안 프로세스 B는 대기합니다. A가 자원을 사용한 후 세마포어를 반납(signal)하면 B가 자원을 이어서 사용합니다.단점: 세마포어를 잘못 사용할 경우 문제가 발생할 수 있습니다 모니터모니터는 세마포어의 단점을 보완한 상호 배제 메커니즘입니다. 모니터는 운영체제에서 처리하는 것이 아닌 프로그래밍 언어 차원에서 제공됩니다.자바에서는 synchronized 키워드를 사용해 모니터를 지원하며, 이 키워드가 붙은 함수는 여러 프로세스에서 동시에 실행되지 않도록 보장합니다.public class Health { private int health = 100; synchronized void increase(int amount) { health += amount; } synchronized void decrease(int amount) { health -= amount; } }모니터는 세마포어처럼 wait와 signal 함수를 직접 사용할 필요가 없기 때문에, 프로그래머가 더 안전하고 편리하게 동기화 문제를 해결할 수 있습니다.데드락 : 교착상태데드락이란교착상태(Deadlock)는 여러 프로세스가 서로 다른 프로세스가 사용하는 자원의 해제를 기다리며, 아무도 작업을 진행하지 못하는 상태를 의미합니다. 주된 원인은 공유 자원 때문입니다. 공유 자원이 없으면 교착상태가 발생하지 않으며, 대표적인 예로 식사하는 철학자 문제가 있습니다. 교착상태 발생 조건:교착상태는 다음 4가지 조건 중 하나라도 충족하지 않으면 발생하지 않습니다:상호배제: 하나의 자원을 한 프로세스만 점유하며, 다른 프로세스는 사용할 수 없습니다.비선점: 프로세스가 점유하고 있는 자원을 다른 프로세스가 강제로 빼앗을 수 없습니다.점유와 대기: 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리는 상황입니다.원형 대기: 여러 프로세스가 점유와 대기를 하면서 원형 구조를 이룹니다.교착상태 예방을 위해 이 조건들을 통제하는 방법이 있지만, 비효율적이고 제약이 많아 예방 대신 해결 방법이 더 많이 연구되었습니다. 데드락 해결 방법1. 교착상태 회피 (Deadlock Avoidance)교착상태 회피는 프로세스에게 자원을 할당할 때, 교착상태가 발생하지 않도록 필요한 자원만을 할당하는 방식입니다. 자원 상태를 안정 상태와 불안정 상태로 나누며, 운영체제는 자원이 부족해 교착상태로 이어질 위험이 없도록 안정 상태를 유지하려 합니다.은행원 알고리즘교착상태 회피를 설명하는 알고리즘으로, 은행이 대출 가능한 자원을 관리하는 방식에 비유됩니다. 은행은 자원을 대출할 때, 자신이 가진 자원과 대출 요청을 비교해 안정 상태를 유지하며, 불안정 상태가 될 가능성이 있는 요청은 거부합니다.은행이 자원을 대출하는 과정에서, 대출 요청을 모두 수용하면 나중에 대출금을 회수하지 못해 교착상태에 빠질 수 있기 때문에 안정 상태를 유지해야 합니다.이 알고리즘은 교착상태를 피할 수 있지만, 구현이 복잡하고 비용이 많이 듭니다. 2. 교착상태 검출 (Deadlock Detection)교착상태 발생을 예방하는 것이 비효율적일 때, 교착상태가 발생하면 이를 검출하고 해결하는 방법이 있습니다.가벼운 교착상태 검출: 타이머를 사용하여 일정 시간 동안 프로세스가 작업을 진행하지 않으면 교착상태로 간주하고 해결합니다.타임아웃 시 체크포인트에서 롤백하여 상태를 복구할 수 있지만, 불필요하게 종료되는 프로세스가 발생할 수 있습니다. 무거운 교착상태 검출: 자원 할당 그래프를 이용하여 운영체제가 자원과 프로세스 간의 관계를 지속적으로 추적합니다. 교착상태가 발생하면 이를 탐지해 교착 상태를 일으킨 프로세스를 강제 종료하거나 롤백합니다.하지만 자원 할당 그래프를 유지하는데 오버헤드가 발생합니다.메모리메모리 종류레지스터CPU 내에 있는 가장 빠른 메모리.CPU가 사용하는 메모리로, 굉장히 속도가 빠름.휘발성 메모리로, 전원이 꺼지면 데이터가 사라짐.CPU 구분 시 32bit, 64bit는 레지스터의 크기를 의미.CPU는 계산 시 메인메모리에 있는 데이터를 레지스터로 가져와 처리 후, 다시 메인메모리에 저장.캐시레지스터와 메인메모리 사이에 존재하며, 휘발성 메모리.레지스터는 빠르지만 메인메모리는 느리기 때문에, 자주 사용될 데이터를 미리 캐시에 저장하여 처리 속도를 높임.여러 단계로 구성되어 있으며, L1 캐시가 가장 빠르고, L2, L3 순으로 속도가 느려짐.CPU가 값을 요청해 레지스터로 값을 옮겨야 한다면, 단계에 따라 L1 캐시를 보고, 여기 없다면 L2 캐시를 확인해보고, 여기도 없다면 메인메모리에서 값을 가져옴.메인메모리운영체제와 각종 프로세스가 실행되는 공간.휘발성 메모리로, 전원이 꺼지면 데이터가 사라지는 휘발성 메모리.하드디스크나 SSD보다 빠르지만 가격이 비싸, 실행 중인 프로그램들만 올려서 사용.보조저장장치하드디스크나 SSD처럼 비휘발성 메모리로, 전원이 꺼져도 데이터를 유지.가격이 저렴하고, 대용량 데이터를 저장하는 데 사용. 메모리와 주소이제 메인메모리를 간단히 "메모리"라고 부르기로 하자.멀티프로그래밍 환경에서는 여러 프로세스가 메모리에 올라오기 때문에, 메모리 관리가 복잡해진다. 운영체제는 메모리를 관리하기 위해 메모리를 1바이트 단위로 나누고, 각 구역에 번호를 매기는데, 이 번호를 "주소"라고 한다. 32bit와 64bit32bit CPU: 레지스터 크기가 32비트며, CPU가 다룰 수 있는 메모리는 최대 4GB(2^32)이다.64bit CPU: 64비트는 32비트보다 더 많은 메모리를 처리할 수 있으며, 성능도 더 뛰어나다. 물리주소와 논리주소물리주소: 컴퓨터가 메모리에서 실제로 사용하는 주소.논리주소: 사용자 관점에서 본 메모리 주소. 사용자는 물리주소를 직접 다루지 않고, 논리주소를 통해 메모리에 접근한다.운영체제는 메모리의 일부를 자신만을 위한 공간으로 예약한다. 사용자 프로세스가 이 공간에 접근하면 보안 문제가 발생할 수 있어, 경계 레지스터를 사용해 이를 방지한다.경계 레지스터는 CPU내에 존재하는 레지스터로 메모리 관리자(MMU)가 사용자 프로세스가 경계 레지스터의 값을 벗어났는지 검사하고, 만약 벗어났다면 그 프로세스를 종료시킨다. 절대주소와 상대주소절대주소: 메모리 관리자(MMU)가 물리적으로 메모리를 관리할 때 사용하는 실제 주소상대주소: 개발자가 프로그램을 개발할 때, 주소를 0번지부터 시작한다고 가정하는 방식.사용자는 프로그램이 메모리의 어느 위치에 있는지 알 필요 없이, 컴파일러가 생성한 상대주소(논리주소)를 사용한다사용자가 요청한 논리주소를 메모리 관리자가 재배치 레지스터 값을 이용해 물리주소로 변환하여 접근한다. 재배치 레지스터는 프로그램이 메모리의 어느 주소에서 시작하는지를 저장하는 레지스터로, 프로그램이 실행될 때마다 그 시작 주소를 기록한다. 메모리 관리자는 프로그램이 실행될 때마다 이러한 재배치 작업을 수행하므로, 사용자 프로그램은 메모리의 어느 위치에서 실행되는지 신경 쓰지 않고도 동작할 수 있다.이 방식 덕분에 개발자는 프로그램이 항상 0번지에서 시작한다고 가정하고 작성할 수 있으며, 실제 메모리 배치는 운영체제가 알아서 처리한다. 만약 프로그램이 다른 위치에서 실행되더라도, 재배치 레지스터만 변경해주면 되기 때문에 매우 유연한 방식이다. 메모리 할당방식초기 유닛 프로그래밍 환경에서는 큰 프로그램을 실행하기 위해 필요한 부분만 메모리에 올리고, 나머지는 스왑영역(보조 저장장치)에 저장하는 메모리 오버레이 기법을 사용했다.*swap : 스왑영역에 있는 데이터 일부를 메모리로 가져오고, 메모리에 있는 데이터를 스왑영역으로 옮기는 것 오늘날 메모리에 여러 프로세스가 올라오는 멀티프로그래밍 환경에서의 메모리 관리메모리 분할 방식가변 분할 방식 프로세스 크기에 맞춰 메모리를 연속된 공간에 할당하는 방식.장점: 내부 단편화가 없음. 단점: 외부 단편화 발생.프로세스가 실행을 마치고 메모리에서 내려가면, 해당 프로세스가 차지하던 공간이 빈다. 이 빈 공간이 여러 군데 흩어져 있을 경우, 새로운 프로세스를 메모리에 올리기 위해 필요한 만큼의 연속된 메모리 공간을 찾기 어려워진다. 이를 외부 단편화라고 한다.외부 단편화를 해결하기 위해 조각 모음(Defragmentation) 작업을 수행한다. 이 과정은 메모리 내에 흩어져 있는 빈 공간을 한데 모아, 연속된 큰 메모리 블록을 확보하는 방식이다. 그러나 조각 모음을 실행하려면, 현재 메모리에서 실행 중인 프로세스들을 일시 중지하거나, 메모리 내 프로세스의 위치를 이동해야 하므로 오버헤드가 발생한다. 고정 분할 방식프로세스를 크기와 상관없이 일정 크기로 나누어 할당하는 방식.장점: 구현이 간단하고 오버헤드가 적음.단점: 작은 프로세스에도 큰 공간이 할당되어 내부 단편화 발생.내부 단편화를 해결하는 방법은 없고, 분할되는 크기를 적절히 최소화해서 내부단편화를 최소화해야 함.내부 단편화는 메모리가 고정된 크기로 분할되었을 때 발생하는 문제이다. 고정된 크기의 메모리 블록에 작은 프로세스를 할당하면, 프로세스가 차지하지 않은 나머지 공간이 낭비되는 현상을 내부 단편화라고 한다.작은 크기의 프로세스를 큰 메모리 블록에 할당할 때 문제가 심각해진다. 이를 해결하기 위해 메모리 블록의 크기를 줄이면 내부 단편화는 감소하지만, 블록이 너무 작으면 관리해야 할 메모리 조각이 많아져 또 다른 성능 문제가 발생할 수 있다. 결국 메모리 블록의 크기를 적절히 조정하는 것이 내부 단편화를 최소화하는 데 중요한 전략이 된다. 버디 시스템고정 분할 방식과 가변 분할 방식의 장점을 결합하여 메모리 관리의 효율성을 높이기 위한 방법2의 제곱수로 메모리를 분할해, 메모리의 단편화 문제를 줄이는 것이 핵심.장점: 외부 단편화를 방지하고, 메모리 할당 및 해제가 용이하다.내부 단편화가 발생하긴 하지만, 공간 낭비는 최소화된다.메모리를 2의 제곱수 크기로 나누고, 프로세스가 필요로 하는 메모리 크기에 가장 가까운 2의 제곱수 크기를 할당한다. 할당된 메모리 블록을 버디(buddy)라고 부르며, 만약 프로세스가 할당된 메모리를 반환하면 이 버디는 다시 인접한 버디와 결합하여 더 큰 블록으로 병합할 수 있다.

워밍업 클럽 CS 2주차 발자국 : 자료구조와 알고리즘

알고리즘재귀 (Recursion)재귀란, 어떤 대상을 정의할 때 그 대상이 자기 자신을 참조하는 개념을 말합니다. 이를 함수로 구현한 것을 재귀 함수라고 합니다.재귀 함수: 자신을 재귀적으로 호출하는 함수.기저 조건(탈출 조건): 재귀 함수가 무한히 호출되지 않도록 종료 조건이 반드시 필요합니다.기저 조건이 없다면, 함수는 계속 호출되며, 결국 콜스택(Call Stack)이라는 메모리 공간이 꽉 차고 프로그램은 강제로 종료됩니다.*콜스택(Call Stack) : 함수 호출 시 해당 함수의 실행 정보를 저장하는 메모리 영역입니다. 스택(Stack) 구조로, 먼저 호출된 함수가 나중에 종료되는 후입선출(LIFO) 방식으로 동작합니다. 재귀적으로 문제 해결하기패턴단순한 반복 실행 단순 반복 작업은 재귀로 구현했을 때 성능 상의 이점이 없습니다. 오히려 반복문보다 더 많은 메모리를 차지하게 됩니다.반복 작업은 재귀보다는 반복문이 더 효율적입니다. 하위 문제를 기반으로 현재 문제 계산하향식 계산 방식으로 문제를 해결하는 경우 재귀가 더 유리합니다.예시: 팩토리얼 함수는 재귀를 이용한 하향식 계산이 가능합니다.같은 문제를 반복문으로 해결할 수도 있지만, 이때는 상향식 계산 방식이 주로 사용됩니다.재귀 함수는 특히 하향식 계산에서 강력한 성능을 발휘합니다. 이 방식은 재귀를 통해서만 구현할 수 있습니다. function hanoi(count = number, from = string, to = string, tmp = string) { if(count === 0) return; hanoi(count - 1, from, tmp, to); console.log(`원반 ${count}를 ${from}에서 ${to}로 이동`); hanoi(count - 1, tmp, to, from); } hanoi(3, 'A', 'C', 'B'); 버블 정렬 (Bubble Sort)버블 정렬은 인접한 두 원소를 비교하고, 크기에 따라 자리를 바꾸는 방식으로 정렬을 수행하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 이해하기 쉽고 구현이 간단한 알고리즘입니다.단점: 효율이 좋지 않아, 실무에서 자주 사용되지 않습니다. function bubbleSort(arr) { for(let i = 0; i arr[j + 1]) { let temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } 선택 정렬 (Selection Sort)선택 정렬은 정렬되지 않은 영역에서 가장 작은 값을 찾아 첫 번째 원소와 교체하는 방식으로 정렬하는 알고리즘입니다.성능: 시간 복잡도는 최악의 경우 O(n2)O(n^2)O(n2).장점: 구현이 단순하며 이해하기 쉽습니다.단점: 성능이 좋지 않아, 대규모 데이터에 적합하지 않습니다. function selectSort(arr) { for(let i = 0; i

워밍업 클럽 CS 1주차 발자국 : 미션

운영체제1. 아래 코드는 1초 마다 플레이어가 스킬을 사용했는지 체크하는 코드입니다. 이 방식은 폴링방식입니다. 1초마다 체크하기 때문에 성능에 좋지 않습니다. 이를 해결하기 위한 방식으로 어떤 걸 이용해야 할까요?while(true){ wait(1); // 1초 멈춤 bool isActivated = checkSkillActivated(); // 체크 }인터럽트를 활용할 수 있습니다.CPU는 입출력 관리자에게 입출력 명령을 내리고, 이 과정에서 다른 작업을 계속 수행할 수 있습니다.입출력 관리자는 입출력이 완료되면 CPU에게 신호를 보내고, CPU는 이 신호를 수신하여 서비스 루틴(Interrupt Service Routine, ISR)을 실행해 작업을 완료합니다.여기서 서비스 루틴이란 특정 인터럽트가 발생했을 때 해당 인터럽트를 처리하기 위해 실행되는 함수를 말합니다.(이 때, “특정 인터럽트가 발생했을 때 해당 인터럽트를 처리한다”는 것은 CPU가 어떤 특정한 이벤트(인터럽트)를 감지하고, 그 이벤트에 따라 미리 정의된 작업, 즉 서비스 루틴을 실행하는 과정을 의미합니다)인터럽트는 비동기적으로 동작하기 때문에 성능을 개선할 수 있는 이점이 있습니다.이와 같이 인터럽트를 사용하면 폴링 방식보다 더 효율적으로 스킬 사용 여부를 체크할 수 있으며, CPU 자원을 보다 효과적으로 활용할 수 있습니다. 2. 프로그램과 프로세스가 어떻게 다른가요?프로그램은 하드디스크나 SSD와 같은 저장장치에 저장된 명령어와 데이터의 집합입니다. 예를 들어, 애플리케이션이나 앱도 프로그램에 해당됩니다. 프로그램은 그 자체로는 실행되지 않으며, 컴퓨터가 실행할 준비 상태에 있는 정적인 존재입니다.프로세스는 실행 중인 프로그램을 의미합니다. 저장장치에 있던 프로그램이 메모리에 로드되어, 운영체제의 제어를 받으며 CPU, 메모리 등 컴퓨터 자원을 활용해 작업을 수행하는 능동적인 존재입니다. 프로세스는 CPU 스케줄링을 통해 처리되고, 필요에 따라 입력 및 출력 작업도 수행합니다. 3. 멀티프로그래밍과 멀티프로세싱이 어떻게 다른가요?멀티프로그래밍은 하나의 CPU가 여러 프로세스를 시분할 방식으로 처리하는 메모리 관리 개념입니다.멀티프로세싱은 여러 CPU가 각기 다른 프로세스를 병렬로 처리하는 CPU 관리 개념입니다.멀티프로그래밍은 메모리 관점에서 여러 프로그램(또는 프로세스)이 동시에 메모리에 올라와 있는 상태를 말합니다. 운영체제는 이 프로그램들 중 하나가 CPU를 사용할 수 없을 때(예: 입출력 작업 대기 시) 다른 프로그램이 CPU를 사용할 수 있도록 하여 자원의 효율성을 높입니다. 즉, 하나의 CPU가 여러 프로그램을 시분할 방식으로 실행하는 것을 말합니다. 멀티프로그래밍의 반대 개념은 유니프로그래밍, 즉 한 번에 하나의 프로그램만 메모리에 올라오는 방식입니다.멀티프로세싱은 CPU 관점에서 둘 이상의 CPU가 동시에 여러 프로세스를 처리하는 것을 의미합니다. 멀티프로세싱 시스템에서는 각 CPU가 독립적으로 다른 작업을 수행할 수 있기 때문에 작업 처리 속도와 시스템의 효율성이 크게 향상됩니다. 이는 다중 CPU 또는 코어를 활용하는 시스템에서 이루어지며, 이를 통해 여러 프로세스가 동시에 병렬로 처리될 수 있습니다. 4. 운영체제는 프로세스를 관리하기 위해서 어떤 것을 사용하나요?운영체제는 프로세스 제어 블록(PCB: Process Control Block)을 사용하여 여러 개의 프로세스를 관리합니다. 각 프로세스가 실행 중일 때, 운영체제는 해당 프로세스의 상태와 정보를 PCB에 저장하여 추적하고 관리합니다.프로세스가 생성되면 운영체제는 그 프로세스에 대한 고유한 PCB를 생성합니다. 이 PCB에는 다음과 같은 주요 정보들이 포함됩니다:프로세스 ID (PID): 프로세스의 고유 식별자프로세스 상태: 실행, 대기, 준비 등 현재 상태CPU 레지스터 정보: 프로세스가 CPU에서 작업을 하던 도중의 상태(레지스터 값)메모리 관리 정보: 프로세스의 코드, 데이터, 스택 등이 저장된 메모리 영역 정보입출력 상태 정보: 입출력 요청이나 장치 사용 상황우선순위: 프로세스의 우선순위에 따른 스케줄링 정보운영체제는 이 PCB들을 연결 리스트(또는 다른 자료구조)로 관리하여, 여러 프로세스를 효율적으로 스케줄링하고 제어합니다. PCB는 각 프로세스의 상태를 기억하기 때문에 프로세스가 CPU를 사용하다가 중단될 때, 해당 프로세스의 정보를 PCB에 저장하고, 나중에 다시 해당 프로세스가 CPU를 사용할 때 이전 상태에서부터 이어서 작업할 수 있습니다.프로세스가 종료되면 운영체제는 해당 프로세스의 PCB를 연결 리스트에서 제거하고 메모리에서 해제하여 자원을 회수합니다. 5. 컨텍스트 스위칭이란 뭔가요?CPU가 한 프로세스에서 다른 프로세스로 전환할 때 수행되는 작업입니다. CPU는 여러 프로세스를 동시에 처리할 수 없기 때문에, 하나의 프로세스를 실행하다가 다른 프로세스를 실행하려면 현재 프로세스의 상태를 저장하고 새로운 프로세스의 상태를 복구해야 합니다. 이러한 상태 정보는 프로세스 제어 블록(PCB)에 저장됩니다.컨텍스트 스위칭 과정은 다음과 같습니다:현재 실행 중인 프로세스의 상태 저장: CPU는 현재 실행 중인 프로세스의 상태(프로그램 카운터, 레지스터 값, 메모리 관리 정보 등)를 PCB에 저장합니다. 이렇게 하면 나중에 이 프로세스를 다시 실행할 때, 중단된 지점부터 작업을 이어서 할 수 있습니다.새로운 프로세스의 상태 로드: 다음으로 실행할 프로세스의 PCB에서 저장된 상태 정보를 CPU에 로드합니다. 이때 새로운 프로세스가 실행되기 위한 프로그램 카운터, 레지스터 값, 메모리 정보 등을 CPU가 가져옵니다.CPU 전환: CPU는 이제 새로운 프로세스의 명령어를 실행하며 작업을 이어나갑니다.컨텍스트 스위칭은 필수적인 작업이지만, 오버헤드가 발생합니다. 이 과정은 비교적 짧은 시간이 걸리지만, 불필요하게 자주 발생하면 CPU가 실제 작업보다는 프로세스 전환에 더 많은 시간을 소모할 수 있습니다.따라서 컨텍스트 스위칭은 효율적인 CPU 자원 관리와 동시성 유지를 위한 필수적인 메커니즘이지만, 너무 빈번하게 발생하지 않도록 스케줄러가 잘 조정해야 합니다. 자료구조와 알고리즘1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.해시 테이블(Hash Table)을 사용하겠습니다. 해시 테이블은 해시 함수를 사용해 데이터를 효율적으로 저장하고 검색할 수 있는 자료구조입니다. 해시 함수를 통해 학생 정보(예: 학생 ID)를 키로 변환하고, 해당 키에 맞는 위치에 데이터를 저장합니다.이 자료구조의 장점은 데이터의 삽입, 수정, 삭제, 검색이 평균적으로 O(1)의 시간 복잡도를 가지기 때문에 매우 빠릅니다. 따라서 학생 정보가 많더라도, 특정 학생의 정보를 빠르게 조회하거나 수정할 수 있습니다. 또한, 해시 테이블은 중복을 허용하지 않으므로 학생 ID와 같은 고유 식별자를 기반으로 데이터 관리가 용이합니다.그러나 해시 테이블의 단점으로는 충돌 관리가 필요하다는 점이 있습니다. 해시 함수가 서로 다른 데이터를 동일한 해시 값으로 변환할 경우, 이를 해결하기 위한 방법(체이닝 또는 오픈 어드레싱 등)을 구현해야 합니다. 하지만 전체적으로 성능과 효율성 측면에서 학생 관리 프로그램에 적합합니다. 2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.큐(Queue)를 선택하겠습니다. 큐는 FIFO(First In, First Out) 구조로, 먼저 들어온 데이터가 먼저 처리되는 자료구조입니다. 주문 처리는 보통 고객이 주문한 순서대로 처리되어야 하기 때문에 큐는 자연스럽게 이러한 요구 사항을 충족시킵니다.큐에서 데이터 삽입(Enqueue)은 뒤쪽에서 이루어지고, 데이터 삭제(Dequeue)는 앞쪽에서 이루어지기 때문에 주문이 들어온 순서대로 처리가 보장됩니다. 즉, 프로그램이 새로운 주문을 받을 때는 큐의 뒤에 추가하고, 주문을 처리할 때는 큐의 앞에서 데이터를 꺼내 처리합니다.큐는 또한 O(1)의 시간 복잡도로 삽입과 삭제 작업이 이루어지기 때문에, 대량의 주문이 처리될 때에도 효율적으로 관리할 수 있습니다. 이 구조 덕분에 고객 주문의 공평한 처리와 성능 측면에서 매우 유리합니다.

워밍업 클럽 CS 1주차 발자국 : 운영체제

운영체제 들어가기운영체제 개요운영체제(OS, Operating System)는 컴퓨터 하드웨어와 사용자 간의 중개자 역할을 하는 소프트웨어입니다.컴퓨터 자원(CPU, 메모리, 디스크, 네트워크 등)을 효율적으로 관리하고, 사용자와 응용 프로그램이 하드웨어를 쉽게 사용할 수 있도록 도와주는 역할을 합니다. 운영체제는 여러 작업을 동시에 처리할 수 있도록 프로세스를 관리하고, 파일 시스템, 네트워크 통신, 보안 등을 담당하며, 하드웨어 장치와 소프트웨어 간의 인터페이스 역할도 합니다.운영체제가 하는 주요 기능:1. 프로세스 관리: 실행 중인 프로그램(프로세스)을 관리하고, 여러 프로세스가 동시에 실행될 수 있도록 스케줄링과 자원 배분을 조절.2. 메모리 관리: 실행 중인 프로그램들이 메모리를 효율적으로 사용하도록 조정하고, 메모리 간 충돌을 방지.3. 하드웨어 관리: CPU, 메모리, 디스크, 입출력 장치 등의 하드웨어 자원을 관리하고, 응용 프로그램이 이 자원에 접근할 수 있도록 인터페이스를 제공.4. 파일 시스템 관리: 데이터를 파일 단위로 저장하고, 사용자가 이를 읽고 쓸 수 있도록 파일 관리 시스템을 제공.5. 보안 및 접근 제어: 시스템 자원에 대한 접근을 제어하고, 권한을 부여해 사용자의 보안을 유지.운영체제는 다양한 하드웨어를 제어하며 컴퓨터 시스템의 효율성과 안정성을 보장하는 중요한 소프트웨어입니다. 대표적인 운영체제에는 윈도우(Windows), 리눅스(Linux), 맥OS(macOS) 등이 있습니다. 운영체제 역사운영체제는 애니악 같은 초기 컴퓨터부터 발전해 왔습니다. 초기에는 입출력 작업과 같은 기본 기능만 수행했지만, 시분할 시스템의 도입으로 멀티프로그래밍과 다중 사용자 환경이 가능해졌고, 이 시기에 유닉스가 탄생했습니다. 이후, 개인용 컴퓨터가 상용화되면서 현대의 운영체제가 발전했습니다.운영체제는 CPU 사용률을 높이고 비용을 절감하려는 노력에서 시작되었습니다. 운영체제의 구조운영체제의 구조는 커널, 사용자 인터페이스, 하드웨어와의 상호작용으로 나눌 수 있습니다.커널(Kernel): 운영체제의 핵심으로, 프로세스, 메모리, 저장장치를 관리합니다. 커널은 사용자가 직접 접근할 수 없으며, 커널이 사용자로부터 자신을 보호하기 위한 인터페이스인 시스템 콜을 통해 응용 프로그램과 소통합니다.사용자 인터페이스: 사용자와 커널 간의 상호작용을 위해 GUI(그래픽 사용자 인터페이스)나 CLI(명령 줄 인터페이스)를 제공합니다. 사용자는 시스템 콜을 통해 커널의 기능을 요청합니다.하드웨어와의 상호작용: 커널은 디바이스 드라이버를 사용하여 하드웨어를 제어합니다. 드라이버는 하드웨어와 커널 간의 통신을 담당하며, 기본적인 드라이버는 커널에 포함되지만 복잡한 장치는 제조사에서 제공하는 드라이버를 설치해야 합니다. 컴퓨터 하드웨어와 구조오늘날의 대부분의 컴퓨터는 프로그램 내장 방식의 폰 노이만 구조를 따릅니다. 과거의 애니악 같은 컴퓨터는 하드웨어로 프로그램을 구성해야 했으며, 프로그램 변경 시마다 스위치와 배선을 재조정하는 불편함이 있었습니다.폰 노이만 구조의 주요 요소:CPU: 중앙 처리 장치로, 모든 연산과 제어를 담당합니다.BUS: 데이터를 전달하는 통로 역할을 합니다.메모리 (RAM): 프로그램을 실행하기 위해 메모리에 올리는 방식입니다. 프로그램이 메모리에 내장되어 실행되므로, 소프트웨어만 교체하면 됩니다.메인보드:하드웨어 연결 장치: 다양한 하드웨어를 연결하여 통합하는 역할을 합니다.데이터 전송: 장치 간의 데이터 전송은 메인보드의 버스가 담당합니다.CPU는 크게 산술논리 연산장치(ALU), 제어장치(Control Unit), 레지스터(Register)로 나눌 수 있습니다:산술논리 연산장치 (ALU):CPU에서 실제 데이터 연산을 수행하는 장치로, 산술 연산(덧셈, 뺄셈 등)과 논리 연산(AND, OR, NOT 등)을 처리합니다.제어장치 (Control Unit):CPU 내 모든 장치의 동작을 지시하고 제어하는 역할을 하며, 프로그램 명령어를 해석하여 ALU와 레지스터 등 다른 장치의 동작을 조정합니다.레지스터 (Register):CPU 내부에서 계산을 위해 임시로 데이터를 보관하는 장치로, 변수를 저장하는 역할을 합니다. 레지스터는 빠른 데이터 접근 속도를 제공합니다.메모리는 크게 RAM과 ROM으로 구분되며, 각각의 특징은 다음과 같습니다:RAM (Random Access Memory):저장된 위치와 관계없이 읽는 속도가 일정합니다.휘발성 메모리로, 전원이 꺼지면 데이터가 사라집니다.주로 메인 메모리로 사용되어, 현재 실행 중인 프로그램과 데이터를 임시로 저장합니다.ROM (Read Only Memory):비휘발성 메모리로, 전원이 꺼져도 데이터가 유지됩니다.데이터가 한 번 쓰이면 수정할 수 없습니다.주로 컴퓨터 부팅과 관련된 BIOS를 저장하는 데 사용됩니다. 컴퓨터 부팅 과정전원 공급: 컴퓨터 전원이 켜지면 하드웨어에 전력이 공급되고, 프로세서가 초기화되면서 부팅이 시작됩니다.BIOS 실행: 컴퓨터의 메인보드에 내장된 ROM(Read-Only Memory)에 저장된 BIOS(Basic Input/Output System)가 실행됩니다. BIOS는 컴퓨터의 기본적인 입출력 기능을 담당하며, 부팅 초기 단계에서 중요한 역할을 합니다.POST(전원 켠 후 자가 테스트): BIOS는 POST(Power-On Self Test)를 수행하여 CPU, 메모리, 키보드, 마우스, 그래픽 카드, 하드디스크 등 주요 하드웨어 장치가 정상적으로 작동하는지 확인합니다. 문제가 있으면 오류음을 내거나 화면에 오류 메시지를 표시하고, 부팅이 중단됩니다.부트로더 로드: 하드웨어 점검이 완료되면, BIOS는 저장 장치(주로 하드디스크 또는 SSD)에서 MBR(Master Boot Record)을 찾아 실행합니다. MBR에는 컴퓨터의 첫 번째 부팅 섹터와 부트로더가 저장되어 있습니다.부트로더 실행: MBR에서 불러온 부트로더는 설치된 운영체제들을 확인하고, 사용자가 부팅할 운영체제를 선택할 수 있도록 합니다. 예를 들어, 컴퓨터에 윈도우와 리눅스가 함께 설치되어 있으면 운영체제 선택 화면이 표시됩니다.운영체제 로드: 사용자가 운영체제를 선택하거나 기본 운영체제가 하나만 있으면, 선택된 운영체제가 하드디스크에서 메모리로 로드됩니다. 이때 운영체제의 커널이 메모리에 올라가며, 운영체제가 컴퓨터를 제어하기 시작합니다.바탕화면 표시: 운영체제가 성공적으로 로드되면, 모니터에 바탕화면이 표시되고, 사용자 인터페이스(UI)가 준비됩니다. 이 시점부터는 사용자가 응용 프로그램을 실행하고, 운영체제가 이를 관리하게 됩니다. 인터럽트인터럽트는 CPU가 입출력 장치와 상호작용할 때 발생하는 중요한 개념입니다.1. 입출력 작업 시작: CPU가 입출력 작업이 들어오면 입출력 관리자에게 명령을 내립니다.2. 폴링 방식CPU는 입출력 명령의 완료 여부를 주기적으로 체크해야 합니다. 이 방식을 폴링(Polling)이라고 합니다.단점: CPU가 자주 확인해야 하므로 성능이 저하됩니다.3. 인터럽트의 도입인터럽트는 폴링의 단점을 해결하는 방식입니다.CPU는 입출력 명령을 내린 후 다른 작업을 계속 수행합니다.입출력 관리자가 작업이 완료되면 CPU에 신호를 보내고, CPU는 이 신호를 수신하여 인터럽트 서비스 루틴(ISR)을 실행하여 작업을 완료합니다.ISR (인터럽트 서비스 루틴):특정 인터럽트가 발생했을 때 그 인터럽트를 처리하는 함수입니다.인터럽트의 장점:인터럽트는 비동기적으로 동작하여 CPU의 성능을 높이는 데 도움을 줍니다.인터럽트의 종류 : 하드웨어 인터럽트: 입출력 장치에서 발생합니다.소프트웨어 인터럽트: 사용자 프로그램에서 발생하며, 예를 들어 0으로 나누기 또는 유효하지 않은 명령어에 접근할 때 발생합니다.프로세스와 스레드프로그램과 프로세스프로그램:하드디스크와 같은 저장장치에 저장된 명령문의 집합체로, 애플리케이션 또는 앱이라고도 함.컴퓨터 관점에서는 수동적인 존재로, 저장장치에만 존재함. 프로세스:실행 중인 프로그램을 의미하며, 저장장치에 있는 프로그램이 메모리에 올라갔을 때 형성됨.능동적인 존재로, 메모리와 CPU를 사용하며 입력과 출력을 처리함.운영체제의 CPU 스케줄링 알고리즘에 따라 CPU 사용. 프로세스의 구조코드 영역 : 실행 중인 프로세스의 코드가 저장됨.데이터 영역: 전역 변수 및 정적 변수가 저장됨.스택 영역:지역 변수와 함수 호출에 필요한 정보가 저장됨.함수 호출 시 매개변수와 복귀 주소를 저장.힙 영역:개발자가 런타임 중 동적으로 메모리를 할당할 수 있는 공간.C 언어에서 malloc, free 함수를 사용하여 자원 할당 및 해제를 수행. 프로세스 생성 과정 (C 언어의 경우)전처리: 전처리기를 통해 매크로를 치환하고 필요한 파일을 포함함. 이때 파일의 확장자는 .i가 됨.컴파일:컴파일러가 C 언어를 저수준 어셈블리어로 변환함. 파일 확장자는 .s가 됨.어셈블리:어셈블러가 어셈블리어를 기계어로 변환함. 결과 파일의 확장자는 .o가 됨.링킹:링커가 여러 라이브러리 및 다른 소스코드를 연결하여 최종 실행 파일을 생성함. 확장자는 .exe가 됨.프로세스 생성:생성된 실행 파일을 더블 클릭하면 하드디스크에 있는 파일이 메모리에 올라가 프로세스가 형성되며 운영체제에 의해 관리됨. CPU 관점에서의 프로세스 실행CPU는 0과 1로 이루어진 기계어만을 실행함.예를 들어, CPU가 숫자 5와 7을 메모리에 저장하고, 이를 레지스터로 가져옴.제어장치가 레지스터의 값들을 가지고 더하라는 명령을 내리면, 산술 논리 연산 장치가 두 숫자를 더하고 결과를 레지스터에 저장.제어장치가 레지스터에서 결과값을 가져와 메모리에 저장함. 멀티프로그래밍과 멀티프로세싱메모리 관점 :유니프로그래밍: 메모리에 오직 하나의 프로세스만 올라와 있는 상태입니다.멀티프로그래밍:메모리에 여러 개의 프로세스가 동시에 올라와 있는 상태입니다.CPU 관점 :멀티프로세싱:CPU가 여러 개의 프로세스를 동시에 처리하는 방식입니다. 오늘날의 운영체제는 멀티프로그래밍과 멀티프로세싱 두 가지 방식을 공존하여 사용합니다.멀티프로그래밍:메모리에 여러 개의 프로세스가 올라와 있으며, 이들 프로세스는 동시에 존재합니다.시분할 처리:CPU는 각 프로세스를 짧은 시간 동안 교대로 실행하여 멀티프로세싱을 구현합니다. 과거에는 메모리의 크기가 작아 멀티프로그래밍이 불가능하여 유니프로그래밍과 멀티프로세싱을 사용했습니다. 스와핑 : 메모리에 있는 데이터를 다른 저장장치로 보내고, 다른 저장장치에서 있는 데이터를 메모리에 올리는 과정을 말합니다. 이로 인해 메모리의 활용성을 극대화할 수 있습니다. PCB : Process Control Block운영체제는 여러 개의 프로세스를 효율적으로 관리하고 공평하게 실행해야 합니다. 프로세스가 생성되면, 운영체제는 해당 프로세스의 정보를 포함하는 PCB(프로세스 제어 블록)를 생성하고 저장합니다. 이 PCB들은 연결 리스트라는 자료구조로 저장되어 운영체제에서 관리됩니다. 프로세스가 종료되면, 연결 리스트에서 해당 프로세스의 PCB가 제거됩니다.포인터:부모 및 자식 프로세스에 대한 포인터와 할당된 자원에 대한 포인터를 포함합니다.프로세스 상태 전환 시 저장하는 포인터를 갖고 있어 효율적인 접근을 지원합니다.프로세스 상태:현재 프로세스의 5가지 상태를 나타냅니다:생성, 준비,실행,대기,완료프로세스 ID (PID):프로세스를 식별하기 위한 고유 숫자를 저장합니다.프로그램 카운터:다음에 실행될 명령어의 주소를 포함합니다. 운영체제가 시분할 처리로 여러 프로세스를 번갈아 실행할 때, 어떤 프로세스가 CPU를 빼앗기고 다시 실행될 때 원래의 명령어가 실행될 수 있도록 프로그램 카운터는 필수적입니다.레지스터 정보:프로세스 실행 시 사용했던 레지스터 값들이 저장됩니다. 이는 CPU를 빼앗긴 후 다시 시작할 때 이전에 사용하던 값을 복구하기 위한 용도로 사용됩니다.메모리 관련 정보:프로세스가 메모리에 있는 위치 정보, 메모리 침범을 방지하기 위한 경계 레지스터 값 등이 저장됩니다.CPU 스케줄링 정보:CPU 스케줄링에 필요한 우선순위, 최종 실행 시간, CPU 점유 시간 등이 저장됩니다.기타 정보:PCB에는 프로세스의 상태 관리와 관련된 기타 정보도 포함될 수 있습니다. 프로세스 상태프로세스는 시분할 처리를 위한 다음과 같은 5가지 상태를 갖습니다:생성 (New):PCB(프로세스 제어 블록)가 생성되고, 메모리에 프로그램을 적재하기 위한 요청이 이루어지는 상태입니다.준비 (Ready):CPU 사용을 기다리는 상태입니다.준비 상태에 있는 프로세스는 배분된 CPU 스케줄러에 의해 CPU가 할당됩니다.대부분의 프로세스는 이 준비 상태에 있습니다.대기 (Waiting):프로세스가 입출력 요청을 할 때, 해당 요청이 완료될 때까지 기다리는 상태입니다.CPU는 매우 빠른 반면, 입출력 작업은 상대적으로 느리기 때문에, 특정 프로세스가 입출력 요청을 하면 CPU가 그 프로세스를 기다리게 하는 것은 비효율적입니다.따라서, 입출력 요청을 한 프로세스는 대기 상태로 전환되고, 다른 프로세스에게 CPU를 할당합니다.입출력 작업이 완료되면 대기 상태에 있던 프로세스에게 CPU 할당 기회를 줍니다.실행 (Running):준비 상태에 있는 프로세스가 CPU 스케줄러에 의해 CPU를 할당받아 실행되는 상태입니다.CPU가 하나인 경우 실행 상태의 프로세스는 최대 1개만 존재합니다.실행 상태에 있는 프로세스도 CPU를 무한정 사용할 수 없으며, 부여된 시간만큼 사용합니다.CPU 스케줄러는 부여된 시간을 초과하면 할당된 CPU를 강제로 뺏고 프로세스는 다시 준비 상태로 전환됩니다.완료 (Terminated):프로세스가 종료된 상태입니다.프로세스가 사용했던 데이터는 메모리에서 제거되고, 생성된 PCB도 제거됩니다. 프로세스 A, B, C가 동시에 실행될 때의 동작 과정:프로세스 로드:사용자의 입력에 의해 운영체제는 A, B, C 프로그램을 메모리에 로드합니다.이 과정에서 각 프로그램에 대한 프로세스 제어 블록(PCB)도 생성됩니다.CPU 할당:운영체제는 스케줄러에 의해 A 프로세스에 CPU를 할당합니다.명령어 주소 지정:운영체제는 PCB에서 A 프로세스의 정보를 가져와 CPU의 프로그램 카운터에 실행될 명령어의 주소를 지정합니다.A 명령어 실행:CPU는 메모리에서 A 프로세스의 동작에 필요한 명령어를 가져오고, 연산을 수행합니다.컨텍스트 스위칭 (A → B):스케줄러에 의해 A 프로세스에서 B 프로세스로 컨텍스트 스위칭이 발생합니다.PCB 업데이트:운영체제는 PCB에서 A 프로세스의 정보를 업데이트합니다. (프로그램 카운터 값도 저장)B 프로세스 정보 로드:운영체제는 PCB에서 B 프로세스의 정보를 가져와 CPU의 프로그램 카운터에 실행될 명령어의 주소를 지정합니다.B 명령어 실행:CPU는 메모리에서 B 프로세스의 동작에 필요한 명령어를 가져오고, 연산을 수행합니다.컨텍스트 스위칭 (B → C):스케줄러에 의해 B 프로세스에서 C 프로세스로 컨텍스트 스위칭이 발생합니다.반복:위의 과정이 반복되면서 A, B, C 프로세스가 CPU를 공유하며 실행됩니다.이러한 방식으로 운영체제는 여러 프로세스의 CPU 자원을 효율적으로 관리하며, 각 프로세스의 PCB를 통해 실행 상태와 정보를 추적합니다. 컨텍스트 스위칭을 통해 CPU는 각 프로세스를 빠르게 교대로 실행하여 사용자에게 다중 작업을 수행하는 것처럼 보이게 합니다. 컨텍스트 스위칭 Context SwitchingCPU가 하나의 프로세스를 실행하다가 다른 프로세스를 실행하기 위해 현재 실행 중인 프로세스의 상태를 저장하고, 다음 프로세스의 상태로 교체하는 작업입니다.이 과정에서 프로세스의 제어를 원활하게 유지하기 위해 프로세스 제어 블록(PCB)의 내용(프로세스 상태, 다음 실행할 명령어의 주소를 담고 있는 프로그램 카운터, 각종 레지스터 값, 메모리 관련 정보)이 변경됩니다. 컨텍스트 스위칭 과정CPU 점유 시간 초과:프로세스 A가 CPU를 사용하는 동안 할당된 점유 시간을 초과합니다.인터럽트 발생:운영체제는 프로세스 A가 CPU를 너무 오랫동안 사용했다고 판단하고 인터럽트를 발생시킵니다.상태 저장:프로세스 A는 현재 실행 중인 작업을 중지하고, 현재 CPU의 레지스터 값과 상태를 PCB A에 저장합니다.프로세스 B 상태 설정:PCB B를 참조하여 이전 프로세스 B의 상태로 CPU의 레지스터 값을 설정합니다.PCB B에는 다음에 실행할 명령어의 주소를 포함하는 프로그램 카운터가 저장되어 있습니다.프로세스 B 실행:CPU는 프로세스 B의 명령어를 실행할 준비가 완료되며, 즉시 실행을 시작할 수 있습니다.다시 인터럽트 발생:프로세스 B가 점유 시간을 다 사용하면, 운영체제는 또 다시 인터럽트를 발생시킵니다.상태 저장 및 교체:프로세스 B의 상태를 PCB B에 저장하고, PCB A에서 프로세스 A의 상태를 가져와 다시 프로세스 A를 실행합니다. 컨텍스트 스위칭 발생 이유컨텍스트 스위칭이 발생하는 이유는 여러 가지가 있습니다:CPU 점유 시간 초과: 프로세스가 할당된 CPU 점유 시간을 초과했을 때.I/O 요청: 프로세스가 입출력 작업을 요청하여 대기 상태로 전환될 때.다른 종류의 인터럽트: 시스템의 다른 요구사항이나 이벤트로 인해 발생하는 인터럽트가 있을 때. 스와핑 (Swapping) vs 컨텍스트 스위칭 (Context Switching)스와핑과 컨텍스트 스위칭은 모두 운영체제가 프로세스를 효율적으로 관리하기 위한 기법이지만, 사용되는 상황과 방법이 다릅니다. 스와핑은 주로 메모리 관리와 관련되어 있으며, 컨텍스트 스위칭은 CPU 자원의 효율적 분배와 관련되어 있습니다.스와핑 (Swapping)정의: 스와핑은 메모리 관리 기법 중 하나로, 운영체제가 프로세스를 메모리에서 디스크(스왑 공간)으로 이동시키는 작업입니다. 프로세스가 필요하지 않을 때 메모리에서 제거하고, 다시 필요할 때 다시 메모리로 로드합니다.목적:메모리 공간을 확보하여 다른 프로세스가 실행될 수 있도록 합니다.물리적 메모리가 제한되어 있는 경우 여러 프로세스의 동시 실행을 지원하기 위해 사용됩니다.작동 방식:프로세스가 메모리에서 제거될 때, 해당 프로세스의 모든 데이터와 상태를 디스크에 저장합니다.나중에 프로세스가 필요할 때, 디스크에서 다시 메모리로 로드합니다. 컨텍스트 스위칭 (Context Switching)정의: 컨텍스트 스위칭은 CPU가 실행 중인 프로세스의 상태를 저장하고, 다른 프로세스의 상태로 교체하는 작업입니다. 이는 다중 프로세스 환경에서 CPU 자원을 효율적으로 할당하기 위해 필요합니다.목적:여러 프로세스 간에 CPU 자원을 공정하게 분배하고, 각 프로세스가 주어진 시간 내에 실행될 수 있도록 합니다.작동 방식:현재 실행 중인 프로세스의 상태(레지스터 값, 프로그램 카운터 등)를 PCB에 저장합니다.다음 실행할 프로세스의 PCB에서 상태를 읽어와 CPU에 로드합니다.주요 차이점 프로세스의 생성과 종료프로세스 생성 과정:1. 사용자 실행: 사용자가 .exe 파일을 더블 클릭하여 프로그램을 실행합니다.2. 메모리 로드: 운영체제가 해당 프로그램의 코드 영역과 데이터 영역을 메모리에 로드하고, 빈 스택과 빈 힙을 생성하여 공간을 확보합니다.3. PCB 생성: 이 프로세스를 관리하기 위한 프로세스 제어 블록(PCB)을 만들어 초기화합니다.위의 프로세스 생성 과정은 운영체제가 부팅되고 0번 프로세스가 생성될 때 딱 한 번만 실행합니다.0번 프로세스와 자식 프로세스:0번 프로세스: 운영체제가 부팅되면 0번 프로세스가 생성되고, 나머지 모든 프로세스는 이 0번 프로세스를 복사하여 생성됩니다. 복사가 새로 생성하는 것보다 더 빠르기 때문입니다.부모-자식 관계: 자식 프로세스는 부모 프로세스인 0번 프로세스의 코드 영역, 데이터 영역, 스택 영역, PCB 내용을 모두 복사합니다. 부모-자식 관계 및 자식 프로세스의 독립적인 실행을 통해 효율적인 메모리 관리와 프로세스 관리를 가능하게 합니다. exec() 함수 사용:자식 프로세스의 실행: fork() 함수로 생성된 자식 프로세스가 부모와 동일하게 실행되지 않도록 하기 위해 exec() 함수를 사용합니다.코드와 데이터 덮어쓰기: exec() 함수를 호출하면 자식 프로세스의 코드와 데이터 영역을 원하는 값으로 덮어써 자식 프로세스는 부모와 완전히 다른 동작을 하게 됩니다. 프로세스 종료:exit() 함수: 자식 프로세스는 작업이 끝났음을 부모 프로세스에게 알리기 위해 exit() 함수를 호출합니다.exit status: 부모 프로세스는 자식 프로세스의 종료 상태(exit status)를 읽고 자식 프로세스를 정리합니다. 좀비 프로세스:정상 종료 실패: 만약 부모 프로세스가 자식 프로세스보다 먼저 종료되거나, 자식이 비정상적으로 종료되어 exit 신호를 주지 못하면, 부모가 자식의 exit status를 읽지 못하고 메모리에 남아 있는 상태를 "좀비 프로세스"라고 부릅니다.성능 저하: 좀비 프로세스가 많아지면 메모리를 차지하여 시스템이 느려질 수 있으며, 재부팅을 통해 메모리가 초기화되어 성능이 회복될 수 있습니다. 스레드운영체제의 작업 처리 단위: 프로세스운영체제는 사용자가 요청하는 작업을 처리하기 위해 프로세스를 생성합니다.각 프로세스는 프로세스 제어 블록(PCB)과 메모리에 필요한 코드, 데이터, 스택, 힙 영역을 할당받습니다. 프로세스의 한계프로세스는 메모리 사용량이 많아 여러 개의 프로세스를 생성하는 것이 비효율적입니다.각 프로세스가 독립적으로 자원을 사용하므로 메모리 오버헤드가 발생합니다. 스레드의 도입스레드는 프로세스 내에서 실행되는 작업의 단위로, 여러 개의 스레드가 존재할 수 있습니다.스레드는 같은 프로세스 내에서 PCB, 코드, 데이터, 힙 영역을 공유합니다. 하지만 각 스레드는 독립적인 스택을 가집니다. 스레드 관리스레드의 구분을 위해 각 쓰레드에 고유한 스레드 ID를 부여하고, 이를 관리하기 위한 스레드 컨트롤 블록(TCB)도 생성됩니다.이로 인해 운영체제는 프로세스 내의 스레드를 개별적으로 관리할 수 있습니다. 장단점 비교:스레드는 프로세스에 비해 메모리 사용이 효율적이고 실행 속도가 빠르며, 적은 오버헤드를 통해 작업을 수행할 수 있는 장점이 있지만, 안정성 측면에서는 프로세스에 비해 취약한 단점을 가집니다.안전성 프로세스: 서로 독립적이므로 하나의 프로세스에 문제가 생겨도 다른 프로세스에 영향을 주지 않습니다.스레드: 같은 프로세스 내에서 실행되므로, 하나의 스레드에 문제가 생기면 해당 프로세스 내의 모든 스레드에 영향을 미칩니다.속도와 자원:프로세스: 각 프로세스가 고유한 자원을 가지므로, 프로세스 간 통신 시 오버헤드가 크고 속도가 느립니다.스레드: 스택 영역을 제외한 모든 영역을 공유하기 때문에 오버헤드가 적고, 데이터 공유가 용이하지만 공유 자원에서 동기화 문제를 발생할 수 있습니다. CPU 스케줄링CPU 스케줄링 개요프로그램을 실행시키면 메모리에 프로세스가 생성되고 각 프로세스에는 1개 이상의 스레드가 있습니다. 프로세스들은 CPU를 차지하기 위해 운영체제의 명령을 기다리고 있습니다.운영체제는 모든 프로세스에 대해 CPU를 할당하고 해제하는 역할을 수행합니다. 이 과정을 CPU 스케줄링이라고 합니다. 스케줄링 고려 사항어떤 프로세스에게 CPU를 할당할 것인가?: 메모리에 있는 수많은 프로세스 중에서 CPU 사용 권한을 부여할 프로세스를 결정합니다.CPU를 할당받은 프로세스가 얼마나 오랫동안 CPU를 사용할 것인가?: 현대의 시스템에서는 시분할 처리 방식으로 여러 프로세스가 짧은 시간 동안 CPU를 번갈아 사용하는 방식입니다. CPU Burst와 I/O BurstCPU Burst: CPU를 할당받아 실행되는 작업입니다.I/O Burst: 입출력 작업으로, CPU와는 별개로 수행됩니다. 다중큐프로세스 상태1. 생성: 프로세스가 생성되면 준비 상태로 전환됩니다.2. 준비 상태: CPU를 기다리고 있는 프로세스들은 CPU 스케줄러에 의해 실행 상태로 전환됩니다.3. 실행 상태: CPU를 할당받은 프로세스는 CPU 사용 시간이 끝나면 다시 준비 상태로 돌아갑니다.- 입출력 요청: 프로세스가 입출력 요청을 하면 대기 상태로 전환됩니다.- 작업 완료: 프로세스 작업이 끝나면 완료 상태로 전환됩니다. 큐와 프로세스 관리준비 상태와 대기 상태의 프로세스는 큐라는 자료구조로 관리됩니다.큐는 선입선출(FIFO) 방식으로, 먼저 들어온 작업이 먼저 처리됩니다. 프로세스 우선순위와 큐프로세스가 실행 상태에서 준비 상태로 돌아갈 때, 운영체제는 해당 프로세스의 우선순위를 확인하고 그에 맞는 준비 큐에 넣습니다. CPU 스케줄러프로세스 정보가 담긴 PCB는 준비 상태의 다중 큐에 들어가 실행되기를 기다립니다.CPU 스케줄러는 준비 상태의 다중 큐에 있는 프로세스들 중에서 적절한 프로세스를 선택하여 실행 상태로 전환합니다. 입출력 작업 관리실행 중인 프로세스에서 입출력 작업이 발생하면, 해당 작업의 종류별로 나뉜 큐에 들어갑니다.CPU 스케줄러는 이 큐를 참조하여 입출력 작업의 스케줄링을 수행합니다. 스케줄링 목표리소스 사용률CPU 사용률: CPU의 효율적인 사용을 극대화.I/O 디바이스 사용률: 입출력 장치의 사용 효율을 높이는 것.오버헤드 최소화스케줄링을 위한 계산이 복잡하거나 컨텍스트 스위칭이 빈번하면 오히려 성능 저하를 초래.스케줄러는 이러한 오버헤드를 최소화하는 것을 목표로 함.공평성모든 프로세스에게 공정하게 CPU를 할당하는 것을 목표로 함.공정성의 의미는 시스템의 특성에 따라 달라질 수 있음.처리량주어진 시간 내에 처리 가능한 작업의 양을 극대화하는 방법을 목표로 함.대기 시간작업 요청 후 실제 작업이 시작되기까지의 대기 시간이 짧아야 함.응답 시간대화형 시스템에서 사용자 요청에 대한 반응 속도를 중요하게 고려.응답 시간이 짧아야 사용자 경험이 향상됨. 상반되는 목표모든 목표를 동시에 최적화하는 것은 어려움.예: 처리량을 높이기 위해 하나의 프로세스에 CPU를 오랫동안 할당하면 응답 시간이 길어질 수 있음. 반대로, 여러 프로세스에 CPU를 고르게 할당하면 응답 시간이 줄어들지만, 처리량이 감소할 수 있음.시스템에 따른 목표 설정목표는 사용자와 사용 환경에 따라 다르게 설정되어야 함. 사용자의 필요와 시스템의 목적에 맞게 조정이 필요함. 스케줄링 알고리즘FIFO : First In First OutFIFO 스케줄링은 먼저 들어온 작업이 먼저 나가는 방식입니다.스케줄링 큐에 들어온 순서대로 CPU를 할당하며, 먼저 들어온 프로세스가 완전히 끝나야 다음 프로세스가 실행될 수 있습니다.FIFO는 직관적인 스케줄링 방식이지만, 평균 대기 시간이 증가할 수 있는 단점이 있어 현대 운영체제에서는 제한적으로 사용되며, 주로 일괄처리 시스템에서 효과적입니다. 장점단순하고 직관적: 구현이 간단하고 이해하기 쉬운 방식입니다.단점긴 대기 시간: 프로세스의 실행 순서만 변경했을 뿐인데도 평균 대기 시간의 차이가 클 수 있습니다.성능 차이: 프로세스의 Burst Time에 따라 성능 차이가 심합니다. 긴 작업이 먼저 실행될 경우, 그 뒤에 대기하는 짧은 작업들의 대기 시간이 늘어날 수 있습니다.비효율적 사용: 입출력 작업이 발생하는 경우 CPU가 대기하는 동안 사용률이 떨어지는 단점이 있습니다. 사용 사례FIFO 알고리즘은 현대 운영체제에서는 잘 사용되지 않지만, 일괄처리 시스템에서 유용합니다. 여기서는 각 프로세스가 완전히 끝나야 다음 프로세스가 시작되기 때문에 실행 시간이 짧고, 단순한 작업 흐름에 적합합니다. 성능 평가스케줄링의 성능은 평균 대기 시간으로 평가됩니다.평균 대기 시간: 여러 프로세스가 실행될 때 이 프로세스들 모두의 대기 시간을 평균한 값으로, 이 값이 낮을수록 스케줄링 효율이 높다고 평가됩니다. SJF, RR, MLFQ는 다음 주차에서..

워밍업 클럽 CS 1주차 발자국 : 자료구조와 알고리즘

개요자료구조와 알고리즘자료구조는 데이터를 저장하고 사용하는 구조를 나타내며, 데이터의 종류에 따라 저장 방식과 처리 방법이 다릅니다.알고리즘은 문제를 해결하는 절차로, 선택한 자료구조에 따라 다양한 알고리즘이 존재할 수 있습니다.즉, 적절한 자료구조를 선택한 후, 이를 효율적으로 처리하는 알고리즘을 적용해 원하는 결과를 얻습니다. 시간복잡도시간복잡도는 알고리즘의 성능을 평가하는 기준입니다.알고리즘의 실행 시간은 컴퓨터 성능에 따라 다르므로, 실제 시간을 측정하는 대신 반복문과 같은 성능에 큰 영향을 미치는 요소를 기준으로 평가합니다.시간복잡도는 여러 경우로 나뉘며, 최악의 경우(O), 평균의 경우(Θ), 최선의 경우(Ω)로 나뉘는데, 주로 빅오 표기법(O)을 사용해 성능을 표현합니다.빅오 표기법은 입력이 늘어날 때 계산량의 증가율을 나타내며, 가장 큰 항만을 표기해 성능을 간략히 표현합니다.예시: 3n^2 + 2n + 100 ⇒ O(n^2) 자료구조배열 (Array)- 특징: 메모리에서 연속된 공간을 할당하여 데이터를 저장. 배열의 시작 주소만 기억하고, 인덱스 참조는 O(1) 성능.- 장점: 빠른 읽기, 쓰기, 참조.- 단점: 삽입, 삭제 시 성능 저하. 배열 크기를 미리 알아야 하고, 메모리 낭비가 발생할 수 있음.- JavaScript 배열: 불연속적 메모리를 할당하지만, 사용자에게는 연속된 배열처럼 보임. 연결 리스트 (Linked List)- 구성: 노드(Data + 다음 노드를 가리키는 포인터)로 이루어짐.- 장점: 데이터의 삽입/삭제가 쉽고, 메모리 공간을 유연하게 사용.- 단점: 참조 시 성능이 O(n)으로 배열보다 느림. 스택 (Stack)- 특징: FILO(First In Last Out) 구조로, 되돌리기와 문법 검사 등에 사용. 큐 (Queue)- 특징: FIFO(First In First Out) 구조로, 운영체제의 프로세스 작업 처리에 주로 사용.- 성능 개선: 마지막 노드를 가리키는 tail 변수를 사용하면 O(1) 성능으로 데이터 제거 가능. 덱 (Deque)- 특징: 헤드와 테일에서 데이터의 삽입/삭제가 모두 가능한 자료구조. 스택과 큐를 모두 구현할 수 있음. 해시테이블 (Hash Table)- 특징: 해시 함수를 사용해 데이터를 효율적으로 저장 및 검색할 수 있는 자료구조.- 장점: 데이터 삽입, 수정, 삭제가 O(1)로 매우 빠름.- 단점: 해시 충돌 시 성능이 O(n)으로 저하될 수 있음. 메모리 효율이 떨어지고, 데이터를 골고루 분배 시켜주는 좋은 해시 함수 구현이 중요. 셋 (Set)- 특징: 데이터의 중복을 허용하지 않으며, 해시 테이블 기반으로 구현. key가 데이터로 사용됨.